3A.3.6 自底向上 - LR(1)、LALR

3.3.6.1 LR(1)项集定义

有的文法构建出来的 LR(0) 项集可能会存在移入、规约冲突，例如：

S -> L = R | R L -> * R | id R -> L

我们为该文法的增广文法构建两个项集闭包：

I0: S’ -> ·S S -> ·L = R S -> ·R L -> ·*R L -> ·id R -> ·L

I1: S -> L· = R R -> L·

可见在 I1 中，我们既可以通过项 R -> L· 进行规约，也可以根据项 S -> L· = R 进行移入操作。想要解决这种冲突，解析器就必须读取更多的上下文信息来辅助自己做决策：即向前查看（Look ahead）符号。如果输入的下一个符号是 =, 那么就继续移入，否则就进行规约。

为了让 Look ahead 的符号能够与项集中的项进行匹配，我们必须让项保存更多信息，也就是说我们必须让项更加“精细化”，Look ahead 将要查看多少个符号，就必须向项里面引入等量的额外分量，来形成新的映射关系。我们在这里仅讨论 LR(1), 所以还需要往项里面引入一个变量，用来表示终结符号。修改之后，之前的项 A -> α·β 变成了 [A -> α·β, a], 终结符号 a 表示该项合法的后继符号，即 Look ahead 符号为 a 时，该项才可能是一个可以应用的项。该类项称为 LR(1) 项，其集合称为 LR(1) 项集。

进一步思考可以发现在项 [A -> α·β, a] 中，如果 β 不为空，则符号 a 其实没有作用，因为此时只可能进行移入操作；只有对于形如 [A -> α·, a] 的项，如果下一个输入符号是 a 时，才能进行规约。由此可见引入 Look ahead 符号其实本质上是在协助判断是否可以进行规约，例如上面例子中，我们需要通过下一个符号来判断是否可以通过 R -> L· 进行规约。

3.3.6.2 规范LR(1)语法分析表

为了正确地构建文法的 LR(1) 项集族，我们需要先对用到的两个算法稍作修改：

• Closure(I), 使用下述三重循环为项集 I 构建闭包项集：

  for (I 中每个项 [A -> α·Bβ, a]) for (文法中的每个产生式 B -> γ) for (First(βa) 中的每个终结符号 b) 将 [B -> ·γ, b] 加入到 I 中

  重复该循环直到没有新的项加入到 I 中为止

• Goto(I, X) 所表示的项集闭包的构建算法如下：

  1. 初始化集合 K

  2. 对于 I 中每个项 [A -> α·Xβ, a], 将 [A -> αX·β, a] 加入到集合 K

  3. Closure(K) 即为 Goto(I, X) 的项集闭包

有了 Closure 与 Goto 算法，我们就可以为文法构建 LR(1) 项集族了：

1. 给定文法 G, 创建其增广文法 G’, 令 C 为 G’ 的项集族，初始化为空集

2. 令 I0 = ｛[S’ -> ·S, $]｝，将 Closure(I0) 加入 C 中

3. 对于 C 中的每个项集 I, 对于 G’ 中的每个文法符号 X, 如果 GOTO(I, X) 不在 C 中，则将其加入其中

4. 循环第 3 步，直到没有新的项集加入到 C 中为止

对比 LR(0) 的项集族算法，其实只有 I0 不一样。现在我们可以为给定文法 G 构造其 LR(1) 的语法分析表了，其算法如下：

1. 求出增广文法 G’ 的项集族 C = ｛I0, I1, I2, … ，In｝，i 代表 Ii 所对应的状态

2. 对于任意项集 Ii, 执行如下操作构造 Action 部分：

   1. 如果 [A -> α·aβ, b] 在 Ii 中，并且 Goto(Ii, a) = Ij, 则将 Action[i, a] 的动作设置为移入

   2. 如果 [A -> α·, a] 在 Ii 中，则将 Action[i, a] 的动作设置为规约

   3. 如果 [S’ -> S·, $] 在 Ii 中，则将 Action[i, $] 设置为“接受”

   如果上述步骤产生了冲突，则该文法就不是 LR(1) 文法，我们无法为其构建一个 LR(1) 分析表

3. 对于任意项集 Ii, 执行如下操作构造 Goto 部分： 对于所有的非终结符号 A, 如果 GOTO(Ii, A) = Ij, 那么将 Goto[i, A] 设置为“状态转换到 j”

4. 将语法分析表中第 2 步与第 3 步没有设置的条目设置为报错

通过该算法得到的语法分析表成为规范 LR(1) 语法分析表。整个算法的思路与 LR(0) 语法分析表的思想是一样的，区别在于为了匹配 Look ahead 符号，在项中引入了额外的分量使项集更加精细化，从而导致产生了更多的项集，这也正是使用 Look ahead 的目的：通过更多的上下文信息将 LR(0) 中有冲突的项集划分开来。

3.3.6.3 LALR语法分析表

规范LR(1) 语法分析表已经将如何利用 Look ahead 符号来辅助解析过程的思路表达得很充分了，但额外增加的状态数量导致了对空间的需求量显著增加，为了使其具备实践价值，我们必须想办法减少状态数量。

我们在构建规范LR(1) 语法分析表时，每一个状态都是有用的，所以我们不可能直接扔掉一些状态来减少分析表的状态数量，那么剩下的策略就只能是合并：在不产生冲突的情况下，将多个状态合并为一个。

如何确定可以合并哪些状态呢？

我们知道对于同一个文法，LR(1) 项集比 LR(0) 项集多的原因是前者引入了额外的分量：Look ahead 符号。再回顾一下 LR(1) 项的形式：[A -> α·β, a], 其中第一个分量是 LR(0) 项：A -> α·β，第二个分量是 LA 符号：a. 我们将 LR(1) 项集中仅由第一个分量组成的集合叫着 LR(1) 项集的核心（Core）。容易得出：任何一个 LR(1) 项集的核心，都有一个 LR(0) 项集与之对应。根据鸽巢原理：必定存在多个 LR(1) 项集的核心，与同一个 LR(0) 项集对应。

为什么 LR(1) 项集核心必定与一个 LR(0) 对应呢？

我们知道 LR(0) 项集所代表的意义是：当前情况下，所有可能的合法产生式集合，以及每个产生式当前所处的位置！这个意义不会因为我们向前查看了输入符号而发生改变，也就是说，在自底向上解析的过程中，在任意时刻，解析器当前状态所对应的那个项集，不管 LR(k) 中的 k 是多少，其项集核心都是一样的；LR(1) 多出来的项集是 LR(0) 项集中各个项与 Look ahead 符号组合形成的新状态，所以将 Look ahead 符号剔除之后，其必定与一个 LR(0) 项集对应。

唯一合理的假设是我们将核心相同的 LR(1) 项集合并成一个状态，但要注意一个问题是：合并之后的状态不能存在冲突。由此可以得到如下合并思路：对于任意 n 个核心相同的 LR(1) 项集，只要他们的移入、规约操作没有冲突，那么就可以将他们合并为一个 LR(1) 项集。通过该方式构建的语法分析表叫着 LALR 语法分析表，由于 LALR 分析表即利用了 LA 技术，又显著减少了状态数量，所以具备很好的实践价值。