Bison为何优先选择Exp→Exp MINUS Exp而非Exp→MINUS Exp？

先明确你给出的简化文法：

%left MINUS
%%
Exp : Exp MINUS Exp
    | MINUS Exp
    | ID
    ;
%%

问题1：解析a - b时，Bison为何优先选择二元减规则而非一元减？ #

这本质上是不存在二选一冲突的场景，而非规则优先级或顺序的问题。解析a - b的完整流程是：

1. 扫描到a，归约为Exp，此时栈为[Exp]，剩余输入为- b；
2. 当前栈顶是Exp，输入符号是MINUS——此时Bison的状态机中，该状态遇到MINUS的唯一合法动作是移进，因为二元减规则Exp → Exp MINUS Exp需要先匹配Exp MINUS前缀，等待后续的Exp；
3. 扫描到b，归约为Exp，栈变为[Exp, MINUS, Exp]，触发二元减规则的归约。

一元减规则Exp → MINUS Exp的触发条件是MINUS作为当前输入的起始符号（即栈顶没有已匹配的Exp），而这里MINUS前面已经有一个Exp，无法和一元减的Exp组成合法文法规则，因此Bison不会考虑将其作为一元运算符处理。

问题2：调换两条规则顺序仍选择二元减，原因何在？ #

Bison的规则顺序仅在归约/归约冲突时生效——即同一状态下，有两条规则都能完成归约动作，此时才会选择文法中先出现的规则。但在a - b的解析过程中，从未出现过这种冲突：

• 一元减规则需要栈顶为MINUS + Exp，才能触发归约；
• 二元减规则需要栈顶为Exp + MINUS + Exp，才能触发归约。

两者的栈状态完全不同，不存在同时满足归约条件的情况，因此调换规则顺序对解析结果没有影响。

问题3：%left MINUS是否对此决策起作用？若有，具体如何影响？ #

%left MINUS在a - b的解析场景中没有直接作用，它主要影响连续二元减的结合性（比如a - b - c会被解析为(a - b) - c而非a - (b - c)）。

不过需要注意：Bison对同一符号的一元/二元版本有内置优先级规则——一元运算符的优先级默认高于二元版本。但这个规则在a - b中没有触发的机会，因为MINUS前面已经有Exp，只能被当作二元运算符处理。只有在类似- a - b的场景中，一元减的高优先级才会生效：-a会先被归约为Exp，再和-b执行二元减，最终解析为(-a) - b而非-(a - b)。

从状态机角度的详细推导 #

我们可以手动推导Bison生成的核心状态转移，更直观地理解解析过程：

1. 状态0（初始状态）：
   • 遇到ID：移进，进入状态1；
   • 遇到MINUS：移进，进入状态2；
2. 状态1（栈顶为Exp）：
   • 遇到MINUS：移进，进入状态3；（对应二元减的前缀Exp MINUS）
3. 状态2（栈顶为MINUS）：
   • 遇到ID：移进，进入状态1；归约ID为Exp后，栈变为MINUS Exp，触发一元减规则归约；
4. 状态3（栈顶为Exp MINUS）：
   • 遇到ID：移进，进入状态1；归约ID为Exp后，栈变为Exp MINUS Exp，触发二元减规则归约。

解析a - b的路径是：状态0 → 移进a→状态1 → 移进-→状态3 → 移进b→状态1 → 归约b为Exp → 归约二元减规则，全程没有可选择的归约动作，自然只会匹配二元减规则。

内容的提问来源于stack exchange，提问作者Stellaream