parsing - 左结合运算符的 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 )

维基百科说:

Several solutions are:

1. rewrite the grammar to be left recursive, or
2. rewrite the grammar with more nonterminals to force the correct precedence/associativity, or
3. if using YACC or Bison, there are operator declarations, %left, %right and %nonassoc, which tell the parser generator which associativity to force.

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

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

此伪代码应识别该样式的左递归语法。