手寫自頂向下解析器

我遇到了寫這個自頂向下解析器的答案：Is there an alternative for flex/bison that is usable on 8-bit embedded systems?但我對幾點感到困惑。手寫自頂向下解析器

說我有這個語法：

Expr = Id | Id '(' Expr ')' 
Stmt = Id '=' Expr | Expr

我不知道，如果它是絕對必要的，但我想我們可以左鍵因素語法：

Expr = Id ExprRest 
ExprRest = ϵ | '(' Expr ')' 
Stmt = Id '=' Expr ';' | Expr ';'

究竟是如何將我寫的代碼正確解析foo(x);作爲Stmt？如果我們寫像Stmt解析代碼：

func ParseStmt() { 
    if ParseId() { 
    return ParseTerminal('=') && ParseExpr() && ParseTerminal(';'); 
    } else { 
    return ParseExpr() && ParseTerminal(';'); 
    } 
}

我們將看到Idfoo，假設我們是在第一種情況下，再失敗，因爲我們無法找到=以下foo。

這個語法不是LL（1）嗎？

來源

2013-09-26 Alec

該語法不是LL(1)，因爲LL(1)語法只需要解析堆棧和先行令牌即可確定要擴展哪個生產。使用空解析堆棧時，如果給出Id預讀標記，則無法分辨使用哪兩個Stmt製作。你可以留下它，但它變得煩人。

由bison創建的可執行文件雖然佔用了很多C行，但實際上非常緊湊。由bison編譯的語法生成了1559行C語言，但是編譯成了一個4K的目標文件，其中（我相信）僅略大於1K對應於實際的代碼和數據。（當然，這沒有任何行動。）

如果你真的想爲表達式語法手動編寫一個解析器，我建議你使用自下而上的'Shunting Yard'算法或自頂向下的'普拉特語法分析器「（這兩種語法都可以通過Google進行搜索），它比處理嚴格的LL語法更能處理運算符的優先級。但是你可能會發現野牛生成的語法具有相當的大小和速度，並且具有更好的可讀性和可維護性。（或者你可能沒有，口味不同）

來源

2013-09-26 17:01:17 rici

你的問題是ID（xxx）可能出現在語句和表達式上下文中。

正如其他答案所說，你必須考慮更多因素。這並不難。寫你的語法是這樣的：

Stmt = Id ('=' Expr ';' | 
      RestOfExpression); 

RestOfExpression = '(' Expr ')' | 
        ϵ); 
Expr = Id RestOfExpression;

的代碼應該是顯而易見的。

來源

2013-09-26 18:58:12

手寫自頂向下解析器

回答

相關問題