我有一个AST(抽象语法树),现在我想通过给它2个或多个数字来测试我的编译器,并期望输出带有数学运算结果的计算器(例如计算器)。
我的问题是,构建解释器的最佳方法是什么? AST节点的访问是递归的,因此直到到达树的末端之前,我不知道存在多少封装的计算。但是,由于这是一个接一个的迭代完成的,我该如何进行所有操作?
谢谢
最佳答案
一旦拥有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或函数调用,必须在树中搜索标签或函数声明,然后在此处继续执行。 [可以通过预扫描树并在查找表中收集所有标签位置/功能声明来加快此过程。这是构建编译器的第一步。您必须调整递归堆栈,我们将其隐藏在函数调用中,因此不容易做到。如果使用明确管理的递归堆栈将此代码转换为迭代循环,则更容易修复堆栈。
关于interpreter - AST解释器?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10554998/