为我的语法消除左递归

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

我知道我还没有为你完成这项练习，但我希望这足以帮助你行动起来。您可能还想检查一下运算符优先语法：根据您的应用程序，它们以优雅的方式处理其中的一些语法。