AST翻译？

Question

我有一个AST（抽象语法树），现在我想通过给它2个或更多数字来测试我的编译器，并期望输出数学运算的结果（如计算器）。

我的问题是，构建解释器的最佳方法是什么？ AST节点的访问是递归的，所以我不知道有多少封装计算存在，直到我到达树的末尾。但是，由于这是通过迭代完成迭代的，所以我怎样才能使所有的操作到最后？

谢谢

Answer 1

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