3

我已经看过这个问题，即使问题标题似乎相同；它不能回答我的问题，至少不能以我能理解的任何方式回答。

解析数学

这是我正在解析的内容：

PI -> 3.14.
Number area(Number radius) -> PI * radius^2.

这就是我希望我的 AST 树的外观，减去所有无用的根节点。

它应该是什么样子 http://vertigrated.com/images/How%20I%20want%20the%20tree%20to%20look.png

以下是我希望我的语法的相关片段：

term : '(' expression ')'
     | number -> ^(NUMBER number)
     | (function_invocation)=> function_invocation 
     | ATOM
     | ID
     ;

power : term ('^' term)* -> ^(POWER term (term)* ) ;
unary : ('+'! | '-'^)* power ;
multiply : unary ('*' unary)* -> ^(MULTIPLY unary (unary)* ) ;
divide : multiply ('/' multiply)* -> ^(DIVIDE multiply (multiply)* );
modulo : divide ('%' divide)* -> ^(MODULO divide (divide)*) ;
subtract : modulo ('-' modulo)* -> ^(SUBTRACT modulo (modulo)* ) ;  
add : subtract ('+' subtract)* -> ^(ADDITION subtract (subtract)*) ;

relation : add (('=' | '!=' | '<' | '<=' | '>=' | '>') add)* ;

expression : relation (and_or relation)*
           | string  
           | container_access
           ;
and_or : '&' | '|' ;

优先级

我仍然想保持precedence如下图所示，但如果可能的话，想消除无用的节点。

来源：Number a(x) -> 0 - 1 + 2 * 3 / 4 % 5 ^ 6.

以下是我要消除的节点：

我希望优先级树看起来如何 http://vertigrated.com/images/example%202%20desired%20result.png

基本上我想消除那些没有直接在它们下面有分支的节点中的任何一个到二元期权。

4

4 回答 4

2

你的规则（和其他类似的）

 add : subtract ('+' subtract)* -> ^(ADDITION subtract (subtract)*) ;

当您没有一系列添加操作时，会产生无用的产品。

我不是 ANTLR 专家，但我猜你需要两种情况，一种用于一元的添加项，另一种用于一组子项，第一个生成标准树，第二个简单将子树传递给父节点，而不创建新节点？

add : subtract ( ('+' subtract)+ -> ^(ADDITION subtract (subtract)*) 
               | -> subtract ) ;

具有运算符操作数序列的其他规则的类似更改。

于 2012-11-16T05:49:30.833 回答
2

你必须意识到这两条规则：

add : sub ( ('+' sub)+ -> ^(ADD sub (sub)*) | -> sub ) ;

和

add : sub ('+'^ sub)* ;

不要产生相同的AST。给定输入1+2+3，第一条规则将产生：

  ADD
   |
.--+--.
|  |  |
1  2  3

第二条规则产生：

     (+)
      |
   .--+--.  
   |     |
  (+)    3
   |
.--+--.
|     |
1     2

后者更有意义：中缀表达式应该有 2 个子节点，而不是更多。

为什么不简单地删除解析器规则中的文字并执行以下操作：

add : sub (ADD^ sub)*;

ADD : '+';

使用重写规则创建相同的 AST 如下所示：

add : (sub -> sub) ('+' s=sub -> ^(ADD $add $s))*;

另请参阅第 7 章： The Definitive ANTLR Reference中的树构造。尤其是Rewrite Rules in Subrules (page 173) 和Reference Previous Rule ASTs in Rewrite Rules (page 174/175)。

于 2012-11-16T08:36:25.887 回答
0

尽管我接受 Barts 的答案是正确的，但我还是想用示例代码发布我自己的完整答案，这些示例代码只是为了完整性而工作。

这是我根据巴特的回答所做的：

unary : ('+'! | '-'^)? term ;
pow : (unary -> unary) ('^' s=unary -> ^(POWER $pow $s))*;
mod : (pow -> pow) ('%' s=pow -> ^(MODULO $mod $s))*;
mult : (mod -> mod) ('*' s=mod -> ^(MULTIPLY $mult $s))*;
div : (mult -> mult) ('/' s=mult -> ^(DIVIDE $div $s))*;
sub : (div -> div) ('-' s=div -> ^(SUBTRACT $sub $s))*;
add : (sub -> sub) ('+' s=sub -> ^(ADD $add $s))*;

这是生成的树的样子：

工作答案 http://vertigrated.com/images/working_answer.png

有一种替代解决方案可以不使用重写并将符号本身提升为根，但如果可能的话，我希望树中的所有描述性标签。我只是在谈论如何表示树，以便我的树行走代码尽可能干净！

power : unary ('^'^ unary)* ;
mod : power ('%'^ power)* ;
mult : mod ('*'^ mod)* ;
div : mult ('/'^ mult)* ;
sub : div ('-'^ div)* ;
add : sub ('+'^ sub)* ;

这看起来像这样：

无需重写 http://vertigrated.com/images/without_the_rewrites.png

于 2012-11-16T06:09:55.690 回答
0

要摆脱不相关的节点，只需明确：

 subtract
    :
    modulo
    ( 
       ( '-' modulo)+  -> ^(SUBTRACT modulo+) // no need for parenthesis or asterisk
       |
      () -> modulo
    )
    ;
于 2012-11-16T13:23:40.990 回答