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.
Best Answer
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 avisit()
method). The method takes, as an argument, a visitor object. In the implementation of thisaccept()
method, you call avisit()
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 differentvisit_*()
methods). The correct visitor will then be dispatched with the correct Node type as argument.