资源描述
图5.7p106,识别文法活前缀的DFA,从初态出发,经读出活前缀后,而到达的项目集称为活前缀的有效项目集,有效项目,如果存在规范推导则项目A12对活前缀1是有效的。如果2，应该移进如果2=，应该用产生式A1归约,LR分析理论的一条基本定理:在任何时候，分析栈中的活前缀X1X2.Xm的有效项目集正是栈顶状态Sm所代表的那个集合。,G:SEEaA|bBAcA|dBcB|d,项目集I5对活前缀bc有效,考虑如下规范推导(1)SEbBbcB(2)SEbBbcBbccB(3)SEbBbcBbcd,同一个项目可能对好几个活前缀都有效,G:SEEaA|bBAcA|dBcB|d,同一个活前缀，可能存在若干个项目对它都是有效的，而且告诉我们应做的事情各不相同，相互冲突。这种冲突通过向前多看几个输入符号,或许能够获得解决。,5.3.3SLR分析表的构造,SLR(1)分析法的引入:LR(0)文法的活前缀识别自动机的每一状态(项目集)都不含冲突性的项目大多数的程序设计语言的文法不能满足LR(0)文法的条件用向前查看一个符号的办法解决冲突,例：设文法G的LR(0)项目集规范族中含有如下一个项目集（状态）I：I=Xb/*移进项目*/A/*归约项目*/B/*归约项目*/,移进归约冲突归约归约冲突,解决冲突策略（1）若a=b，则移进（2）若aFollow(A),则用A归约（3）若aFollow(B),则用B归约（4）此外，报错,用SLR(1)方法解决冲突,假定LR(0)规范族的一个项目集I中含有m个移进项目:A1a11，A2a22，Amamm同时含有n个归约项目:B11,B22,Bnn如果集合a1,am、FOLLOW(B1)、FOLLOW(Bn)两两不相交，a是现行输入符号，则:（1）若a是某个ai，i=1,2,m，则移进；（2）若aFOLLOW(Bi)，i=1,2,n，则用产生式Bii进行归约；（3）此外，报错。,例5.11p111,考虑下面的拓广文法(文法5.8)（0）SE（1）EE+T（2）ET（3）TT*F（4）TF（5）F(E)（6）FI构造其LR(0)项目集规范族,I0:SEEE+TETTT*FTFF(E)Fi,I1:SEEE+T,I2:ETTT*F,I3:TF,I4:F(E)EE+TETTT*FTFF(E)Fi,I5:Fi,I6:EE+TTT*FTFF(E)Fi,I7:TT*FF(E)Fi,I8:F(E)EE+T,I9:EE+TTT*F,I10:TT*F,I11:F(E),移进-接受冲突,移进-归约冲突,移进-归约冲突,DFA图5.8p112,FOLLOW(S)=#,#+，因此I1中的冲突可解决。遇+移进，遇#接受其它情况则报错。,I1:SEEE+T,（0）SE（1）EE+T（2）ET（3）TT*F（4）TF（5）F(E)（6）FI,SLR(1)解决方法,FOLLOW(E)=+,),#FOLLOW(E)*=,因此I2中的冲突可解决。,I2:ETTT*F,（0）SE（1）EE+T（2）ET（3）TT*F（4）TF（5）F(E)（6）FI,FOLLOW(E)=+,),#FOLLOW(E)*=,因此I9中的冲突可解决。,I9:EE+TTT*F,(0)SE(1)EE+T(2)ET(3)TT*F(4)TF(5)F(E)(6)FI,构造SLR(1)分析表,(1)若Aa属于Ik,且GO(Ik,a)=Ij,则置ACTIONk,a为sj(2)若A属于Ik，aFOLLOW(A)，则置ACTIONk,a为rjj是产生式A的编号。(3)若SS属于Ik,则置ACTIONk,#为acc(4)若GO(Ik,A)=Ij，则置GOTOk,A=j(5)凡不能用规则(1)(4)填入的空白格均置为“出错标志”。,更正,Follow(S)=#,Follow(E)=#,),+,(0)SE(1)EE+T(2)ET(3)TT*F(4)TF(5)F(E)(6)FI,SLR(1)分析表图5.5p101,(0)SE(1)EE+T(2)ET(3)TT*F(4)TF(5)F(E)(6)FI,SLR分析表:按上述方法构造分析表,每个入口不含多重定义SLR(1)文法:具有SLR表的文法SLR分析器:使用SLR表的分析器,例：一个非SLR文法的例子p113,有如下文法:(文法5.9)(0)SS(1)SL=R(2)SR(3)L*R(4)Li(5)RL求LR(0)项目集规范族及识别活前缀的DFA,Follow(R)=#,=,识别活前缀的DFA,I2:移进-归约冲突,(0)SS(1)SL=R(2)SR(3)L*R(4)Li(5)RL,无法用SLR(1)法解决,文法5.9的SLR分析表,入口含多重定义,
展开阅读全文