0

你能帮我举个例子吗？我应该如何用这种大小进行左递归消除？我知道如何做更简单的例子。

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
4

1 回答 1

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

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

于 2015-11-05T01:55:45.120 回答