左结合运算符的BNF语法

Question

我有一个针对简单算术表达式的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 这样的解析工具，只使用简单的递归下降。我所询问的是否可能？

- fredoverflow

Answer 1

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;
}

这个伪代码应该能够识别那种左递归语法。

- Puppy

---

最后一行会使我的递归下降解析器进入无限递归。 - fredoverflow

正如我所说，您必须使用LR解析器（或递归上升）来识别左递归语法。 - Puppy

Answer 2

小狗所建议的也可以用以下语法表达：

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

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

factor: number
      | '(' expression ')

- Branco Medeiros

---

这样移除左递归会使操作符变为右结合。 - Indrajit Banerjee