​

Compiler Design

​

Compilation Pipeline

1. Tokenize the source code (Parser/lexer/ and Parser/tokenizer/)
2. Parse the token stream into an Abstract Syntax Tree (Parser/parser.c)
3. Transform AST into an instruction sequence (Python/compile.c)
4. Construct a Control Flow Graph and apply optimizations (Python/flowgraph.c)
5. Emit bytecode based on the CFG (Python/assemble.c)

​

Parsing

​

Grammar Definition

• Grammar/python.gram - PEG grammar specification
• Grammar/Tokens - Literal token definitions

• Parser/parser.c - Generated C parser code

​

Abstract Syntax Trees (AST)

​

ASDL Definition

​

Example ASDL Fragment

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

• Three statement types: FunctionDef, Return, Yield
• Modifiers: ? (optional), * (zero or more)
• Common attributes like lineno for all statements

​

Generated C Structures

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;
}

​

AST Generation

• _PyParser_ASTFromString() - For string input
• _PyParser_ASTFromFile() - For file input

​

Memory Management

​

Arena API

• PyArena_New() - Create a new arena
• PyArena_Free() - Free all arena memory at once
• PyArena_AddPyObject() - Register PyObject for cleanup

• Include/internal/pycore_pyarena.h
• Python/pyarena.c

​

Control Flow Graphs

​

Basic Blocks

• Always execute sequentially (no branches within)
• Have a single entry point (at the beginning)
• Have a single exit point (at the end)

​

Example: If Statement CFG

if x < 10:
    f1()
    f2()
else:
    g()
end()

1. Condition block: x < 10 → conditional jump
2. If block: f1(), f2() → jump to end block
3. Else block: g() → jump to end block
4. End block: end()

​

AST to Bytecode

​

Compilation Steps

1. Build Symbol Table
   • _PySymtable_Build() in Python/symtable.c
   • Determines variable scopes (local, global, nonlocal, etc.)
   • Tracks code blocks and nested scopes
2. Generate Instruction Sequence
   • compiler_codegen() transforms AST into pseudo-instructions
   • Uses compiler_visit_{xx} functions for each node type
   • Emits instructions using macros like ADDOP, ADDOP_I, etc.
3. Construct CFG
   • _PyCfg_FromInstructionSequence() builds the control flow graph
   • Identifies basic blocks and their connections
4. Optimize CFG
   • _PyCfg_OptimizeCodeUnit() applies peephole optimizations
   • Examples: constant folding, dead code elimination
5. Assemble Bytecode
   • _PyAssemble_MakeCodeObject() generates final bytecode
   • Converts pseudo-instructions to real bytecode
   • Constructs exception and location tables
   • Creates PyCodeObject

​

Instruction Emission Macros

• ADDOP(c, loc, op) - Add simple opcode
• ADDOP_I(c, loc, op, arg) - Add opcode with integer argument
• ADDOP_O(c, loc, op, obj, type) - Add opcode with object argument
• ADDOP_JUMP(c, loc, op, block) - Add jump instruction
• ADDOP_LOAD_CONST(c, loc, obj) - Add LOAD_CONST instruction

​

Important Files

​

Parser

• Parser/Python.asdl - AST node definitions
• Parser/asdl.py - ASDL parser
• Parser/asdl_c.py - C code generator from ASDL
• Parser/parser.c - Generated PEG parser
• Parser/peg_api.c - High-level parser API

​

Compiler

• Python/compile.c - Main compiler (AST → instruction sequence)
• Python/symtable.c - Symbol table builder
• Python/flowgraph.c - CFG construction and optimization
• Python/assemble.c - Final bytecode assembly
• Python/codegen.c - Code generation utilities

​

AST

• Python/Python-ast.c - Generated AST C structures
• Python/asdl.c - ASDL sequence types
• Python/ast.c - AST validation
• Python/ast_preprocess.c - AST preprocessing
• Python/ast_unparse.c - Convert AST back to string

​

Headers

• Include/cpython/code.h - PyCodeObject definition
• Include/internal/pycore_ast.h - Generated AST definitions
• Include/internal/pycore_symtable.h - Symbol table structures
• Include/internal/pycore_compile.h - Compiler structures

​

Code Object Structure

• co_code_adaptive - Bytecode array (with inline caches)
• co_consts - Tuple of constants
• co_names - Tuple of names used
• co_varnames - Tuple of local variable names
• co_exceptiontable - Exception handling table
• co_linetable - Source location table

​

Related Topics

• Parser Guide - Detailed parser documentation
• Bytecode Interpreter - How bytecode executes
• Code Objects - Code object structure
• Exception Handling - Exception table format