7

对于带有左关联运算符的简单算术表达式，我有以下EBNF语法：

expression:
    term {+ term}
    
term:
    factor {* factor}
    
factor:
    number
    ( expression )

如何在不更改运算符关联性的情况下将其转换为BNF语法？以下 BNF 语法对我不起作用，因为现在运算符已变为右关联：

expression:
    term
    term + expression
    
term:
    factor
    factor * term
    
factor:
    number
    ( expression )

维基百科说：

几种解决方案是：

  1. 将语法重写为左递归，或
  2. 用更多的非终结符重写语法以强制正确的优先级/关联性，或
  3. 如果使用 YACC 或 Bison，则有运算符声明，%left、%right 和 %nonassoc，它们告诉解析器生成器强制执行哪种关联。

但它并没有说如何重写语法，我也没有使用任何解析工具，如 YACC 或 Bison，只是简单的递归下降。我所要求的甚至可能吗？

4

2 回答 2

10 
expression
    : term 
    | expression + term;

就这么简单。当然，您将需要一个具有某种描述的 LR 解析器来识别左递归语法。或者，如果递归下降，识别这样的文法是可能的，但不像右结合文法那么简单。你必须滚动一个小的递归上升解析器来匹配这样的。

Expression ParseExpr() {
    Expression term = ParseTerm();
    while(next_token_is_plus()) {
        consume_token();
        Term next = ParseTerm();
        term = PlusExpression(term, next);
    }
    return term;
}

这个伪代码应该能识别出这种风格的左递归文法。

于 2012-07-11T14:14:25.097 回答
1

Puppy 所暗示的也可以用下面的语法来表达：

expression: term opt_add
opt_add: '+' term opt_add
       | /* empty */

term:  factor opt_mul
opt_mul: '*' factor opt_mul
       | /* emtpty */

factor: number
      | '(' expression ')
于 2016-12-08T16:12:35.870 回答