利用ANTLR 4的左递归消歧

Question

我想要一个语法和计算器（ANTLR解析树步行者），它只包含二进制非终端，在访问表达式节点时无需打开运算符来确定要执行的操作（就像左前分解语法的情况一样，因为访问者将访问"additionNode"，访问者可以静态地假设它必须执行加法）。

相当直接的问题。ANTLR支持左递归，所以这是一个有效的语法

expr :
    | expr ('+'|'-') expr
    | expr ('*'|'/') expr
    | '(' expr ')'
    | literal
    ;

漂亮，但是任何为此的步行者/访问者/编译器后端现在都必须对类型进行自己的调度，这很臭：

onVisitExit(ExprContext ctx){
    left = compiledMap.get(ctx.getChild(0));
    right = compiledMap.get(ctx.getChild(2));
    operator = ctx.getChild(1);
    switch(operator.getToken()){
        case "+": compiledMap.put(ctx, left + right);
        case "-": compiledMap.put(ctx, left - right);
        case "*": compiledMap.put(ctx, left * right);
        case "/": compiledMap.put(ctx, left / right);
    }
}

此策略的优缺点：

• antlr 为我构建了一个二叉树，其中（二进制）每个规则都有一个左参数和一个右参数，这意味着我不必担心 while 循环用于 kleene 闭包。我真的很喜欢这个
• 我必须在令牌上手动调度（切换），而不是在节点类型上。

使用更传统且已经左分解的语法

expr                : addOrSub ;
addOrSub            : multOrDiv (('+'/'-') multOrDiv)* ;
multOrDiv           : bracks (('*'/'/') backs)* ;
bracks              : '(' expr ')' | literal ;
literal             : TOKEN ;

与此相关的访问者与上面的 2 种语法具有相反的优缺点：ANTLR 将为我完成对类型的调度 - 大多数情况下，仍然必须区分"+"和"-" - 但现在我必须包含那些 kleene 闭包的 while 循环，因为我不再有严格的二叉树，这很烦人。

我想我理想的语法是这样的

expression : expr ;
fragment expr : 
    (addition | subtraction) 
    | (multiplication | division)
    | brackets
    | literal
    ;
addition        : expr '+' expr ;
subtraction     : expr '-' expr ;
multiplication  : expr '*' expr ;
division        : expr '/' expr ;
brackets        : '(' expr ')' ;
literal         : TOKEN ; 

这将解决我所有的问题，当然，这在ANTLR是非法的

Answer 1

写完这个问题后，它让我在功能上思考了一点

长话短说，我正在使用语法

expr : 
    | expr (plus|minus) expr
    | expr (multi|div) expr
    | '(' expr ')'
    | literal
    ;
plus   : '+' ;
minus  : '-' ;
multi  : '*' ;
div    : '/' ;

这给了我们倾听的访客：

onVisitExit(ExprContext ctx){
    left = values.get(ctx.child(0));
    right = values.get(ctx.child(2));
    operator = binaryOperators.get(ctx.child(1));
    result = operator.doUsing(left, right);
    values.put(ctx, result);
}
onVisitExit(PlusContext ctx){
    binaryOperators.put(ctx, (left, right) -> left + right);
}
onVisitExit(MinusContext ctx){
    binaryOperators.put(ctx, (left, right) -> left - right);
}
//...

这解决了我所有的问题 - 事实上，第一个访问者实现很可能没有一个if或for语句，这将非常漂亮。

但长话短说：

标准的多态技术会让你尝试将开关中的功能推送到你打开的变量中。所以代码

switch(operator.getToken()){
    case "+": do(left + right);
    //...

成为

operator.doOperationUsing(left, right);

然后运算符的各种实现会做不同的事情。问题是为操作员生成不同的影响。对于典型的多态性，如果您只使用枚举，那么每个枚举实例具有自定义实现的枚举实际上并不比仅切换更好。但在这里，我们可以使用访问的非终端规则来生成该实现，并带有 lambda :)