How to recursively perform a "tree walk" on an abstract syntax tree?

Question

A simple assignment example in my language:

x = 3 -> 

This is where AST is generated after parsing (In Python):

 [('statement', ('assignment', 'x', ('assignment_operator', '='), ('expr', ('term', ('factor', '3')))), '->')] 

How can I recursively access any possible depth to print all of them in the most trivial case? (Or convert text to something else?). Is there a specific algorithm for this? If so, do you recommend any specific material?

Answer 1

To walk on a tree, simply use the stack or queue (depending on whether you want to first gain depth or exhale first).

For each node encountered, push the children onto the stack or queue, then pop the next element from the data structure for processing and repetition.

For example, the first breath may look like this:

 from collections import deque def walk(node): queue = deque([node]) while queue: node = queue.popleft() if isinstance(node, tuple): queue.extend(node[1:]) # add the children to the queue yield node 

which produces the following walking order for your tree:

 >>> for node in walk(tree[0]): ... print(node[0] if isinstance(node, tuple) else node) ... statement assignment -> x assignment_operator expr = term factor 3 

Your data structure is a bit messy, mixing tuples of different lengths. You may want to use the nametuple class to style the content a bit.