资源描述
单击此处编辑母版标题,单击此处编辑母版文本样式,第二级,第三级,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题,单击此处编辑母版文本样式,第二级,第三级,图,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,有效项目,如果存在规范推导,则项目,A,1,2,对活前缀,1,是,有效的,。,如果,2,，应该移进,如果,2,=,，应该用产生式,A,1,归约,*,R,R,1,2,A,S,LR,分析理论的一条基本定理,:,在任何时候，分析栈中的活前缀,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,项目集,I,5,对活前缀,bc,有效,考虑如下规范推导,(1),S,E,bB,bc,B,(2),S,E,bB,bcB,bc,cB,(3),S,E,bB,bcB,bc,d,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,同一个活前缀，可能存在若干个项目对它都是有效的，而且告诉我们应做的事情各不相同，相互冲突。,这种冲突通过向前多看几个输入符号,或许能够获得解决。,5.3.3 SLR,分析表的构造,SLR(1),分析法的引入,:,LR(0),文法的活前缀识别自动机的每一状态,(,项目集,),都不含冲突性的项目,大多数的程序设计语言的文法不能满足,LR(0),文法的条件,用向前查看一个符号的办法解决冲突,例：,设文法,G,的,LR(0),项目集规范族中含有如下一个项目集（状态）,I,：,I=X,b,/*,移进项目*,/,A,/*,归约项目*,/,B,/*,归约项目*,/,移进归约冲突,归约归约冲突,解决冲突策略,（,1,）若,a=b,，则移进,（,2,）若,aFollow(A),则用,A,归约,（,3,）若,aFollow(B),则用,B,归约,（,4,）此外，报错,用,SLR(1),方法解决冲突,假定,LR(0),规范族的一个项目集,I,中含有,m,个移进项目,:,A,1,a,1,1,，,A,2,a,2,2,，,，,A,m,a,m,m,同时含有,n,个归约项目,:,B,1,1,B,2,2,B,n,n,如果集合,a,1,a,m,、,FOLLOW(B,1,),、,、,FOLLOW(B,n,),两两不相交，,a,是现行输入符号，则,:,（,1,）若,a,是某个,a,i,，,i=1,2,m,，则移进；,（,2,）若,aFOLLOW(B,i,),，,i=1,2,n,，,则用产生式,B,i,i,进行归约；,（,3,）此外，报错。,例,5.11,p111,考虑下面的拓广文法,(,文法,5.8),（0）,S,E,（1）,E,E+T,（2）,E,T,（3）,T T*F,（4）,T F,（5）,F,(E),（6）,F,I,构造其,LR(0),项目集规范族,I,0,:,S,E,E,E+T,E,T,T,T,*,F,T,F,F,(E),F,i,I,1,:,S,E,E,E +T,I,2,:,E,T,T,T,*,F,I,3,:,T,F,I,4,:,F,(E),E,E+T,E,T,T,T,*,F,T,F,F,(E),F,i,I,5,:,F,i,I,6,:,E,E+T,T,T,*,F,T,F,F,(E),F,i,I,7,:,T,T,*,F,F,(E),F,i,I,8,:,F,(E ),E,E +T,I,9,:,E,E+T,T,T,*,F,I,10,:,T,T,*,F,I,11,:,F,(E),移进,-,接受,冲突,移进,-,归约,冲突,移进,-,归约,冲突,DFA,图,5.8,p112,FOLLOW(S)=#,#+,，因此,I,1,中的冲突可解决。,遇,+,移进 ，遇,#,接受,其它情况则报错。,I,1,:,S,E,E,E +T,（0）,S,E,（1）,E,E+T,（2）,E,T,（3）,T T*F,（4）,T F,（5）,F,(E),（6）,F,I,SLR(1),解决方法,FOLLOW(E)=+,),#,FOLLOW(E)*=,因此,I,2,中的冲突可解决。,I,2,:,E,T,T,T *F,（0）,S,E,（1）,E,E+T,（2）,E,T,（3）,T T*F,（4）,T F,（5）,F,(E),（6）,F,I,FOLLOW(E)=+,),#,FOLLOW(E)*=,因此,I,9,中的冲突可解决。,I,9,:,E,E+T,T,T *F,(0)S,E,(1)E,E+T,(2),E,T,(3),T T*F,(4),T F,(5),F,(E),(6),F,I,构造,SLR(1),分析表,(1)若,Aa,属于,I,k,且,GO(I,k,a)=I,j,则置,ACTIONk,a,为,s,j,(2)若,A,属于,I,k,，,aFOLLOW(A),，,则置,ACTIONk,a,为,r,j,j,是产生式,A,的编号。,(3)若,S,S,属于,I,k,则置,ACTIONk,#,为,acc,(4),若,GO(I,k,A)=I,j,，,则置,GOTOk,A=,j,(5)凡不能用规则(1),(4),填入的空白格均置为“出错标志”。,更正,状,态,ACTION,GOTO,i,+,*,(,),#,E,T,F,0,s5,s4,1,2,3,1,s6,acc,2,r2,s7,r2,r2,Follow(,S,)=#,Follow(,E,)=#,),+,(0)S,E,(1),E,E+T,(2),E,T,(3),T T*F,(4),T F,(5),F,(E),(6),F,I,状,态,ACTION,GOTO,i,+,*,(,),#,E,T,F,0,s5,s4,1,2,3,1,s6,acc,2,r2,s7,r2,r2,3,r4,r4,r4,r4,4,s5,s4,8,2,3,5,r6,r6,r6,r6,6,s5,s4,9,3,7,s5,s4,10,8,s6,s11,9,r1,s7,r1,r1,10,r3,r3,r3,r3,11,r5,r5,r5,r5,SLR(1),分析表,图,5.5 p101,(0)S,E,(1),E,E+T,(2),E,T,(3),T T*F,(4),T F,(5),F,(E),(6),F,I,SLR,分析表,:,按上述方法构造分析表,每个入口不含多重定义,SLR(1),文法,:,具有,SLR,表的文法,SLR,分析器,:,使用,SLR,表的分析器,例：一个非,SLR,文法的例子,p113,有如下文法:,(,文法,5.9),(0,)S,S,(1)S,L=R,(2)S R,(3)L*R,(4)L i,(5)R L,求,LR(0),项目集规范族及识别活前缀的,DFA,Follow(,R,),=#,=,识别活前缀的,DFA,I,0,:S,S,S,L=R,S,R,L,*R,L,i,R,L,I,6,:,S,L=,R,R,L,L,*R,L,i,I,2,:,S,L,=R,R L,I,4,:,L,*,R,R,L,L,*R,L,i,I,1,:,S,S,I,3,:,S,R,I,7,:,L,*R,I,8,:,R,L,I,5,:,L,i,I,9,:,S,L=R,=,R,*,R,L,i,R,S,*,i,i,L,*,L,I,2,:,移进,-,归约冲突,(0),S,S,(1)S,L=R,(2)S R,(3)L*R,(4)L i,(5)R L,无法用,SLR(1),法解决,r,1,9,r,5,r,5,8,r,3,r,3,7,9,8,S,4,S,5,6,r,4,r,4,5,7,8,S,4,S,5,4,r,2,3,r,5,S,6,/r,5,2,acc,1,3,2,1,S,4,S,5,0,R,L,S,#,*,i,=,GOTO,ACTION,状态,文法,5.9,的,SLR,分析表,入口含多重定义,
展开阅读全文