3.3 自底向上分析：LR家族
3.3 自底向上分析：LR 家族
本节摘要：自底向上分析从单元流出发，反复"移进或归约"，把产生式右部收缩成左部，直到只剩开始符号。本节用主线语句的简化工法演示移进归约的完整拉锯过程，讲清活前缀与句柄两个关键概念、LR(0)/SLR/LALR/LR(1) 的强弱谱系，以及移进归约冲突如何用优先级裁决——这正是 yacc 的内核机制。
阅读完本节，你应当能够：
- 手工执行一段输入的移进归约序列，标出每步动作
- 解释句柄为什么是"可归约的最短左部"，归约顺序为何是规范（最右）推导的逆
- 比较四种 LR 分析器的状态规模与文法覆盖面
- 说明移进归约冲突的经典场景与裁决办法
移进还是归约：一场拉锯
自底向上的分析器只有两个基本动作。移进：把下一个单元压上栈。归约：栈顶若干元素恰好匹配某产生式右部，把它们弹出、压入左部非终结符。用简化输入 price * qty 走一遍（文法沿用 3.1 节的项层产生式）：
栈内容 剩余输入 动作 （空） price * qty 移进 price price * qty 归约：因子 → ID （因子） * qty 归约：项 → 因子 （项） * qty 移进 * （项 *） qty 移进 qty （项 * qty） 结尾 归约：因子 → ID （项 * 因子） 结尾 归约：项 → 项 MULOP 因子 （项） 结尾 归约：表达式 → 项，接受
每一步的抉择就是"移进还是归约"。栈顶出现 项 * 因子 时恰好能归约，而把 qty 归约成因子前也必须先移进 qty——什么时候停、什么时候收，由分析表说了算，分析表由文法机械计算（LR 项目集规范族）。手工推导整个表超出本节篇幅，但表的行为就是上面那列动作序列，逐行可查。
句柄：归约的合法靶点
自底向上分析绝不能"看见右部就归约"。栈顶若是 表达式 ADDOP 表达式，虽然匹配"表达式 → 表达式 ADDOP 项"的一部分，但此时右侧那个"项"还没归约出来就急着收，会得到错误的树。句柄的定义：栈顶那个"必须最先归约的完整右部"。找句柄的直觉：它对应规范推导（最右推导）逆过程的最先一步。分析表的精巧之处就在于每个状态恰好编码了"此刻句柄可能是什么"，从而归约永远打在正确的靶点上。
图 移进归约：栈的推拉与树的逆生长
LR 谱系：四种分析器排座次
LR(k) 表示"从左到右扫描、最右推导的逆、看 k 个符号"。k 越大能力越强，但状态爆炸。实际流通的四档：
| 型号 | 记 lookahead 的位置 | 状态规模 | 文法覆盖 | 典型用户 |
|---|---|---|---|---|
| LR(0) | 不看 | 小 | 太窄，实用价值低 | 教学 |
| SLR(1) | 归约时查 FOLLOW 集 | 中 | 中等 | 教学与小工具 |
| LALR(1) | 状态合并后仍带各自 lookahead | 中 | 广，工业甜点 | yacc/Bison |
| LR(1) | 每个项目带自己的 lookahead | 巨大 | 最广 | 少数研究编译器 |
LALR 之所以是工业甜点：状态规模与 SLR 相当，能力却接近完整 LR(1)。yacc 的选择逻辑很实际——分析表大小决定编译器前端的内存占用与生成代码体积，LALR 用 SLR 的价格买到接近 LR(1) 的货。代价是文法要过 LALR 检查，冲突要人工裁决。
冲突：文法与表的摩擦点
两类冲突。移进归约冲突：某状态里"移进下一个单元"与"归约栈顶句柄"都可执行。经典例子是 if 语句没有 else 时：
栈：if 条件 then 语句 输入下一个：else 候选 A 归约：语句 → if 条件 then 语句 （else 属于外层） 候选 B 移进：else （else 属于本层） yacc 默认移进 → else 最近匹配
归约归约冲突：两个产生式同时可归约，通常意味着文法设计有歧义或两个非终结符职责重叠。yacc 按先声明的产生式归约并发出警告——警告不该被无视，它是文法在喊疼。
裁决手段按优雅程度排：改文法分层（治本）；声明优先级与结合性（治标快，适合表达式类冲突）；默认规则（移进优先、先声明优先，快但危险，等于把裁决权交给工具的偶然行为）。
⚠️ 常见坑：以为 LR 家族"万能"到能处理一切想当然的文法。二义文法 LR 表必带冲突；即便无二义，LALR 合并状态也可能制造"归约归约冲突"，而完整 LR(1) 没有。从 LR(1) 降到 LALR 不是免费午餐。
💡 关键直觉：自顶向下是"猜结构、再验证"，自底向上是"攒材料、够数就收"。前者像按图纸从骨架搭房子，后者像砌好砖再认出这是面墙。递归下降好写好调，LR 好生成好复用——选型看团队是要"读得懂的代码"还是"写得出的大文法"。
阶段之外的疑问
问：递归下降和 LR 能分析同一份文法吗？ 各有限制。递归下降吃不了左递归（要先消）、对候选式公共前缀要提左因子；LR 系不怕左递归（反而欢迎），但二义文法必带冲突。同一语言常备两份等价文法：给手写递归下降的消除过左递归，给 yacc 的保留左递归形式——文法为分析器服务，不是反过来。
问：为什么说 LR 分析器的归约是最右推导的逆？ 自底向上归约时，总是先归约句柄——它恰好是最右推导中最先被展开的那个位置。把归约序列倒放，就是一次最右推导。这个对应关系不是巧合，是 LR 名字里 R 的本义，也解释了为什么 LR 分析栈与规范推导的现场一一对应。
补一问：分析表到底长什么样？ 一张二维表：行是状态编号，列是终结符与非终结符；终结符列填移进或归约动作，非终结符列填状态跳转。分析循环每步只做一次查表：栈顶状态加当前输入单元，查到什么执行什么。生成器的工作就是从文法算出这张表并检查冲突——yacc 生成的代码骨架里，那张巨大的数组就是它。
本节要点回顾
- 两动作：移进（上栈等更多信息）与归约（句柄收缩、树上长父节点）
- 句柄：栈顶必须最先归约的完整右部，分析表状态编码了它的位置
- 谱系：LR(0) 弱、SLR 用 FOLLOW 省状态、LALR 工业主流、LR(1) 全能但笨重
- 冲突：移进归约看 else 场景，归约归约多半文法有恙；优先级声明是快刀
- 路线对照：递归下降可读可调试，LR 生成器文法兼容强，现代工程两派并存
结构之树已经搭稳。下一节处理现实问题：用户漏写分号、多打括号时，语法层如何检测、报告并恢复。