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屋！