-LR(0)项目集族和LR(0)分析表的构造

第五章语法分析5.1自下而上分析基本问题5.2算符优先分析5.3LR分析5.4YACC5.3LR分析5.3.1LR分析器5.3.2LR(0)项目集族＆LR(0)分析 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 的构造5.3.3SLR分析表的构造5.3.4规范LR分析表的构造5.3.5LALR分析表的构造5.3.6二义文法的应用5.3.2LR(0)项目集族＆LR(0)分析表的构造一、前缀、活前缀p104二、构造识别文法所有活前缀的DFAp104三、LR(0)项目集规范族的构造p106四、有效项目p108五、LR(0)分析表的构造p109一、前缀、活前缀前缀:符号串的头活前缀:规范句型的一个前缀,这种前缀不包含句柄之后的任何符号.*可归前缀:包含句柄的活前缀.规范推导序列S=>aAcBe=>aAcde=>aAbcde=>abbcdeε,a,abε,a,aA,aAbε,a,aA,aAc,aAcdε,a,aA,aAc,aAcB,aAcBe活前缀可归前缀ab,aAb,aAcd,aAcBe补充例:找出句型#abbcde#的所有活前缀G:S→aAcBe[1]　　A→b[2]　　A→Ab[3]　　B→d[4]当栈顶出现可归前缀即可归约栈里的文法符号与剩余符号串一起构成了规范句型栈里的文法符号构成活前缀S=>aAcBe=>aAcde=>aAbcde=>abbcde规范推导序列#abbcde#的规范归约过程步骤符号栈剩余输入串动作1#abbcde#移进2#abbcde#移进3#abbcde#归约A→b4#aAbcde#移进5#aAbcde#归约A→Ab6#aAcde#移进7#aAcde#移进8#aAcde#归约B→d9#aAcBe#移进10#aAcBe#归约S→aAcBe11#S#接受识别句型#abbcde#所有活前缀的DFA确定化最小化G:S→aAcBe[1]A→b[2]A→Ab[3]B→d[4]利用DFA进行移近-归约分析(见黑板)G:S→aAcBe[1]A→b[2]A→Ab[3]B→d[4]rrrrrrrrrrrrrrrrrrrrrrrraccSSSSSSGOTOACTION222222333333444444111111LR分析表DFA的矩阵表示一个LR分析器实质上是一个DFAacebd#SAB0211234346556787899小结识别文法所有活前缀的DFALR分析表LR分析二、构造识别文法所有活前缀的DFA1.LR(0)项目2.构造识别文法所有活前缀的DFA3.LR(0)项目的分类求出文法所有的活前缀根据产生式得出可能出现在栈中的符号串1.LR(0)项目在文法G中每个产生式的右部适当位置添加一个圆点构成项目.对空产生式A→ε,仅有项目A→·　例:产生式AXYZ对应的项目有A·XYZAX·YZAXY·ZAXYZ·一个产生式可对应的项目个数是它的右部符号长度加1每个项目的含义与圆点的位置有关补充例对应的项目:(1)S·aAd(2)Sa·Ad(3)SaA·d(4)SaAd·(5)A·bc(6)Ab·c(7)Abc·借助项目构造识别文法活前缀的DFAG:SaAdAbc2.构造识别文法所有活前缀的DFA1).文法的每个项目都为NFA的一个状态2).确定状态之间的转换关系3).确定化最小化例5.8p105G':S'→E　　E→aA|bB　　A→cA|d　　B→cB|d更正1．S'→·E2．S'→E·11.E→·bB3．E→·aA　12.E→b·B4．E→a·A　13.E→bB·5．E→aA·14.B→·cB6．A→·cA　15.B→c·B7．A→c·A　16.B→cB·8．A→cA·　17.B→·d9．A→·d　　18.B→d·10.A→d·文法的项目:1).文法的每个项目都为NFA的一个状态2).确定状态之间的转换关系XiX→X1X2…Xi-1·Xi…XnX→X1X2…Xi·Xi+1…XnεX→α·AβA→·γ状态i状态j出自同一产生式项目1为初态P106NFA1．S'→·E2．S'→E·3．E→·aA4．E→a·A5．E→aA·6．A→·cA7．A→c·A8．A→cA·9．A→·d10.A→d·11.E→·bB12.E→b·B13.E→bB·14.B→·cB15.B→c·B16.B→cB·17.B→·d18.B→d·每个状态都为活前缀识别态◎句柄识别态(可归前缀识别态):圆点在最后的项目 句子 关于阅读的唯美句子关于古风的唯美句子执行力的经典句子鼓励人努力奋斗的句子用沉默代替一切的句子 识别态p106识别一个文法活前缀的DFA3).确定化最小化每个状态是一个项目集,称作LR(0)项目集整个状态集称为LR(0)项目集规范族3.LR(0)项目的分类移进项目:A→α·aβ分析时把a移进符号栈待约项目:A→α·Bβ用产生式A的右部归约时,首先要将B的产生式右部归约为B,对A的右部才能继续进行分析归约项目:A→α·表明一个产生式的右部已分析完，句柄已形成可以归约接受项目:S'→S·表明已分析成功三、LR(0)项目集规范族的构造构造识别文法活前缀DFA的三种方法*求出活前缀的正规表达式，然后由此正规表达式构造NFA,再确定化为DFA。求出文法的所有项目，按一定规则构造识别活前缀的NFA,再确定化为DFA。通过闭包函数和转换函数，直接求出LR(0)项目集规范族，再由转换函数建立状态之间的连接关系得到识别活前缀的DFA。1.拓广文法2.项目集I的闭包函数CLOSURE(I)3.状态转换函数GO(I,X)4.构造文法的LR(0)项目集规范族1.拓广文法原文法G的开始符号为S,在G中加S'→S后得新的文法G'，则称G'为原文法G的拓广文法。使文法的开始符号不出现在任何产生式右部，当栈顶出现S′,则分析完成。注:即使原开始符号S不出现在任何产生式右部,为了统一起见也要增加该产生式。2.项目集I的闭包函数CLOSURE(I)a)I的项目均在CLOSURE(I)中。b)若A→α·Bβ属于CLOSURE(I),则每一形如B→·γ的项目也属于CLOSURE(I)c)重复b)直到CLOSURE(I)不再扩大。NFA:状态集合I的ε-闭包ε-closure(I)εA→α·BβB→·γ补充例I＝{S'→·E}CLOSURE(I)={S'→·E,E→·aA,E→·bB}1．S'→·E2．S'→E·3．E→·aA4．E→a·A5．E→aA·6．A→·cA7．A→c·A8．A→cA·9．A→·d10.A→d·11.E→·bB12.E→b·B13.E→bB·14.B→·cB15.B→c·B16.B→cB·17.B→·d18.B→d·13113.状态转换函数GO(I,X)GO(I,X)=CLOSURE(J)　,X∈(VN∪VT),J={A→αX·β|A→α·Xβ∈I}XA→α·XβA→αX·β若状态I识别活前缀γ,则状态J识别活前缀γX状态I状态JNFA:状态集合I的a弧转换补充例I＝{S'→·E,E→·aA,E→·bB}GO(I,a)=CLOSURE({E→a·A})={E→a·A,A→·cA,A→·d}1．S'→·E2．S'→E·3．E→·aA4．E→a·A5．E→aA·6．A→·cA7．A→c·A8．A→cA·9．A→·d10.A→d·11.E→·bB12.E→b·B13.E→bB·14.B→·cB15.B→c·B16.B→cB·17.B→·d18.B→d·13114694.构造文法的LR(0)项目集规范族C={I0,I1,……,In}核:圆点不在产生式右部最左边的项目称为核a)置项目S'→·S为初态集的核，然后对核求闭包，CLOSURE({S'→·S}）得到初态的项目集。b)对初态集或其它所构造的项目集应用转换函数GO(I，X)=CLOSURE(J)求出新状态J的项目集。c)重复b)直到不出现新的项目为止。算法Procedureitemsets(G')BeginC:={CLOSURE({S'·S})}RepeatforC中的每一个I和每一个XdoifGO(I,X)非空且不属于Cthen把GO(I,X)放入C中untilC不再增大endp107初态的项目集应用状态转换函数得到新的项目集G':S'→E　　E→aA|bB　　A→cA|dB→cB|dI0:S'•EE•aAE•bBI8:Bc•BB•cBB•dI3:Eb•BB•cBB•dI2:Ea•AA•cAA•dI1:S'E•I5:Ac•AA•cAA•dI10:AcA•I6:Ad•I4:EaA•I7:EbB•I9:Bd•I11:BcB•bEaccccddddAABB识别文法所有活前缀的DFALR(0)项目集规范族{I0,I1,…,I11}四、有效项目*如果存在规范推导则项目A1·2对活前缀1是有效的。如果2，应该移进如果2=，应该用产生式A1归约G':S'→EE→aA|bBA→cA|dB→cB|d项目集I5对活前缀bc有效考虑如下规范推导(1)SEbBbcB(2)SEbBbcBbccB(3)SEbBbcBbcd图5.7p106识别文法活前缀的DFA从初态出发,经读出活前缀γ后,而到达的项目集称为活前缀γ的有效项目集LR分析理论的一条基本定理p108在任何时候，分析栈中的活前缀X1X2...Xm的有效项目集正是栈顶状态Sm所代表的那个集合。同一个项目可能对好几个活前缀都有效G':S'→EE→aA|bBA→cA|dB→cB|d同一个活前缀，可能存在若干个项目对它都是有效的，而且告诉我们应做的事情各不相同，相互冲突。这种冲突通过向前多看几个输入符号,或许能够获得解决。移进-归约冲突一个项目集中移进和归约项目同时存在：　　A→α·aβB→γ·归约-归约冲突一个项目集中归约和归约项目同时存在:A→β·B→γ·五、LR(0)分析表的构造LR(0)文法假若一个文法G的拓广文法G的活前缀识别自动机中的每个状态(项目集)不存在下述情况①既含移进项目又含归约项目②或者含有多个归约项目则称G是一个LR(0)文法。LR(0)文法规范族的每个项目集不包含任何冲突项目(移进-归约冲突、归约-归约冲突)。LR(0)分析表的构造假设已构造出LR(0)项目集规范族为:C={I0,I1,…,In}令包含S'→·S项目的集合Ik的下标k为分析器的初始状态。a)若项目A→α·aβ属于Ik,且GO(Ik,a)=Ij则置ACTION[k,a]为Sjb)若项目A→α·属于Ik，则对任何终结符a和‘#’置ACTION[k,a]和ACTION[k,#]为“rj”,j为在文法G'中某产生式A→α的序号。c)若项目S'→S·属于Ik,则置ACTION[k,#]为“acc”/接受d)若GO(Ik,A)＝Ij，则置GOTO[k,A]为"j"e)凡不能用上述方法填入的元素,均填上“报错标志”/“空白”I0:S'•EE•aAE•bBI8:Bc•BB•cBB•dI3:Eb•BB•cBB•dI2:Ea•AA•cAA•dI1:S'E•I5:Ac•AA•cAA•dI10:AcA•I6:Ad•I4:EaA•I7:EbB•I9:Bd•I11:BcB•bEaccccddddAABB(0)S'→E　　　　(1)E→aA　　　　　(2)E→bB　　　　(3)A→cA(4)A→d(5)B→cB(6)B→d构造LR(0)分析表过程见黑板根据这种方法构造的LR(0)分析表不含多重定义时，称这样的分析表为LR(0)分析表能用LR(0)分析表的分析器称为LR(0)分析器