5.3.2-LR(0)项目集族和LR(0)分析表的构造PPT课件.ppt

单击此处编辑母版标题,单击此处编辑母版文本样式,第二级,第三级,第五章 语法分析,5.1,自下而上分析基本问题,5.2,算符优先分析,5.3 LR,分析,5.4 YACC,5.3 LR,分析,5.3.1 LR,分析器,5.3.2 LR(0),项目集族,LR(0),分析表的构造,5.3.3 SLR,分析表的构造,5.3.4,规范,LR,分析表的构造,5.3.5 LALR,分析表的构造,5.3.6,二义文法的应用,5.3.2 LR(0),项目集族,LR(0),分析表的构造,一、前缀、活前缀,p104,二、构造识别文法所有活前缀的,DFA,p104,三、,LR(0),项目集规范族的构造,p106,四、有效项目,p108,五、,LR(0),分析表的构造,p109,一、前缀、活前缀,前缀,:,符号串的头,活前缀,:,规范句型的一个前缀,这种前缀不包含句柄之后的任何符号,.,*可归前缀,:,包含句柄的活前缀,.,规范推导序列,S,=,aAcBe,=aAc,d,e,=a,Ab,cde=a,b,bcde,a,ab,a,aA,aAb,a,aA,aAc,aAcd,a,aA,aAc,aAcB,aAcBe,活前缀,可归前缀,ab,aAb,aAcd,aAcBe,补充例,:,找出,句型,#abbcde#,的所有活前缀,G:SaAcBe1,Ab2,AAb3,Bd4,a,b,b,c,d,e,A,A,B,S,当栈顶出现可归前缀即可归约,步,骤,符号栈,剩余,输入串,动作,1,#,abbcde,#,移进,2,#a,bbcde#,移进,3,#a,b,bcde#,归约,Ab,4,#aA,bcde#,移进,5,#a,Ab,cde#,归约,AAb,6,#aA,cde#,移进,7,#aAc,de#,移进,8,#aAc,d,e#,归约,Bd,9,#aAcB,e#,移进,10,#,aAcBe,#,归约,SaAcBe,11,#S,#,接受,a,b,b,c,d,e,A,A,B,S,栈里的文法符号与剩余符号串一起构成了规范句型,栈里的文法符号构成活前缀,S,=,aAcBe,=aAc,d,e,=a,Ab,cde,=a,b,bcde,规范推导序列,#abbcde#,的规范归约过程,S,=,S,=,aAcBe,=aAc,d,e,=a,Ab,cde,=a,b,bcde,规范推导序列,识别,句型,#abbcde#,所有活前缀的,DFA,S,a,b,a,A,b,a,A,c,d,a,A,c,B,e,确定化,最小化,0,2,4,5,1,3,6,8,9,7,S,a,A,b,c,B,e,d,*,b,G:SaAcBe1,Ab2,AAb3,Bd4,利用,DFA,进行,移近,-,归约分析,(,见黑板,),a,c,e,b,d,#,S,A,B,0,2,1,1,2,3,4,3,4,6,5,5,6,7,8,7,8,9,9,0,2,4,5,1,3,6,8,9,7,S,a,A,b,c,B,e,d,*,b,G:SaAcBe1,Ab2,AAb3,Bd4,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.,构造识别文法所有活前缀的,DFA,3.LR(0),项目的分类,求出文法所有的活前缀,根据产生式得出可能出现在栈中的符号串,1.LR(0),项目,在文法,G,中每个产生式的右部适当位置添加一个圆点构成项目,.,对空产生式,A,仅有项目,A,例,:,产生式,A,XYZ,对应的项目有,A,XYZ A,X,YZA,XY,Z A,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,借助项目构造识别文法活前缀的,DFA,G:,S,aAd,A,bc,2.,构造识别文法所有活前缀的,DFA,1).,文法的每个项目都为,NFA,的一个状态,2).,确定状态之间的转换关系,3).,确定化最小化,例,5.8 p105,G:,SE,Ea,A,|bB,AcA|d,BcB|d,更正,1,S,E,2,SE,11.E,bB3,E,aA,12.Eb,B4,Ea,A,13.EbB,5,EaA,14.B,cB6,A,cA,15.Bc,B7,Ac,A,16.BcB,8,AcA,17.B,d9,A,d,18.Bd,10.Ad,文法的项目,:,1).,文法的每个项目都为,NFA,的一个状态,2).,确定状态之间的转换关系,X,i,XX,1,X,2,X,i-1,X,i,X,n,XX,1,X,2,X,i,X,i+1,X,n,X,A,A,状态,i,状态,j,出自同一产生式,项目,1,为,初态,P106,NFA,1,S,E,2,SE,3,E,aA4,Ea,A,5,EaA,6,A,cA,7,Ac,A8,AcA,9,A,d,10.Ad,11.E,bB,12.Eb,B,13.EbB,14.B,cB,15.Bc,B16.BcB,17.B,d,18.Bd,每个状态都为,活前缀识别态,句柄识别态,(,可归前缀识别态,),:,圆点在最后的项目,句子识别态,a,E,*,A,c,A,d,d,c,B,b,B,7,8,6,3,4,10,5,9,1,2,13,18,16,11,12,14,15,17,p106,识别一个文法活前缀的,DFA,3).,确定化 最小化,每个状态是一个项目集,称作,LR(0),项目集,整个状态集称为,LR(0),项目集规范族,3.LR(0),项目的分类,移进项目,:,A,a,分析时把,a,移进符号栈,待约项目,:,A,B,用产生式,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),项目集规范族,1.,拓广文法,原文法,G,的开始符号为,S,在,G,中加,SS,后得新的文法,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,a,E,*,A,c,A,d,d,c,B,b,B,7,8,6,3,4,10,5,9,1,2,13,18,16,11,12,14,15,17,补充例,I,S,E,CLOSURE(I)=S,E,E,aA,E,bB,1,S,E,2,SE,3,E,aA4,Ea,A,5,EaA,6,A,cA,7,Ac,A8,AcA,9,A,d,10.Ad,11.E,bB,12.Eb,B,13.EbB,14.B,cB,15.Bc,B16.BcB,17.B,d,18.Bd,1,3,11,3.,状态转换函数,GO(I,X),GO(I,X)=CLOSURE(J),X(V,N,V,T,),J=,A,X,|,A,X,I,X,A,X,A,X,若状态,I,识别活前缀,则状态,J,识别活前缀,X,状态,I,状态,J,NFA,:,状态集合,I,的,a,弧转换,a,E,*,A,c,A,d,d,c,B,b,B,7,8,6,3,4,10,5,9,1,2,13,18,16,11,12,14,15,17,补充例,I,S,E,E,a,A,E,bB,GO(I,a)=CLOSURE(,E,a,A,),=,Ea,A,A,cA,A,d,1,S,E,2,SE,3,E,aA4,Ea,A,5,EaA,6,A,cA,7,Ac,A8,AcA,9,A,d,10.Ad,11.E,bB,12.Eb,B,13.EbB,14.B,cB,15.Bc,B16.BcB,17.B,d,18.Bd,1,3,11,4,6,9,4.,构造文法的,LR(0),项目集规范族,C=I,0,I,1,I,n,核,:,圆点不在产生式右部最左边的项目称为核,a),置项目,S,S,为初态集的核，然后对核求闭包，,CLOSURE(S,S,）得到初态的项目集。,b),对初态集或其它所构造的项目集应用转换函数,GO(I,，,X)=CLOSURE(J),求出新状态,J,的项目集。,c),重复,b),直到不出现新的项目为止。,算法,Procedure itemsets(G),Begin,C:=CLOSURE(S,S),Repeat,for,C,中的每一个,I,和每一个,X,do,if,GO(I,X),非空且不属于,C,then,把,GO(I,X),放入,C,中,until,C,不再增大,end,p107,初态的项目集,应用状态转换函数得到新的项目集,G:,SE,EaA|bB,AcA|d,BcB|d,I,0,:,S,E,E,aA,E,bB,I,8,:,B,c,B,B,cB,B,d,I,3,:,E,b,B,B,cB,B,d,I,2,:,E,a,A,A,cA,A,d,I,1,:,S,E,I,5,:,A,c,A,A,cA,A,d,I,10,:A,c,A,I,6,:,A,d,I,4,:E,a,A,I,7,:E,bB,I,9,:,B,d,I,11,:B,cB,b,E,a,c,c,c,c,d,d,d,d,A,A,B,B,识别文法所有活前缀的,DFA,LR(0),项目集规范族,I,0,I,1,I,11,四、有效项目*,如果存在规范推导,则项目,A,1,2,对活前缀,1,是,有效的,。,如果,2,，应该移进,如果,2,=,，应该用产生式,A,1,归约,*,R,R,1,2,A,S,I,0,:S,E,E,aA,E,bB,I,5,:B,c,B,B,cB,B,d,I,3,:E,b,B,B,cB,B,d,I,2,:E,a,A,A,cA,A,d,I,1,:S,E,I,4,:A,c,A,A,cA,A,d,I,8,:A,c,A,I,10,:,A,d,I,6,:E,a,A,I,7,:E,bB,I,11,:,B,d,I,9,:B,cB,b,E,a,c,c,c,c,d,d,d,d,A,A,B,B,G:,SE,EaA|bB,AcA|d,BcB|d,项目集,I,5,对活前缀,bc,有效,考虑如下规范推导,(1),S,E,bB,b,c,B,(2),S,E,bB,bcB,bc,cB,(3),S,E,bB,bcB,bc,d,图,5.7 p106,识别文法,活前缀的,DFA,从初态出发,经读出活前缀,后,而到达的项目集称为,活前缀,的,有效项目集,I,0,:,S,E,E,aA,E,bB,I,5,:,B,c,B,B,cB,B,d,I,3,:,E,b,B,B,cB,B,d,I,2,:,E,a,A,A,cA,A,d,I,1,:S,E,I,4,:,A,c,A,A,cA,A,d,I,8,:A,c,A,I,10,:,A,d,I,6,:E,a,A,I,7,:E,bB,I,11,:,B,d,I,9,:B,cB,b,E,a,c,c,c,c,d,d,d,d,A,A,B,B,LR,分析理论的一条基本定理,p108,在任何时候，分析栈中的活前缀,X,1,X,2,.X,m,的有效项目集正是栈顶状态,S,m,所代表的那个集合。,I,0,:S,E,E,aA,E,bB,I,5,:B,c,B,B,cB,B,d,I,3,:E,b,B,B,cB,B,d,I,2,:E,a,A,A,cA,A,d,I,1,:S,E,I,4,:A,c,A,A,cA,A,d,I,8,:A,c,A,I,10,:,A,d,I,6,:E,a,A,I,7,:E,bB,I,11,:,B,d,I,9,:B,cB,b,E,a,c,c,c,c,d,d,d,d,A,A,B,B,同一个项目可能对好几个活前缀都有效,G:,SE,EaA|bB,AcA|d,BcB|d,同一个活前缀，可能存在若干个项目对它都是有效的，而且告诉我们应做的事情各不相同，相互冲突。,这种冲突通过向前多看几个输入符号,或许能够获得解决。,移进,-,归约冲突,一个项目集中移进和归约项目同时存在：,A,a,B,归约,-,归约冲突,一个项目集中归约和归约项目同时存在,:,A,B,五、,LR(0),分析表的构造,LR(0),文法,假若一个文法,G,的拓广文法,G,的活前缀识别自动机中的每个状态,(,项目集,),不存在下述情况,既含移进项目又含归约项目,或者含有多个归约项目,则称,G,是一个,LR(0),文法,。,LR(0),文法规范族的每个项目集不包含任何冲突项目,(,移进,-,归约冲突、归约,-,归约冲突,),。,LR(0),分析表的构造,假设已构造出,LR(0),项目集规范族为,:,C=I,0,I,1,I,n,令包含,S,S,项目的集合,I,k,的下标,k,为分析器的初始状态。,a),若项目,A,a,属于,I,k ,且,GO(I,k,a)=I,j,则置,ACTIONk,a,为,S,j,b),若项目,A,属于,I,k,，则对任何终结符,a,和,#,置,ACTIONk,a,和,ACTIONk,#,为,“,r,j,”,j,为在文法,G,中某产生式,A,的序号。,c),若项目,SS,属于,I,k,则置,ACTIONk,#,为,“,acc,”,/,接受,d),若,GO(I,k,A),I,j,，则置,GOTOk,A,为,j,e),凡不能用上述方法填入的元素,均填上,“,报错标志,”,/,“,空白,”,I,0,:,S,E,E,aA,E,bB,I,8,:,B,c,B,B,cB,B,d,I,3,:,E,b,B,B,cB,B,d,I,2,:,E,a,A,A,cA,A,d,I,1,:,S,E,I,5,:,A,c,A,A,cA,A,d,I,10,:A,c,A,I,6,:,A,d,I,4,:E,a,A,I,7,:E,bB,I,9,:,B,d,I,11,:B,cB,b,E,a,c,c,c,c,d,d,d,d,A,A,B,B,(0)SE,(1)EaA,(2)EbB,(3)AcA,(4)Ad,(5)BcB,(6)Bd,构造,LR(0),分析表,过程见黑板,根据这种方法构造的,LR(0),分析表不含多重定义时，称这样的分析表为,LR(0),分析表,能用,LR(0),分析表的分析器称为,LR(0),分析器,