左关联运算符的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,只是简单的递归下降.我要求甚至可能吗？

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

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