编译原理张晶版第六章LR法必威体育精装版.ppt

6.5 LALR分析表的构造 三、构造LALR分析表的算法 3、从C’构造ACTION表： --(3)若（S’ S?,#)∈Jk，则置ACTION[k,#]=acc. 4、GOTO表的构造： ----假定JK是Ii1,Ii2,….Iit合并后的新集。由于这些Ii同心，因此，GO(Ii1,X),GO(Ii2,X),….GO(Iit,X)也同心，并记为Ji,即：GO(Jk,X)=Ji. ----若有GO(Jk,A)=Ji,A是非终结符，则置GOTO[K,A]=i. 5、凡是不能用上述步骤填写的空白项均填上“报错” 第六章 LR分析法及分析程序自动构造（92） 例：有如下文法： ?1、S’ S 2、S L=R ?3、S R 4、L *R ?5、L i 6、R L ?写出此文法的LALR分析表，并根据文法的LALR分析表分析输入串“i=*i=#” ?解：1、写出此文法的LR(1)分析表，再根据该文法写出其LALR分析表 第六章 LR分析法及分析程序自动构造（93） 状态 ACTION GOTO = i * # S L R 0 S5 S4 1 2 3 1 acc 2 S6 r6 3 r3 4 S5 S4 8 7 5 r5 r5 6 S10 S12 11 9 7 r4 r4 8 r6 r6 9 r2 10 r5 11 r6 12 S10 S12 11 13 LR(1)分析表 第六章 LR分析法及分析程序自动构造（94） 状态 ACTION GOTO = i * # S L R 0 S5 S4 1 2 3 1 acc 2 S6 r6 3 r3 4 S5 S4 8 7 5 r5 r5 6 S5 S4 8 9 7 r4 r4 8 r6 r6 9 r2 新构造的LALR分析表 第六章 LR分析法及分析程序自动构造（95） “i=*i=#”的LR(1)分析过程 步骤 状态栈 符号栈 输入串 0 0 # i=*i=# 1 0，5 #i =*i=# 2 0，2 #L =*i=# 3 0，2，6 #L= *i=# 4 0，2，6，12 #L=* i=# 5 0，2，6，12，10 #L=*i =# 报错 第六章 LR分析法及分析程序自动构造（96） “i=*i=#”的LALR(1)分析过程 步骤 状态栈 符号栈 输入串 0 0 # i=*i=# 1 0，5 #i =*i=# 2 0，2 #L =*i=# 3 0，2，6 #L= *i=# 4 0，2，6，4 #L=* i=# 5 0，2，6，4，5 #L=*i =# 6 0,2,6,4,8 #L=*L =# 7 0,2,6,4,7 #L=*R =# 8 0,2,6,8 #L=L =# 9 0,2,6,9 #L=R =# 报错 第六章 LR分析法及分析程序自动构造（97） 6.5 LALR分析表的构造 注：用LR(1)方法,遇到输入串有错就立即报错；而LALR方法没有立即报错，多做了几步归约之后才报错。但它们对错误的定位是相同的，故LALR方法的报错能力没减弱。 第六章 LR分析法及分析程序自动构造（98） 6.5 LALR分析表的构造 四、LALR(1)文法 ? 定义：用上述算法构造分析表，若不存在重定义项，则此文法是LALR(1)文法。 第六章 LR分析法及分析程序自动构造（99） 6.6 二义文法的应用 一、定理 ?任何二义文法决不是一个LR文法，故而也不是SLR或LALR文法。 ?注：虽然二义文法不是LR文法，但有些二义文法很有用，给它加上一些限制后，它可能成为描述某种语言的最简单的文法。 ?本节讨论如何使用LR分析法的基本思想，凭借其它一些条件，来分析二义文法所定义的语言。 第六章 LR分析法及分析程序自动构造（100） ---例如：G1:E’ E --- E E+E|E*E|(E)|i --- G2:E’ E --- E E+T|T --- T T*F|F --- F (E)|i 第六章 LR分析法及分析程序自动构造（101） 6.6 二义文法的应用 ?两个文法进行对比可以发现G1有两个优点： --1、若需要改变算法的优先级或结合规则，不需要改变文法G1本身； --2、文法G1的分析表所包含的状态肯定比G2的状态要少得多。因为，在文法G2中含有单个非终结符的产生式，这些产生式用来定义算符的