interpreter - ASTインタープリター？

Question

AST (抽象構文木) があり、2 つ以上の数値を指定してコンパイラをテストし、数学演算 (電卓など) の結果を出力することを期待しています。

私の質問は、インタープリターを構築する最良の方法は何ですか? AST ノードの訪問は再帰的であるため、ツリーの最後に到達するまで、カプセル化された計算がいくつ存在するかわかりません。しかし、これは反復ごとに行われるため、最終的にすべての操作を行うにはどうすればよいですか?

ありがとうございました

Answer 1

AST があれば、インタープリターのコーディングは非常に簡単です。

 int interpret(tree t)
 { /* left to right, top down scan of tree */
   switch (t->nodetype) {
     case NodeTypeInt:
        return t->value;
     case NodeTypeVariable:
        return t->symbtable_entry->value
     case NodeTypeAdd:
        { int leftvalue= interpret(t->leftchild);
          int rightvalue= interpret(t->rightchild);
          return leftvalue+rightvalue;
        }
     case NodeTypeMultiply:
        { int leftvalue= interpret(t->leftchild);
          int rightvalue= interpret(t->rightchild);
          return leftvalue*rightvalue;
        }
     ...
     case NodeTypeStatementSequence: // assuming a right-leaning tree
        { interpret(t->leftchild);
          interpret(t->rightchild);
          return 0;
        }
     case NodeTypeAssignment:
        { int right_value=interpret(t->rightchild);
          assert: t->leftchild->Nodetype==NodeTypeVariable;
          t->leftchild->symbtable_entry->value=right_value;
          return right_value;
        }
     case NodeTypeCompareForEqual:
        { int leftvalue= interpret(t->leftchild);
          int rightvalue= interpret(t->rightchild);
          return leftvalue==rightvalue;
        }
     case NodeTypeIfThenElse
        { int condition=interpret(t->leftchild);
          if (condition) interpret(t->secondchild);
          else intepret(t->thirdchild);
          return 0;
     case NodeTypeWhile
        { int condition;
          while (condition=interpret(t->leftchild))
                interpret(t->rightchild);
          return 0;

     ...
   }
 }

煩わしいのは「goto」です。これにより、通訳者の注意点が変わるからです。goto または関数呼び出しを実装するには、ツリーでラベルまたは関数宣言を検索し、そこで実行を継続する必要があります。[ツリーを事前にスキャンし、すべてのラベルの場所/関数宣言をルックアップ テーブルに収集することで、これを高速化できます。これは、コンパイラを構築するための最初のステップです。] これでも十分ではありません。再帰スタックを調整する必要がありますが、これは関数呼び出しに隠しているため、簡単ではありません。このコードを再帰スタックを明示的に管理する反復ループに変換すると、スタックの修正がはるかに簡単になります。