將EBNF轉換爲BNF的LALR解析器

Question

我知道有幾個帖子的標題類似。大多數鏈接到一個死網站 - 無論如何我有一個更具體的問題。

我試圖將EBNF in the XPath spec轉換成直BNF，這樣我就可以輕鬆創建一個兼容Bison的語法文件。

自從我做完這件事以來已經有一段時間了，我不記得遞歸屬於哪個生產環節。我認爲這是左邊的 - 但是當我們通過Bison生成的解析器運行時，我的「直接」翻譯給了我簡單的XPath表達式的語法錯誤。

所以，如果有人可以幽默我和權衡 - 所以我不追鬼：

在下面的Expr規則：

Expr::=  
    ExprSingle ("," ExprSingle)* 

這是正確的翻譯？ （把左邊的遞歸）：

Expr::= 
    Expr "," ExprSingle 
    | ExprSingle 

Answer 1

這很好....

你可以把遞歸的權利，它應該工作，但是你要讓解析器「做更多的工作「因爲它必須跟蹤遞歸的脊柱，並且這樣做必須使用更多的堆棧位置。