bodacydo bodacydo - 1 year ago 116
Python Question

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

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

method (?) that would somehow get called (from where?). That about concludes my understanding.

To simplify everything, suppose I have nodes
and the tree looks like this:

/ \
/ \
Number(5) \
/ \
/ \
/ \
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 Source

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download