Yacc语法中Shift/Reduce冲突的解决方法求助

咱们先拆解一下你遇到的冲突根源：当解析器匹配完B之后，如果接下来看到?，它会陷入两难——到底是把当前的B直接归约成A（用规则A : B），还是先移进?，再把B ?归约成A（用规则A : B '?'）。这种歧义就是Shift/Reduce冲突的核心原因。

下面给你两种靠谱的解决办法，你可以根据自己的需求选：

方案一：纯语法重构（不依赖解析器工具特性） #

通过新增一个非终结符，把带?的B变体单独封装，从根源上消除歧义。修改后的语法如下：

A : A '+' B_with_opt | B_with_opt
B_with_opt : B '?' | B
B : "a" | "c" A "t" A

为什么这能解决冲突？ #

原来的冲突是因为A的两个规则都以B开头，导致解析器无法判断后续的?属于哪个规则。现在我们把“带可选?的B”做成一个独立的B_with_opt，解析器匹配完B后：

• 如果看到?，就会先移进?，再归约成B_with_opt；
• 如果没看到?，直接归约成B_with_opt；
  之后再把B_with_opt参与A的组合（包括+连接的情况）。这样就彻底消除了歧义，不会再有Shift/Reduce冲突。

另外，A的规则用了左递归（A : A '+' B_with_opt），这符合大多数表达式的左结合逻辑（比如a + b + c会被解析成(a + b) + c），也能避免右递归可能带来的栈溢出问题。

方案二：利用解析器的优先级设置（适合YACC/Bison等工具） #

如果你用的是YACC、Bison这类支持优先级声明的解析器工具，可以直接给?设置更高的优先级，让解析器优先选择移进?而非归约B为A。示例代码如下：

%token A_LIT C_LIT T_LIT QUESTION PLUS
%left PLUS       // 声明+的左结合性，优先级低于?
%right QUESTION  // 给?设置更高优先级，让解析器优先移进它

%%
A : A PLUS A
  | B QUESTION
  | B
  ;
B : A_LIT        // 这里用A_LIT代替"a"，对应词法分析的token
  | C_LIT A T_LIT A
  ;
%%

原理说明 #

通过%right QUESTION告诉解析器：当遇到?时，优先级比归约A : B更高，所以会优先移进?，再执行A : B '?'的归约，自然就解决了冲突。这种方式不需要修改语法结构，适合不想重构语法的场景。

你可以先试试方案一，它更通用，不依赖特定工具的特性；如果是用Bison这类工具，方案二会更简洁。

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