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或函数调用，必须在树中搜索标签或函数声明，然后在此处继续执行。 [可以通过预扫描树并在查找表中收集所有标签位置/功能声明来加快此过程。这是构建编译器的第一步。您必须调整递归堆栈，我们将其隐藏在函数调用中，因此不容易做到。如果使用明确管理的递归堆栈将此代码转换为迭代循环，则更容易修复堆栈。