Chapter 22: Tokenizer and PEG Parser

Python 源码进入 CPython 编译链路时，第一段可观察转换发生在 tokenizer 和 parser 之间。tokenizer 读取源文本，处理编码、换行、缩进、字符串、数字、名字、运算符和文件结束标记，输出 token stream。PEG parser 再按照 grammar 消耗这些 token，确认它们能组成合法 Python 程序，并为后续 AST 与编译阶段建立结构边界。

读完本章应能追踪一段 Python 源码从字符到 token stream，再到 PEG grammar 匹配的路径；应能判断一个错误更接近词法层、缩进层、语法层还是后续语义层；也应能区分 tokenizer、grammar、parser state 和 AST 之间各自承担的责任。

本章使用下面这段代码作为贯穿材料。它同时包含函数定义、括号内隐式续行、缩进块、条件语句和返回语句，足够覆盖 tokenizer 与 parser 的交接关系。

def scale(items):
    total = (
        sum(items)
        + len(items)
    )
    if total > 10:
        return total
    return 0

本章版本边界以 CPython 3.14 附近的实现模型为主。词法规则可回溯到 Python 3.14 Lexical analysis，当前 grammar 形状可回溯到 Python 3.14 Full Grammar specification，CPython 从 LL(1) parser 迁移到 PEG parser 的背景可回溯到 PEP 617。不同 Python 实现可以保留相同语言语义，并使用不同内部 parser 组织方式。

这张图给出本章只关心的前半段编译入口。图中的 AST 只作为交接点出现，下一章会展开 AST 与 symbol table。

关键路径是 源文本 → token stream → grammar 匹配 → 结构结果。tokenizer 负责把字符边界整理成可消费的 token；parser 负责判断这些 token 是否满足 grammar；AST 阶段接收 parser 已经确认过的结构结果，再进入作用域分析和字节码生成前的语义整理。

22.1 Lexical analysis and tokenizer

词法分析（lexical analysis）解决的问题是把连续源文本切成带类别的片段。源码文件里的字符本身没有语法层级，def、scale、(、items、)、:、换行、缩进和 return 需要先被识别成 token，parser 才能按 grammar 处理它们的组合关系。

在贯穿材料中，tokenizer 先处理源码编码和物理行。CPython 语言参考规定，源码会按声明编码或默认 UTF-8 解码成 Unicode source characters；换行序列会规整成统一的行结束含义。这个阶段的失败通常表现为源码解码失败或非法字符错误，它发生在 parser 看到结构之前。

逻辑行是 Python 词法层最容易影响阅读的对象。源码中的物理行以文件中的换行结束，逻辑行是 tokenizer 提供给 parser 的语句边界。贯穿材料里的 total = ( 到 ) 横跨多个物理行，但括号内部启用隐式续行，内部换行不会生成终止语句的 NEWLINE token。直到右括号后的换行，total = (...) 这一条赋值语句才完成。

缩进同样由 tokenizer 转换成 token。Python 用缩进表达语句块，tokenizer 会维护缩进层级栈：文件开始时栈中有零缩进；新逻辑行缩进更深时压栈并产生 INDENT；缩进回退时弹栈并产生一个或多个 DEDENT。贯穿材料中，def scale(items): 后面的函数体缩进产生一个 INDENT，return 0 仍在函数体内，文件结束时会补齐对应的 DEDENT。

可以用 Python 标准库的 tokenize 模块观察类似 token stream。这个工具服务于理解 token 边界，输出形式和 CPython 内部 tokenizer 数据结构并非逐字段相同。下面的列表用简化 token 名称表达贯穿材料的主干，不覆盖每个列号和精确字符范围。

token_stream_shape = [
    "NAME:def", "NAME:scale", "OP:(", "NAME:items", "OP:)", "OP::", "NEWLINE",
    "INDENT",
    "NAME:total", "OP:=", "OP:(",
    "NAME:sum", "OP:(", "NAME:items", "OP:)",
    "OP:+", "NAME:len", "OP:(", "NAME:items", "OP:)",
    "OP:)", "NEWLINE",
    "NAME:if", "NAME:total", "OP:>", "NUMBER:10", "OP::", "NEWLINE",
    "INDENT", "NAME:return", "NAME:total", "NEWLINE", "DEDENT",
    "NAME:return", "NUMBER:0", "NEWLINE",
    "DEDENT", "ENDMARKER",
]

这组 token 说明两个判断点。第一，空格和换行有不同地位：普通空格多数只分隔 token，逻辑行结束会产生 NEWLINE，块结构变化会产生 INDENT 和 DEDENT。第二，tokenizer 给 parser 的输入已经带有块边界，parser 处理 block grammar 时可以读取 NEWLINE INDENT statements DEDENT 这类结构，而无需重新计算每一行的空格数量。

名字和关键字的边界也在 tokenizer 与 parser 之间协作完成。硬关键字如 def、if、return 由 grammar 作为固定字面量使用；软关键字如 match、case、type 保留上下文弹性。语言参考明确说明软关键字的区分发生在 parser 层。也就是说，match = 1 中的 match 可以作为普通名字，match value: 中的 match 才在特定 grammar 位置承担语法作用。

源码阅读时可以按这个顺序定位词法问题：先看编码和非法字符，再看物理行如何合成逻辑行，再看括号、反斜杠和字符串是否改变换行含义，再看缩进栈是否能产生合法的 INDENT 与 DEDENT，最后看 token 类别是否足以支持 grammar 匹配。这个顺序能把“字符级失败”和“结构级失败”分开。

22.2 PEG parser, grammar, and parse tree

PEG parser 解决的问题是把 token stream 放入 grammar 规则中进行结构识别。tokenizer 输出 NAME、OP、NEWLINE、INDENT、DEDENT 等 token 后，parser 按起始规则读取整个输入，确认它能构成 file input、interactive input、eval input 或 function type input 之一。普通源码文件走的起始形态可以概括为 file: [statements] ENDMARKER。

PEG 是 Parsing Expression Grammar 的缩写。它的核心特征是有序选择：一个规则有多个候选分支时，parser 按 grammar 中写出的顺序尝试，前面的分支成功后就使用该分支。PEP 617 用这个特征解释 CPython 迁移到 PEG parser 的动机：grammar 可以更自然地表达 Python 的语法形状，包括一些 LL(1) 时代需要改写得较绕的规则。

以贯穿材料开头为例，parser 看到 def scale(items): 时，会在 statement 相关规则中进入 compound statement，再匹配 function definition。这个判断依赖 token 顺序：def 开始函数定义，后面跟函数名、参数列表、冒号和 block。block 再消费 NEWLINE INDENT statements DEDENT，因此函数体范围由 tokenizer 交付的缩进 token 明确限定。

这张图中的 parse tree 是教学上的结构树，显示 token stream 被 grammar 分组后的层级。CPython 当前 PEG grammar 可以带 action，规则匹配成功时可以直接构造内部 AST 节点。读源码时要把概念结构和实现产物区分清楚：语法识别需要树状结构来表达层级，CPython 实现可以通过 grammar action 缩短中间步骤，把结构结果直接组织成后续阶段使用的内部 AST。

grammar 文件中的符号也应按 parser 行为理解。大写名称如 NAME、NUMBER、STRING 指向 token 类别；单引号字符串通常表示硬关键字或固定符号；双引号字符串表示软关键字；e1 e2 表示顺序匹配；e1 | e2 表示候选分支；[e] 或 e? 表示可选；e* 和 e+ 表示重复；&e 与 !e 是前瞻检查；~ 表示 commit 到当前分支。

parser 的失败不等于程序已经整体非法。在有序选择中，一个候选分支失败只是让 parser 尝试后续分支。只有起始规则最终无法完整消费输入，或者进入已确认分支后遇到不可恢复的不匹配，才会上升为 SyntaxError 或更具体的语法类异常。这个行为解释了为什么 grammar 分支顺序会影响错误位置和错误信息。

源码阅读时，Grammar/python.gram 是主入口，Parser/parser.c 通常是生成后的 C parser 形态，Parser/pegen.c、Parser/peg_api.c 和 Parser/pegen_errors.c 承担 PEG parser 运行、API 入口和错误处理相关职责。CPython main 分支附近还把 tokenizer 与 lexer 相关代码放在 Parser/tokenizer/、Parser/lexer/ 等目录下。具体文件名会随 CPython 版本调整，阅读时应先确认目标版本的源码树。

22.3 Parser state and parser evolution

parser state 是一次解析过程中 parser 持有的输入位置、错误位置、memo 状态、arena、起始规则和 tokenizer 连接状态。这个状态让 parser 可以在 grammar 分支之间尝试、回退、提交和记录失败位置。没有这些状态，PEG 的有序选择、前瞻检查和错误定位都无法稳定工作。

贯穿材料中的 total = ( 触发一个典型状态变化：parser 进入赋值语句后看到右侧表达式，tokenizer 在括号深度大于零时继续提供后续物理行上的 token。parser state 需要知道当前 grammar 正在匹配表达式，tokenizer state 需要知道当前换行处于括号内部。二者通过 token stream 协作，最终在右括号后交还一个完整赋值语句。

PEG parser 常与 memoization 一起讨论。直接递归下降在复杂 grammar 下可能重复尝试同一位置的同一规则，memo 可以记录某个规则在某个 token 位置的结果，减少重复工作。CPython 的 grammar 规则中也能看到 (memo) 标记，它表示对应规则参与缓存策略。这个实现细节服务于性能和可维护性，语言语义层面只要求源码按 Python grammar 被接受或拒绝。

parser 演进边界要从 Python 3.9 和 Python 3.10 分开看。PEP 617 引入新的 PEG parser，Python 3.9 阶段保留迁移与切换安排，Python 3.10 移除旧 parser 相关路径。对读者来说，工程结论是：读 Python 3.10 之后的 CPython 源码时，应以 PEG grammar 和 generated parser 为主线；读更早版本时，需要额外识别 LL(1) parser 时代的源码组织。

这个演进还影响语法设计。LL(1) parser 只能看有限前瞻，某些规则需要被改写成更适合机器判断的形状。PEG parser 支持有序选择、前瞻和更自然的左递归表达方式，grammar 可以更贴近语言设计者想表达的结构。代价是 parser 行为和 grammar 顺序绑定更紧，修改 grammar 时要同时考虑分支顺序、commit 点、错误信息和性能。

parser state 也承担内存所有权边界。CPython parser 构造内部 AST 时会使用 arena 管理解析期间创建的对象。arena 让一批编译期对象具有统一生命周期，解析失败或编译完成后可以集中释放。这个细节属于实现策略，但它解释了 grammar action 为什么可以在解析过程中创建结构节点，并把它们交给后续编译阶段。

读 parser 代码时可以按四个状态问题推进：当前从哪个 start rule 进入；当前 token index 或输入位置在哪里；当前 grammar 规则成功、失败或提交到了哪个分支；当前错误位置记录的是第一轮失败、第二轮诊断失败还是专门错误规则命中。把这四个问题问清楚，parser 代码就会从大量生成函数变成可追踪的状态机。

22.4 Syntax error recovery

语法错误定位解决的问题是把“无法匹配 grammar”转成读者能理解的错误位置和错误信息。parser 的诊断需要超过单个“失败”标签，尽量指出失败发生在哪个 token、哪个源码范围、哪类结构附近。Python 的 SyntaxError、IndentationError 和 TabError 都和这个前半段编译入口相关，但它们的触发层级不同。

看一个改坏的贯穿材料变体。这里 if 语句缺少冒号，缩进本身没有表达出合法 block 入口。

def scale(items):
    total = sum(items)
    if total > 10
        return total
    return 0

这个错误接近 parser 层。tokenizer 可以正常产生 NAME:if、表达式 token、NEWLINE 和后续缩进 token；parser 在匹配 if statement 时需要在条件表达式后看到冒号。冒号缺失时，grammar 无法完成 if header，错误位置通常会指向 header 结束附近或后续 token。判断依据是 token 本身合法，组合关系不满足 grammar。

再看一个缩进层错误。下面的代码中 return 0 的缩进层级回退到了之前没有出现过的列位置。

def scale(items):
    total = sum(items)
   return 0

这个错误更接近 tokenizer 缩进栈。tokenizer 在新逻辑行开头计算缩进列数，发现回退位置无法匹配栈中已有层级，就可以抛出缩进相关异常。parser 还没有机会把这一行作为合法 statement 放入函数体结构中。源码排查时，先看缩进栈能否生成合法 DEDENT，再看 grammar 是否能消费这些 token。

CPython grammar 还包含一类 invalid_ 开头的规则，用于产生更具体的语法错误。当前 grammar 注释说明，这些规则第一轮解析时不会启用；第一轮失败后，第二轮才会带上 invalid rules 进行诊断。如果第二轮仍然给出泛化语法错误，错误位置会回到第一轮失败位置。这个设计让 parser 保留正常 grammar 的主路径，同时为常见错误提供更清楚的反馈。

错误恢复在这里应理解为诊断恢复。CPython parser 在语法错误后不会像某些 IDE parser 那样继续构造一棵残缺树供后续分析；它的目标是在编译入口失败时给出稳定位置和消息。IDE、formatter、linter 可以使用容错 parser 或增量 parser，它们的目标是编辑体验；CPython 编译入口的目标是接受合法程序并拒绝非法程序。

定位语法错误时可以用三步判断。第一步看 tokenizer 是否已经能形成完整 token stream，包括合法编码、合法字符串、合法缩进和文件结束。第二步看 parser 是否在某个 grammar header 或 block 位置缺少固定 token，例如冒号、右括号、逗号或 DEDENT。第三步看错误信息是否来自专门 invalid rule，这类信息通常说明 parser 已识别出常见错误形状。

22.5 Token stream as compiler input

token stream 是编译链路中第一个稳定边界。源文本经过 tokenizer 后，后续阶段看到的是 token 类别、token 字符串、起止位置、逻辑行边界和缩进结构。这个边界让 parser 可以专注 grammar 组合，也让后续 AST、symbol table、CFG 和 bytecode 阶段建立在已经规整的结构输入之上。

贯穿材料可以压缩成三个层级的输入输出关系。字符层看到的是换行、空格、字母和符号；token 层看到的是 NAME、OP、NEWLINE、INDENT、DEDENT；grammar 层看到的是 function definition、assignment、if statement 和 return statement。每升高一层，低层细节会被整理成更稳定的结构，下一层只接收自己需要的边界。

这个边界也解释了 AST 阶段的职责。AST 不再关心普通空格数量，也不再重新判断 def 后面是否有冒号；这些已经由 tokenizer 与 parser 共同处理。AST 需要表达的是函数定义节点、赋值节点、调用节点、二元运算节点、比较节点和返回节点之间的父子关系，并为 symbol table 和 bytecode generation 提供结构化输入。

同时，token stream 保留源码位置。错误消息、traceback、调试信息和 ast 节点位置都依赖前面阶段保存的行号和列偏移。PEP 617 中的 grammar action 示例也展示了 parser action 会接触 start_lineno、start_col_offset、end_lineno、end_col_offset 这类位置数据。位置不是装饰信息，它参与错误定位和工具链行为。

把 token stream 作为 compiler input 时，常见判断顺序如下。先确认源码能被解码成字符；再确认逻辑行、隐式续行、字符串和注释的词法边界；再确认缩进栈能产生合法 block token；再确认 grammar 能从 start rule 完整消费到 ENDMARKER；最后把成功匹配的结构交给 AST 和 symbol table。这个顺序也是阅读编译前端源码的最小路径。

这种分层判断能解释许多表面相似的报错。未闭合字符串属于 tokenizer 的字符串状态；括号未闭合横跨 tokenizer 与 parser 的协作边界；缺少冒号属于 grammar header 匹配；return 出现在函数外则进入后续语义检查和编译阶段。错误文本相似时，先把它放回这条路径，定位会更稳定。

本章最终建立的理解是：tokenizer 负责把源文本变成有类别、有位置、有缩进结构的 token stream；PEG parser 负责按有序 grammar 消费 token 并建立语法结构；parser state 记录尝试、回退、提交和错误位置；token stream 是后续 AST 与编译阶段接收的第一个稳定输入边界。

最小自检任务

阅读下面代码，按本章的判断顺序回答三个问题：match 和 case 在这里由哪个阶段解释成语法结构；函数体和 case body 的边界由哪个阶段提供；如果删除 case 0: 末尾的冒号，错误更接近哪个阶段。

def choose(value):
    match value:
        case 0:
            return "zero"
    return "other"

答案要点

match 和 case 在源码字符层只是名字形态的文本，tokenizer 会把它们作为带字符串内容的名字类 token 交给 parser。它们作为软关键字的语法含义由 parser 在特定 grammar 位置解释：match value: 进入 match statement，case 0: 进入 case block。

函数体和 case body 的边界由 tokenizer 的缩进栈提供。def choose(value): 后的换行和更深缩进产生函数体的 INDENT，case 0: 后的更深缩进产生 case body 的 INDENT，缩进回退产生对应 DEDENT。parser 在 block 规则中消费这些 token，并把语句放入正确层级。

删除 case 0: 末尾冒号后，tokenizer 仍能识别 case、0、换行和缩进。失败发生在 parser 匹配 case pattern 头部时，因为 grammar 需要冒号来结束 case header 并进入 block。因此这个错误更接近 parser grammar 匹配；如果缩进列数本身无法回到已有层级，才更接近 tokenizer 缩进栈。

本章知识点总结

• 词法入口：CPython 编译前端先把源文本解码成 source characters，再由 tokenizer 生成 parser 可消费的 token stream。
• 逻辑行：物理换行需要经过显式续行、隐式续行和字符串状态处理后，才会成为语句边界上的 NEWLINE。
• 缩进栈：tokenizer 用缩进层级栈生成 INDENT 和 DEDENT，parser 直接消费这些 block token。
• token 类别：NAME、NUMBER、STRING、OP、NEWLINE、INDENT、DEDENT 和 ENDMARKER 构成 parser 输入的关键边界。
• 软关键字：match、case、type 这类词的上下文语法含义由 parser 判断，普通名字用法仍可保留。
• PEG 选择：PEG grammar 的候选分支按书写顺序尝试，前面分支成功后会决定当前结构归属。
• grammar 符号：大写名称指向 token 类别，单引号常表示硬关键字或固定符号，双引号表示软关键字。
• 结构结果：教学上可把 parser 输出理解成语法结构树，CPython 实现可通过 grammar action 直接构造内部 AST。
• parser state：parser state 保存输入位置、分支尝试、memo、arena、起始规则和错误位置，使 PEG 解析可追踪。
• 版本边界：Python 3.10 之后的 CPython 源码阅读应以 PEG parser 为主线，更早版本需要识别旧 parser 组织。
• 错误分层：非法字符、未闭合字符串和缩进栈失败偏向 tokenizer；缺少冒号、括号和语句组合失败偏向 parser。
• invalid 规则：invalid_ grammar rules 用于第二轮错误诊断，帮助 CPython 给出更具体的语法错误信息。
• 位置数据：token 和 parser action 保存源码位置，错误提示、调试信息和 AST 位置信息都依赖这些数据。
• 编译边界：token stream 是后续 AST、symbol table、CFG 和 bytecode 阶段接收的第一个稳定结构输入。