How to do a "tree walk" recursively on an Abstract Syntax Tree?

Question

Simple example of assignment in my language:

x = 3 ->

Here's the generated AST after parsing (In Python):

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

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

Answer 1

To walk a tree, just use a stack or a queue (depending on wether you want to go depth first or breath first).

For each node encountered, push the children onto the stack or into the queue, then take the next item out of the data structure to process and repeat.

For example, breath first could 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 little messy, mixing tuples of different length. You may want to look to using a nametuple class to formalise the contents a little.