3

在整个 Bison 语法中，我都在使用右递归，并且我读过左递归更好，因为它不必先构建整个堆栈。

但是，当我尝试在其中任何一个上切换到左递归时，我总是会遇到很多冲突，我不明白为什么。

谁能告诉我一个通用示例，说明使用左递归而不是右递归会导致冲突（当右递归不会导致冲突时）。那么在切换到左时需要做什么来纠正这样的冲突。我认为一个基本的例子对我的帮助不仅仅是纠正我自己的语法。

编辑：
但我想无论如何我都应该包含一个特定的示例，因为我的理解还不够完整:-) 将“列表分隔符命令”更改为“命令分隔符列表”可以解决冲突。

State 9 conflicts: 3 shift/reduce


Grammar

    0 $accept: input $end

    1 input: error NEWLINE
    2      | input NEWLINE
    3      | input list NEWLINE
    4      | /* empty */

    5 list: command
    6     | command separator
    7     | list separator command

    8 separator: SEMI
    9          | L_OR
   10          | L_AND

   11 command: variable_assignment
   12        | external_w_redir
   13        | external_w_redir AMP
   14        | pipeline
   15        | pipeline AMP

...

state 9

    5 list: command .
    6     | command . separator

    SEMI   shift, and go to state 18
    L_AND  shift, and go to state 19
    L_OR   shift, and go to state 20

    SEMI      [reduce using rule 5 (list)]
    L_AND     [reduce using rule 5 (list)]
    L_OR      [reduce using rule 5 (list)]
    $default  reduce using rule 5 (list)

    separator  go to state 22
4

2 回答 2

4

编辑：

我不得不收回我原来的答案。正如我首先想到的那样，您的左递归语法似乎并不模棱两可。我想我对用于使最终分隔符可选的额外规则感到困惑。

这是原始右递归语法的简化版本：

list: COMMAND
      | COMMAND SEPARATOR
      | COMMAND SEPARATOR list
      ;

这个语法匹配（如果我没有比我想象的更困惑，这当然是可能的）输入 C、CS、CSC、CSCS、CSCSC、CSCSCS 等。也就是说，一系列分隔符分隔的命令，最后带有一个可选的分隔符。

这是左递归语法的简化版本，它在 Bison 中产生了移位/减少冲突：

list: COMMAND
      | COMMAND SEPARATOR
      | list SEPARATOR COMMAND
      ;

如果我正确扩展了内容，则此语法与输入 C、CS、CSC、CSSC、CSCSC、CSSCSC 等匹配。它不是模棱两可的，但它不等同于您的左递归语法。COMMAND 列表末尾不能有 SEPARATOR，COMMAND 之间的 SEPARATOR 可以加倍。

我认为移位/减少冲突的原因是 Bison 在决定是移位还是减少时只向前看一个标记，并且使用第二种语法中引入的双分隔符，有时会感到困惑。

如果最后一个分隔符是可选的很重要，并且语法必须是左递归的，我建议重写它：

list: separatedlist
      | separatedlist SEPARATOR
      ;

separatedlist: COMMAND
               | separatedlist SEPARATOR COMMAND
               ;

但我不会担心左或右，除非你的列表真的很长，或者你打算在非常有限的硬件上运行你的解析器。在现代台式计算机上，我认为这并不重要。

于 2009-11-08T18:34:00.333 回答
1

混乱/错误似乎来自列表的制作。您的左递归版本是：

list: command
    | command separator
    | list separator command

您正确的递归版本是：

list: command
    | command separator
    | command separator list

这两个规则集实际上是完全不同的，匹配不同的东西。第一个匹配一个或多个command，它们之间有分隔符，每个command后面还有一个可选的额外分隔符。第二个类似，只是它只允许在LAST命令之后使用额外的可选分隔符。

假设你真正想要的是后者的左递归版本，你想要的是

list_no_trailer: command
               | list_no_trailer separator command

list: list_no_trailer
    | list_no_trailer separator

您的版本中的冲突来自这样一个事实，即在解析“命令”并看到前向分隔符后，它不知道是在命令之后将其作为可选分隔符拉入，还是在假设下减少命令它是一个列表分隔符，后面会有另一个命令。它需要 2 个字符的前瞻，所以你的语法是 LR(2)，而不是 LR(1)

于 2009-11-08T23:53:12.007 回答