AST translator?

Question

I have an AST (abstract syntax tree), and now I want to test my compiler by giving it 2 or more numbers and waiting for output with the result of mathematical operations (for example, a calculator).

My question is: what is the best way to build an interpreter? Visiting AST nodes is recursive, so I don’t know how many encapsulated computations exist until I get to the end of the tree. But since this is done by iterating over iteration, how can I do all the operations at the end?

thanks

Answer 1

Intepreters are pretty easy to code as soon as you have 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; ... } } 

What needs to be done is "goto" because it changes the point of view of the translator. To implement goto or function calls, you need to search the tree for the label or function declaration and continue execution there. [You can speed this up by pre-scanning the tree and collecting all the shortcuts / function declarations in the lookup table. This is the first step to creating a compiler.] Even this is not enough; you need to set up a recursion stack that we hide in function calls, so this is not easy to do. If one converts this code into an iterative loop with an explicitly controlled recursion stack, it is much easier to fix the stack.