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 或函数调用，必须在树中搜索标签或函数声明，并在那里继续执行。[可以通过预扫描树并在查找表中收集所有标签位置/函数声明来加快这一速度。这是构建编译器的第一步。] 即使这样还不够；您必须调整递归堆栈，我们将其隐藏在函数调用中，因此这并不容易。如果将此代码转换为具有显式管理的递归堆栈的迭代循环，则修复堆栈会容易得多。