消除语法的左递归

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的定义。

我知道我还没有完成你的练习，但我希望这有助于你的运动。您可能还想查看运算符优先级语法：它们以优雅的方式处理这些问题，具体取决于您的应用程序。