パーズツリーをASTに変換する

Question

質問をまず入れておきます。この特定の文法を実装しているパーズツリーをASTに変換することは簡単ですか？

私はパースツリー構築するために、この文法を与えられました。この特定のたとえば

literal := INTEGER | FLOAT | TRUE | FALSE . 

designator := IDENTIFIER { "[" expression0 "]" } . 

op0 := ">=" | "<=" | "!=" | "==" | ">" | "<" . 
op1 := "+" | "-" | "or" . 
op2 := "*" | "/" | "and" . 

expression0 := expression1 [ op0 expression1 ] . 
expression1 := expression2 { op1 expression2 } . 
expression2 := expression3 { op2 expression3 } . 
expression3 := "not" expression3 
     | "(" expression0 ")" 
     | designator 
     | call-expression 
     | literal . 

を：

func main() : void { 
    let a = 1 + 2 + 3 + 4; 
} 

私のパーサは、このような

としてパースツリー（の一部）が生成されます

  EXPRESSION1 
       EXPRESSION2 
        EXPRESSION3 
        LITERAL 
         INTEGER(1)(lineNum:2, charPos:10) 
       OP1 
        ADD(lineNum:2, charPos:12) 
       EXPRESSION2 
        EXPRESSION3 
        LITERAL 
         INTEGER(2)(lineNum:2, charPos:14) 
       OP1 
        ADD(lineNum:2, charPos:16) 
       EXPRESSION2 
        EXPRESSION3 
        LITERAL 
         INTEGER(3)(lineNum:2, charPos:18) 
       OP1 
        ADD(lineNum:2, charPos:20) 
       EXPRESSION2 
        EXPRESSION3 
        LITERAL 
         INTEGER(4)(lineNum:2, charPos:22) 

EXPRESSION1の下のこれらのツリーブランチがどのようになって行くかに気をつけてください：

EXPRESSION2 + EXPRESSION2 + EXPRESSION2 + EXPRESSION2 

演算子+は2つのオペランドに対応しません。ですから、AST変換では、単に非終端記号EXPRESSION1を置き換えるために演算子をプルアップするだけで3アドレスのIRコード生成を支援するASTを得ることはできません。

この目標を達成するために、私は、この言語のために書かれているだろう文法は2式の下の枝だけ

EXPRESSION1 + EXPRESSION2 

しかし、この文法ではありませんされ、この代わりに

expression1 := expression2 | expression1 + expression2 (1) 
expression2 := expression3 | expression2 * expression3 (2) 
expression3 := literal         (3) 

のようになります| FIRST（式2）以降のLL（1）| = | {リテラル、+} | > 1

（1）このパースツリーを変換するには、最もエレガントで些細な方法は何でしょうか？ （2）は、私がASTをコーディングし始めたはずのこの文法のための時間の完全な無駄な構文解析ツリーの構築です。

Answer 1

私はあなたのようなASTを作成したいと考えている：

 ADD 
    /\ 
    1 ADD 
     /\ 
     2 ADD 
     /\ 
      3 4 

しかし、おそらくあなたのパースツリーが実際にグループの演算子と単一パスでそのオペランドに簡単な出発点を表すないフラットなリストであることに気づきました。とにかく、より高度なパーサーをコーディングし、ツリー構造を認識し、文法の縮小を適用することは簡単な作業ではありません。

これを行う前に、yaccやANTLRのような既存のパーサジェネレータを検討することをお勧めします。おそらく、文法を書き換えて、反復ユーティリティとして扱うのではなく、演算子を中心としたルールを作成する必要があります。モダンジェネレータ（ANTLRのような）がより大きな先読み、述語などを持つLL（k）文法を扱い、そのタイプのバイパス問題を処理できるように、古典的なLL（1）でない文法は大きな問題ではないかもしれません。

まだコードを主張しているのであれば、式を収集するとスタックを使用してシンボルを保存し、ASTノードに変換することを手動で考えますが、やはり単純な作業ではありません。