AST interpreter?

Question

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).

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?

Thank you

Vining

Answer 1

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;

     ...
   }
 }

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.

Circumspect

How would you do if there were if statements and compare operators in-between? – Vining

See patch to interpreter to support CompareForEqual,Assignment,IfThenElse – Circumspect

Is this recursive approach good for interpreting large ast – Jaquez

This approach doesn't care how big the AST is, modulo the time to look up function names and statement labels, which need efficient treatment if the AST is large. – Circumspect