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

Answer 2

Wikipedia has a great overview of how the Visitor pattern works, although the sample implementation that they use is in Java. You can easily port that to Python, though, no?

Basically, you want to implement a mechanism for double dispatch. Each node in your AST would need to implement an accept() method (NOT a visit() method). The method takes, as an argument, a visitor object. In the implementation of this accept() method, you call a visit() method of the visitor object (there will be one for each AST node type; in Java, you'll use parameter overloading, in Python I suppose you can use different visit_*() methods). The correct visitor will then be dispatched with the correct Node type as argument.