LR项目集族和LR分析表的构造课件.ppt

第五章语法分析,5.1自下而上分析基本问题5.2算符优先分析5.3LR分析5.4YACC,5.3LR分析,5.3.1LR分析器5.3.2LR(0)项目集族LR(0)分析表的构造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:SaAcBe1Ab2AAb3Bd4,当栈顶出现可归前缀即可归约,栈里的文法符号与剩余符号串一起构成了规范句型栈里的文法符号构成活前缀,S=aAcBe=aAcde=aAbcde=abbcde,规范推导序列,#abbcde#的规范归约过程,识别句型#abbcde#所有活前缀的DFA,确定化,最小化,G:SaAcBe1Ab2AAb3Bd4,利用DFA进行移近-归约分析(见黑板),G:SaAcBe1Ab2AAb3Bd4,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,acc,S,S,S,S,S,S,GOTO,ACTION,2,2,2,2,2,2,3,3,3,3,3,3,4,4,4,4,4,4,1,1,1,1,1,1,LR分析表,DFA的矩阵表示,一个LR分析器实质上是一个DFA,小结,识别文法所有活前缀的DFA,LR分析表,LR分析,二、构造识别文法所有活前缀的DFA,1.LR(0)项目2.构造识别文法所有活前缀的DFA3.LR(0)项目的分类,求出文法所有的活前缀根据产生式得出可能出现在栈中的符号串,1.LR(0)项目,在文法G中每个产生式的右部适当位置添加一个圆点构成项目.对空产生式A,仅有项目A,例:产生式AXYZ对应的项目有AXYZAXYZAXYZAXYZ,一个产生式可对应的项目个数是它的右部符号长度加1每个项目的含义与圆点的位置有关,补充例,对应的项目:(1)SaAd(2)SaAd(3)SaAd(4)SaAd(5)Abc(6)Abc(7)Abc,借助项目构造识别文法活前缀的DFA,G:SaAdAbc,2.构造识别文法所有活前缀的DFA,1).文法的每个项目都为NFA的一个状态2).确定状态之间的转换关系3).确定化最小化,例5.8p105,G:SEEaA|bBAcA|dBcB|d,更正,1SE2SE11.EbB3EaA12.EbB4EaA13.EbB5EaA14.BcB6AcA15.BcB7AcA16.BcB8AcA17.Bd9Ad18.Bd10.Ad,文法的项目:,1).文法的每个项目都为NFA的一个状态,2).确定状态之间的转换关系,Xi,XX1X2Xi-1XiXn,XX1X2XiXi+1Xn,XA,A,状态i,状态j,出自同一产生式,项目1为初态,P106NFA,1SE2SE3EaA4EaA5EaA6AcA7AcA8AcA9Ad10.Ad11.EbB12.EbB13.EbB14.BcB15.BcB16.BcB17.Bd18.Bd,每个状态都为活前缀识别态句柄识别态(可归前缀识别态):圆点在最后的项目,句子识别态,p106,识别一个文法活前缀的DFA,3).确定化最小化,每个状态是一个项目集,称作LR(0)项目集整个状态集称为LR(0)项目集规范族,3.LR(0)项目的分类,移进项目:Aa分析时把a移进符号栈待约项目:AB用产生式A的右部归约时,首先要将B的产生式右部归约为B,对A的右部才能继续进行分析归约项目:A表明一个产生式的右部已分析完，句柄已形成可以归约接受项目:SS表明已分析成功,三、LR(0)项目集规范族的构造,构造识别文法活前缀DFA的三种方法*求出活前缀的正规表达式，然后由此正规表达式构造NFA,再确定化为DFA。求出文法的所有项目，按一定规则构造识别活前缀的NFA,再确定化为DFA。通过闭包函数和转换函数，直接求出LR(0)项目集规范族，再由转换函数建立状态之间的连接关系得到识别活前缀的DFA。,1.拓广文法2.项目集I的闭包函数CLOSURE(I)3.状态转换函数GO(I,X)4.构造文法的LR(0)项目集规范族,2019/12/15,21,可编辑,1.拓广文法,原文法G的开始符号为S,在G中加SS后得新的文法G，则称G为原文法G的拓广文法。使文法的开始符号不出现在任何产生式右部，当栈顶出现S,则分析完成。注:即使原开始符号S不出现在任何产生式右部,为了统一起见也要增加该产生式。,2.项目集I的闭包函数CLOSURE(I),a)I的项目均在CLOSURE(I)中。b)若AB属于CLOSURE(I),则每一形如B的项目也属于CLOSURE(I)c)重复b)直到CLOSURE(I)不再扩大。,NFA:状态集合I的-闭包-closure(I),AB,B,补充例,ISECLOSURE(I)=SE,EaA,EbB,1SE2SE3EaA4EaA5EaA6AcA7AcA8AcA9Ad10.Ad11.EbB12.EbB13.EbB14.BcB15.BcB16.BcB17.Bd18.Bd,1,3,11,3.状态转换函数GO(I,X),GO(I,X)=CLOSURE(J),X(VNVT),J=AX|AXI,X,AX,AX,若状态I识别活前缀,则状态J识别活前缀X,状态I,状态J,NFA:状态集合I的a弧转换,补充例,ISE,EaA,EbBGO(I,a)=CLOSURE(EaA)=EaA,AcA,Ad,1SE2SE3EaA4EaA5EaA6AcA7AcA8AcA9Ad10.Ad11.EbB12.EbB13.EbB14.BcB15.BcB16.BcB17.Bd18.Bd,1,3,11,4,6,9,4.构造文法的LR(0)项目集规范族C=I0,I1,In,核:圆点不在产生式右部最左边的项目称为核a)置项目SS为初态集的核，然后对核求闭包，CLOSURE(SS）得到初态的项目集。b)对初态集或其它所构造的项目集应用转换函数GO(I，X)=CLOSURE(J)求出新状态J的项目集。c)重复b)直到不出现新的项目为止。,算法,Procedureitemsets(G)BeginC:=CLOSURE(SS)RepeatforC中的每一个I和每一个XdoifGO(I,X)非空且不属于Cthen把GO(I,X)放入C中untilC不再增大end,p107,初态的项目集,应用状态转换函数得到新的项目集,G:SEEaA|bBAcA|dBcB|d,I0:SEEaAEbB,I8:BcBBcBBd,I3:EbBBcBBd,I2:EaAAcAAd,I1:SE,I5:AcAAcAAd,I10:AcA,I6:Ad,I4:EaA,I7:EbB,I9:Bd,I11:BcB,b,E,a,c,c,c,c,d,d,d,d,A,A,B,B,识别文法所有活前缀的DFALR(0)项目集规范族I0,I1,I11,四、有效项目*,如果存在规范推导则项目A12对活前缀1是有效的。如果2，应该移进如果2=，应该用产生式A1归约,G:SEEaA|bBAcA|dBcB|d,项目集I5对活前缀bc有效,考虑如下规范推导(1)SEbBbcB(2)SEbBbcBbccB(3)SEbBbcBbcd,图5.7p106,识别文法活前缀的DFA,从初态出发,经读出活前缀后,而到达的项目集称为活前缀的有效项目集,LR分析理论的一条基本定理p108,在任何时候，分析栈中的活前缀X1X2.Xm的有效项目集正是栈顶状态Sm所代表的那个集合。,同一个项目可能对好几个活前缀都有效,G:SEEaA|bBAcA|dBcB|d,同一个活前缀，可能存在若干个项目对它都是有效的，而且告诉我们应做的事情各不相同，相互冲突。这种冲突通过向前多看几个输入符号,或许能够获得解决。,移进-归约冲突一个项目集中移进和归约项目同时存在：AaB归约-归约冲突一个项目集中归约和归约项目同时存在:AB,五、LR(0)分析表的构造,LR(0)文法,假若一个文法G的拓广文法G的活前缀识别自动机中的每个状态(项目集)不存在下述情况既含移进项目又含归约项目或者含有多个归约项目则称G是一个LR(0)文法。LR(0)文法规范族的每个项目集不包含任何冲突项目(移进-归约冲突、归约-归约冲突)。,LR(0)分析表的构造,假设已构造出LR(0)项目集规范族为:C=I0,I1,In令包含SS项目的集合Ik的下标k为分析器的初始状态。,a)若项目Aa属于Ik,且GO(Ik,a)=Ij则置ACTIONk,a为Sjb)若项目A属于Ik，则对任何终结符a和#置ACTIONk,a和ACTIONk,#为“rj”,j为在文法G中某产生式A的序号。c)若项目SS属于Ik,则置ACTIONk,#为“acc”/接受d)若GO(Ik,A)Ij，则置GOTOk,A为je)凡不能用上述方法填入的元素,均填上“报错标志”/“空白”,I0:SEEaAEbB,I8:BcBBcBBd,I3:EbBBcBBd,I2:EaAAcAAd,I1:SE,I5:AcAAcAAd,I1