PEP 339 – Design of the CPython Compiler | peps.python.org
PEP 339 – Design of the CPython Compiler PEP 339 – Design of the CPython Compiler Author : Brett Cannon <brett at python.org> Status : Withdrawn Type : Informational Created : 02-Feb-2005 Post-History : Table of Contents Abstract Parse Trees Abstract Syntax Trees (AST) Memory Management Parse Tree to AST Control Flow Graphs AST to CFG to Bytecode Introducing New Bytecode Code Objects Important Files Known Compiler-related Experiments References Note This PEP has been withdrawn and moved to the Python developer’s guide.
Abstract Historically (through 2.4), compilation from source code to bytecode involved two steps: Parse the source code into a parse tree (Parser/pgen.c) Emit bytecode based on the parse tree (Python/compile.c) Historically, this is not how a standard compiler works. The usual steps for compilation are: Parse source code into a parse tree (Parser/pgen.c) Transform parse tree into an Abstract Syntax Tree (Python/ast.c) Transform AST into a Control Flow Graph (Python/compile.c) Emit bytecode based on the Control Flow Graph (Python/compile.c) Starting with Python 2.5, the above steps are now used.
This change was done to simplify compilation by breaking it into three steps. The purpose of this document is to outline how the latter three steps of the process works. This document does not touch on how parsing works beyond what is needed to explain what is needed for compilation. It is also not exhaustive in terms of the how the entire system works. You will most likely need to read some source to have an exact understanding of all details.
Parse Trees Python’s parser is an LL(1) parser mostly based on the implementation laid out in the Dragon Book [Aho86] . The grammar file for Python can be found in Grammar/Grammar with the numeric value of grammar rules are stored in Include/graminit.h. The numeric values for types of tokens (literal tokens, such as : , numbers, etc.) are kept in Include/token.h). The parse tree made up of node * structs (as defined in Include/node.h).
Querying data from the node structs can be done with the following macros (which are all defined in Include/token.h): CHILD(node *, int) Returns the nth child of the node using zero-offset indexing RCHILD(node *, int) Returns the nth child of the node from the right side; use negative numbers! NCH(node *) Number of children the node has STR(node *) String representation of the node; e.g., will return : for a COLON token TYPE(node *) The type of node as specified in Include/graminit.h REQ(node *, TYPE) Assert that the node is the type that is expected LINENO(node *) retrieve the line number of the source code that led to the creation of the parse rule; defined in Python/ast.c To tie all of this example, consider the rule for ‘while’: while_stmt : 'while' test ':' suite [ 'else' ':' suite ] The node representing this will have TYPE(node) == while_stmt and the number of children can be 4 or 7 depending on if there is an ‘else’ statement.
To access what should be the first ‘:’ and require it be an actual ‘:’ token, (REQ(CHILD(node, 2), COLON) . Abstract Syntax Trees (AST) 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 three different kinds of statements; function definitions, return statements, and yield statements. 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, 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 expr arguments 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. The FunctionDef() constructor function sets ‘kind’ to FunctionDef_kind and initializes the ‘name’, ‘args’, ‘body’, and ‘attributes’ fields. Memory Management Before discussing the actual implementation of the compiler, a discussion of how memory is handled is in order. To make memory management simple, an arena is used. This means that a memory is pooled in a single location for easy allocation and removal.
What this gives us is the removal of explicit memory deallocation. Because memory allocation for all needed memory in the compiler registers that memory with the arena, a single call to free the arena is all that is needed to completely free all memory used by the compiler. In general, unless you are working on the critical core of the compiler, memory management can be completely ignored. But if you are working at either the very beginning of the compiler or the end, you need to care about how the arena works.
All code relating to the arena is in either Include/pyarena.h or Python/pyarena.c . PyArena_New() will create a new arena. The returned PyArena structure will store pointers to all memory given to it. This does the bookkeeping of what memory needs to be freed when the compiler is finished with the memory it used. That freeing is done with PyArena_Free(). This needs to only be called in strategic areas where the compiler exits.
As stated above, in general you should not have to worry about memory management when working on the compiler. The technical details have been designed to be hidden from you for most cases. The only exception comes about when managing a PyObject. Since the rest of Python uses reference counting, there is extra support added to the arena to cleanup each PyObject that was allocated. These cases are very rare. However, if you’ve allocated a PyObject, you must tell the arena about it by calling PyArena_AddPyObject().
Parse Tree to AST The AST is generated from the parse tree (see Python/ast.c) using the function PyAST_FromNode() . The function begins a tree walk of the parse tree, creating various AST nodes as it goes along. It does this by allocating all new nodes it needs, calling the proper AST node creation functions for any required supporting functions, and connecting them as needed. Do rea
The rest of this page is on the live site.