Happy：调整产生式顺序消除归约/归约冲突

这问题其实戳中了Happy（Haskell的LR解析器生成器）处理优先级、归约冲突的核心逻辑，咱们一步步拆解明白：

1. 冲突的根源：输入的歧义性 #

你提到的both 7 -3和both 7-3 2的歧义，本质是语法对负号表达式和减法表达式的解析优先级没理清楚。假设你的语法里有类似Expr -> both Expr Expr的产生式，那么：

• 对于both 7 -3，有两种可能的解析方向：
  • 方向1：把-3归约为负号表达式（Expr -> '-' Expr），最终得到both (7) (-3)
  • 方向2：把7 -当成减法的左半部分（等待后续的3），但这里输入到-3就结束了，这时候分析器会陷入困惑——到底该归约负号表达式，还是认为减法不完整？
• 对于both 7-3 2，则应该解析为both (7-3) (2)，但如果优先级没设置对，分析器可能误把-3当成负号，导致解析错误。

这种歧义反映在LR分析器的状态里，就会出现归约/归约冲突：同一个状态下，当前的输入符号（比如后续的结束符或2）同时匹配多个产生式的右部，分析器不知道该选哪个归约。

2. 交换产生式顺序为什么能消除冲突？ #

Happy作为LR(1)解析器，处理归约/归约冲突时遵循一个简单规则：优先选择语法中排在前面的产生式进行归约。

假设你原来的Expr产生式顺序是：

Expr : Expr '-' Expr  -- 减法产生式
     | '-' Expr %prec NEG  -- 负号产生式
     | NUM
     | both Expr Expr

这时候，当分析器遇到可以归约减法或负号的场景时，会优先选择减法产生式，这就和负号的解析需求冲突了——因为负号的优先级应该比减法高，我们需要先把-3当成负号表达式，而不是把7 -当成减法的开头。

交换两个产生式的顺序后：

Expr : '-' Expr %prec NEG  -- 负号产生式排前面
     | Expr '-' Expr  -- 减法产生式
     | NUM
     | both Expr Expr

Happy会优先选择负号产生式进行归约，这就符合我们的语义预期，冲突自然就消失了。

3. %prec NEG的作用：给产生式指定优先级 #

你可能会问：为什么去掉%prec NEG冲突又回来了？这得从Happy的优先级规则说起：

• 默认情况下，每个产生式的优先级由它最后一个终结符决定。比如Expr -> Expr '-' Expr的优先级就是'-'的优先级，通常我们会给'-'设置左结合（%left '-'）。
• 但对于Expr -> '-' Expr这个产生式，它的最后一个符号是非终结符Expr，Happy无法自动推断它的优先级。如果不加%prec NEG，它会继承'-'的优先级，和减法产生式优先级相同。这时候，分析器在遇到歧义场景时，左结合规则会让它倾向于归约减法产生式，再次引发冲突。

而%prec NEG的作用，就是给这个负号产生式手动指定优先级——让它继承NEG这个伪终结符的优先级（我们通常会把NEG的优先级设得比'-'高，比如用%nonassoc NEG放在%left '-'之前）。这样一来，负号产生式的优先级高于减法产生式，分析器会优先归约负号表达式，自然就不会有冲突了。

总结一下 #

• 归约/归约冲突的本质是LR分析器在某个状态下，无法确定该归约哪个产生式；
• Happy默认按产生式的书写顺序解决归约冲突，排在前面的产生式优先被选择；
• %prec指令是为那些无法自动推断优先级的产生式（比如单目运算符）指定优先级，确保它的语义优先级高于对应的双目运算符，避免歧义。

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