複数行のコードの抽象構文ツリーの作成

Question

複数のコード行からASTを作成する際の一般的な慣行は何ですか？たとえば、私は、ある言語から別の言語のコードを変換するトランスレータを書いていたならば、そして私はこのような文のセットに遭遇しました：私は成功し、ここでのコードの個々の行ごとにASTのを作成することができます

x = 2 
f = k->o 
a = 1+2*3 

。さて、翻訳されたコードを生成する必要がありますが、コードがn行長い場合、ASTではなくASTを1つ使用する方が良いでしょうか？もしそうなら、そのASTはどのように形成されますか？

Answer 1

まず、「コードの行」という言葉を考えてはいけません。パーサーへの入力は、トークンのストリームです。あなたdoにはレクサーがありますか？ :-)

ASTが多くのステートメントにまたがっているのは完璧に（そして正常な）です。実際、それは通常、単一の関数やモジュール全体（読み込み：ソースファイル）など、コンパイル単位全体に及ぶでしょう。

たとえば、このプログラムを検討：

fun f(x, y) { 
    z = x + y; 
    if (z > 3) { 
     return z; 
    } else { 
     return g(x); 
    } 
} 

fun g(x) { 
    return x * 2; 
} 

コンパイラは次のようになりますASTを構築する可能性がある（詳細を無視して、一般的な構造に焦点を当ててください）：

ModNode 
    FunNode[Name = "f"] 
    CompoundStmtNode 
     AssignStmtNode 
     VarNode[Name = "z"] 
     BinExprNode[Oper = "+"] 
      VarNode[Name = "x"] 
      VarNode[Name = "y"] 
     IfStmtNode 
     BinExprNode[Oper = ">"] 
      VarNode[Name = "z"] 
      ConstNode[Value = 3] 
     CompoundStmtNode 
      ReturnNode 
      VarNode[Name = "z"] 
     CompoundStmtNode 
      ReturnNode 
      CallNode[Name = "g"] 
       VarNode[Name = "x"] 
    FunNode[Name = "g"] 
    CompoundStmtNode 
     ReturnNode 
     BinExprNode[Oper = "*"] 
      VarNode[Name = "x"] 
      ConstNode[Value = 2] 

ソースファイル全体のASTを構築する利点は、コードに対して複数の論理的なパスを簡単に実行できることです（たとえば、前方参照を解決するため）。もちろん、欠点は、ASTがかなり大きくなることです。

Answer 2

私はあなたが小さなastの1つAstを持っているアドバイスをします。再帰を使用してそれらを通過させます。ツリーのデザインのためにどちらかを選択できます。しかし、各行には右辺を使用し、次のコード行には左辺を使用します。それを引き出す。私はつもりだ

= 1 + 2 * 3

o>があなたがassignNodeとexprNodeを解析する方法を知っているし、ちょうど= K-F

x = 2の

大きな画像を表示すると仮定

これはあなたのためです。

        [AssignNode] 
          left      right 
         [AssignNode]     [x=2] 
       left     right 
      [AssignNode]    [f=k->o] 
    left    right 
    [Null]   a = [ExprNode] 

          [1] + [2*3] 

私はnullになるまで右に移動して行きます。いったんヌルを押すと、ノードに戻り、左に戻ります。

これは小さいアスタリスクで構成されたAstです。新しいNode/Astを押すたびに、同じトラバーサルを行い、次に右に移動します。

私たちに与えること 右に行くx = 2 その後、nullを返し、左に行く。 AssignmoreNode 右折f = k-> o を押してから、ヌル戻ると左へ移動します。 Get AssignNode a = ExprNodeを取得する 右に移動し、ExprNodeを解析して を返し、assignNodeを終了して に戻り、左に進みます。 左がnullです。