LR：移进、归约与项集自动机
自顶向下方法的困难都源于同一件事：它必须在看到证据之前就选定产生式。左递归无解、共享前缀需要额外 lookahead，都是这个「先猜后验」结构的后果。
自底向上反过来：不猜，先把 token 攒起来，等攒出的东西恰好是某条产生式的右部时再归约成左部。这条路线由 Donald Knuth 在 1965 年奠定，是 yacc / bison / LALRPOP 一族的核心。
1 · 移进与归约
驱动器只有两个动作。移进（shift）把当前输入 token 压入栈；归约（reduce）把栈顶若干个符号（恰好是某条产生式的右部）弹出，压入该产生式的左部。栈上最终只剩起始符号时接受。
n+n*n 在分层算术文法下的动作序列如下：
移进 n · 归约 F→n · 归约 T→F · 移进 + · 移进 n · 归约 F→n
· 归约 T→F · 移进 * · 移进 n · 归约 F→n · 归约 T→T*F · 归约 E→E+T
把这串归约倒着读，正是从 出发的最右推导：每步替换当前串中最右边的非终结符。这就是 LR 里那个 R 的含义。
@vega/parsing/lr 的 buildTable，树与计数来自它的 parse；栈动画由树反读出的反向最右推导给出，读数条末项核对反读的移进与归约次数是否与引擎自报的一致。可切换四个等级观察状态数与冲突数的变化。
左递归在此毫无障碍：
意味着「栈上已有一个
，再攒出 + 与
就能归约成新的
」，这是一个循环而非无限递归。图 1-1 里默认的分层算术文法保留了左递归，且树形就是左结合的，不必像 LL 那样先做消左递归变换，也就不必承受那次变换带来的树形改变。
2 · 项集：记住「可能在哪」
难点在于怎么知道「栈顶这段恰好是某条产生式的右部」，以及同一段可能对应多条产生式时怎么选。答案是一个自动机，它的状态记录当前的识别进度。
定义 2.1（LR(0) 项） 一个项是在某条产生式右部插入一个点的形式，如 ，表示「这条产生式的右部已识别到点之前的部分」。一个项集是若干项的集合，表示当前可能同时处在这几条产生式的这几个位置上。
从起始项出发做闭包（点在非终结符之前时，把该非终结符的所有产生式以点在最左的形式加入）与转移（对每个符号推进点），得到的自动机就是 LR 自动机。栈上除符号还并行记录状态编号，「当前该移进还是归约」只需查当前状态与下一个 token 决定。
项集这个结构解释了 LR 比算符优先强在哪里：算符优先分析 一页的关系矩阵只知道「栈顶某段是一个句柄」，而项集直接记着「这是哪条产生式的哪个位置」，归约时因此知道用哪条规则，也就能建树。
3 · 移进-归约与归约-归约
一个状态里若同时可以做两件事，就是冲突。
移进-归约冲突：状态里既有「点在末尾」的项（可以归约）又有「点在终结符之前」的项（可以移进），而 lookahead 落在两者的许可集合里。经典例子是 dangling-else：if a then if b then c else d 里的 else 该属于哪个 if，文法本身没说清。
归约-归约冲突：两个「点在末尾」的项，即栈顶同一段可以归约成两个不同的非终结符，而 lookahead 分不开。
冲突报告能说到多细，是个值得看一眼的实现细节。@vega/parsing/lr 的 Conflict 只有三个字段：状态号、触发的 lookahead、种类。歧义算术在 LR(1) 下报的是 {state: 4, symbol: "+", kind: "shift/reduce"}，止步于「4 号状态见到
+ 时移进与归约撞了」，说不出撞的是哪两条产生式。bison 的 -Wcounterexamples 会进一步给出一个能触发该冲突的具体输入串，那是定位文法缺陷时最有用的东西，也是本实现与工业工具之间差距最明显的一处：状态号要靠图 1-1 的项集面板人工回查才能变成人能读的信息。
警示 · 冲突有两种性质完全不同的成因。一是文法歧义，即同一个串真有多棵树，此时任何等级、任何 lookahead 数量都消不掉冲突，只能改文法或改方法（见 GLR 与 GLL 一页）。二是文法无歧义但当前等级的 lookahead 不够精确，此时换更高等级可能就好了（见
lookahead 的四档精度 一页）。工程上区分两者的办法很直接：把等级依次调到 LR(1)，若冲突仍在，多半是真歧义。bison 默认对移进-归约冲突「偏向移进」并只给一句警告，这个默认刚好让 dangling-else 得到多数语言期望的语义，但也让真正的文法缺陷容易被忽略。
4 · 与自顶向下的分工
| 自顶向下（LL） | 自底向上（LR） | |
|---|---|---|
| 决策时机 | 展开非终结符时就要选定产生式 | 攒够右部才归约，决策被推迟 |
| 左递归 | 无解，须先变换 | 天然支持，且树形保持左结合 |
| 可接受的文法类 | LL(k) ⊊ LR(k) | 严格更大 |
| 表的规模 | 非终结符 × 终结符 | 状态 × 符号，状态数通常大一个量级 |
| 状态数对等级的敏感度 | 不适用 | 分层算术实测：LR(0) / SLR(1) / LALR(1) 均 12 个状态，LR(1) 涨到 22 个 |
| 出错时的可读性 | 栈上就是「还期望什么」，消息自然 | 状态编号对人无意义，消息须额外加工 |
最后一行是 LR 在工业界的主要摩擦点。「syntax error at line 42」这种消息之所以常见，是因为 LR 驱动器出错时手上只有一个状态号；要给出「期望 )」需要反查该状态里所有可移进的符号，而要给出「因为第 30
行的括号没闭合」还需要额外维护结构信息。手写递归下降在这一点上天然占优：它的调用栈本身就是「当前在解析什么」的完整说明。
5 · 参考文献
- Knuth, D. E. (1965). On the translation of languages from left to right. Information and Control, 8(6), 607–639.
- Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools (2nd ed.). Addison-Wesley. §4.5–4.6。