Recommended Compiler Parse Tree Data Structure

Question

I am trying to build a custom python based parse tree data structure. I know that python contains the modules ast, parser, tokenize, etc. Which are designed to make parsing python syntax relatively easy, but since most of these modules contain little documentation I am struggling with them. So I guess I have 2 questions:

1.) How can I use modules like ast to get a parse tree? 2.) What type of tree data structure would you recommend to use to save this information so that I can view/edit it later?

Any help would be greatly appreciated.

Answer 1

At the Python terminal, type help(ast):

>>> import ast
>>> help(ast)
Help on module ast:

NAME
    ast

FILE
    /System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/ast.py

MODULE DOCS
    http://docs.python.org/library/ast

DESCRIPTION
    ast
    ~~~

    The `ast` module helps Python applications to process trees of the Python
    abstract syntax grammar.  The abstract syntax itself might change with
    each Python release; this module helps to find out programmatically what
    the current grammar looks like and allows modifications of it.

    An abstract syntax tree can be generated by passing `ast.PyCF_ONLY_AST` as
    a flag to the `compile()` builtin function or by using the `parse()`
    function from this module.  The result will be a tree of objects whose
    classes all inherit from `ast.AST`.
    …

This tells us to call the parse() method. Let’s try that:

#!/usr/bin/env python2.7

import ast
import sys

with open(sys.argv[0], 'r') as my_source:
    my_ast = ast.parse(my_source.read())

print ast.dump(my_ast)

The output is a bit messy, but paste it into your editor, auto-indent it, and you get the detailed AST:

Module(body=[Import(names=[alias(name='ast',
                                 asname=None)]),
             Import(names=[alias(name='sys',
                                 asname=None)]),
             With(context_expr=Call(func=Name(id='open',
                                              ctx=Load()),
                                    args=[Subscript(value=Attribute(value=Name(id='sys',
                                                                               ctx=Load()),
                                                                    attr='argv',
                                                                    ctx=Load()),
                                                    slice=Index(value=Num(n=0)),
                                                    ctx=Load()),
                                          Str(s='r')],
                                    keywords=[],
                                    starargs=None,
                                    kwargs=None),
                  optional_vars=Name(id='my_source',
                                     ctx=Store()),
                  body=[Assign(targets=[Name(id='my_ast',
                                             ctx=Store())],
                               value=Call(func=Attribute(value=Name(id='ast',
                                                                    ctx=Load()),
                                                         attr='parse',
                                                         ctx=Load()),
                                          args=[Call(func=Attribute(value=Name(id='my_source',
                                                                               ctx=Load()),
                                                                    attr='read',
                                                                    ctx=Load()),
                                                     args=[],
                                                     keywords=[],
                                                     starargs=None,
                                                     kwargs=None)],
                                          keywords=[],
                                          starargs=None,
                                          kwargs=None))]),
             Print(dest=None,
                   values=[Call(func=Attribute(value=Name(id='ast',
                                                          ctx=Load()),
                                               attr='dump',
                                               ctx=Load()),
                                args=[Name(id='my_ast',
                                           ctx=Load())],
                                keywords=[],
                                starargs=None,
                                kwargs=None)],
                   nl=True)])

To poke at things with code, run the above script with python -i foo.py to get a my_ast object that you can poke at interactively with dir():

>>> dir(my_ast)
['__class__', '__delattr__', '__dict__', '__doc__', '__format__', '__getattribute__', '__hash__', '__init__', '__module__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', '__weakref__', '_attributes', '_fields', 'body']
>>> my_ast.body
[<_ast.Import object at 0x1055b3590>, <_ast.Import object at 0x1055b3610>, <_ast.With object at 0x1055b3690>]
>>> with_stmt = my_ast.body[2]
>>> dir(with_stmt)
['__class__', '__delattr__', '__dict__', '__doc__', '__format__', '__getattribute__', '__hash__', '__init__', '__module__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', '__weakref__', '_attributes', '_fields', 'body', 'col_offset', 'context_expr', 'lineno', 'optional_vars']
>>> with_stmt.lineno
6
>>> with_stmt.body
[<_ast.Assign object at 0x1055b3910>]
>>> assign1 = with_stmt.body[0]
>>> dir(assign1)
['__class__', '__delattr__', '__dict__', '__doc__', '__format__', '__getattribute__', '__hash__', '__init__', '__module__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', '__weakref__', '_attributes', '_fields', 'col_offset', 'lineno', 'targets', 'value']
>>> assign1.value
<_ast.Call object at 0x1055b3990>