語法中的左遞歸衝突

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

語法中的左遞歸衝突

回答

相關問題