AST 解释器? [英] AST interpreter?

问题描述

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

I have an AST (abstract syntax tree) and now i want to test my compiler by giving it 2 or more numbers and expect an output with the result of math operations (like a calculator).

我的问题是，构建解释器的最佳方法是什么?AST 节点的访问是递归的，因此在到达树的末尾之前，我不知道存在多少封装计算.但是既然这是一个迭代一个迭代完成的，那么最后怎么才能把所有的操作都做完呢?

My question is, what is the best way to build the interpreter? The visiting of the AST nodes is recursive, so i don't know how many encapsulated calculations exists until i get to the end of the tree. But since this is done iteration by iteration, how can i make all the operations in the end?

谢谢

推荐答案

一旦你有了 AST，解释器就很容易编写代码:

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

What's annoying to do is "goto", because this changes the point of attention of the interpreter. To implement goto or function calls, one has to search the tree for the label or the function declaration, and continue execution there. [ One can speed this up by prescanning the tree and collecting all the label locations/function declarations in a lookup table. This is the first step towards building a compiler.] Even this isn't quite enough; you have to adjust the recursion stack, which we hid in function calls so it isn't easy to do. If one converts this code to a iterative loop with an explicitly managed recursion stack, it is a lot easier to fix up the stack.

这篇关于AST 解释器?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！