Shift/reduce yacc 语法冲突

Question

我写了一个语法规则如下：

A : B '?'  
  | B
  | A '+' A
  ;

B : "a"
  | "c" A "t" A
  ;

这让我在

上产生 shift/reduce 冲突

A : B . '?'  (96)
A : B .  (98)

我已经尝试了多种方法来更改语法，但当我尝试更改内容时似乎会产生更多冲突。我怎样才能消除这个冲突？

提前致谢，如有任何帮助，我们将不胜感激。

Answer 1

LALR(1) 解析器使用单字符先行解决它们的冲突。当前瞻无法消除不同操作之间的歧义时，就会向用户显示冲突。

在下面的状态下，一个“？”前瞻意味着解析器可以移动。

A : B . '?'
A : B .

但是如果减少A呢？它可能会减少到以下状态：

B: "c" A "t" A .

其中，通过减少 B，可以直接回到：

A : B . '?'
A : B .

因此，“？”也是一个有效的前瞻性减少。

那你怎么解决这个问题呢？

您有两个选择：

1) 尝试用左递归而不是右递归重写语法。它可能有帮助，但不能保证。

2) 告诉 YACC 在发生冲突时选择哪一个（例如，使用 %left 或 %right）。

或者，也许，使用更智能的解析器。例如 elkhound 或 antlr.

Shift/reduce conflict in yacc grammar