语法中的左递归冲突

在整个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

来源

2009-11-08 Kyle Brandt

你可以发布一个最小的例子，你观察这种效果吗？我不认为它是这样工作的，我的猜测是你的语法有其他问题。即使左递归效率更高，Bison也不应该存在左递归或右递归问题。 – 2009-11-08 18:22:59

@Thomas Padron-McCarthy：已更新为在调试模式下包含Bison的y.output。 – 2009-11-08 18:24:08

编辑：

我要收回我原来的答复。正如我第一次想到的那样，您的左递归语法而不是似乎是模棱两可的。我想我被用来使最终分隔符可选的额外规则困惑。

这是您原来，右递归，语法的简化版本：

list: COMMAND 
     | COMMAND SEPARATOR 
     | COMMAND SEPARATOR list 
     ;

此语法匹配（如果我不是更糊涂了，比我想，这是当然的可能性）的输入C，CS，CSC，CSCS，CSCSC，CSCSCS等。也就是说，一系列SEPARATOR分开的COMMAND，最后有一个可选的SEPARATOR。

这是你的左递归语法，这给移进/归约冲突野牛的简化版本：

list: COMMAND 
     | COMMAND SEPARATOR 
     | list SEPARATOR COMMAND 
     ;

如果我正确地扩大了的事情，该语法中的输入c匹配，CS，CSC ，CSSC，CSCSC，CSSCSC等。它不是含糊不清的，但它不等同于你的左递归语法。 COMMANDS列表最后不能有SEPARATOR，COMMANDS之间的SEPARATOR可以加倍。

我认为转移/减少冲突的原因是，当它决定是否转移或减少时，Bison只会提前看到一个标记，并且在第二个语法中引入双重分隔符时，它有时可能会感到困惑。

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

list: separatedlist 
     | separatedlist SEPARATOR 
     ; 

separatedlist: COMMAND 
       | separatedlist SEPARATOR COMMAND 
       ;

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

来源

2009-11-08 18:34:00

如果是这样的话，我不明白它如何变得模糊不清。这里是整个y.output：http://www.pastebin.org/51936 – 2009-11-08 19:05:45

@凯尔：是的，它并不含糊。我改变了我的答案。但现在这不是一个很好的答案。 – 2009-11-08 19:30:52

我只注意到它与分隔符匹配的事实，这不是我想要的。所以我想我需要正确的递归示例，或者找出如何使用左递归获取第一个示例匹配的内容。 – 2009-11-08 19:35:43

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

list: command 
    | command separator 
    | list separator command

你的右递归的版本是：

list: command 
    | command separator 
    | command separator list

这两个规则集实际上是相当不同的，匹配不同的东西。第一个相匹配的一个或多个命令 s的分离器在它们之间 S，并且每个命令后一个额外的选择隔板。第二种是类似的，除了它只允许在命令之后的额外的可选分隔符之后。

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

list_no_trailer: command 
       | list_no_trailer separator command 

list: list_no_trailer 
    | list_no_trailer separator

在您的版本冲突来自于一个事实，即解析“命令”，看到一个分隔符后在它们看来，它不知道是否将该内容作为可选分隔符放在该命令之后，或者在假设其为列表分隔符并且在其后将存在另一个命令的情况下减少该命令。这将需要2个字符的lookahead，所以你的语法是LR（2），但不是LR（1）

来源

2009-11-08 23:53:12

语法中的左递归冲突

回答

相关问题