# 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 技术，又显著减少了状态数量，所以具备很好的实践价值。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://gocompiler.shizhz.me/3.b-yu-fa-fen-xi-li-lun-zhi-shi/3.3.6-zi-di-xiang-shang-lr1lalr.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.