# 7.2 CPython 解析器-分词器

编程语言对词法分析器（lexer）有不同的实现。有些语言会将词法分析器生成器（lexer generator）作为解析器生成器（parser generator）的一个补充。

CPython 有一个用 C 语言编写的解析器-分词器（parser-tokenizer）模块。

### 相关源文件

以下是与解析器-分词器相关的文件：

| 文件                 | 用途                                                |
| ------------------ | ------------------------------------------------- |
| Python/pythonrun.c | 从输入执行解析器和编译器；                                     |
| Parser/parsetok.c  | 解析器和分词器的实现；                                       |
| Parser/tokenizer.c | 分词器的实现；                                           |
| Include/token.h    | 单词符号类型申明，由`Tools/scripts/generate_token.py` 文件生成； |
| Include/node.h     | 用于分词器的语法分析树节点接口和宏定义。                              |

### 从文件向解析器输入数据

解析器-分词器的入口点是：[PyParser\_ASTFromFileObject()](https://github.com/python/cpython/blob/v3.9.0b1/Python/pythonrun.c#L1442)其获取一个文件句柄、编译器标志和`PyArena` 实例并把文件对象转换为一个模块。

这个函数主要有两个步骤：

1. 通过 [PyParser\_ParseFileObject()](https://github.com/python/cpython/blob/v3.9.0b1/Parser/parsetok.c#L165) 函数转换成具象语法树（CST）；
2. 通过使用抽象语法树（AST）函数 [PyAST\_FromNodeObject()](https://github.com/python/cpython/blob/v3.9.0b1/Python/ast.c#L741) 转换为抽象语法树或模块。

[PyParser\_ParseFileObject()](https://github.com/python/cpython/blob/v3.9.0b1/Parser/parsetok.c#L165) 函数有两个重要的任务：

1. 通过调用 [PyTokenizer\_FromFile()](https://github.com/python/cpython/blob/v3.9.0b1/Parser/tokenizer.c#L779) 创建一个分词器状态实例 `tok_state` ；
2. 通过调用 [parsetok()](https://github.com/python/cpython/blob/v3.9.0b1/Parser/parsetok.c#L216) 将单词符号转换为一棵具象语法树（由一系列 node 节点构成）。

### 解析器-分词器工作流

解析器-分词器接收文本输入并循环执行分词器和解析器，直到光标到达文本末尾才结束（或者出现了一个语法错误）。

在执行前，解析器-分词器会先创建出一个 `tok_state` 实例，分词器会将所有的状态存放到这个临时的数据结构中。分词器状态包括当前光标位置、行等信息。

解析器-分词器通过调用 `tok_get()` 获取到下个单词符号（token）。解析器-分词器将生成的单词符号 ID 传递给解析器，其将使用解析器生成器生成的 DFA 在具象语法树上创建节点。

[tok\_get()](https://github.com/python/cpython/blob/v3.9.0b1/Parser/tokenizer.c#L1178) 函数是整个 CPython 代码基线中最复杂的函数之一。其已经超过了 640 行并且包含了几十年的边缘案例、新语言特性和语法。

循环调用分词器和解析器的流程如下图所示：

<figure><img src="https://1029588898-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FJhewUmzI3BNeGgeFH9Rv%2Fuploads%2Fgit-blob-7a9b4d6ef64e9b6257560560cf569740e61b3ac4%2F%E5%9B%BE7.2.1%20%E8%A7%A3%E6%9E%90%E5%99%A8-%E8%AF%8D%E6%B3%95%E5%88%86%E6%9E%90%E5%99%A8.png?alt=media" alt=""><figcaption></figcaption></figure>

由 [PyParser\_ParseFileObject()](https://github.com/python/cpython/blob/v3.9.0b1/Parser/parsetok.c#L165) 函数返回的具象语法树根节点是下一阶段将具象语法树（CST）转换为抽象语法树（AST）的关键环节。

节点类型定义在 `Include/node.h` 文件中：

<figure><img src="https://1029588898-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FJhewUmzI3BNeGgeFH9Rv%2Fuploads%2Fgit-blob-22bd613af0a74b3fbea6d432097291ca16c9a058%2F%E5%9B%BE7.2.2%20node%E5%AE%9A%E4%B9%89.png?alt=media" alt=""><figcaption></figcaption></figure>

<figure><img src="https://1029588898-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FJhewUmzI3BNeGgeFH9Rv%2Fuploads%2Fgit-blob-3da6be1c507bb7c18cbd6a6de3b880da99ca231b%2F%E5%9B%BE7.2.3%20node%E5%AE%9A%E4%B9%892.png?alt=media" alt=""><figcaption></figcaption></figure>

由于具象语法树是一棵包含语法、单词符号 ID 和符号的树，因此编译器很难基于 Python 语言做出快速决策。

在你学习 AST 之前，这里有个办法可以看到解析阶段的输出：CPython 有一个叫做 `parser` 的标准模块，其通过 Python API 暴露出一个 C 函数。

输出将会是一个数值，使用的是由 `make regen-grammar` 阶段产生的单词符号和符号数值，这些数值存储在 `Include/token.h` 头文件中：

<figure><img src="https://1029588898-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FJhewUmzI3BNeGgeFH9Rv%2Fuploads%2Fgit-blob-db660957bf5cddf4833e7115ec27e7a384972998%2F%E5%9B%BE7.2.4%20%E8%A7%A3%E6%9E%90%E5%99%A8%E8%A7%A3%E6%9E%90%E8%BF%87%E7%A8%8B.png?alt=media" alt=""><figcaption></figcaption></figure>

<figure><img src="https://1029588898-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FJhewUmzI3BNeGgeFH9Rv%2Fuploads%2Fgit-blob-8f2b70f541ea35e2efe3c37da1289aca3e5e708c%2F%E5%9B%BE7.2.5%20%E8%A7%A3%E6%9E%90%E5%99%A8%E8%A7%A3%E6%9E%90%E8%BF%87%E7%A8%8B2.png?alt=media" alt=""><figcaption></figcaption></figure>

为了更容易理解，你可以将所有这些符号和单词模块中的数字都放入到字典中，然后递归的将 `parser.st2list()` 的输出值替换为单词符号的名字。

<figure><img src="https://1029588898-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FJhewUmzI3BNeGgeFH9Rv%2Fuploads%2Fgit-blob-5e89de152ee499000e4ae98db905ea7f7b824453%2F%E5%9B%BE7.2.6%20%E8%A7%A3%E6%9E%90%E5%99%A8%E8%A7%A3%E6%9E%90%E8%BF%87%E7%A8%8B%E8%BD%AC%E6%8D%A2.png?alt=media" alt=""><figcaption></figcaption></figure>

你可以用一个简单的表达式来运行 lex()函数，比如：查看 a + 1 是如何表示成一棵语法分析树：

<figure><img src="https://1029588898-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FJhewUmzI3BNeGgeFH9Rv%2Fuploads%2Fgit-blob-d5abd2f1020c91ee581abe3b20f8eaa3f70e608c%2F%E5%9B%BE7.2.7%20%E6%89%A7%E8%A1%8C%E8%A7%A3%E6%9E%90%E5%99%A8%E8%A7%A3%E6%9E%90%E8%BF%87%E7%A8%8B%E8%BD%AC%E6%8D%A2.png?alt=media" alt=""><figcaption></figcaption></figure>

在输出中，你可以看到小写的符号，如：`arith_expr` ，以及大写的单词符号，如：`NUMBER` 。