# 7.3 抽象语法树
CPython 解释器的下一个阶段是将解析器（parser）生成的具象语法树（CST）转换为能被执行且抽象层次更高的东西。
具象语法树是代码文件中文本的字面表示方式。Python 的基本语法结构已经被解释过了，但你无法使用具象语法树来建立函数、作用域或者任何 Python 语言核心特性。
在代码被编译前，具象语法树需要转换为能表示 Python 实际结构的更高层次的结构。这个能表示具象语法树的结构被称为：抽象语法树（AST）。
比如：在 AST 中的二元运算操作被称为 `BinOp` 并被定义为一种表达式类型。其由三部分构成：
1. `left` ：运算的左侧部分；
2. `op` ：运算符，如：+、-、\*；
3. `right` ：运算的右侧部分。
`a+1` 的 AST 可以这样表示：
抽象语法树由 CPython 语法解析器生成，但是你也可以通过使用标准库中的`ast` 模块从 Python 代码生成抽象语法树。
在深入探究抽象语法树实现前，使用一些基础的 Python 代码来理解抽象语法树对我们会有所帮助。
### 相关源文件
下面是和抽象语法树相关的文件有：
| 文件 | 用途 |
| -------------------- | -------------------------------------- |
| Include/Python-ast.h | 抽象语法树节点类型声明，由 `Parser/asdl_c.py` 文件生成； |
| Parser/Python.asdl | 在领域特定语言 **ASDL 5** 中的抽象语法树节点类型和属性列表集合； |
| Python/ast.c | 抽象语法树的实现。 |
### 使用 Instaviz 工具展示抽象语法树
Instaviz 是为本书编写的一个 Python 软件包。其在 Web 界面上展示抽象语法树和编译的代码。
你可以通过 `pip` 来安装 `instaviz` 软件包。
然后，通过在命令行中运行不带参数的 `python` 打开一个交互式解释器（REPL）。`instaviz.show()` 函数接收一个 `code object` 类型参数。
你会在下一章节学习到代码对象（code object）。比如：定义一个函数并且用函数名作为参数值：
你会在命令行上看到一个通知：一个 web 服务器已在 8080 端口启动。如果你将此端口用于其他用途，那么你可以通过调用 `instaviz.show(example, port=9090)` 来修改它，当然你也可以指定另一个端口号。
在浏览器上，你可以看到函数的详细细分：
左下角图表是你在交互式解释器上定义的函数，其将用抽象语法树来展示。树上的每一个节点都是一个抽象语法树类型。其都可以在 `ast` 模块中被找到并且都从 `_ast.AST` 继承下来。
某些节点具有将其链接到子节点的属性，不像具象语法树那样具有通用子节点属性。
比如：你点击中间的 `Assign` 节点，那么它会链接到 `b = a + 1` ：
`Assign` 节点有两个属性：
1. `targets` 是要赋值的变量名集合。这是个集合的原因是你可以通过单一表达式解包的方式对多个变量进行赋值；
2. `value` 是要赋值的值，在这个示例中是一 个 `a + 1` 的 `BinOp` 表达式。
如果你点击 `BinOp` 语句，那么 Web 页面就会展现相关属性：
* `left`：运算符左侧的节点；
* `op`：运算符，在这个示例里是一个用于加的 `Add` 节点（+）；
* `right`：运算符右侧的节点。
### 编译抽象语法树
在 C 语言中编译抽象语法树并不是一个简单的工作。 `Python/ast.c` 文件模块拥有 5000 行以上的代码。
这里有几个入口函数构成了抽象语法树的公共 API。抽象语法树 API 接收一棵节点树（具象语法树）、一个文件名、编译器标志以及一个内存存储区。输出类型是一个能表示 Python 模块的[`mod_ty`](https://github.com/python/cpython/blob/v3.9.0b1/Include/Python-ast.h#L14) ，其定义在 `Include/Python-ast.h` 文件中。
`mod_ty` 是 Python 中用于存放四种模块类型之一的容器结构体：
1. `Module` ；
2. `Interactive`；
3. `Expression`；
4. `Function`。
所有的模块类型都在 `Python/Python.asdl` 文件中列举出。你可以看到模块类型、语句类型、表达式类型、操作符以及列表推导式都在这个文件中定义。
在 `Parser/Python.asdl` 文件中的类型名和抽象语法树生成的类相关，并且和 `ast` 标准模块库中的类名相同。
当重新生成语法文件时，`ast` 模块会导入到 `Python-ast.h` 文件中，`Python-ast.h` 是由 `Parser/Python.asdl` 文件自动生成的。`Include/Python-ast.h` 文件中的参数以及名称和 `Parser/Python.asdl` 中定义的参数和名称有直接的关联关系。
`mod_ty` 类型由 `Parser/Python.asdl` 中的模块定义自动生成到 `Include/Python-ast.h` 文件中。
C 的头文件就在 `Python/Python-ast.h` 文件中，因此 `Python/ast.c` 文件可以很快生成带有相关数据指针的结构体。
AST 的入口函数是：[PyAST\_FromNodeObject()](https://github.com/python/cpython/blob/v3.9.0b1/Python/ast.c#L741) 函数，其本质上是一个围绕 `TYPE(n)` 的 `switch` 语句。`TYPE()` 是一个宏定义，抽象语法树用此宏定义来确定节点在具象语法树中的类型。`TYPE()` 的结果是一个符号（symbol）或是一个单词符号（token）类型。
如果从根节点开始，那么它只能是 `Module` 、`Interactive` 、`Expression` 、以及 `FunctionType` 中的一种。
* 对于 `file_input` ，类型只能是 `Module` ；
* 对于 `eval_input` ，比如：来自交互式解释器，类型可能是一个 `Expression` 。
对于每一种语句类型，`Python/ast.c` 文件中都会有一个对应的 `ast_for_xxx` ，其会查看 CST 中的节点来完成该语句类型的属性信息。
一个简单的例子是幂表达式，如：2\*\*4 或 2 的 4 次方。[`ast_for_power()`](https://github.com/python/cpython/blob/v3.9.0b1/Python/ast.c#L2694) 函数会返回一个 `BinOp` （二元运算操作）：运算符是 `Pow` （幂），左侧是 e(2) 以及右侧是 f(4)。
如果你输入一个短函数给 `instaviz` 模块，你就可以看到这个幂表达式的结果：
你同样可以在 UI 界面上看到对应的属性信息。
总而言之，每个语句类型和表达式都有一个对应的 `ast_for_*()` 函数来创建它。参数定义在 `Parser/Python.asdl` 中并通过标准库中的 `ast` 模块对外暴露。
如果表达式或者语句有子节点，那么抽象语法树就会在深度遍历优先中调用相应的 `ast_for_*()` 子函数。