LR 分析

自底向上的另一条路:LR 比 LL 能处理更多文法,不需要消除左递归——代价是必须靠生成器。理解 LR(0)→SLR→LR(1)→LALR 的每一步升级,就理解了 yacc/bison 的本质。

概述

递归下降与 LL是自顶向下:从文法出发,推导输入。LR 是自底向上:从输入 token 出发,逐步归约(reduce)到文法符号,直到整个输入归约到起始符号。LR 比 LL 强大——能处理的文法严格多于 LL(1),且不需要消除左递归。LR 的代价是:不能手写(太复杂),必须靠生成器(yacc/bison/lalrpop)从文法自动构建 parse table。这篇讲 LR 从 LR(0) 逐步升级到 LALR 的每一步——每一步都在解决上一步的"不是少就是多"。

LR 分析器的结构

LR 分析器由三个部件组成,输入和栈驱动:

输入: [id, +, id, *, id, $]         ← token 流, $ 是结束符
栈:   [0, E, 1, +, 2, T, 5, ...]    ← 状态栈 + 文法符号交替
                  ↑ 栈顶

每一步查表:
  action(state, next_token) → shift s / reduce A→β / accept / error
  goto(state, nonterminal)  → 下一个状态

• shift:把下一个输入 token 和 action 表给出的目标状态压入栈。
• reduce A→β:从栈顶弹出 2×|β| 个元素(其中 |β| 是归约式右部包含的文法符号个数,每个符号在栈上对应一个"符号+状态"对),再把 A 压栈,用 goto 表确定新状态并压栈。
• accept:成功解析。
• error:语法错误。

parse table(action + goto)是 LR 分析的全部智慧所在——编译器生成器的核心工作就是构建这张表。

从 LR(0) 到 LALR:步步升级

LR(0):基础但不实用

item(项目)是 LR 理论的核心概念:一个形如 A → α·β 的带点规则,点表示"已经识别了 α,尚未识别 β"。

LR(0) 的 parse table 构造:

closure(I):   ← I 是一组 item
    对 I 中每个 item A→α·Bβ:
        把 B 的所有产生式 B→·γ 加进 I (如果不在 I 中)
    重复直到不再增加

goto(I, X):   ← X 是文法符号 (terminal or nonterminal)
    对 I 中每个 item A→α·Xβ, 把 A→αX·β 加到 J
    return closure(J)

从初始 item S'→·S 的 closure 出发,反复对每个可能符号 X 计算 goto,产生新状态,直到所有状态饱和——得到 LR(0) canonical collection。

LR(0) 的问题⁠:对于 A→α·(点在末尾,可归约),在任何输入下都归约——完全不看当前 token。这意味着很多实用文法(有 else 的 if、有优先级的表达式)在 LR(0) 下产生 shift/reduce 冲突。LR(0) 能处理的文法非常有限,大多数实际语言都需要至少 SLR(1) 的能力。

SLR(1):用 FOLLOW 削减不必要的归约

SLR 的改进:对 item A→α· (可归约),只在当前 token 属于 FOLLOW(A)时才归约——换言之,只在"文法认为 A 后面可能出现这个 token"时才做归约。

LR(0) reduce:  在所有输入下归约 A→α
SLR reduce:    仅在 next_token ∈ FOLLOW(A) 时归约 A→α

SLR 解决了 LR(0) 的大部分无意义归约。但 FOLLOW 是全局集合——它在所有出现 A 的位置都相同,不区分"A 在这个状态下归约时,下一个 token 是什么"。SLR 仍然会在某些上下文中做不必要的归约。

LR(1):完全精确,但状态爆炸

LR(1) 的 item 不仅记录"点在哪",还记录 lookahead——在这个状态下归约这条规则时,下一个 token 应该是哪个符号。

LR(0) item:   A → α·β
LR(1) item:   [A → α·β, a]     ← a 是 lookahead token

LR(1) 的 closure 比 LR(0) 复杂:

closure(I):
    for I 中的 [A→α·Bβ, a]:
        for B 的每个产生式 B→γ:
            for b ∈ FIRST(βa):        ← β 可能推导出的首个 token, 或如果 β→ε 则为 a
                把 [B→·γ, b] 加进 I (如果不在 I 中)

LR(1) 的 parse table 几乎不会无谓冲突——能处理的文法非常广。代价是状态数量膨胀⁠:同一个 LR(0) 状态因为 lookahead 不同,分裂成数个 LR(1) 状态。对于实际的编程语言文法,LR(1) 状态数可能达到 LR(0) 的 5–10 倍。

LALR(1):合并"魂相同的状态",实际世界的选择

LALR(Look-Ahead LR) 是 LR(1) 的精简版,是所有实际 LR 生成器(yacc/bison/lalrpop)的默认算法:

取 LR(1) 的状态集合, 把所有 LR(0) 核心相同 (item 相同, 但 lookahead 不同) 的状态合并
  合并后每个状态的 lookahead = 原来几个状态 lookahead 的并集
  用合并后的状态集合构建 parse table

• LALR 的状态数 = LR(0) 的状态数⁠(远小于 LR(1)),但解析能力非常接近 LR(1)。
• 代价:合并可能引入新的 reduce/reduce 冲突——但实践中非常罕见,且几乎总是意味着文法本身有问题。

为什么 LALR 是工业标准:状态数少 → parse table 小 → 编译器占用内存低,且构建 parse table 的时间可接受。绝大多数编程语言(LR 路线的)的 parser 生成器都用 LALR(1)。

Shift/Reduce 与 Reduce/Reduce 冲突

LR 表生成时可能遇到两类冲突:

• Shift/Reduce:action 表的某格中同时有 shift 和 reduce。最经典的案例是 dangling else——看到 if...if...else 时,else 应该 shift(匹配最近的 if)还是 reduce(闭合外层 if)?大多数生成器默认 prefer shift(匹配最近 if),这正好符合编程直觉。
• Reduce/Reduce:同格中两个不同归约冲突。这总是文法问题的信号——语法有真正的歧义,必须改文法或加优先级规则。

yacc/bison 允许给 token 和规则设优先级⁠:%left '+' '-' → 如果 expr + expr 在一个状态中同时面临 shift+和 reduce,优先级决定行为。这比改文法消左递归或消歧义更工程化,但过度使用会让文法语义随优先级设置而微妙变化。

lalrpop:LR 的现代替代

lalrpop 是 Rust 的 LR(1)/LALR(1) parser generator——文法直接写在 Rust 源码中,生成的代码也是 Rust。和 yacc/bison 的核心不同:lalrpop 处理的是参数化文法⁠(带了 Rust 类型的语义动作),而 yacc/bison 处理的是无类型文法⁠(语义动作是 C 代码块)。

lalrpop 文法示例:

Expr: i32 = {
    <l:Expr> "+" <r:Term> => l + r,       ← 右操作数用 Term 类型(自动提升到 Expr)
    Term,
};

Term: i32 = {
    <l:Term> "*" <r:Factor> => l * r,
    Factor,
};

生成的 LR 表嵌入在 Rust 编译时生成的代码中——本质上和 yacc/bison 生成的 C 表是同一套 LALR 算法。lalrpop 中 Term 会自动提升到 Expr(因为 Expr 包含 Term variant)。

LR 分析的错误恢复

LR parser 在遇到错误 token(当前状态下 action 表为空)时要恢复。标准策略:

• panic mode:从栈顶向下 pop 状态,直到找到某个状态对某个 token 有合法的 shift——跳过中间的 token,继续解析。跳过的 token 就是"被错误吞掉的部分"。
• error productions:在文法中显式写 Stmt → error ';',然后 parser 生成器把 error 当作"匹配任何 token 通配"的特殊符号——parser 在错误后"吃垃圾直到遇到同步标记"。

这比 LL 的错误恢复更难做好⁠——LR 不知道当前正在解析哪个语义结构(它在"自底向上",不知道上层期望什么),所以报错信息通常比手写递归下降差。这也是工业编译器偏好 LL 路线的一个重要原因。

选 LL 还是 LR

工业趋势是 LL 手写⁠(错误信息 + 增量) > LR 生成器⁠(新项目越来越少用)。LR 的价值主要在理解已有系统(如 Bash/awk 的 parser、yacc 时代的大量遗留代码)和需要快速构造 DSL parser 的场景。

参考

• Dragon Book: Chapter 4, Sections 4.5–4.7 — LR(0)/SLR/LR(1)/LALR 的完整数学推导
• Knuth (1965): "On the Translation of Languages from Left to Right" — LR 分析的原始论文
• lalrpop: https://github.com/lalrpop/lalrpop — Rust LALR(1) parser generator

Keywords: LR, LR(0), SLR, LR(1), LALR, shift, reduce, shift/reduce conflict, reduce/reduce conflict, item, closure, goto, parse table, yacc, bison, lalrpop, dangling else, precedence, associativity, panic mode, error productions