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

次の 2 つのルールがあることを認識しておく必要があります。

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

と

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

同じ AST を生成しないでください。input が与えられると1+2+3、最初のルールは以下を生成します。

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

ここで、2 番目のルールは以下を生成します。

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

後者の方が理にかなっています。中置式は 2 つの子ノードを持つことが期待されますが、それ以上ではありません。

パーサールールのリテラルを単純に削除して、次のようにしてください。

add : sub (ADD^ sub)*;

ADD : '+';

書き換えルールを使用して同じ AST を作成すると、次のようになります。

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

章 7: The Definitive ANTLR Referenceからのツリー構築も参照してください。特に、サブルール内のルールの書き換え(173 ページ) および書き換えルール内の以前のルール AST の参照(174/175 ページ) の段落。

于 2012-11-16T08:36:25.887 に答える
2

あなたのルール（および他の同様のルール）

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

一連の追加操作がない場合、無駄な生産が生成されます。

私は ANTLR の専門家ではありませんが、2 つのケースが必要だと思います。1 つは単項の add 項用で、もう 1 つは子のセット用です。1 つ目は標準ツリーを生成し、2 つ目は単に新しいノードを作成せずに、子ツリーを親に渡しますか?

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

演算子へのオペランドのシーケンスを使用する他のルールについても、同様の変更が行われます。

于 2012-11-16T05:49:30.833 に答える
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 に答える