6.1 移进-归约（shift-reduce）分析
自顶向下语法分析器（parser）从开始符号预测展开；自底向上语法分析器从输入词法单元（token）出发，反复识别某条产生式右部并把它归约为左部。被当前归约的右部叫句柄（handle）。对 E -> E + E | id，id + id 可反向最右推导：id + id => E + id => E + E => E。真正困难不是“看到 id 就归约”，而是判断何时归约一定安全；LR 状态（state）正是这种有限记忆。
栈、ACTION 与 GOTO
LR 语法分析器维护输入光标（cursor）与交错存放文法（grammar）符号/状态的栈。ACTION[state, lookahead] 只有四种结果：shift s 消费向前看（lookahead）符号并压入 s；reduce A -> beta 弹出 beta 对应的符号和状态，再查 GOTO[newTop,A]；accept 在增广开始规则和 EOF 时接受；error 表示无合法延续。归约不消费输入，因此一次移进（shift）后可能连续归约多次。
一个具体的分析表
抽象描述不如一张真实的表直观。把上面四种动作放到最小文法 E -> E + T | T、T -> id 上，构造出的 LR 分析表如下（状态用数字表示，s5 表示移进并进入状态 5，r(A->β) 表示按该产生式归约，acc 表示接受，空白表示错误）：
| state | id | + | $ | E | T |
|---|---|---|---|---|---|
| 0 | s5 | 1 | 2 | ||
| 1 | s3 | acc | |||
| 2 | r(E->T) | r(E->T) | |||
| 3 | s5 | 4 | |||
| 4 | r(E->E+T) | r(E->E+T) | |||
| 5 | r(T->id) | r(T->id) |
右侧两列（E、T）是 GOTO：归约出一个非终结符（nonterminal）后，用栈顶剩下的状态查这两列决定进入哪个状态。这张表完全决定了语法分析器的每一步，语法分析器本身不再需要回头看历史输入。
用这张表分析 id + id
用上表跟踪 id + id，把状态写在符号旁边，可以看到栈如何随动作增减：
| 步骤 | 栈 | 剩余输入 | 动作 |
|---|---|---|---|
| 1 | 0 | id + id $ | 移进 id |
| 2 | 0 id 5 | + id $ | 归约 T -> id |
| 3 | 0 T 2 | + id $ | 归约 E -> T |
| 4 | 0 E 1 | + id $ | 移进 + |
| 5 | 0 E 1 + 3 | id $ | 移进 id |
| 6 | 0 E 1 + 3 id 5 | $ | 归约 T -> id |
| 7 | 0 E 1 + 3 T 4 | $ | 归约 E -> E + T |
| 8 | 0 E 1 | $ | 接受 |
注意第 2-3 步连续两次归约而中间没有移进：id 先归约成 T，T 又立刻归约成 E。这正是“归约不消费输入”的体现——一个完成的内层短语会立刻让外层短语也变得完整。第 6 行的栈最长，对应识别 E + id 的中间状态；归约 E -> E + T 后，栈一次性缩短回 0 E 1。
句柄不是任意匹配后缀
句柄是反向最右推导中下一步应归约的片段，不是任意像产生式右部的子串。id * id + id 中某个 id 虽匹配 Factor -> id，当前向前看符号与上下文仍决定是否可以归约。栈保存的是可行前缀（viable prefix）：它不越过下一句柄的有效右句型前缀。单纯扫描后缀无法处理优先级、悬空 else（dangling else）或共享后缀。
shift 表示“再读一个词法单元，保留可能性”；reduce 表示“此栈后缀已确定是一个短语”；goto 表示“在此上下文识别该短语后进入的状态”。
归约同时运行语义动作（semantic action），将右部词法单元/节点值组装成抽象语法树（AST）。左递归 Expr -> Expr + Term | Term 对递归下降危险，却天然表达了左结合的归约顺序。自底向上语法分析器更强，但代价是表与状态机的工程复杂度。
自顶向下与自底向上对比
两类方法常被并列比较。下表把关键差异放在一起：
| 维度 | 自顶向下（LL / 递归下降） | 自底向上（LR / 移进-归约） |
|---|---|---|
| 出发点 | 从开始符号预测展开 | 从输入词法单元归约回开始符号 |
| 决策时机 | 看到左部就要预测整条规则 | 看到完整句柄才归约 |
| 左递归 | 必须先消除 | 天然支持 |
| 可接受的文法 | LL(1) 等较小的类 | LR(1)/LALR 等更大的类 |
| 典型实现 | 易手写、控制流清晰 | 多用生成器（generator）、表驱动 |
一个直观的判据：自顶向下在“话还没说完”时就得押注是哪条规则，因此对前缀共享和左递归敏感；自底向上则一直累积，直到栈顶凑出一个完整短语才行动，所以能自然处理左结合，代价是需要构造状态机和分析表。
手工走一遍最小跟踪（trace）
用 E -> E + T | T、T -> id 分析 id + id EOF。先移进第一个 id，归约为 T，再归约为 E；移进 +，移进第二个 id，归约为 T，最后把 E + T 归约为 E。语法分析器没有猜树形；每次归约都是把栈顶已完成短语替换为它所属的文法范畴。
真实栈可能写成 0 id 5，其中 0/5 是 LR 状态。按 T -> id 归约时，同时弹出 id 与状态 5；剩余状态查 GOTO(0,T)。符号旁的状态让同一个 T 在不同上下文拥有不同的后续动作。
跟踪检查
- 移进必须恰好消费一个词法单元。
- 归约不消费输入，且除 epsilon 规则外应缩短栈。
- 弹出的数量是 RHS 的符号数，不是词法单元名字的字符数。
- 接受同时要求增广开始规则和 EOF，不能忽略尾随词法单元。