利用 ANTLR 4 的左递归消歧

Question

我想要一个仅包含二进制非终结符的语法和求值器（ANTLR 解析树遍历器），而无需在访问表达式节点时打开运算符以确定要执行的操作（例如预左因式语法，因为访问者会访问一个 "additionNode" 访问者可以静态地假设它必须做加法 ).

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

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

漂亮，但是任何 walker/visitor/compiler-back-end 现在都必须对类型进行自己的调度，这很糟糕：

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

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

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

这个相应的访问者与上面的两个语法有相反的优点和缺点：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);

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

利用 ANTLR 4 的左递归消歧

Leveraging ANTLR 4's left recursion disambiguation

grammar

parsing

antlr

visitor-pattern

left-recursion