CODEWITHSUNDEEP
compiler-constructioninterpreterabstract-syntax-tree
sigflup
sigflup

Reputation: 305

Interpreter backend, how do you traverse your abstract syntax tree?

I'm working on an interpreter and have not found a good explanation of how to traverse and abstract syntax tree after semantic analysis. I wondering what the correct way to do it is. I understand that you merge terminals into their parents processing from left to right and repeat this as much as you can.

I have this abstract syntax tree, which may or may not be correct.

ast
(source: theadesilva.com)

What do I do?

merge 34 and 3 into *, then merge 4 and * into +, then merge ident into call and + into call? Is that right? What is a good algorithm to traverse a tree backwards like that?

Upvotes: 1

Views: 1454

Answers (1)

Guy Coder
Guy Coder

Reputation: 24996

I would not have built the AST as you did. I would view print as a function with one argument. So I would build the tree as

print
     \
      +
    /   \
   4     *
       /   \
      3     34

You walk the tree and evaluate the children before you apply the operator/function in the root to the children. There is no rule that says you can only have two children. If you need several you can have several children.

i.e. fun(a,b,c,d)

    fun
  / / \ \
 a b  c  d

or no children

i.e. currentTime()

currentTime

so for your question with my AST it would be

visit                                               
print          need to evaluate right child  
+              left is 4, need to evaluate right  
*              left is 3, right is 34  
               evaluate 3 * 34 and return right = 102  
               evaluate 4 + 102 and return right = 106  
               evaluate print, so print 106

Upvotes: 1

Related Questions