Learn Python – Interactive Python

The abstract syntax tree (AST) is a high-level representation of the program structure without the necessity of containing the source code; it can be thought of as an abstract representation of the source code. The specification of the AST nodes is specified using the Zephyr Abstract Syntax Definition Language (ASDL) [Wang97].

The definition of the AST nodes for Python is found in the file Parser/Python.asdl.

Each AST node (representing statements, expressions, and several specialized types, like list comprehensions and exception handlers) is defined by the ASDL. Most definitions in the AST correspond to a particular source construct, such as an ‘if’ statement or an attribute lookup. The definition is independent of its realization in any particular programming language.

The following fragment of the Python ASDL construct demonstrates the approach and syntax:

module Python
{
    stmt = FunctionDef(identifier name, arguments args, stmt* body,
                       expr* decorators)
           | Return(expr? value) | Yield(expr? value)
           attributes (int lineno)
}

The preceding example describes two different kinds of statements and an expression: function definitions, return statements, and yield expressions. All three kinds are considered of type stmt as shown by | separating the various kinds. They all take arguments of various kinds and amounts.

Modifiers on the argument type specify the number of values needed; ? means it is optional, * means 0 or more, while no modifier means only one value for the argument and it is required. FunctionDef, for instance, takes an identifier for the name, arguments for args, zero or more stmt arguments for body, and zero or more exprarguments for decorators.

Do notice that something like ‘arguments’, which is a node type, is represented as a single AST node and not as a sequence of nodes as with stmt as one might expect.

All three kinds also have an ‘attributes’ argument; this is shown by the fact that ‘attributes’ lacks a ‘|’ before it.

The statement definitions above generate the following C structure type:

typedef struct _stmt *stmt_ty;

struct _stmt {
      enum { FunctionDef_kind=1, Return_kind=2, Yield_kind=3 } kind;
      union {
              struct {
                      identifier name;
                      arguments_ty args;
                      asdl_seq *body;
              } FunctionDef;

              struct {
                      expr_ty value;
              } Return;

              struct {
                      expr_ty value;
              } Yield;
      } v;
      int lineno;
 }

Also generated are a series of constructor functions that allocate (in this case) a stmt_ty struct with the appropriate initialization. The kind field specifies which component of the union is initialized. TheFunctionDef() constructor function sets ‘kind’ to FunctionDef_kind and initializes the name, args, body, and attributes fields.