SLR分析表的构造.pptx

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

1、会计学1SLR分析分析(fnx)表的构造表的构造第一页，共20页。有效有效有效有效(y(y uxio)uxio)项目项目项目项目如果存在规范推导如果存在规范推导 则项目则项目A A 112 2 对活前缀对活前缀 1 1 是有效是有效(yuxio)(yuxio)的。的。如果如果2 2 ，应该移进，应该移进如果如果2=2=，应该用产生式，应该用产生式A A 1 1归约归约*RR 1 2 A SLRLR分析理论的一条基本定理分析理论的一条基本定理:在任何时候，分析栈在任何时候，分析栈中的活前缀中的活前缀(qinzhu)X1X2.Xm(qinzhu)X1X2.Xm的有效项目集正的有效项目集正是栈顶状态

2、是栈顶状态SmSm所代表的那个集合。所代表的那个集合。第1页/共20页第二页，共20页。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 BG:SEEaA|bBAcA|dBcB|d 项目项目(xingm(xingm)集集I5I5对对活前缀活前缀bcbc有效有效考虑如下规范考虑如下规范(gufn)推导推导(1)S E bB bcB(2)S E

3、bB bcB bccB(3)S E bB bcB bcd第2页/共20页第三页，共20页。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同一个项目同一个项目(xingm)(xingm)可能对好可能对好几个活前缀都有效几个活前缀都有效G:SEEaA|bBAcA|dBcB|d 第3页/共20页第四页，共20页。同一个活前缀，可能存在若干个项

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

5、项目 大多数的程序设计语言的文法不能满足大多数的程序设计语言的文法不能满足LR(0)LR(0)文法的条件文法的条件 用向前查看一个符号的办法用向前查看一个符号的办法(bnf(bnf)解决冲突解决冲突 第5页/共20页第六页，共20页。例：设文法例：设文法(wnf(wnf)G)G的的LR(0)LR(0)项目集规范族中项目集规范族中含有如下一个项目集（状态）含有如下一个项目集（状态）I I：I=I=X X b b/*/*移进项目移进项目*/*/AA /*/*归约项目归约项目*/*/B B /*/*归约项目归约项目*/*/移进归约冲突移进归约冲突(chngt)归约归约冲突归约归约冲突(chngt)解

6、决解决(jiju)冲突策略冲突策略（1）若）若a=b，则移进，则移进（2）若）若aFollow(A),则用则用 A 归约归约（3）若）若aFollow(B),则用则用 B 归约归约（4）此外，报错）此外，报错第6页/共20页第七页，共20页。用用用用SLR(1)SLR(1)方法解决方法解决方法解决方法解决(jiju)(jiju)冲突冲突冲突冲突假定假定LR(0)LR(0)规范族的一个项目集规范族的一个项目集I I中含有中含有m m个移进项目个移进项目:A1a11A1a11，A2a22A2a22，AmammAmamm同时含有同时含有n n个归约项目个归约项目:B11,B22,BnnB11,B22

7、,Bnn如果集合如果集合a1,ama1,am、FOLLOW(B1)FOLLOW(B1)、FOLLOW(Bn)FOLLOW(Bn)两两两不相交，两不相交，a a是现行输入符号，则是现行输入符号，则:（1 1）若）若a a是某个是某个(mu)ai(mu)ai，i=1,2,mi=1,2,m，则移进；，则移进；（2 2）若）若aFOLLOW(Bi)aFOLLOW(Bi)，i=1,2,ni=1,2,n，则用产生式则用产生式BiiBii进行归约；进行归约；（3 3）此外，报错。）此外，报错。第7页/共20页第八页，共20页。例例例例5.11 5.11 p111p111 考虑下面考虑下面(xi mian)(

8、xi mian)的拓广文法的拓广文法(文法文法5.8)5.8)（0 0）S S E E （1 1）E E E+T E+T （2 2）E E T T （3 3）T T T*F T*F （4 4）T T F F （5 5）F F(E)(E)（6 6）F F I I构造其构造其LR(0)LR(0)项目集规范族项目集规范族第8页/共20页第九页，共20页。I0:S E E E+T E T T T*F T F F (E)F iI1:S E E E +T I2: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*

9、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)移进移进-接受接受(jishu)冲突冲突移进移进-归约冲突归约冲突(chngt)移进移进-归约归约冲突冲突(chngt)DFA 图图5.8 p112第9页/共20页第十页，共20页。n nFOLLOW(S)=#,FOLLOW(S)=#,n n#+#+，因此，因此(ync(ync)I1)I1中中的冲突可解决。的冲突可解决。n n遇遇+移进移进 ，遇，遇#接受接受n n其它情况则报错。其它情况则报错。I1:S E E E +T（0）S E

10、（1）E E+T（2）E T（3）T T*F（4）T F（5）F(E)（6）F ISLR(1)SLR(1)SLR(1)SLR(1)解决解决解决解决(jiju)(jiju)(jiju)(jiju)方法方法方法方法第10页/共20页第十一页，共20页。n nFOLLOW(E)=+,),#FOLLOW(E)=+,),#n nFOLLOW(E)*=,FOLLOW(E)*=,因此因此(ync(ync)I2)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 I第11页/共20页第十二页，共20页。n n

11、FOLLOW(E)=+,),#FOLLOW(E)=+,),#n nFOLLOW(E)*=,FOLLOW(E)*=,因此因此(ync(ync)I9)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第12页/共20页第十三页，共20页。构造构造构造构造(guzo)SLR(1)(guzo)SLR(1)(guzo)SLR(1)(guzo)SLR(1)分析表分析表分析表分析表(1)(1)若若 Aa Aa 属于属于(shy)Ik,(shy)Ik,且且GO(Ik,a)=Ij GO(Ik,a)=Ij

12、,则置则置 ACTIONk,a ACTIONk,a 为为 sj sj(2)(2)若若 A A 属于属于(shy)Ik(shy)Ik，aFOLLOW(A)aFOLLOW(A)，则置则置 ACTIONk,a ACTIONk,a 为为 rj rj j j是产生式是产生式AA的编号的编号 。(3)(3)若若 S S SS属于属于(shy)Ik,(shy)Ik,则置则置 ACTIONk,#ACTIONk,#为为 accacc(4)(4)若若 GO(Ik,A)=Ij GO(Ik,A)=Ij，则置则置 GOTOk,A=j GOTOk,A=j(5)(5)凡不能用规则凡不能用规则(1)(4)(1)(4)填入的空

13、白格均置为填入的空白格均置为“出错出错标志标志”。更正更正(gngzhng)第13页/共20页第十四页，共20页。状状态态ACTIONGOTOi+*()#E TF0s5s41231s6acc2r2s7r2r2Follow(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第14页/共20页第十五页，共20页。状状态态ACTIONGOTOi+*()#ETF0s5s41231s6acc2r2 s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1 s7r1r11

14、0r3r3r3r311r5r5r5r5SLR(1)分析分析(fnx)表表图图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第15页/共20页第十六页，共20页。n nSLRSLR分析表分析表:按上述方法构造分析表按上述方法构造分析表,每个入口每个入口不含多重定义不含多重定义n nSLR(1)SLR(1)文法文法(wnf(wnf):):具有具有SLRSLR表的文法表的文法(wnf(wnf)n nSLRSLR分析器分析器:使用使用SLRSLR表的分析器表的分析器第16页/共20页第十七页，共20页。例：一个非例：一个非例：一个非例：一

15、个非SLRSLR文法文法文法文法(wnf(wnf)的例子的例子的例子的例子 p113 p113有如下文法有如下文法:(文法文法5.9)5.9)(0)S (0)S S S (1)S (1)S L=RL=R (2)S (2)S R R (3)L (3)L *R*R (4)L (4)L i i (5)R (5)R L L求求LR(0)LR(0)项目项目(xingm)(xingm)集规范族及识别活前缀的集规范族及识别活前缀的DFADFA第17页/共20页第十八页，共20页。Follow(R)=#,=识别识别(shbi)(shbi)活前缀的活前缀的DFADFAI0:SS S L=R S R L*R L

16、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:移进移进-归约冲突归约冲突(chngt)(0)S S (1)S L=R(2)S R (3)L*R(4)L i (5)R L无法无法(wf)(wf)用用SLR(1)SLR(1)法解决法解决第18页/共20页第十九页，共20页。r1 9 r5 r58 r3 r3798S4S56r4 r4578 S4S54r2 3 r5S6/r52 acc1321S4S50RLS#*i=GOTOACTION状态状态文法文法(wnf)5.9 (wnf)5.9 的的SLRSLR分分析表析表入口入口(r ku)含多重定义含多重定义第19页/共20页第二十页，共20页。