编译器Parsing（三）：LR(1)文法和解析器

为什么 LR 解析几乎成了编译器的默认选择

写语法分析器时，真正困难的并不是“把输入读进去”，而是在读到一半时，判断接下来该移进、归约，还是报错。这正是 LR 解析解决的问题。它把解析过程改写成一种自底向上的状态机执行：一边从左到右读 token，一边在栈上构造最右推导的逆过程。这样做的结果是，很多 LL 方法难以处理的语法，比如左递归语法和更接近真实编程语言写法的语法，在 LR 框架里反而更自然。

这篇文章想说明三件事。第一，LR 解析到底在“做什么”；第二，LR(0)、SLR(1) 和 LR(1) 的能力差别来自哪里；第三，为什么工程上常见的是 LALR(1) 这一类折中方案。把这条主线抓住，再看各种项目、闭包、自动机和分析表，就不会觉得它们只是一些分散的定义。

解析的本质是受限搜索

语法分析的输入是一个上下文无关文法，输出则是某个字符串的语法树；如果字符串不属于这个文法，就要报错。理论上这是一个搜索问题：同一段输入可能对应多种推导路径，歧义文法甚至可能有多棵语法树。一般算法能处理得很广，但代价通常较高，经典方法的最坏复杂度可以到 $O(n^3)$。

编译器不会接受这样的代价，于是实际做法通常不是追求“能处理所有文法”，而是限制文法的形状，换取线性时间解析。LL 和 LR 都属于这种思路，只是约束方式不同。LL 从顶向下猜“接下来该展开哪个产生式”；LR 从底向上判断“栈顶这一段是否已经能归约成某个非终结符”。两者都在减少搜索，只是削减不确定性的方向不一样。

为什么自顶向下方法经常让人写得别扭

LL(1) 的优点是直观：从开始符号出发，逐步展开左推导，用一个预测表或递归下降函数来决定每一步。但它对文法形状要求很高。文法往往必须手动改写，不能有左递归，很多时候还要做左因子提取。

这和真实语言设计的习惯并不总一致。比如表达式天然就喜欢写成左递归形式：

$$ S \to S + E \mid E $$

而不是为了迁就解析器改写成更绕的形式。问题不只是“麻烦”，更在于语法本身的结构信息被迫让位给解析技术限制。LR 方法之所以重要，正是因为它允许文法更接近语言本来的结构。

LR 解析做的不是“猜”，而是“回收已经确认的结构”

LR 的名字可以拆开看：从左到右读输入，构造最右推导。更准确地说，真正运行时构造的是最右推导的逆过程。解析器并不从开始符号往下展开，而是不断观察当前栈顶，寻找一段已经足够确定的句柄，把它归约成更高层的非终结符。

这就是经典的 shift-reduce parsing。

• Shift：把当前向前看 token 移进栈。
• Reduce：如果栈顶符号串 $\gamma$ 恰好是某个产生式 $X \to \gamma$ 的右部，就把它弹出，再压入 $X$。

解析状态由两部分组成：栈和尚未消费的输入。在任意时刻，栈加上剩余输入，代表的都是某个最右推导逆过程中的中间步骤。这个不变量非常关键，因为它解释了为什么“归约”不是随便替换，而是在逐步恢复更高层的语法结构。

一个简单例子就能看出自底向上的直觉

考虑下面这个文法：

$$ S \to S + E \mid E $$

$$ E \to \text{number} \mid (S) $$

读入表达式 (1 + 2 + (3 + 4)) + 5 时，自顶向下方法很早就要决定该展开哪条产生式；但自底向上方法可以先把已经确认的局部结构收起来，比如先把 1 归约成 E，再归约成 S，之后继续处理 + 2，再继续处理括号内部。

把这个过程画成树以后会更容易看懂：自底向上的关键不是“已经把整棵树建好”，而是树的某些局部已经足够确定，可以先向上折叠。图里最值得注意的一点是，某些左括号虽然已经读到了，但还没有完成它们对应结构的处理；这说明 LR 解析并不是简单顺序消费字符，而是在维护“哪些结构已经封闭、哪些还在等待后续输入”。

真正的难点不是归约本身，而是何时归约

只看定义，shift 和 reduce 都不复杂。难的是：同一个时刻到底该选哪一个动作。

给定当前栈 $\sigma$ 和向前看符号 $b$，解析器需要回答：

• 直接把 $b$ 移进栈吗？
• 还是把栈顶某段归约成某个非终结符？
• 如果能归约，归约哪一条产生式？
• 如果既能移进又能归约，谁优先？

这就是动作选择问题。仅靠“栈顶长得像某个产生式右部”并不够，因为“能归约”不代表“现在就应该归约”。某些归约如果做早了，后面就无法继续匹配正确结构。LR 系列方法的核心价值，其实就是把这个选择问题编译成一个有限状态机，再进一步编译成分析表。

LR(0) 的想法是把“栈前缀”压缩成有限状态

LR(0) 先从最简单的版本开始：完全不看向前看符号，只根据当前栈对应的状态来决定动作。

为了做到这一点，它不再直接记录“我现在可能在归约什么”，而是引入了 item。一个 LR(0) item 就是在某条产生式右部中插入一个点 .，表示当前匹配进度。例如：

$$ S \to .(L) $$

表示这条产生式还什么都没看到；而

$$ L \to S. $$

则表示这一条已经完整匹配，可以归约。

点左边的符号代表“已经在栈上”，点右边代表“接下来可能看到的东西”。于是，一个 LR(0) 状态就是一组 item，它表示“当前这个栈前缀下，接下来所有可能的归约进度”。

这一步很重要，因为它把无限多种栈前缀，压缩成了有限个可区分的状态。

闭包和转移把这些状态组织成一个 DFA

为了让状态完整，不能只放一个 item。只要某个 item 的点后面出现了非终结符，就必须把这个非终结符的所有产生式也补进来，而且点要放在最左边。这就是 closure。

例如先给文法加一个新的开始产生式：

$$ S' \to S$ $$

初始 item 是：

$$ S' \to .S$ $$

因为点后面是非终结符 $S$，所以还必须加入所有 $S$ 的产生式，且点放在最前面。这样不断补，直到不再新增 item 为止。

有了闭包以后，再看状态中点后面可能出现的符号。对每个这样的符号做一次“把点向右移动一格，再取闭包”，就得到一条 DFA 边和一个新状态。于是，整个 LR(0) 解析器背后其实是一个读取栈内容的 DFA。

这张自动机图最值得看的不是节点数量，而是节点含义：每个节点都不是“一个产生式”，而是“当前栈前缀下所有可能解析进度的集合”。当某个节点里出现点在最右端的 item，就说明此时存在可归约动作。也正因此，LR 分析表本质上只是把这个 DFA 查表化。

用元组文法看 LR(0) 会清楚很多

下面这个文法非常适合做例子：

$$ S \to (L) \mid id $$

$$ L \to S \mid L, S $$

它描述的是非空元组和标识符，比如 x、(x,y)、(x,(y,z),w) 这类结构。这个文法的好处是，括号、逗号、嵌套和列表递归都在里面，但规模又足够小。

解析 (x, (y, z), w) 时，栈上的动作大致是这样的：

• 看到 x 后，先归约 S \to id
• 接着归约 L \to S
• 读到逗号和左括号后，继续进入嵌套结构
• 内层 (y, z) 归约成一个 S
• 再与前面的 L 组合，继续归约 L \to L, S
• 最终整个 (L) 归约成 S

这个过程看起来像“边读边改写”，但本质上每一步都依赖前面那个 DFA 状态判断是否合法。

从自动机到分析表，解析器才真正可执行

真正实现时，不会每次都把整段栈重新拿去跑 DFA。更高效的做法是：栈里不只存语法符号，还把到达的状态一起存进去。这样每次 shift 时直接转移，reduce 时先按产生式长度弹栈，再通过 goto 跳到新状态。

于是分析表就分成两部分：

• action 表：面对终结符时，决定 shift、reduce、done 或 error
• goto 表：归约出非终结符后，该跳到哪个状态

这张表最容易被误读成“死记硬背的结果”，其实它只是自动机的一种压缩表示。比如表中 s3 的意思是“移进并进入状态 3”，g5 的意思是“归约后沿非终结符转移到状态 5”。只要把它和上一张 DFA 图对起来看，就会发现两者是一回事：一个是图，一个是矩阵。

LR(0) 为什么不够强

LR(0) 的限制非常直接：它不看任何向前看符号。所以只要某个状态里既出现可归约项，又出现可移进项，或者同时出现多个归约项，它就会卡住。

这会产生两类经典冲突：

shift/reduce 冲突

某个状态里既可以 shift，也可以 reduce，但 LR(0) 无法决定该选哪个。

reduce/reduce 冲突

某个状态里同时有两条不同归约都合法，LR(0) 无法判断该归约哪一条。

表达式语法中的结合性和优先级问题，尤其容易引发 shift/reduce 冲突。比如右结合形式的求和文法：

$$ S \to E + S \mid E $$

$$ E \to \text{number} \mid (S) $$

当栈里只有一个 E 时，既可能把它归约成 S，也可能继续 shift 后面的 +。LR(0) 因为没有向前看，只能看到“这两件事都像是可能的”，却不知道哪一个才对。

SLR(1) 的改进很克制，但很实用

SLR(1) 没有重建一套全新的自动机。它保留 LR(0) 的 DFA，只在决定 reduce 时引入一个向前看符号。核心规则是：

如果某个状态允许把 $A$ 归约出来，那么只有当当前向前看符号属于 $\text{Follow}(A)$ 时，才执行这次归约；否则就不归约。

这相当于给“归约”加了一层语法上下文过滤。它不能解决所有问题，但能解决不少原本纯 LR(0) 无法判断的冲突。尤其当多个可能归约对应的 Follow 集彼此不重叠时，reduce/reduce 冲突就能被拆开。

SLR(1) 的价值在于它很便宜：自动机不变，只是动作更谨慎。所以它是理解“lookahead 如何增强 LR”最好的第一步。

LR(1) 真正把向前看信息放进状态里

LR(1) 比 SLR(1) 更强，因为它不再只在最后一刻参考 Follow 集，而是把向前看信息直接并入 item。

一个 LR(1) item 形如：

$$ A \to \alpha . \beta,\ L $$

其中 $L$ 是一组允许出现在这个归约之后的向前看符号。这样一来，同一个“点位置”如果搭配不同 lookahead，就会成为不同的 item。也就是说，LR(1) 不是在冲突出现后补救，而是在状态构造阶段就把上下文差异分开了。

它的 closure 规则也更细。若已有 item：

$$ A \to \beta . C\delta,\ L $$

那么为非终结符 $C$ 新增 item 时，lookahead 不是随便继承，而是要计算：

1. 把 $\text{FIRST}(\delta)$ 加进去
2. 如果 $\delta$ 可以推出空串，再把原来的 $L$ 也加进去

这一步看似技术性很强，其实含义很朴素：新展开的子结构，要知道自己结束后后面可能跟着什么。只有这样，归约时才不会把本来只在一种上下文里合法的动作，错误地推广到所有上下文。

LR(1) 能解决的，本质上是“同形不同境”的问题

很多 LR(0) 冲突之所以棘手，不是因为项目本身长得复杂，而是因为相同的栈形状，在不同后续输入下应该做不同决定。LR(0) 看不到这个差别，SLR(1) 用全局 Follow 集粗略补充，LR(1) 则把这些差异精确编码进状态。

这张状态片段最关键的地方，是两个看起来几乎一样的 item，因为 lookahead 不同而表现出不同作用。也正因如此，表里的 shift 和 reduce 可以在原本冲突的位置被分开。换句话说，LR(1) 的强大之处不是“多看一个符号”这么简单，而是把那个符号纳入状态定义。

为什么工业界常见的是 LALR(1)

LR(1) 的表达能力强，但代价是状态数和表规模往往明显变大。工程上如果直接用表驱动实现，空间成本和生成复杂度都会上升。

LALR(1) 的思路是折中：把那些“核心 item 相同、只是在 lookahead 集合上不同”的 LR(1) 状态合并。合并后表会小很多，通常也仍然足够处理大多数编程语言语法。所以传统 parser generator，像 yacc、ocamlyacc 这一类，常用的就是 LALR(1)。

代价当然也有。某些原本在 LR(1) 中可区分的上下文，合并后可能重新产生冲突，尤其是 reduce/reduce 冲突。但从实际效果看，这个折中非常成功：它牺牲一部分理论最强能力，换来了更小、更实用的分析表。

各种文法类别之间是什么关系

从能力上看，这几类文法大致形成一个包含关系：

$$ LL(1) \subset LR(0) \subset SLR(1) \subset LALR(1) \subset LR(1) $$

更准确地说，课程里的分类图强调的是：LR 家族整体比 LL 更能表达真实编程语言语法，而 LR(1) 在单符号向前看条件下拥有最强能力。LALR(1) 是最常见的工程折中，SLR(1) 适合作为理解过渡，LR(0) 则更像概念起点。

这条链条真正值得记住的，不是集合关系本身，而是每前进一步都在做同一件事：更精确地区分“相同栈前缀在不同上下文中的动作选择”。

理解 LR 时最该抓住的主线

很多人第一次学 LR，会被 item、closure、goto、DFA、action/goto 表这些名词淹没。其实它们都服务于同一个目标：在每一步都准确决定当前该 shift 还是 reduce。

沿着这条主线看，整个体系就会变得很清楚：

• shift/reduce 解析定义了执行模型
• item 描述了产生式匹配进度
• closure 补全某个状态里所有可能的后续结构
• goto 把状态连成自动机
• action/goto 表把自动机变成可执行程序
• lookahead 则用来解决“现在能归约，但是否应该现在归约”的问题

一旦把这个过程连起来，LR 就不再是一堆分散技巧，而是一种非常统一的设计：用有限状态控制自底向上的归约时机。这也是它长期成为编译器前端核心技术的原因。