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

Posted by bodacydo on Stack Overflow See other posts from Stack Overflow or by bodacydo
Published on 2010-03-26T18:14:07Z Indexed on 2010/03/26 18:23 UTC
Read the original article Hit count: 520

Filed under:

abstract-syntax-tree

|

parsing

|

visitor-pattern

|

compiler

|

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

© Stack Overflow or respective owner

Related posts about abstract-syntax-tree

How exactly is an Abstract Syntax Tree created?

as seen on Programmers - Search for 'Programmers'
I think I understand the goal of an AST, and I've build a couple of tree structures before, but never an AST. I'm mostly confused because the nodes are text and not number, so I can't think of a nice way to input a token/string as I'm parsing some code. For example, when I looked at diagrams of… >>> More
How to write the Visitor Pattern for Abstract Syntax Tree in Python?

as seen on Stack Overflow - Search for 'Stack Overflow'
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… >>> More
What is the difference between an Abstract Syntax Tree and a Concrete Syntax Tree?

as seen on Stack Overflow - Search for 'Stack Overflow'
I've been reading a bit about how interpreters/compilers work, and one area where I'm getting confused is the difference between an AST and a CST. My understanding is that the parser makes a CST, hands it to the semantic analyzer which turns it into an AST. However, my understanding is that the… >>> More
Representing C#3 code as an Abstract Syntax Tree in XML

as seen on Stack Overflow - Search for 'Stack Overflow'
I was wondering if there is something similar to GCC_XML for C#3; basically a way to represent a program's entire syntactic structure in XML. Once the representation is created, I was hoping to parse it into an XDocument and interpret or query it from there. Are there tools out there for this? >>> More
javac.exe AST programmatic access example

as seen on Stack Overflow - Search for 'Stack Overflow'
Is it possible to access the Abstract Syntax Tree(AST) inside the javac.exe programmatically? Could you provide an example? >>> More

Related posts about parsing

Hot to fix nautilus desktop on linux mint

as seen on Ask Ubuntu - Search for 'Ask Ubuntu'
so I'm using Linux Mint 13 with Cinnamon and suddenly there are no icons on the desktop and the right click doesn't work, it's like the desktop doesn't start up at all, but the Cinnamon interface and everything else are working just fine. This happens only when I open the session with Cinnamon, if… >>> More
Is parsing JSON faster than parsing XML

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm creating a sophisticated JavaScript library for working with my company's server side framework. The server side framework encodes its data to a simple XML format. There's no fancy namespacing or anything like that. Ideally I'd like to parse all of the data in the browser as JSON. However, if… >>> More
Looking for a tutorial on Recursive Descent Parsing.

as seen on Stack Overflow - Search for 'Stack Overflow'
I am trying to parse some data to no success. Can anyone recommend a good introduction with a lot of examples to Recursive Descent Parsing? I haven't been able to find any. >>> More
Parsing XML with Hpricot, a Gem of a Ruby Gem

as seen on Internet.com - Search for 'Internet.com'
Need to parse complex XML documents but don't know where to begin? Leave the task to Ruby's powerful Hpricot library. >>> More
Parsing scripts that use curly braces

as seen on Programmers - Search for 'Programmers'
To get an idea of what I'm doing, I am writing a python parser that will parse directx .x text files. The problem I have deals with how the files are formatted. Although I'm writing it in python, I'm looking for general algorithms for dealing with this sort of parsing. .x files define data using… >>> More