编译原理5.3.3-SLR分析表的构造.ppt

《编译原理5.3.3-SLR分析表的构造.ppt》由会员分享，可在线阅读，更多相关《编译原理5.3.3-SLR分析表的构造.ppt（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图图5.7 p1065.7 p106识别文法识别文法活前缀的活前缀的DFADFA从初态出发从初态出发,经读出活经读出活前缀前缀后后,而到达的项而到达的项目集称为目集称为活前缀活前缀的的有效项目集有效项目集I0:SE E aA E bBI5:BcB B cB B dI3:EbB B cB B dI2:EaA A cA A dI1:S E I4:AcA A cA A dI8:Ac AI10:A d I6:EaA I7:EbBI11:B d I9:BcB b E a c c c c d d d d A A B B有效项目有效项目如果存在规范推导如果存在规范推导 则项目则项目A 1 2 对活前缀对活前

2、缀 1 是是有效的有效的。o如果如果 2 ，应该移进，应该移进o如果如果 2 2=，应该用产生式，应该用产生式A 1归约归约*RR 1 2 A SLRLR分析理论的一条基本定理分析理论的一条基本定理:在任何时候，在任何时候，分析栈中的活前缀分析栈中的活前缀X X1 1X X2 2.X Xm m的有效项目集正的有效项目集正是栈顶状态是栈顶状态S Sm m所代表的那个集合。所代表的那个集合。I0:SE E aA E bBI5:BcB B cB B dI3:EbB B cB B dI2:EaA A cA A dI1:S E I4:AcA A cA A dI8:Ac AI10:A d I6:EaA I

3、7:EbBI11:B d I9:BcB b E a c c c c d d d d A A B BG:SEEaA|bBAcA|dBcB|d 项目集项目集I I5 5对活前缀对活前缀bc有效有效考虑如下规范推导考虑如下规范推导(1)S E bB bcB(2)S E bB bcB bccB(3)S E bB bcB bcdI0:SE E aA E bBI5:BcB B cB B dI3:EbB B cB B dI2:EaA A cA A dI1:S E I4:AcA A cA A dI8:Ac AI10:A d I6:EaA I7:EbBI11:B d I9:BcB b E a c c c c d

4、 d d d A A B B同一个项目可能对好同一个项目可能对好几个活前缀都有效几个活前缀都有效G:SEEaA|bBAcA|dBcB|d 同一个活前缀，可能存在若干个项目对它都是有效的，同一个活前缀，可能存在若干个项目对它都是有效的，而且告诉我们应做的事情各不相同，相互冲突。而且告诉我们应做的事情各不相同，相互冲突。这种冲突通过向前多看几个输入符号这种冲突通过向前多看几个输入符号,或许能够获得或许能够获得解决。解决。5.3.3 SLR分析表的构造分析表的构造SLR(1)分析法的引入分析法的引入:LR(0)文法的活前缀识别自动机的每一状态文法的活前缀识别自动机的每一状态(项目集项目集)都不含冲突

5、性的项目都不含冲突性的项目 大多数的程序设计语言的文法不能满足大多数的程序设计语言的文法不能满足LR(0)文法的条件文法的条件 用向前查看一个符号的办法解决冲突用向前查看一个符号的办法解决冲突 例：例：设文法设文法G的的LR(0)项目集规范族中含有如项目集规范族中含有如下一个项目集（状态）下一个项目集（状态）I：I=X b /*移进项目移进项目*/A/*归约项目归约项目*/B/*归约项目归约项目*/移进归约冲突移进归约冲突归约归约冲突归约归约冲突解决冲突策略解决冲突策略（1）若）若a=b，则移进，则移进（2）若）若aFollow(A),则用则用 A 归约归约（3）若）若aFollow(B),则

6、用则用 B归约归约（4）此外，报错）此外，报错用用SLR(1)方法解决冲突方法解决冲突假定假定LR(0)LR(0)规范族的一个项目集规范族的一个项目集I I中含有中含有m m个移进项目个移进项目:A A1 1a a1 11 1，A A2 2a a2 22 2，A Am ma am mm m同时含有同时含有n n个归约项目个归约项目:B B1 11 1,B B2 22 2,B Bn nn n如果集合如果集合a a1 1,a,am m、FOLLOW(BFOLLOW(B1 1)、FOLLOW(BFOLLOW(Bn n)两两不相交，两两不相交，a a是现行输入符号，则是现行输入符号，则:（1 1）若）

7、若a a是某个是某个a ai i，i=1,2,i=1,2,m,m，则移进；，则移进；（2 2）若）若aFOLLOW(BaFOLLOW(Bi i)，i=1,2,i=1,2,n,n，则用产生式则用产生式B Bi ii i进行归约；进行归约；（3 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)项目集规范族项目集规范族I0:S E E E+T E T T T*F T F F (E)F iI1:S E E E +T I

8、2:E T T T *FI3:T F I4:F (E)E E+T E T T T*F T F F (E)F iI5:F i I6:E E+T T T*F T F F (E)F iI7:T T*F F (E)F iI8:F (E )E E +T I9:E E+T T T *FI10:T T*F I11:F (E)移进移进-接受接受冲突冲突移进移进-归约归约冲突冲突移进移进-归约归约冲突冲突DFA 图图5.8 p112FOLLOW(S)=#,#+，因此，因此I1中的冲突中的冲突可解决。可解决。遇遇+移进移进 ，遇，遇#接受接受其它情况则报错。其它情况则报错。I1:S E E E +T（0）S E（

9、1）E E+T（2）E T（3）T T*F（4）T F（5）F(E)（6）F ISLR(1)SLR(1)解决方法解决方法FOLLOW(E)=+,),#FOLLOW(E)*=,因此因此I2中中的冲突可解决。的冲突可解决。I2: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 IFOLLOW(E)=+,),#FOLLOW(E)*=,因此因此I9中中的冲突可解决。的冲突可解决。I9: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)SLR(1)分析表分

10、析表(1)(1)若若 AAaa 属于属于I Ik k ,且且GO(IGO(Ik k,a)=,a)=I Ij j ,则置则置 ACTIONkACTIONk,a,a 为为 s sj j(2)(2)若若 AA 属于属于I Ik k，aFOLLOW(AaFOLLOW(A)，则置则置 ACTIONk,aACTIONk,a 为为 r rj j j j是产生式是产生式AA的编号的编号 。(3)(3)若若 S SSS属于属于I Ik k,则置则置 ACTIONkACTIONk,#,#为为 accacc(4)(4)若若 GO(IGO(Ik k,A,A)=)=I Ij j ，则置则置 GOTOkGOTOk,A=,

11、A=j j(5)(5)凡不能用规则凡不能用规则(1)(1)(4)(4)填入的空白格均置为填入的空白格均置为“出错出错标志标志”。更正更正状状态态ACTIONGOTOi+*()#E TF0s5s41231s6acc2r2 s7r2r2Follow(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状状态态ACTIONGOTOi+*()#ETF0s5s41231s6acc2r2 s7r2r23r4 r4r4r44s5s48235r6 r6r6r66s5s4937s5s4108s6s119r1 s7r1r110r3 r

12、3r3r311r5 r5r5r5SLR(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 ISLR分析表分析表:按上述方法构造分析表按上述方法构造分析表,每个入每个入口不含多重定义口不含多重定义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)项目集规范族及识别活前缀的

13、项目集规范族及识别活前缀的DFAFollow(R)=#,=识别活前识别活前缀的缀的DFADFAI0:SS S L=R S R L*R L i R LI6:SL=R R L L*R L iI2:SL=R R L I4:L*R R L L*R L iI1:SSI3:SRI7:L*RI8:RLI5:Li I9:SL=R=R*R L i R S*i iL*LI2 2:移进移进-归约冲突归约冲突(0)S S (1)S L=R(2)S R (3)L*R(4)L i (5)R L无法用无法用SLR(1)SLR(1)法解决法解决 r1 9 r5 r58 r3 r3798S4S56r4 r4578 S4S54r2 3 r5S6/r52 acc1321S4S50RLS#*i=GOTOACTION状态状态文法文法5.95.9 的的SLRSLR分析表分析表入口含多重定义入口含多重定义