ANTLR v3 树行者 class。如何评估正确的关联函数，例如 Factorial

Question

我正在尝试使用 ANTLR v3 构建表达式求值器，但我无法获得阶乘函数，因为它是右结合的。这是代码：

class ExpressionParser extends Parser;
options { buildAST=true; }
imaginaryTokenDefinitions :
SIGN_MINUS
SIGN_PLUS;
expr     : LPAREN^ sumExpr RPAREN! ;
sumExpr  : prodExpr ((PLUS^|MINUS^) prodExpr)* ;
prodExpr : powExpr ((MUL^|DIV^|MOD^) powExpr)* ;
powExpr  : runary (POW^ runary)? ;
runary   : unary (FAT)?;
unary    : (SIN^|COS^|TAN^|LOG^|LN^|RAD^)* signExpr;
signExpr : (
     m:MINUS^ {#m.setType(SIGN_MINUS);}
     | p:PLUS^  {#p.setType(SIGN_PLUS);}
     )? atom ;
atom     : NUMBER | expr ;

class ExpressionLexer extends Lexer;

    PLUS  : '+' ;
    MINUS : '-' ;
    MUL   : '*' ;
    DIV   : '/' ;
    MOD   : '%' ;
    POW   : '^' ;
    SIN   : 's' ;
    COS   : 'c' ;
    TAN   : 't' ;
    LOG   : 'l' ;
    LN    : 'n' ;
    RAD   : 'r' ;
    FAT   : 'f' ;
    LPAREN: '(' ;
    RPAREN: ')' ;
    SEMI  : ';' ;
protected DIGIT : '0'..'9' ;
    NUMBER  : (DIGIT)+ ('.' (DIGIT)+)?;

{import java.lang.Math;}
class ExpressionTreeWalker extends TreeParser;
expr returns [double r]
{ double a,b; int i,f=1; r=0; }
 : #(PLUS  a=expr b=expr) { r=a+b; }
| #(MINUS a=expr b=expr) { r=a-b; }
| #(MUL   a=expr b=expr) { r=a*b; }
| #(DIV   a=expr b=expr) { r=a/b; }
| #(MOD   a=expr b=expr) { r=a%b; }
| #(POW   a=expr b=expr) { r=Math.pow(a,b); }
| #(SIN   a=expr       ) { r=Math.sin(a);   }
| #(COS   a=expr       ) { r=Math.cos(a);   }
| #(TAN   a=expr       ) { r=Math.tan(a);   }
| #(LOG   a=expr       ) { r=Math.log10(a); }
| #(LN    a=expr       ) { r=Math.log(a);   }
| #(RAD   a=expr       ) { r=Math.sqrt(a);  }
| #(FAT   a=expr       ) { for(i=1; i<=a; i++){f=f*i;}; r=(double)f;}
| #(LPAREN a=expr)       { r=a; }
| #(SIGN_MINUS a=expr)   { r=-1*a; } 
| #(SIGN_PLUS  a=expr)   { if(a<0)r=0-a; else r=a; }
| d:NUMBER               { r=Double.parseDouble(d.getText()); } ;

如果我在 class TreeWalker 中更改 FAT 匹配大小写，如下所示：

 | #(a=expr    FAT      ) { for(i=1; i<=a; i++){f=f*i;}; r=(double)f;}

我收到以下错误：

 Expression.g:56:7: rule classDef trapped:
 Expression.g:56:7: unexpected token: a
 error: aborting grammar 'ExpressionTreeWalker' due to errors
 Exiting due to errors.

Answer 1

据我所知，你的树行者（原来的那个）很好。

但是，您可能需要在语法中标记FAT：

runary : unary (FAT^)?;

（注意帽子 ^，与所有其他作品一样。）

编辑:

如 Antlr3 wiki 中所述，需要帽子运算符才能使节点成为 "root of subtree created for entire enclosing rule even if nested in a subrule"。在这种情况下，! 运算符嵌套在条件子规则 ((FAT)?) 中。这与运算符是前缀还是后缀无关。

请注意，在您的语法中，! 运算符不是右结合运算符，因为 a!! 根本无效。但我会说结合性只对中缀运算符有意义。

ANTLR v3 树行者 class。如何评估正确的关联函数，例如 Factorial

ANTLR v3 Treewalker class. How to evaluate right associative function such as Factorial

antlr

grammar

factorial