Reduce-Reduce冲突及消除给定Yacc文件中该冲突的方法

简单来说，在LR语法分析器工作时，它会维护一个符号栈，一边读输入一边决定是“移进”（把当前输入符号压栈）还是“归约”（把栈顶的一串符号替换成某个非终结符）。Reduce-Reduce冲突就是在某个状态下，分析器发现有两个甚至更多不同的产生式都可以用来归约当前栈顶的符号序列——这时候它就犯难了，不知道该选哪个产生式，直接导致语法分析失败。

举个接地气的例子：假设你有两个规则，水果 → 苹果和零食 → 苹果，当分析器读到“苹果”的时候，如果上下文既允许出现水果又允许出现零食，它就不知道该把“苹果”归成水果还是零食，这就是典型的Reduce-Reduce冲突。

先看你给出的代码片段：你定义了MATH_EXPRESSION（数学表达式）和LOGICAL_EXPRESSION（逻辑表达式）两个独立的非终结符，冲突大概率出现在两者的产生式存在重叠的可归约场景——比如当栈顶是OPERAND（操作数）时，分析器不知道该把它归约成MATH_EXPRESSION还是LOGICAL_EXPRESSION，或者当某个子结构同时符合两个非终结符的规则时。

下面是几种靠谱的解决方法：

1. 统一顶层表达式（最推荐） #

把数学和逻辑表达式合并到一个顶层的EXPRESSION非终结符下，通过Yacc的优先级声明明确运算顺序，彻底消除歧义。这样分析器就能根据优先级和结合性正确判断该移进还是归约，不会再纠结归约到哪个非终结符。

修改后的代码示例：

%token OPERAND PLUS MINUS MULTIPLY DIVIDE REMAINDER POWER BRACKET_OPEN BRACKET_CLOSE LOGICAL_AND LOGICAL_OR

// 按优先级从低到高排列，%left表示左结合，%right表示右结合
%left LOGICAL_OR
%left LOGICAL_AND
%left PLUS MINUS
%left MULTIPLY DIVIDE REMAINDER
%right POWER
%right UMINUS  // 给负号单独设置优先级

%%
EXPRESSION : EXPRESSION LOGICAL_OR EXPRESSION
           | EXPRESSION LOGICAL_AND EXPRESSION
           | EXPRESSION PLUS EXPRESSION
           | EXPRESSION MINUS EXPRESSION
           | EXPRESSION MULTIPLY EXPRESSION
           | EXPRESSION DIVIDE EXPRESSION
           | EXPRESSION REMAINDER EXPRESSION
           | EXPRESSION POWER EXPRESSION
           | MINUS EXPRESSION %prec UMINUS  // 引用UMINUS的优先级
           | BRACKET_OPEN EXPRESSION BRACKET_CLOSE
           | OPERAND
           ;

2. 严格区分上下文 #

如果必须保留两个独立的非终结符，那就要确保它们出现的场景完全不重叠：

• 规定MATH_EXPRESSION只能出现在赋值语句右侧（比如VAR = MATH_EXPRESSION）
• 规定LOGICAL_EXPRESSION只能出现在条件判断中（比如IF LOGICAL_EXPRESSION THEN ...）

这样分析器在不同的上下文里，只会考虑对应的非终结符，自然就不会有冲突了。

3. 提取公共子结构 #

如果两个表达式有公共的子规则（比如都包含OPERAND或括号表达式），可以把这些公共部分抽成一个单独的非终结符，避免重复定义带来的歧义：

// 公共原子表达式
ATOM_EXPRESSION : OPERAND
                | BRACKET_OPEN EXPRESSION BRACKET_CLOSE
                ;

MATH_EXPRESSION : MATH_EXPRESSION PLUS MATH_EXPRESSION
                | MINUS MATH_EXPRESSION %prec UMINUS
                // 其他数学运算规则...
                | ATOM_EXPRESSION
                ;

LOGICAL_EXPRESSION : LOGICAL_EXPRESSION LOGICAL_AND LOGICAL_EXPRESSION
                // 其他逻辑运算规则...
                | ATOM_EXPRESSION
                ;

不过这种方法还是要配合上下文区分使用，否则在通用场景下还是可能出现冲突，所以优先推荐第一种方法。

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