编译原理课件Chapt5-3.ppt

《编译原理课件Chapt5-3.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理第五章语法分析——自下而上分析SLR分析LR(0)方法对文法的要求严格，现实中很难保证文法的符合LR(0)通过对非终结符跟随符号的展望可以解决部分LR(0)分析冲突假定一个LR(0)规范族中含有如下的一个项目集(状态):I＝{X→·b，A→·，B→·}。若FOLLOW(A)和FOLLOW(B)的交集为，且不包含b，那么，当状态I面临任何输入符号a时，可以:1.若a=b，则移进；2.若aFOLLOW(A)，用产生式A→进行归约；3.若aFOLLOW(B)，用产生式B→进行归约；4.此外，报

2、错。假定LR(0)规范族的一个项目集I={A1→·a11，A2→·a22，…，Am→·amm，B1→·，B2→·，…，Bn→·}如果集合{a1，…，am}，FOLLOW(B1)，…，FOLLOW(Bn)两两不相交(包括不得有两个FOLLOW集合有#)，则：1.若a是某个ai，i=1,2,…,m，则移进；2.若aFOLLOW(Bi)，i=1,2,…,n，则用产生式Bi→进行归约；3.此外，报错。冲突性动作的这种解决办法叫做SLR(1)解决办法。SLR分析的特点SLR的DFA与LR(0)完全相同

3、！不同在于构造分析表的方法不同对于LR(0)存在冲突的状态，SLR可以通过计算Follow集来判断移进还是规约，以及用哪条产生式规约SLR(1)与LR(0)LR(0)只看分析栈的内容，不考虑当前输入符SLR(1)考虑输入符，用Follow集来解决冲突，因此SLR(1)要比LR(0)分析能力强构造SLR(1)分析表方法:首先把G拓广为G，对G构造LR(0)项目集规范族C和活前缀识别自动机的状态转换函数GO.然后使用G和GO，按下面的算法构造SLR分析表：令每个项目集Ik的下标k作为分析器的状态，包含项目S→

4、·S的集合Ik的下标k为分析器的初态。分析表的ACTION和GOTO子表构造方法：1.若项目A→·a属于Ik且GO(Ik,a)=Ij，a为终结符，则置ACTION[k,a]为“sj”；2.若项目A→·属于Ik，那么，对任何终结符a，aFOLLOW(A)，置ACTION[k,a]为“rj”；其中，假定A为文法G的第j个产生式；3.若项目S→S·属于Ik，则置ACTION[k,#]为“acc”;4.若GO(Ik,A)＝Ij，A为非终结符，则置GOTO[k,A]=j；5.分析表中凡不能用规则1至4填入信

5、息的空白格均置上“出错标志”。按上述方法构造出的ACTION与GOTO表如果不含多重入口，则称该文法为SLR(1)文法。使用SLR表的分析器叫做一个SLR分析器。每个SLR(1)文法都是无二义的。但也存在许多无二义文法不是SLR(1)的.例5.11考察下面的拓广文法：(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→·EE→·E+TE→·TT→·T*FT→·T*FT→·FF→·(E)F→·iI1:S→E·E→E·+T

6、I2:E→T·T→T·*FI3:T→F·I4:F→(·E)E→·E+TE→·TT→·T*FT→·FF→·(E)F→·iI5:F→i·I6:E→E+·TT→·T*FT→·FF→·(E)F→·iI7:T→T*·FF→·(E)F→·iI8:F→(E·)E→E·+TI9:E→E+T·T→T·*FI10:T→T*F·I11:F→(E)·I0I1I2I3I4I5I6I7I8I9I10I11E+T*TTiF(i(FE(Fi+F*()I1、I2和I9都含有“移进－归约”冲突。FOLLOW(E)＝{#,),+}FOLLOW(S’)

7、={#}FOLLOW(T)={*,#,),+}I2:E→T·T→T·*FI1:S→E·E→E·+TI9:E→E+T·T→T·*F其分析表如下:非SLR文法示例：考虑如下文法：(0)S→S(1)S→L=R(2)S→R(3)L→*R(4)L→i(5)R→L计算FOLLOW集合所得到的超前符号集合可能大于实际能出现的超前符号集。这个文法的LR(0)项目集规范族为：I0：S→·SS→·L=RS→·RS→·*RL→·iR→·LI1：S→S·I2：S→L·=RR→L·I3：S→R·I4：L→*·RR→·LL→·*RL

8、→·iI5：L→i·I6：S→L=·RR→·LL→·*RL→·iI7：L→*R·I9：S→L=R·I8：R→L·I2含有“移进－归约”冲突。FOLLOW(R)＝{#,=}，I2：S→L·=RR→L·如下文法：(0)S→S(1)S→L=R(2)S→R(3)L→*R(4)L→i(5)R→L当状态2显现于栈顶而且面临输入符号为‘=’时，实际上不能用对栈顶L进行归约。不含“R=