消除語法的左遞歸

Question

你能幫我解釋一下這個例子嗎？我應該如何做這個大小的左遞歸消除？我知道如何做更簡單的例子。

Expr1  ::= Number 
    | String 
    | `true` 
    | `false` 
    | `undefined`    
    | Expr1 `+` Expr1    
    | Expr1 `-` Expr1    
    | Expr1 `*` Expr1    
    | Expr1 `%` Expr1    
    | Expr1 `<` Expr1    
    | Expr1 `===` Expr1    
    | Ident AfterIdent    
    | `[` Exprs `]`   
    | `[` `for` `(` Ident `of` Expr `)` ArrayCompr Expr `]`    
    | `(` Expr `)` 

這是解決方法嗎？

Expr1  ::= Number ExprB  
    | String ExprB  
    | `true` ExprB  
    | `false` ExprB  
    | `undefined` ExprB      
    | Ident AfterIdent ExprB   
    | `[` Exprs `]`    
    | `[` `for` `(` Ident `of` Expr `)` ArrayCompr Expr `]`    
    | `(` Expr `)` 
ExprB  ::= ϵ 
    | `+` Expr1 ExprB 
    | `-` Expr1 ExprB 
    | `*` Expr1 ExprB 
    | `%` Expr1 ExprB 
    | `<` Expr1 ExprB 
    | `===` Expr1 ExprB 

Answer 1

我學到的訣竅是引入建設性的非終端，以在任何一個地方獲得更少的語法規則。您仍然會在語言中遇到一些固有的惡意擴展，但是您可以在每一步都簡化過程。

Scalar ::= Number | String | `true` | `false` | `undefined` 
Op  ::= '+' | '-' | '*' | '%' | '<' | '===' 
OpExpr ::= Expr1 Op Expr1 
ParenExpr ::= 
     `[` Exprs `]` 
    | `[` `for` `(` Ident `of` Expr `)` ArrayCompr Expr `]` 
    | `(` Expr `)` 

Expr1 ::= 
     Scalar 
    | OpExpr 
    | ParenExpr 
    | Ident AfterIdent 

這裏有兩個主要的增益。一個是如果你正在實現解析器，那麼規則現在更接近處理的家族。您可以對分類減少採取一些共同行動。第二個是你可以簡化你的遞歸消除：你有相同數量的終端開始Expr1，但只有一個規則可以擴展，即OpExpr的定義。

我知道我還沒有完成你的練習，但我希望這有助於你的運動。您可能還想查看運算符優先級語法：它們以優雅的方式處理這些問題，具體取決於您的應用程序。