AST解释器？

Question

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

我的问题是，构建解释器的最佳方式是什么？ AST节点的访问是递归的，因此在到达树的末尾之前，我不知道存在多少封装的计算。但是由于这是迭代完成的，我该如何使所有操作在结束时进行？

谢谢

- Nitrate

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

- Ira Baxter

---

如果存在if语句和比较运算符之间，你会怎么做？ - Nitrate

请参见对解释器的补丁，以支持CompareForEqual、Assignment和IfThenElse。 - Ira Baxter

这种递归方法对于解释大型抽象语法树是否好？ - user11747064

这种方法不关心AST有多大，除了查找函数名称和语句标签所需的高效处理（如果AST很大）之外。 - Ira Baxter