利用ANTLR 4的左递归消歧

Question

我想要一个只包含二进制非终端的语法和评估器（ANTLR解析树walker），而不需要在访问表达式节点时切换操作符以确定要执行的操作因为访问者将访问“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建立二叉树对我来说，在哪里（二）每个规则有一个左和右的说法，意思是我不担心，而对克林循环关闭。我真的很喜欢这个
• 我必须在令牌上手动调度（切换），而不是在节点的类型上。

使用更传统的&已经离开-因素语法

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

//... 

解决了我所有的问题--infact第一访问者实施很可能会没有一个单一的if或for声明它，这将是真的很漂亮。

但要保持很长的故事长：

标准多态性技术将让你尝试的开关切换功能到变量您接通。因此，代码

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

成为

operator.doOperationUsing(left, right); 

，然后运营商的各种实现方式会做不同的事情。问题是为操作员生成不同的实现。对于典型的多态，如果你只是使用一个枚举，每个枚举实例定制实现的枚举实际上并不比仅仅切换更好。但在这里，我们可以使用访问过非终端的规则，以生成执行，有拉姆达 :)