无法 fix/understand 一个简单的 "shift/reduce conflict" 野牛

Question

我正在尝试消除 Bison 语法文件中的所有冲突。我无法理解有几个实例的冲突来源。我缩小了问题的范围并创建了这个小的 Bison 文件来准确说明原始文件中出现的问题：

注意：自首次发布以来代码已更改。

  %token terminalA terminalB
  %token INTEGER
  %%
  START : startEntries
  startEntries:  terminalBLine
                 terminalALines //Optional
                 {
                 }
  terminalALines : terminalALine
                   | terminalALines terminalALine
                   | //To allow terminalALine to be not present at all.
  terminalALine :  terminalA INTEGER
  terminalBLine :  terminalB INTEGER
  %%

~
运行 bison 文件输出：

      bison -v -y test.y
      test.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]

是的，我知道用于查看冲突的 -v 选项。 .output 文件中的相关部分是：

State 4
2 startEntries: terminalBLine . terminalALines
terminalA  shift, and go to state 7
terminalA  [reduce using rule 5 (terminalALines)]
$default   reduce using rule 5 (terminalALines)
terminalALines  go to state 8
terminalALine   go to state 9

如果我删除带有独奏“|”的注释行那么冲突就解决了。但是没有 terminalALines 也是有效的输入，我相信如果我删除“|”将不可能线。 如果我将注释行移动到 "terminalALine : terminalA INTEGER" 之后的行，它应该有相同的目的（？）但会导致更多的冲突。

我删除了所有错误处理和操作语句以专注于核心问题。

我在发布问题后意识到前缀 "terminal" 没有语义含义。

Answer 1

让我们关注规则：

terminalALines : terminalALine
                   | terminalALines terminalALine
                   | //To allow terminalALine to be not present at all.
terminalALine :  terminalA INTEGER

假设我的输入是 terminalA INTEGER.

terminalALines 允许递归 terminalALines。此外，terminalALines 可以为空。所以让我们从解析一个空的 terminalALines 开始，然后递归。现在，terminalALines 可以以 terminalALines 开头，它可以是空的，所以...

错误或多或少是说，如果它试图解析 terminalALines 并看到 terminalA 标记，它无法决定是否递归 运行 terminalALines 再次规则或从中解析单个 terminalALine。

您可以通过重新安排规则使递归大小写为 second

来解决此问题

terminalALines : terminalALine terminalALines
                   | // empty
terminalALine :  terminalA INTEGER

现在如果你看到 terminalA，事情就很清楚了：你必须解析出一个 terminalALine，然后寻找另一个 terminalALines，它可能为空也可能不为空。