CPython-02-解析器-概览

1. 模块职责

解析器（Parser）模块负责将 Python 源代码转换为抽象语法树（AST），是 CPython 编译流程的前端部分。该模块包含两个核心组件：

  1. 词法分析器（Tokenizer/Lexer）：将源代码字符流转换为 Token 流
  2. 语法分析器（Parser）：将 Token 流构建为 AST

输入与输出

输入：

  • Python 源代码字符串
  • Python 源文件（FILE*）
  • 交互式输入（readline 接口）

输出：

  • AST 节点树（mod_ty 类型）
  • 语法错误信息（SyntaxError）

上下游依赖

上游（调用方）：

  • Programs/python.c：主程序入口
  • Python/pythonrun.c：运行时执行接口
  • PyRun_* 系列函数

下游（被调用）：

  • Objects/：创建 AST 节点对象（PyObject）
  • Python/ast.c：AST 节点构造函数
  • Python/compile.c：编译器（接收 AST）

生命周期

stateDiagram-v2
    [*] --> 创建Tokenizer: _PyTokenizer_FromXXX()
    创建Tokenizer --> 初始化Parser: _PyPegen_Parser_New()
    初始化Parser --> 解析循环: _PyPegen_parse()
    解析循环 --> 词法分析: Token获取
    词法分析 --> 语法规则匹配: PEG规则
    语法规则匹配 --> AST构建: 执行Action
    AST构建 --> 解析循环: 继续
    解析循环 --> 返回AST: [成功]
    解析循环 --> 返回错误: [失败]
    返回AST --> 释放Parser: _PyPegen_Parser_Free()
    返回错误 --> 释放Parser
    释放Parser --> 释放Tokenizer: _PyTokenizer_Free()
    释放Tokenizer --> [*]

状态说明：

  1. 创建 Tokenizer：根据输入源（字符串/文件/readline）创建 tok_state 结构
  2. 初始化 Parser：创建 Parser 结构，包含 Token 缓冲区和 Memoization 缓存
  3. 解析循环：递归下降解析，PEG 规则匹配
  4. Token 获取：调用 Tokenizer 按需生成下一个 Token
  5. AST 构建：规则匹配成功时执行 Action 代码，构造 AST 节点
  6. 释放资源：清理 Parser 和 Tokenizer 状态

2. 模块架构图

flowchart TB
    subgraph 输入源
        A1[字符串源] --> A[Tokenizer工厂]
        A2[文件源] --> A
        A3[交互式源] --> A
    end

    subgraph Tokenizer_词法分析器
        A --> B[tok_state 状态机]
        B --> C[字符读取 underflow]
        C --> D[Token识别]
        D --> E[缩进栈管理]
        E --> F[F-string解析]
        D --> G[关键字识别]
        D --> H[字面量解析]
    end

    subgraph Parser_语法分析器
        I[Parser结构] --> J[Token缓冲区]
        J --> K[PEG规则匹配]
        K --> L[Memoization缓存]
        K --> M[左递归处理]
        K --> N[错误恢复]
    end

    subgraph AST_生成
        O[AST Factory] --> P[mod节点]
        O --> Q[stmt节点]
        O --> R[expr节点]
        P --> S[Module]
        P --> T[Interactive]
        P --> U[Expression]
    end

    subgraph 错误处理
        V[语法错误检测]
        W[invalid_规则]
        X[错误位置标注]
        Y[SyntaxError异常]
    end

    F --> J
    G --> J
    H --> J

    K --> O
    N --> V
    V --> W
    W --> X
    X --> Y

    O --> Z[返回AST]

架构说明

Tokenizer 层（词法分析）

职责：将字符流分割为 Token 序列

核心结构：struct tok_state（定义在 Parser/lexer/state.h）

关键字段：

struct tok_state {
    // 输入缓冲
    char *buf;        // 缓冲区起始
    char *cur;        // 当前字符指针
    char *inp;        // 输入结束指针
    char *end;        // 缓冲区结束

    // 行列信息
    int lineno;       // 当前行号（1-based）
    int col_offset;   // 当前列偏移
    const char *line_start;  // 当前行起始

    // 缩进管理
    int indent;       // 当前缩进级别
    int indstack[MAXINDENT];  // 缩进栈（最大100层）
    int atbol;        // 是否在行首
    int pendin;       // 待处理的INDENT/DEDENT数量

    // F-string 支持
    tokenizer_mode tok_mode_stack[MAXFSTRINGLEVEL];  // 模式栈
    int tok_mode_stack_index;  // 当前模式索引

    // 编码
    char *encoding;   // 源文件编码（默认 UTF-8）

    // 错误状态
    int done;         // 错误码（E_OK, E_EOF, E_ERROR等）

    // 函数指针
    int (*underflow)(struct tok_state *);  // 读取更多输入
};

Token 类型（定义在 Grammar/Tokens）：

  • 关键字：if, for, def, class 等（硬关键字）
  • 软关键字：match, case, _（上下文相关）
  • 运算符：+, -, *, ==, != 等
  • 分隔符：(, ), [, ], :, , 等
  • 字面量：NAME, NUMBER, STRING
  • 缩进：INDENT, DEDENT, NEWLINE
  • 特殊：ENDMARKER, ERRORTOKEN

F-string 处理：

  • F-string 支持嵌套（最多 150 层）
  • 使用模式栈跟踪 {} 内的表达式
  • 动态切换 TOK_REGULAR_MODE 和 TOK_FSTRING_MODE

Parser 层（语法分析）

解析算法：PEG（Parsing Expression Grammar）

核心结构：Parser（定义在 Parser/pegen.h）

关键字段：

typedef struct {
    struct tok_state *tok;      // Tokenizer 引用
    Token **tokens;             // Token 缓冲区
    int mark;                   // 当前 Token 索引
    int fill;                   // 已填充 Token 数量
    int size;                   // 缓冲区大小

    PyArena *arena;             // 内存池（用于 AST 节点分配）

    int *errcode;               // 错误码指针
    int error_indicator;        // 错误标志

    int level;                  // 递归深度
    int call_invalid_rules;     // 是否调用 invalid_ 规则（第二遍）

    int flags;                  // 解析标志（TYPE_COMMENTS等）
    int feature_version;        // 特性版本（控制语法兼容性）
} Parser;

PEG 特性：

  1. 有序选择（Ordered Choice）

    • 规则 A | B | C 按顺序尝试
    • 第一个匹配成功的分支被采纳
    • 不会产生二义性

  2. 左递归支持

    expr: expr '+' term | term  // 直接左递归
    • 使用 Memoization 缓存实现
    • 支持直接和间接左递归

  3. Lookahead

    • &e：正向前瞻（不消耗输入）
    • !e：负向前瞻（匹配失败时成功）
    • 用于消除歧义

  4. Memoization（记忆化）

    • 缓存规则匹配结果（mark → (type, node)）
    • 避免指数时间复杂度
    • 关键规则添加 (memo) 标记

AST 生成层

AST 节点类型（定义在 Parser/Python.asdl）：

mod = Module(stmt* body, type_ignore* type_ignores)
    | Interactive(stmt* body)
    | Expression(expr body)
    | FunctionType(expr* argtypes, expr returns)

stmt = FunctionDef(identifier name, arguments args, stmt* body, ...)
     | ClassDef(identifier name, expr* bases, stmt* body, ...)
     | If(expr test, stmt* body, stmt* orelse)
     | While(expr test, stmt* body, stmt* orelse)
     | For(expr target, expr iter, stmt* body, stmt* orelse, ...)
     | ...

expr = BinOp(expr left, operator op, expr right)
     | Call(expr func, expr* args, keyword* keywords)
     | Name(identifier id, expr_context ctx)
     | ...

Action 代码（Grammar/python.gram）：

# 示例：解析 if 语句
if_stmt[stmt_ty]:
    | 'if' a=named_expression ':' b=block c=elif_stmt {
        _PyAST_If(a, b, c, EXTRA)
    }
  • Action 在 {} 内，使用 C 代码
  • EXTRA 宏展开为位置信息
  • 返回 AST 节点指针

边界条件

并发限制：

  • Parser 不是线程安全的（内部状态可变）
  • 每个线程需要独立的 Parser 实例

超时与中断：

  • 长时间解析可通过 PyErr_CheckSignals() 中断
  • 典型触发：Ctrl+C（KeyboardInterrupt）

递归深度：

  • 最大递归深度：Py_GetRecursionLimit()（默认 1000）
  • 超过限制抛出 RecursionError

缓进度限制：

  • Token 缓冲区：动态扩展，无硬限制
  • Memoization 缓存：按需分配，受限于可用内存
  • 缩进栈：最大 100 层（MAXINDENT）
  • F-string 嵌套：最大 150 层（MAXFSTRINGLEVEL）

幂等性：

  • 解析同一源码多次产生等价 AST（但不是同一对象）
  • 错误位置报告稳定（确定性）

异常与回退

语法错误类型：

  1. 通用语法错误（Generic SyntaxError）

    • 触发：所有规则都匹配失败
    • 位置：最远尝试匹配的 Token 位置
    • 示例：def foo(] → “invalid syntax”

  2. 特定语法错误（Specific SyntaxError）

    • 触发：invalid_ 规则匹配（第二遍解析）
    • 位置：精确到错误构造
    • 示例：print "hello" → “Missing parentheses in call to ‘print’”

两阶段解析：

  1. 第一阶段：仅匹配有效规则

    • 快速路径
    • 不考虑 invalid_ 规则

  2. 第二阶段（失败时）：包含 invalid_ 规则

    • 提供更好的错误提示
    • 性能开销可接受（反正要失败）

错误恢复：

  • Parser 不尝试错误恢复
  • 一旦出错立即返回 NULL
  • 由上层决定是否继续（交互模式）

性能特征

时间复杂度：

  • 平均：O(n)，n 为源码字符数
  • 最坏：O(n)（Memoization 保证）
  • 实际：~1000 行/ms（典型代码）

空间复杂度：

  • Token 缓冲区：O(n)
  • Memoization 缓存：O(n × m)，m 为规则数（稀疏，按需分配）
  • AST：O(n)
  • 调用栈：O(d)，d 为语法嵌套深度（通常 < 100）

容量假设：

  • 单文件：< 100K 行（实践中罕见超过）
  • Token 数量：约 10 × 行数
  • AST 节点：约 5 × 行数
  • 内存开销：约 1KB/100 行

版本兼容与演进

特性版本控制：

parser->feature_version  // 例如：7（Python 3.7）
  • 控制语法特性可用性
  • 向后兼容旧版本语法
  • 示例：Python 3.9 支持字典合并运算符 |，旧版本不支持

语法演进示例：

  • Python 3.10：match/case 语句（软关键字）
  • Python 3.12：类型参数语法 class Foo[T]: ...
  • Python 3.15：增强的 f-string（支持更复杂的表达式）

兼容性策略：

  • 新语法通过 __future__ 导入启用
  • 废弃语法发出 DeprecationWarning（至少两个版本）
  • 移除语法发出 SyntaxError

迁移工具：

  • 2to3：Python 2 → Python 3 转换
  • pyupgrade：自动升级语法到新版本
  • lib2to3：可扩展的语法转换框架

3. 解析流程示例

示例代码

# example.py
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

result = factorial(5)

词法分析（Token 流）

1:  NAME "def"        (硬关键字)
1:  NAME "factorial"  (标识符)
1:  OP "("
1:  NAME "n"
1:  OP ")"
1:  OP ":"
1:  NEWLINE
2:  INDENT            (缩进增加)
2:  NAME "if"         (硬关键字)
2:  NAME "n"
2:  OP "<="
2:  NUMBER "1"
2:  OP ":"
2:  NEWLINE
3:  INDENT            (缩进再增加)
3:  NAME "return"     (硬关键字)
3:  NUMBER "1"
3:  NEWLINE
4:  DEDENT            (缩进减少)
4:  NAME "return"
4:  NAME "n"
4:  OP "*"
4:  NAME "factorial"
4:  OP "("
4:  NAME "n"
4:  OP "-"
4:  NUMBER "1"
4:  OP ")"
4:  NEWLINE
5:  DEDENT            (返回顶层)
5:  NEWLINE
6:  NAME "result"
6:  OP "="
6:  NAME "factorial"
6:  OP "("
6:  NUMBER "5"
6:  OP ")"
6:  NEWLINE
7:  ENDMARKER         (文件结束)

AST 结构（简化）

Module(
  body=[
    FunctionDef(
      name='factorial',
      args=arguments(
        args=[arg(arg='n')],
        ...
      ),
      body=[
        If(
          test=Compare(
            left=Name(id='n', ctx=Load()),
            ops=[LtE()],
            comparators=[Constant(value=1)]
          ),
          body=[
            Return(value=Constant(value=1))
          ],
          orelse=[]
        ),
        Return(
          value=BinOp(
            left=Name(id='n', ctx=Load()),
            op=Mult(),
            right=Call(
              func=Name(id='factorial', ctx=Load()),
              args=[
                BinOp(
                  left=Name(id='n', ctx=Load()),
                  op=Sub(),
                  right=Constant(value=1)
                )
              ],
              keywords=[]
            )
          )
        )
      ],
      ...
    ),
    Assign(
      targets=[Name(id='result', ctx=Store())],
      value=Call(
        func=Name(id='factorial', ctx=Load()),
        args=[Constant(value=5)],
        keywords=[]
      )
    )
  ],
  type_ignores=[]
)

解析时序（关键步骤）

  1. 初始化：创建 Tokenizer 和 Parser
  2. 读取第一个 Token：def
  3. 匹配规则：funcdef_rule
  4. 递归解析：
    • 函数名：factorial
    • 参数列表：(n)
    • 函数体：block_rule
  5. 构建 AST 节点：执行 Action 代码
  6. 返回根节点：Module(...)

4. 扩展点与定制

自定义 Token 类型

需要修改 Grammar/Tokens 并重新生成代码：

make regen-token

自定义语法规则

修改 Grammar/python.gram 并重新生成解析器：

make regen-pegen

插入语法检查

在 invalid_ 规则中添加自定义检查：

invalid_foo:
    | 'foo' 'bar' { RAISE_SYNTAX_ERROR("Don't use foo-bar!") }

调试技巧

详细日志：

python -d script.py  # 打印解析过程（需要 --with-pydebug 编译）

AST 可视化：

import ast
tree = ast.parse(source)
print(ast.dump(tree, indent=2))

5. 参考资料

7. 解析器API源码深度剖析

7.1 核心解析API：_PyPegen_run_parser

```c // Parser/pegen.c

mod_ty _PyPegen_run_parser_from_string(const char *str, int start_rule, PyObject *filename_ob, PyCompilerFlags *flags, PyArena *arena) { int exec_input = start_rule == Py_file_input;

// 1. 创建tokenizer
struct tok_state *tok;
if (flags != NULL && flags->cf_flags & PyCF_IGNORE_COOKIE) {
    tok = _PyTokenizer_FromUTF8(str, exec_input, 0);
} else {
    tok = _PyTokenizer_FromString(str, exec_input, 0);
}
if (tok == NULL) {
    if (PyErr_Occurred()) {
        _PyPegen_raise_tokenizer_init_error(filename_ob);
    }
    return NULL;
}

// 设置文件名
tok->filename = Py_NewRef(filename_ob);

// 2. 计算解析器标志
int parser_flags = compute_parser_flags(flags);
int feature_version = flags && (flags->cf_flags & PyCF_ONLY_AST) ?
    flags->cf_feature_version : PY_MINOR_VERSION;

// 3. 创建解析器
Parser *p = _PyPegen_Parser_New(tok, start_rule, parser_flags,
                                feature_version, NULL, str, arena);
if (p == NULL) {
    goto error;
}

// 4. 运行解析器生成AST
mod_ty result = _PyPegen_run_parser(p);

// 5. 清理资源
_PyPegen_Parser_Free(p);

error: _PyTokenizer_Free(tok); return result; } ```

解析流程时序图：

```mermaid sequenceDiagram autonumber participant Comp as 编译器 participant API as _PyPegen_run_parser_from_string participant Tok as Tokenizer participant Parser as PEG Parser participant AST as AST Builder

Comp->>API: 传入源代码字符串

rect rgb(240, 248, 255)
note over API,Tok: 阶段1: 词法分析
API->>Tok: _PyTokenizer_FromString(str)
Tok->>Tok: 初始化tok_state
Tok->>Tok: 设置输入缓冲区
Tok-->>API: tok_state*
end

rect rgb(255, 248, 240)
note over API,Parser: 阶段2: 创建解析器
API->>Parser: _PyPegen_Parser_New(tok)
Parser->>Parser: 初始化Parser结构
Parser->>Parser: 分配token缓冲区
Parser->>Parser: 设置起始规则
Parser-->>API: Parser*
end

rect rgb(240, 255, 240)
note over API,AST: 阶段3: 解析并生成AST
API->>Parser: _PyPegen_run_parser(p)
loop 每个语法规则
    Parser->>Tok: 请求下一个token
    Tok-->>Parser: Token
    Parser->>Parser: 匹配语法规则
    Parser->>AST: 构建AST节点
    AST-->>Parser: AST节点
end
Parser-->>API: mod_ty (AST根节点)
end

rect rgb(255, 240, 240)
note over API: 阶段4: 清理资源
API->>Parser: _PyPegen_Parser_Free(p)
API->>Tok: _PyTokenizer_Free(tok)
end

API-->>Comp: 返回AST

```

7.2 核心数据结构UML图

```mermaid classDiagram class tok_state { «tokenizer» +FILE* fp +char* buf +char* cur +char* inp +char* end +int lineno +int level +int pendin +char* prompt +char* nextprompt +PyObject* filename +int indent[MAXINDENT] +int indstack[MAXINDENT] +int atbol +int decoding_state +int encoding_changed +tokenizer_mode tok_mode_stack[] +int tok_mode_stack_index }

class Token {
    +int type
    +PyObject* bytes
    +int level
    +int lineno
    +int col_offset
    +int end_lineno
    +int end_col_offset
    +Memo* memo
    +PyObject* metadata
}

class Parser {
    +tok_state* tok
    +Token** tokens
    +int mark
    +int fill
    +int size
    +PyArena* arena
    +KeywordToken** keywords
    +int start_rule
    +int* errcode
    +int parsing_started
    +int error_indicator
    +int flags
    +int feature_version
    +int level
    +location last_stmt_location
}

class mod_ty {
    <<AST根节点>>
    +enum kind
    +union body
    +int lineno
    +int col_offset
    +int end_lineno
    +int end_col_offset
}

class stmt_ty {
    <<语句节点>>
    +enum kind
    +union v
    +int lineno
    +int col_offset
    +int end_lineno
    +int end_col_offset
}

class expr_ty {
    <<表达式节点>>
    +enum kind
    +union v
    +int lineno
    +int col_offset
    +int end_lineno
    +int end_col_offset
}

class PyArena {
    <<内存管理>>
    +PyListObject* a_objects
    +block* a_blocks
    +int a_cur_block_index
}

Parser "1" --> "1" tok_state : uses
Parser "1" --> "*" Token : manages
Parser "1" --> "1" PyArena : allocates from
Parser "1" ..> "1" mod_ty : produces
mod_ty "1" --> "*" stmt_ty : contains
stmt_ty "1" --> "*" expr_ty : contains

```

7.3 Tokenizer架构与状态机

Tokenizer架构图：

```mermaid flowchart TD Start[源代码输入] –> Init[初始化tok_state] Init –> ReadChar[读取字符]

ReadChar --> CheckState{当前状态}

CheckState -->|行首| CheckIndent[检查缩进]
CheckState -->|行中| ParseToken[解析Token]
CheckState -->|EOF| EmitEOF[发送ENDMARKER]

CheckIndent --> CompIndent{缩进比较}
CompIndent -->|增加| EmitIndent[发送INDENT]
CompIndent -->|减少| EmitDedent[发送DEDENT]
CompIndent -->|相同| ParseToken

ParseToken --> TokenType{Token类型}

TokenType -->|标识符| ParseName[解析名称/关键字]
TokenType -->|数字| ParseNumber[解析数字]
TokenType -->|字符串| ParseString[解析字符串]
TokenType -->|操作符| ParseOp[解析操作符]
TokenType -->|注释| SkipComment[跳过注释]
TokenType -->|空白| SkipWhite[跳过空白]

ParseName --> EmitToken[发送Token]
ParseNumber --> EmitToken
ParseString --> EmitToken
ParseOp --> EmitToken

SkipComment --> ReadChar
SkipWhite --> ReadChar

EmitToken --> CheckMode{模式检查}
CheckMode -->|普通| AddToken[添加到缓冲区]
CheckMode -->|f-string| PushMode[推入f-string模式]

AddToken --> ReadChar
PushMode --> ReadChar

EmitIndent --> AddToken
EmitDedent --> AddToken
EmitEOF --> Done[完成]

style Start fill:#e1f5ff
style Done fill:#e1ffe1
style CheckState fill:#fff3e1
style TokenType fill:#ffe1f3

```

缩进处理状态机：

```mermaid stateDiagram-v2 [*] –> LineStart: 新行开始

LineStart --> CountSpaces: 遇到空格/制表符
CountSpaces --> CountSpaces: 继续计数
CountSpaces --> CompareIndent: 遇到非空白字符

CompareIndent --> EmitIndent: 缩进增加
CompareIndent --> EmitDedent: 缩进减少
CompareIndent --> ParseToken: 缩进不变
CompareIndent --> IndentError: 缩进不匹配

EmitIndent --> ParseToken: 更新indstack
EmitDedent --> CheckMore: 更新indstack
CheckMore --> EmitDedent: 需要多个DEDENT
CheckMore --> ParseToken: 缩进匹配

ParseToken --> LineEnd: 遇到换行符
LineEnd --> LineStart: 继续下一行

ParseToken --> [*]: EOF
IndentError --> [*]: 语法错误

```

7.4 PEG解析器核心算法

记忆化解析（Packrat Parsing）：

```c // Parser/pegen.c

// 记忆化查找 static void *_PyPegen_get_memo(Parser *p, int type, int node, int *endmark) { if (node == p->mark) { // 当前位置，检查memo for (Memo *m = p->tokens[node]->memo; m != NULL; m = m->next) { if (m->type == type) { // 找到缓存结果 *endmark = m->mark; return m->node; } } } return NULL; }

// 记忆化存储 static void _PyPegen_insert_memo(Parser *p, int mark, int type, void *node) { // 创建新memo节点 Memo *m = PyMem_Malloc(sizeof(Memo)); if (m == NULL) { return; } m->type = type; m->node = node; m->mark = p->mark; m->next = p->tokens[mark]->memo; p->tokens[mark]->memo = m; } ```

解析规则示例（函数定义）：

```c // Parser/parser.c (自动生成)

// function_def: decorators function_def_raw | function_def_raw static stmt_ty function_def_rule(Parser *p) { if (p->level++ == MAXSTACK) { _Pypegen_stack_overflow(p); } if (p->error_indicator) { p->level–; return NULL; }

stmt_ty _res = NULL;
int _mark = p->mark;

// 尝试规则1: decorators function_def_raw
if (p->mark == p->fill && _PyPegen_fill_token(p) < 0) {
    p->error_indicator = 1;
    p->level--;
    return NULL;
}

asdl_expr_seq* d;
stmt_ty f;
if (
    (d = decorators_rule(p))  // decorators
    &&
    (f = function_def_raw_rule(p))  // function_def_raw
)
{
    // 匹配成功，添加装饰器
    _res = _PyAST_FunctionDef(
        f->v.FunctionDef.name,
        f->v.FunctionDef.args,
        f->v.FunctionDef.body,
        d,  // decorators
        // ...
    );
    goto done;
}
p->mark = _mark;  // 回溯

// 尝试规则2: function_def_raw
if (
    (f = function_def_raw_rule(p))  // function_def_raw
)
{
    _res = f;
    goto done;
}
p->mark = _mark;  // 回溯

_res = NULL;

done: p->level–; return _res; } ```

PEG解析流程图：

```mermaid flowchart TD Start[开始解析规则] –> CheckMemo{检查memo} CheckMemo –>|命中| ReturnCached[返回缓存结果] CheckMemo –>|未命中| SaveMark[保存当前位置mark]

SaveMark --> TryChoice1[尝试选择1]

TryChoice1 --> Match1{匹配成功?}
Match1 -->|是| BuildNode1[构建AST节点]
Match1 -->|否| RestoreMark1[恢复mark位置]

RestoreMark1 --> TryChoice2[尝试选择2]
TryChoice2 --> Match2{匹配成功?}
Match2 -->|是| BuildNode2[构建AST节点]
Match2 -->|否| RestoreMark2[恢复mark位置]

RestoreMark2 --> TryMore{还有选择?}
TryMore -->|是| TryNext[尝试下一选择]
TryMore -->|否| FailRule[规则失败]

TryNext --> Match3{匹配成功?}
Match3 -->|是| BuildNode3[构建AST节点]
Match3 -->|否| RestoreMark3[恢复mark]

RestoreMark3 --> FailRule

BuildNode1 --> StoreMemo[存储到memo]
BuildNode2 --> StoreMemo
BuildNode3 --> StoreMemo

StoreMemo --> Return[返回结果]
ReturnCached --> Return
FailRule --> Return

style Start fill:#e1f5ff
style Return fill:#e1ffe1
style FailRule fill:#ffe1e1

```

7.5 AST构建API

AST节点创建函数：

```c // Python/Python-ast.c (自动生成)

// 创建FunctionDef语句节点 stmt_ty _PyAST_FunctionDef(identifier name, arguments_ty args, asdl_stmt_seq *body, asdl_expr_seq *decorator_list, expr_ty returns, string type_comment, int lineno, int col_offset, int end_lineno, int end_col_offset, PyArena *arena) { stmt_ty p; if (!name) { PyErr_SetString(PyExc_ValueError, “field ’name’ is required”); return NULL; } if (!args) { PyErr_SetString(PyExc_ValueError, “field ‘args’ is required”); return NULL; }

// 从arena分配内存
p = (stmt_ty)_PyArena_Malloc(arena, sizeof(*p));
if (!p)
    return NULL;

// 设置字段
p->kind = FunctionDef_kind;
p->v.FunctionDef.name = name;
p->v.FunctionDef.args = args;
p->v.FunctionDef.body = body;
p->v.FunctionDef.decorator_list = decorator_list;
p->v.FunctionDef.returns = returns;
p->v.FunctionDef.type_comment = type_comment;
p->lineno = lineno;
p->col_offset = col_offset;
p->end_lineno = end_lineno;
p->end_col_offset = end_col_offset;

return p;

} ```

AST节点类型层次：

```mermaid classDiagram class mod_ty { «AST Root» +enum kind +Module | Interactive | Expression | FunctionType }

class stmt_ty {
    <<Statement>>
    +FunctionDef | AsyncFunctionDef
    +ClassDef | Return | Delete
    +Assign | AugAssign | AnnAssign
    +For | AsyncFor | While | If
    +With | AsyncWith | Match
    +Raise | Try | TryStar | Assert
    +Import | ImportFrom | Global | Nonlocal
    +Expr | Pass | Break | Continue
}

class expr_ty {
    <<Expression>>
    +BoolOp | NamedExpr | BinOp | UnaryOp
    +Lambda | IfExp | Dict | Set
    +ListComp | SetComp | DictComp | GeneratorExp
    +Await | Yield | YieldFrom | Compare
    +Call | FormattedValue | JoinedStr
    +Constant | Attribute | Subscript
    +Starred | Name | List | Tuple | Slice
}

class arguments_ty {
    <<Function Args>>
    +asdl_arg_seq* posonlyargs
    +asdl_arg_seq* args
    +arg_ty vararg
    +asdl_arg_seq* kwonlyargs
    +arg_ty kwarg
    +asdl_expr_seq* defaults
    +asdl_expr_seq* kw_defaults
}

class arg_ty {
    <<Argument>>
    +identifier arg
    +expr_ty annotation
    +string type_comment
}

mod_ty "1" --> "*" stmt_ty : contains
stmt_ty "1" --> "*" expr_ty : contains
stmt_ty "1" --> "0..1" arguments_ty : has
arguments_ty "1" --> "*" arg_ty : contains

```

7.6 完整函数调用链

从字符串到AST的完整调用链：

``` PyRun_StringFlags └─> _PyParser_ASTFromString ├─> _PyPegen_run_parser_from_string │ ├─> _PyTokenizer_FromString │ │ ├─> tok_new │ │ └─> tok_setup │ │ │ ├─> _PyPegen_Parser_New │ │ ├─> PyMem_Calloc (分配Parser) │ │ ├─> _PyPegen_fill_token (预填充tokens) │ │ └─> initialize_token (初始化token数组) │ │ │ └─> _PyPegen_run_parser │ ├─> file_rule / eval_rule / func_type_rule │ │ (根据start_rule调用不同的顶层规则) │ │ │ ├─> 递归调用各种语法规则 │ │ ├─> statement_rule │ │ │ ├─> function_def_rule │ │ │ ├─> class_def_rule │ │ │ ├─> if_stmt_rule │ │ │ └─> … │ │ │ │ │ └─> expression_rule │ │ ├─> atom_rule │ │ ├─> power_rule │ │ └─> … │ │ │ └─> PyAST* (构建AST节点) │ ├─> _PyAST_Module │ ├─> _PyAST_FunctionDef │ ├─> _PyAST_Expr │ └─> … │ └─> PyAST_Validate (验证AST) ```

7.7 错误处理与恢复

语法错误报告：

```c // Parser/pegen.c

void _Pypegen_raise_error(Parser *p, PyObject *errtype, int use_mark, const char *errmsg, …) { // 1. 确定错误位置 Token *t = p->tokens[use_mark ? p->mark : p->fill - 1];

// 2. 构建错误消息
va_list va;
va_start(va, errmsg);
PyObject *errstr = PyUnicode_FromFormatV(errmsg, va);
va_end(va);

// 3. 创建SyntaxError异常
PyObject *value = PyTuple_Pack(2, errstr, 
    Py_BuildValue("(OiiOii)",
        p->tok->filename,
        t->lineno,
        t->col_offset + 1,
        t->end_lineno,
        t->end_col_offset + 1,
        // ...
    )
);

// 4. 设置异常
PyErr_SetObject(errtype, value);

// 5. 标记错误
p->error_indicator = 1;

} ```

错误恢复策略：

```mermaid flowchart TD Error[检测到语法错误] –> Record[记录错误位置] Record –> CheckMode{解析模式}

CheckMode -->|严格模式| Report[立即报告错误]
CheckMode -->|容错模式| TryRecover[尝试错误恢复]

TryRecover --> FindSync[查找同步点]
FindSync --> SyncPoints{同步标记}

SyncPoints -->|;| SkipToSemi[跳到分号]
SyncPoints -->|换行| SkipToNewline[跳到新行]
SyncPoints -->|}| SkipToRBrace[跳到右括号]

SkipToSemi --> Resume[恢复解析]
SkipToNewline --> Resume
SkipToRBrace --> Resume

Resume --> CheckNext{下一token有效?}
CheckNext -->|是| Continue[继续解析]
CheckNext -->|否| Report

Report --> SetError[设置error_indicator]
SetError --> Return[返回NULL]

Continue --> Success[解析成功]

style Error fill:#ffe1e1
style Success fill:#e1ffe1
style Return fill:#ffe1e1

```

7.8 性能优化技术

1. Token预填充：

```c // Parser/pegen.c static int _PyPegen_fill_token(Parser *p) { const char *start; const char *end; int type = _PyTokenizer_Get(p->tok, &start, &end);

// 预分配token数组
if (p->fill == p->size) {
    int newsize = p->size * 2;
    Token **new_tokens = PyMem_Realloc(p->tokens, newsize * sizeof(Token *));
    if (new_tokens == NULL) {
        return -1;
    }
    p->tokens = new_tokens;
    p->size = newsize;
}

// 创建并存储token
Token *t = PyMem_Malloc(sizeof(Token));
t->type = type;
t->bytes = PyBytes_FromStringAndSize(start, end - start);
// ...
p->tokens[p->fill++] = t;

return 0;

} ```

2. Memo缓存统计：

优化技术 效果 说明
记忆化解析 ~30%性能提升 避免重复解析相同位置
Token预填充 ~15%性能提升 减少I/O次数
Arena内存分配 ~20%性能提升 批量分配，快速释放
关键字哈希表 ~5%性能提升 O(1)关键字查找

7.9 实战案例

解析并打印AST：

```c #include <Python.h>

void print_ast_tree(mod_ty mod) { // 使用ast模块的dump功能 PyObject *ast_module = PyImport_ImportModule(“ast”); PyObject *dump_func = PyObject_GetAttrString(ast_module, “dump”);

// 将mod_ty转换为Python对象
PyObject *ast_obj = PyAST_mod2obj(mod);

// 调用ast.dump()
PyObject *result = PyObject_CallFunctionObjArgs(dump_func, ast_obj, NULL);

// 打印结果
PyObject *str = PyObject_Str(result);
const char *ast_str = PyUnicode_AsUTF8(str);
printf("%s\n", ast_str);

Py_DECREF(str);
Py_DECREF(result);
Py_DECREF(ast_obj);
Py_DECREF(dump_func);
Py_DECREF(ast_module);

}

int main() { Py_Initialize();

const char *code = "def hello(name):\n    return f'Hello, {name}!'";

PyArena *arena = _PyArena_New();
mod_ty mod = _PyParser_ASTFromString(code, "<string>", Py_file_input,
                                      NULL, arena);

if (mod) {
    print_ast_tree(mod);
}
else {
    PyErr_Print();
}

_PyArena_Free(arena);
Py_FinalizeEx();
return 0;

} ```