6.3 LR 移入归约与语法树：从栈中的前缀恢复结构
递归下降从开始符号预测下一步。LR 解析器从输入出发，依据状态和前瞻 token 决定何时移入、何时把栈顶的句柄归约为非终结符。仅仅“看起来像某条产生式右侧”还不足以归约；状态表负责确认这个时机。它维护可行前缀，构造最右推导的逆过程。
本课目标
- 解释 shift、reduce、accept 和 error 动作；
- 理解 LR item、closure 与 goto 的用途；
- 区分 shift/reduce 和 reduce/reduce 冲突；
- 选择 CST、AST 或 lossless tree，并保留源码来源。
1. 移入与归约
文法：
E → E + T | T
T → id输入 id + id 的概念过程：
栈 输入 动作
id + id $ shift id
id + id $ reduce T → id
T + id $ reduce E → T
E + id $ shift +
E + id $ shift id
E + id $ reduce T → id
E + T $ reduce E → E + T
E $ accept真实 LR 栈还保存自动机状态，ACTION 表根据“栈顶状态 + lookahead”选择动作，GOTO 表在归约后根据“新栈顶状态 + 左侧非终结符”决定下一状态。
2. LR item 表示产生式进度
item 在产生式右侧放一个点：
E → E · + T表示 E 已识别，下一步期待 + T。若点在非终结符前，closure 要加入以该非终结符为左侧、点在右侧开头的 item，并继续传播；读到一个文法符号后，goto 把点跨过该符号并再次求 closure。
item 集合构成一个 DFA：状态概括“目前识别了哪些文法前缀”。LR(1) item 还携带 lookahead，用于决定完成产生式后在哪些 token 上归约。
SLR 用非终结符的全局 FOLLOW 决定归约前瞻；canonical LR(1) 把具体前瞻放进 item，closure 按后缀与原有前瞻的 FIRST 传播；LALR 通常合并具有相同 LR(0) 核心的状态并合并前瞻。它们的表大小和能处理的文法范围不同。不能把它们都笼统当作同一个“LR”。
3. 两类冲突
Shift/reduce
同一表项既可移入 lookahead，又可归约。经典例子是悬空 else：看到 else 时，可以先归约无 else 的 if，也可以移入并与最近 if 结合。
Reduce/reduce
同一表项可按两条不同产生式归约，表示当前栈内容有两个完成解释。它通常比 shift/reduce 更难通过简单优先级合理解决。
工具常允许声明运算符优先级与结合性来解决表达式冲突。必须检查冲突涉及的具体状态与产生式，不能只确认冲突总数符合预期；用“总是 shift”静默掩盖新冲突，会让语言行为随文法修改意外变化。
4. Bison 风格语义动作
下面是文法与动作片段，不是完整 .y 文件。需要配置 %locations、token 与语义值类型，提供 lexer、yyerror 和 AST 构造函数后才能生成并编译。这里只实现加法和乘法产生式，减法和除法声明为后续扩展保留：
%left '+' '-'
%left '*' '/'
%%
expr:
expr '+' expr { $$ = make_binary($1, PLUS, $3, @$); }
| expr '*' expr { $$ = make_binary($1, STAR, $3, @$); }
| '(' expr ')' { $$ = with_span($2, @$); }
| NUMBER { $$ = make_number($1, @$); }
;$1、$3 是右侧符号语义值，$$ 是左侧结果；Bison 的 @$ 表示整条规则左侧结果的位置，具体位置类型可配置。后声明的优先级更高，所以这里乘法高于加法，%left 决定同级冲突时左结合。语义动作中的分配失败、异常和错误恢复必须遵守生成器运行时的栈清理约定，否则容易泄漏节点。
文法中的优先级声明是紧凑方案，但分层非终结符通常更容易被多种解析器和读者理解。选择应考虑语言规范可读性与工具诊断。
5. CST、AST 与 lossless syntax tree
| 结构 | 通常保留 | 主要用途 |
|---|---|---|
| CST | 文法节点、标点、括号 | 解释解析过程 |
| AST | 语义相关表达式、声明、语句 | 类型检查、IR 生成 |
| lossless tree | 全部 token、空白、注释、错误节点 | 格式化、IDE、重构 |
AST 可以删除括号节点，因为树结构已表达优先级；但若工具要保留用户写法，必须在其他结构中保留括号与 trivia。不存在对所有消费者都最好的唯一语法树。
6. 源位置不应只挂在叶子上
二元表达式节点的 span 通常覆盖左操作数起点到右操作数终点；运算符 token 另有 span。这样可以：
- 报告整个错误表达式；
- 精确强调操作符；
- 在宏展开时追踪 spelling 与 expansion 位置；
- 让优化后的节点仍能回到源结构。
合成节点与缺失 token 需要零长度或 synthetic span。诊断渲染必须识别它，避免产生倒置或越界范围。
7. LR 错误恢复不是天然更差
LR 解析器可使用特殊 error 符号，弹栈到能够移入 error 的状态，再丢弃输入直到同步 token。现代实现也能做局部修复和生成期望 token 集。
LL 与 LR 的诊断质量主要取决于文法、状态信息、恢复算法和人为设计，不能用“LL 好、LR 差”一概而论。LR 状态更难直接映射为用户概念，但也包含精确的可行前缀信息。
8. 如何选择解析路线
- 文法适合预测、团队重视手写控制与定制诊断：递归下降或 Pratt；
- 已有成熟 LR 文法、需要处理左递归和较宽文法类：LR 生成器；
- 需要保留二义或处理自然语言式文法：GLR、Earley 等广义算法；
- 需要优先选择语义：PEG。它不会保留多个候选解析，但第一分支失败后可以回退并尝试下一分支；packrat 的记忆化可避免重复解析。优先选择语义与传统 CFG 不同。
选择解析器之前，应固定语言语义、错误恢复要求、增量能力和工具链生态，不能只比较一张“支持文法更多”的表。
常见误区
- LR 从左到右产生最左推导：它构造最右推导的逆过程。
- 有冲突就说明语言二义：可能是所选 LR 变体状态合并造成，也可能通过更强 lookahead 解决。
- 优先级声明会自动符合语言规范：声明顺序写错会稳定地产生错误语义。
- AST 丢掉标点后所有工具都能复用：源码工具通常需要 lossless tree 或 token 映射。
练习
- 手工完成
id + id的 shift/reduce 轨迹。 - 为
+、*和右结合^写优先级与结合性声明。 - 给悬空 else 文法解释 shift/reduce 两种选择各产生什么树。
- 为编译、格式化和 IDE 三类消费者选择树结构并说明取舍。
小结
LR 解析器把文法前缀编码成状态，在状态栈上执行移入和归约。冲突必须被解释而不是消音，语义动作则把归约结果变成 AST 或其他树结构。无论选择 LL 还是 LR，源码位置和错误恢复都是核心功能，不是后加装饰。
下一章会在树上建立符号与类型关系，再把高层结构降到更适合分析和生成代码的中间表示。