6.4 移进-归约(shift-reduce)与归约-归约(reduce-reduce)冲突
分析表冲突(conflict)证明当前文法和构造方法无法在某个单元格选择唯一动作。它不是应被静默压掉的警告,而是二义性、向前看(lookahead)不足、状态(state)合并损失或语言规则未写清的证据。
两类冲突的性质差别很大,下表先列出对照:
| 类型 | 竞争双方 | 常见根因 | 是否有合理默认 | 典型修复 |
|---|---|---|---|---|
| 移进-归约 | 移进向前看 vs 归约完成式 | 优先级/结合性未定、悬空 else | 常有(先定语言含义后编码) | 分层文法、优先级声明(precedence declaration) |
| 归约-归约 | 两条完成产生式 | 同位置真实二义、文法重叠 | 几乎没有 | 重构语法、加关键字/分隔符、移到语义分析 |
记住:移进-归约多半是“还没声明优先级”,归约-归约往往是“语法本身没说清”,后者更需要结构性改动。
移进-归约:继续读还是立即完成?
Expr -> Expr + Expr | Expr * Expr | NUMBER 在 NUMBER + NUMBER 后看见 * 时产生移进-归约冲突:立即归约得到 (a+b)*c,移进则得到 a+(b*c)。语言必须规定 * 优先级更高,可通过分层文法、生成器(generator)优先级声明或专用表达式语法分析器(parser)实现。悬空 else 通常规定移进 else,使其配对最近的未匹配 if;这条规则也应明确写出。
归约-归约:两个完整故事竞争
归约-归约表示两条完成产生式都要求在同一向前看符号上归约,通常比优先级更危险。不要依赖“文件里第一条规则获胜”;规则排序会悄悄改变语言。修复可能是重构语法、加入关键字/分隔符、把上下文区别移到语义分析,或选支持真实二义性的策略。
每份冲突案例文件应保存状态、向前看符号、竞争动作、最短见证、原因与明确决议;CI 也应监测意外新增的冲突。
先决定语言含义,再编码
a-b-c 要么是 (a-b)-c(左结合),要么是 a-(b-c)(右结合)。移进-归约偏好只有在先确定源语言含义后才可能正确。分层文法如 Sum -> Sum - Product | Product 可直接表达左结合,同时让 Product 保护更高的乘法优先级。用生成器声明也可以,但测试必须检查 AST 形状,不能只检查警告消失。
若 Type -> IDENT 与 Name -> IDENT 在同一位置都可归约,优先级无法解释用户想要哪个含义。可能需要关键字、分隔符、后续语义规则或更强语法分析器;“第一条规则获胜”只是偶然稳定。
冲突分诊
1. 找到最短见证词法单元序列。
2. 画两种树/动作。
3. 写清语言承诺哪一种。
4. 在文法/声明/代码中编码,并以见证回归测试。