Bison实现Pascal语法出现14个shift/reduce冲突的原因与修复方法

问题描述 #

• 基于Bison编写的Pascal语法目前可正常运行，但共产生14个移进/归约（shift/reduce）冲突。
• 此前编写结构高度相似的6502汇编器Bison语法时未出现任何同类冲突，因此对本次冲突的来源存在疑问。
• 所有冲突全部集中在Bison生成的状态51，对应opr规则的NOT subexpr .位置：当解析推进到该位置时，若后续token为各类二元运算符，Bison无法决策应当执行归约操作，还是移进后续的二元运算符。
• 已提供完整语法定义代码、Bison输出的冲突详情报告，需要明确冲突产生的具体原因，以及可彻底消除该类冲突的可行修复方法。

冲突根因 #

这是单目前缀运算符NOT未配置正确优先级导致的典型冲突。之前写的6502汇编语法没出同类问题，本质是6502汇编不存在这类可出现在子表达式后、后方又能直接衔接二元运算符的前缀单目运算，没有触发二义性的语法场景。
当解析走到NOT subexpr .这个状态点时，栈内已经完整匹配了NOT subexpr的规则右部，此时看到后续跟着的二元运算符（比如+、*、AND这类），Bison会同时识别到两个合法的解析路径：

1. 归约路径：把栈里的NOT subexpr归约为opr（即单目NOT的运算结果），将这个结果作为后续二元运算的左操作数，移进二元运算符继续解析，对应语义是(NOT a) + b
2. 移进路径：直接移进后方的二元运算符，把当前的subexpr作为二元运算的左操作数，等二元运算的右操作数解析完成后，再把NOT （二元运算整体结果）归约，对应语义是NOT (a + b)
   如果没有给单目NOT和各个二元运算符明确指定优先级、结合性规则，Bison无法判断哪条路径符合语法设计预期，就会抛出移进/归约冲突。遇到的14个冲突，刚好对应语法里定义的14个可出现在表达式中的二元运算符，和观察到的冲突位置完全吻合。

修复方案 #

两种方案都可以彻底消除这类冲突，按需选择即可：

• 方案1：显式声明单目NOT的优先级（改动最小，推荐）
  Bison的优先级规则是：后声明的token优先级高于先声明的。只需要在优先级声明区块，先按从低到高的顺序列完所有二元运算符的结合性和优先级，最后单独给单目NOT设置最高优先级即可。
  示例配置：

  /* 二元运算符按优先级从低到高声明，%left代表左结合 */
  %left OR
  %left AND
  %left EQ NE LT GT LE GE
  %left PLUS MINUS
  %left MUL DIV MOD
  /* 声明单目NOT的优先级标记，优先级高于上述所有二元运算符 */
  %token NOT
  

  之后在NOT对应的语法规则上显式绑定优先级：

  opr: NOT subexpr %prec NOT { /* 你的语义处理逻辑 */ }
  

  这是Bison处理单目运算符冲突的标准写法，不需要改动现有语法结构，配置完成后冲突会直接消失。
• 方案2：分层定义表达式语法，从结构上消除二义性
  如果不想依赖Bison的优先级声明特性，可以按照运算符优先级从低到高拆分表达式规则，让语法本身不存在二义性，参考结构：

  /* 最低优先级：逻辑或 */
  expr: expr OR and_expr | and_expr
  /* 逻辑与 */
  and_expr: and_expr AND cmp_expr | cmp_expr
  /* 比较运算 */
  cmp_expr: cmp_expr EQ add_expr | cmp_expr NE add_expr | /* 其余比较规则 */ | add_expr
  /* 加减运算 */
  add_expr: add_expr PLUS mul_expr | add_expr MINUS mul_expr | mul_expr
  /* 乘除模运算 */
  mul_expr: mul_expr MUL unary_expr | mul_expr DIV unary_expr | mul_expr MOD unary_expr | unary_expr
  /* 最高优先级：单目运算、原子表达式 */
  unary_expr: NOT unary_expr | atom_expr
  atom_expr: INT_LITERAL | IDENTIFIER | '(' expr ')'
  

  这种写法的语法本身是LALR(1)无冲突的，但是需要重构现有所有表达式相关的规则，改动量比方案1大很多。

注意不要图省事用%expect 14直接压制冲突。Bison默认遇到移进/归约冲突时会选择移进，这种默认行为会把NOT a + b解析为NOT (a + b)，和Pascal标准中单目NOT优先级高于所有二元算术、逻辑运算符的语义要求不符，会生成错误的运算逻辑。

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