LR(0) → SLR(1) → LALR(1) → LR(1)

lookahead 的四档精度

LR 一页的项集自动机回答了「栈顶这段是哪条产生式」，但还有一个问题没答：什么时候可以归约。一个状态里若既能归约又能移进，就要靠 lookahead 决定。四个等级的全部差别就在这个判断上，驱动器与项集构造过程完全共用。

1 · 归约的许可条件

等级	归约的许可条件	代价
LR(0)	无条件，只要点在末尾就归约	与移进撞车的概率最高
SLR(1)	lookahead 属于 $\text{FOLLOW}(A)$	FOLLOW 是全文法的，对具体状态往往过大
LALR(1)	lookahead 属于该状态下真正可能的后继集	需要先算 LR(1) 再按 core 合并
LR(1)	同上，且不合并状态	状态数显著膨胀

图 1-1 · 三份文法 × 四个等级的冲突数与状态数，全部来自 @vega/parsing/lr 的 buildTable。下方可查看任一等级的项集，冲突状态的行号标红。三行分别演示「LR(0) 不够」「SLR(1) 不够」「四个等级都不够」三种处境。

警示 · 要在别处复现这张表，等级得写成 buildTable(g, start, { mode: 'LR1' })。第三个参数是 options 对象，写成 buildTable(g, start, 'LR1') 不会报错，也不会生效：options.mode 取不到值，一律回落到默认的 SLR1。这个静默回落的表现是四个等级给出完全相同的冲突数与状态数（本页三份文法都会显示为 SLR(1) 那一列），看上去像「等级根本不起作用」。判据是看状态数：分层算术在 LR(1) 下应为 22 个状态，若四档都报 12，就是回落了。

2 · 从 LR(0) 到 SLR(1)

分层算术文法在 LR(0) 下有两处冲突，在 SLR(1) 下为零，两者的状态数都是 12。

冲突落在 S2 与 S9，两者结构相同。S2 含两个项：

S2:  E → T •            ← 点在末尾，可以归约成 E
     T → T • '*' F      ← 点在终结符之前，可以移进 '*'

LR(0) 无条件归约，读到 n*n 的首个操作数后就把 $T$ 归约成 $E$ ，* 于此再也接不上。SLR(1) 给归约加上条件：只有 lookahead 属于 $\text{FOLLOW}(E) = \{+, )\, \$\}$ 时才归约。* 不在其中，故此处只能移进，冲突消失。

值得注意的是 $\text{FOLLOW}(T)$ 确实含 *（因为 $T \to T * F$ 里 $T$ 之后就是 *）。此处管事的是被归约成的那个非终结符的 FOLLOW，即 $\text{FOLLOW}(E)$ ，不是右部里出现的 $T$ 的。分层文法的优先级设计刚好让 $E$ 与 $T$ 的 FOLLOW 集分了开，SLR(1) 由此够用。

3 · 从 SLR(1) 到 LALR(1)

经典的分界例子是龙书 §4.7 的这份文法（ $i$ 表标识符，* 表解引用）：

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

它在 LR(0) 与 SLR(1) 下都有一处移进-归约冲突，落在这个状态：

S2:  S → L • '=' R          ← 可以移进 '='
     R → L •                ← 可以归约成 R

$\text{FOLLOW}(R) = \{=, \$\}$ ，因为文法里存在 $S \to L = R$ ，而 $R \to L$ 使 $L$ 与 $R$ 可以互相出现在对方的位置上，故某些推导中 $R$ 之后确实可以是 =。SLR(1) 据此允许在 = 前把 $L$ 归约成 $R$ ，而那条路走下去接受不了任何合法输入。

LALR(1) 在此给出零冲突，且状态数与 SLR(1) 相同（都是 10）。它先按 LR(1) 项（项加精确 lookahead 集）构造自动机，算出该状态下 $R \to L \cdot$ 的真实 lookahead 集只有 $，然后把 core 相同的状态合并回去。图 1-1 切到 LALR(1) 后 S2 的第二项显示为 R → L • , $，= 已被排除。LR(1) 同样零冲突，但状态数是 14。

定义 3.1（LALR(1)） 把 LR(1) 自动机中 core（去掉 lookahead 后的项集）相同的状态合并，合并时取 lookahead 集的并。所得自动机的状态数与 LR(0) 相同，而 lookahead 精度接近 LR(1)。

这个「精度接近 LR(1)、规模等于 LR(0)」的组合就是 yacc 与 bison 选择 LALR(1) 的全部理由。在内存以 KB 计的年代，LR(1) 的状态膨胀是不可接受的；而 LALR(1) 用一次合并把成本降回去，代价只是极少数文法会因合并而产生本不存在的归约-归约冲突。

4 · 歧义的不可消解

第三份文法 $E \to E + E \mid n$ 在四个等级下都是一处冲突，状态数都是 5。

原因与 lookahead 精度无关：n+n+n 在这份文法下真有两棵树，任何确定性方法都必须在某处二选一，而文法本身没有提供依据。这就是 LR 一页所说的两类成因的分界：把等级依次调到 LR(1) 若冲突仍在，几乎可以断定是真歧义。

注 · 工程上处理这类冲突有三条路。一是改文法，把优先级与结合性编进层次（即分层算术那种写法）。二是用生成器提供的显式声明，bison 的 %left / %right / %prec 就是在冲突格上直接指定该移进还是该归约：文法仍是歧义的，只是冲突被人工裁决了。三是换用接受歧义的引擎，让它把多棵树都产出来，见 GLR 与 GLL 一页。

5 · 等级之外：真实生成器的选择

今天各生成器的选择有明显的分野。bison（LALR(1)，可选 GLR 与 IELR(1)）与 LALRPOP（LR(1) 为主）延续表驱动路线；ANTLR 走 LL(*)，用运行期的自适应前瞻取代构造期的等级；而多数主流语言的编译器前端干脆手写递归下降，把等级这件事完全绕开。

这不意味着等级理论过时。它的价值在于判据：一份文法是不是 LALR(1)，是关于该文法的一个客观事实，也是「这门语言的语法有多容易被机器读懂」的一个可计算指标。语言设计阶段拿它做一次体检，比事后在手写 parser 里发现某处需要三个 token 的前瞻要便宜得多。

6 · 参考文献

DeRemer, F. L. (1969). Practical translators for LR(k) languages (Doctoral dissertation). Massachusetts Institute of Technology.
DeRemer, F., & Pennello, T. (1982). Efficient computation of LALR(1) look-ahead sets. ACM Transactions on Programming Languages and Systems, 4(4), 615–649.
Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools (2nd ed.). Addison-Wesley. §4.7。