2

我想要一个仅包含二进制非终结符的语法和评估器（ANTLR parse tree walker），而无需在访问表达式节点以确定要执行的操作时打开运算符（例如左分解语法的情况） ，因为访问者会访问一个“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 中是非法的

4

1 回答 1

2

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

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

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

//...

这解决了我所有的问题——事实上，第一个访问者实现很可能没有一个iforfor语句，这真的很漂亮。

但为了长话短说：

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

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

变成

operator.doOperationUsing(left, right);

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

于 2015-01-09T21:18:15.530 回答