龙书中lr(0)和slr(1)文法的一点解释

《龙书中lr(0)和slr(1)文法的一点解释》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、1965年，D.knuth首先提出了LR(K)文法及LR(K)分析技术。括号中的K表示向右查看输入串符号的个数。这种方法比起自顶向下的LL(K)分析方法和算符优先分析方法对文法的限制要少得多，也就是说对于大多数用无二义性上下文无关文法描述的语言都可以用相应的LR分析器进行识别，而且这种方法还具有分析速度快，能准确、及时地指出出错位置。它的主要缺点是对于一个实用语言文法的分析器的构造工作量相当大，K愈大构造愈复杂，实现相当困难。目前对于真正实用的编译程序，所采用的LR分析器都是借助于美国Bell实验室1974年推出的"一个编译器的编译器-YACC"来实现

2、的。它能接受一个用BNF描述的满足LALR(1)的上下文无关文法并将自动构造LALR(1)语法分析器。LR(0)分析器是在分析过程中不需向右查看输入符号，因而它对文法的限制较大，对绝大多数高级语言的语法分析器是不能适用的，然而，它是构造其它LR类分析器的基础。当K=1时，已能满足当前绝大多数高级语言编译程序的需要。SLR(1)和LALR(1)分别是LR(0)和LR(1)的一种改进。LR(0)表示在每一步分析时都不用向前输入符号LR(1)表示在每一步分析时都向前看一个输入符号来决定当前的动作。SLR(1)表示简单的LR(1)，即只在动作不唯一的地方向前看

3、一个符号，在动作唯一时则不向前看输入符号。各语法之间powerful等级：LR(1)>SLR(1)>LR(0)LR(0)语法分析表的构建：1.若goto(Ik，a)=Ij，则action[k，a]=Sj【项集中出去的箭头上写的非终结符号(一般小写字母或$)】2.若goto(Ik，A)=Ij，则goto[k，A]=j【项集中出去的箭头上写的终结符号(一般大写字母)】3.若Ik包含A→α·，则aciton[k，a]=rj，a为任何终结符号或$，j为产生式A→α的编号(含有归约项目的状态是可归前缀识别态)【注意加颜色那句，这样分析表里就可能有了一行行完全相同

4、的项了，LR(0)的分析表课本(紫龙书)里没有】4.若Ik包含S’→S·，则action[k，$]=acc【串被接受，通常是I1里面的】例子：SLR(1)分析表的构建项目集合中的冲突例子：对于以下文法：我们只关注其项集I1此处有移入--规约冲突，故不是LR(0)文法，由此引入SLR(1)文法。当存在冲突时才向前看一个符号，因此是一种简单的LR(1)分析方法，称为SLR分析继续上面的例子，FOLLOW(E)={$,+,)},可以看出*不再FOLLOW(E)中，这意味着如果我们看到下一个符号(即lookahead向前看符号)是*,则可以使用做移进；若向前看

5、符号是{$,+,)}中的一个，则使用进行规约。课本中图4-37的分析表即是有移入-规约冲突的SLR(1)分析表。(本科教学版P149)例子：文法：考虑项集I1，此处有规约规约冲突。此处FOLLOW(X)∩FOLLOW(Y)=Φ,仍可以通过检查向前看符号确定规约式，可以用SLR(1)解决。但对于这个例子;I1上有移入--规约冲突，但此处=∈FOLLOW(R)，不能通过向前看符号确定是移入还是规约。一个更强大的语法LR(1)由此引出。因其产生过多的状态，一般只使用其简化版，即LALR(1)，与LR(0)有相同的状态，但较之更强大。一般情况，弄清楚LR(0)

6、和SLR(1)即可。最后一个例子：1.画自动机2.LR(0)分析表注意，虽不是LR(0)文法，因I3中有移入--规约冲突，但要求的是LR(0)分析表注意ACTION[3,,]这个表项，有移入-规约冲突，则会出现一个表项中填两个值3.画SLR(1)分析表FOLLOW(S)={$},FOLLOW(D)={$,','}