LR文法整理【LR文法的概念、LR(0)、SLR、LR(1)、LALR】（下）

最新推荐文章于 2022-12-03 18:23:52 发布

weixin_47365232

最新推荐文章于 2022-12-03 18:23:52 发布

阅读量4.1k

点赞数 5

分类专栏：编译原理文章标签：其他

本文链接： https://blog.csdn.net/weixin_47365232/article/details/125332262

版权

编译原理专栏收录该内容

5 篇文章 5 订阅

订阅专栏

LR(1)分析法

在Follow集合中的符号，只是进行归约的必要条件，而非充分条件。

出错原因：从下图的分析树中可以看到，R在不同的位置进行归约，后继符号是不一样的，简单的说，在特定位置中，A的后继符集合只是FOLLOW(A)的子集，这也就应证了上面说的，仅仅满足存在于FOLLOW集中，这是一个必要不充分条件，因此不能笼统的通过Follow集合进行判断，需要更加细化判断条件。

概念

学习了LR(0)和SLR之后，LR(1)项目的定义理解相对容易了很多。学习LR(1)主要需要知道展望符的概念和作用。

对于移入项目和待约项目，展望符a没有任何作用。

笔记回顾

这里补充两点

1、对于一个项目，并不是 · 在中间就是待约项目，比如 b · bBB这个是移进项目；

2、待约项目是没有等价项目的。

LR(1)等价项目

大体上和LR(0)是一样的，主要是多了对于展望符的推导。
如果β = ε ，则b = a；
如果β ≠ ε ，则b = FIRST(β)，注意是FIRST(β)而不是FIRST(B)。

LR(1)自动机转换图的构造

还是通过例子来进行解析，下图是LR(1)自动机的转换图。

拿I0进行分析：

项目1是通过用来进行增广的产生式0)得到的，其结束符号只能是$，因此1的展望符为$，这个项目为待约项目。因此根据文法中S的两个产生式1)和2)，写出两个等价项目2和3，由于项目1中S后面是空串，因此2和3直接继承1的展望符$。

项目2也是一个待约项目，因此根据L的产生式3)和4)可以得到其等价项目4和5。由于L后面的符号是 = 号，因此4和5的展望符为 = 号。

项目3也是一个待约项目，根据R的产生式5)可以得到它的等价项目6，由于R后面是一个空串，因此项目6直接继承项目3的展望符$。

项目4和项目5都是移进项目。

项目6是待约项目，同理可以得到其等价项目7和8，同理7和8也继承6的展望符$。

项目7和8都是移进项目。

至此，I0的项目集闭包成功找到。

LR(1)自动机分析表的构造

根据转换图，可以构造出LR(1)自动机的分析表。

对于移入项目和待约项目的处理方法与LR(0)是一样的，对于归约项目，则有特定的后继符号要求才能进行归约。

归约条件比较

就拿I2来进行说明

LR(0)分析表：对于任何一个输入符号，都可以执行归约动作。

SLR分析表：对于Follow®集中的任何一个符号，都可以执行归约动作。

LR(1)分析表：只有当下一个输入符号为$的时候，才可以执行归约动作。

错误预见解析

下面由红色虚线框住的状态，如果根据SLR文法分析，当输入符号为 = 号的时候是可以进行归约的，但是从我们初始的文法可以看到，输入语句中最多只有一个 = 号，而I10、I12、I13状态都要经过I2和I6这两步得到，很明显在进行 = 号的归约之前，就已经存在一个 = 号，因此这里如果遇到 = 号进行归约肯定是错误的。