How to write the Visitor Pattern for Abstract Syntax Tree in Python?

Question

My collegue suggested me to write a visitor pattern to navigate the AST. Can anyone tell me more how would I start writing it?

As far as I understand, each Node in AST would have visit() method (?) that would somehow get called (from where?). That about concludes my understanding.

To simplify everything, suppose I have nodes Root, Expression, Number, Op and the tree looks like this:

       Root
        |
       Op(+)
      /   \
     /     \
 Number(5)  \
             Op(*)
             /   \
            /     \
           /       \
       Number(2)   Number(444)

Can anyone think of how the visitor pattern would visit this tree to produce output:

 5 + 2 * 444

Thanks, Boda Cydo.

Answer 1

See the docs for ast.NodeVisitor, e.g. a crude possibility might be:

import ast

class MyVisitor(ast.NodeVisitor):
  def visit_BinaryOp(self, node):
    self.visit(node.left)
    print node.op,
    self.visit(node.right)
  def visit_Num(self, node):
    print node.n,

of course this doesn't emit parentheses even where needed, etc, so there's actually more work done, but, it's a start;-).