【编译原理笔记07】语法分析：SLR、LR(1)、LALR、二义性分析与错误处理

本次笔记内容：
4-12 SLR
4-13 LR1分析
4-14 LALR分析法
4-15 二义性文法的LR分析
4-16 LR分析中的错误处理

本节课幻灯片，见于我的 GitHub 仓库：第7讲 语法分析_4.pdf

上节课的内容中，LR(0)存在冲突。这节课首先提出SLR进行解决。SLR的改进很简单，但还存在冲突。因此又引出LR(1)。

但是，LR(1)的状态过多，于是引出LALR化简、合并其状态。

最后，介绍了二义性与错误处理。

SLR分析

上节课的例子中，我们认识到：LR(0)分析过程中存在冲突。而规定 FOLLOW 集，可以帮我们判断，在那些情况下，不进行归约。这也正是 SLR的基本思想。

基本思想

这里的 S 代表simple，因为其只需要一个 FOLLOW 集就可以化解冲突。但是对于某些冲突，需要更复杂的方法化解（后文会提到）。

SLR分析表

与 LR(0) 分析表进行对比：

• 在 LR(0) 分析表中，每一个状态在遇到任何输入符号时，都采取归约动作，因此归约状态在这一行中每一项都是归约动作（如第2行、第9行）；
• 而在 SLR 分析表中，对于归约状态，只有遇到 FOLLOW 集中的元素，才采取归约动作。

例：SLR分析法构造

SLR 分析表构造算法

如上，SLR分析表与LR(0)分析表是类似的，唯一不同在于FOLLOW集的使用。

如果给定文法的SLR分析表中不存在有冲突的动作，那么该文法称为SLR文法。

SLR分析中的冲突

如上图，产生了移入-归约冲突。

LR(1)分析法

SLR分析存在的问题：SLR只是简单地考察下一个输入符号b是否属于与归约项目A→α相关联的FOLLOW(A)，但b∈FOLLOW(A)只是归约α的一个必要条件，而非充分条件。

如上图，对于树中的 R ，在不同地方，其后继符是不同的，一个地方对应=，一个地方对应$。

由此可见：在特定位置，A的后继符集合是FOLLOW(A)的子集。

因此，我们规定了新规则，如$R \rightarrow L \cdot , =$R→L⋅,=，表示只有当下一个符号是=时，才可以将栈顶的L归约为R。

规范LR(1)项目

将一般形式为[A→α·β, a]的项称为LR(1) 项，其中A→αβ 是一个产生式，a 是一个终结符(这里将$视为一个特殊的终结符)它表示在当前状态下，A后面必须紧跟的终结符，称为该项的展望符(lookahead)：

• LR(1) 中的1指的是项的第二个分量的长度
• 在形如[A→α·β, a]且β ≠ ε的项中，展望符a没有任何作用
• 但是一个形如[A→α·, a]的项在只有在下一个输入符号等于a时才可以按照A→α 进行归约：这样的``a的集合总是FOLLOW(A)的子集，而且它通常是一个真子集

等价LR(1)项目

如上，[ A→α·Bβ, a ]等价于[ B→·γ, b ]，其中：

• 如果β可以为空，则b=a叫继承的后继符；
• 否则叫自生的后继符。

例：LR(1)自动机

注意，待约项目一定有等价项目。因此有待约项目，一定要继续写下去。

个人理解：如 I0 到 I4 ，相当于 I0 遇到 * 号，则将 I0 中两个以 * 开头的式子写入，并且由这两个式子进行推导，得到下面的一系列式子，直到待约项目都推导完为止。

例：赋值语句文法的LR(1)分析表

承接上例，构造出的分析表如图。注意到对于状态2，只有当下一个符号是$时才采取归约动作，而是=时，采取移入动作。

可以注意到，其比SLR多了4个状态，这正是LR(1)进行信息细化的结果。

如果除展望符外，两个LR(1)项目集是相同的，则称这两个LR(1)项目集是同心的。

LR(1)项目集闭包

GOTO函数

为文法G’ 构造LR(1)项集族

LR(1)自动机的形式化定义

LR分析表的构造算法

如上，与LR(0)、SLR分析法不同之处在于归约项目的处理上。

如果LR(1)分析表中没有语法分析动作冲突，那么给定的文法就称为LR(1)文法。

LALR 分析法

LR(1)的局限性

在之前的LR(1)分析法中：

• 通过赋值语句例子我们发现，存在一些同心项目集合；
• 换句话说，LR(1)分析法实际上是根据展望符集合的不同，将原始的LR(0)项目分裂成不同的LR(1)项目。
• 这样就使得LR(1)自动机的状态数多了很多；
• 比如对于C语法，LR(0)只有几百个状态，但是LR(1)会有几千个状态。

如上，对于状态8与10，其动作是不冲突的，因此，其实这两个同心项目可以合并。此外，还有其他没有动作冲突的状态可以合并。

基本思想

• 寻找具有相同核心的LR (1) 项集，并将这些项集合并为一个项集。所谓项集的核心就是其第一分量的集合；
• 然后根据合并后得到的项集族构造语法分析表
• 如果分析表中没有语法分析动作冲突，给定的文法就称为LALR (1) 文法，就可以根据该分析表进行语法分析。

例：合并通信项集

如上，可以删除10到13号状态，由此得到如下的 LALR自动机。

合并同心项集时产生归约-归约冲突的例子

如上，可能产生归约-归约冲突。

合并同心项集不会产生移进-归约冲突。这是因为同心项目集，其心是相同的，那么合并时，合并的是对应项目集的展望符集合，而展望符只在规约时起作用，在移入是是不起作用的。

合并同心项集后，虽然不产生冲突，但可能会推迟错误的发现

如上，将 I4 与 I9 进行合并后，如果输入一个错误的 d$ ，其在状态4没有被发现（在原有自动机中是可以直接发现的）。推迟了2步，才被发现。

LALR分析法可能会作多余的归约动作，但绝不会作错误的移进操作。

LALR(1)的特点

• 形式上与LR(1)相同
• 大小上与LR(0)/SLR相当
• 分析能力介于SLR和LR(1)二者之间，SLR<LALR(1)<LR(1)，合并后的展望符集合仍为FOLLOW集的子集。

二义性文法的LR分析

二义性文法的特点

• 每个二义性文法都不是LR的
• 某些类型的二义性文法在语言的描述和实现中很有用：更简短、更自然，如下图

二义性算术表达式文法的LR(0)分析器

如上，二义性文法产生的自动机本身带有冲突，那么该如何消解呢？

如蓝色的箭头：

• 对于状态7，如果栈外的输入符号是*，乘法优先级高，则先移入乘号到栈中，首先计算乘法，进入到状态5。

因此，用优先级和结合性解决冲突。

例：二义性if 语句文法的LR分析

if本身是一个二义性文法。

在第2章中讲过就近匹配原则。

在状态4，移入下一个输入符号是e时，将e移到栈中，使其跟前面与之最近的iS进行匹配，以此化解状态4的冲突。

二义性文法的使用

应该保守地使用二义性文法，并且必须在严格控制之下使用，因为稍有不慎就会导致语法分析器所识别的语言出现偏差。

LR分析中的错误处理

• 语法错误的检测：当LR分析器在查询分析表并发现一个报错条目时，就检测到了一个语法错误；
• 错误恢复策略：恐慌模式错误恢复、短语层次错误恢复。

恐慌模式错误恢复

• 从栈顶向下扫描，直到发现某个状态si，它有一个对应于某个非终结符A的GOTO目标，可以认为从这个A推导出的串中包含错误；
• 然后丢弃0个或多个输入符号，直到发现一个可能合法地跟在A之后的符号a为止；
• 之后将s_{i+1} =GOTO(si , A)压入栈中，继续进行正常的语法分析。

短语层次错误恢复

• 检查LR分析表中的每一个报错条目，并根据语言的使用方法来决定程序员所犯的何种错误最有可能引起这个语法错误；
• 然后构造出适当的恢复过程。

例：算数表达式文法的LR分析器

如图，e1代表错误处理例程error1。

带有错误处理子程序的算术表达式文法LR分析表

分析表如上图。