无法解决/理解野牛的简单“转移/减少冲突”

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 -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，它可能为空，也可能不为空。