从现代编译器的角度看, 解释器和编译器的边界已经相当的模糊我们后面的讨论说到的编译器就是 Python 的解释器, 没有特别说明的指的是 CPython 的实现
内存管理(Memory Management)
在讨论编译器的具体实现之前, 我们不得不了解一下在这里面内存是如何井然有序地被分配的为了让内存分配简单一些, 一般我们都会建立一个 Arena(不知道用中文怎么准确的表达)来管理内存有了 Arena 我们就可以把内存集中在一起更容易地进行分配和销毁在这里面没有了真正的内存的释放, 也就是说内存的释放不会显式地对应系统的 free(3)调用也正是由于编译器每部每次内存的分配对于 Arena 都只是一次注册, 释放编译器用到的所有内存也变得非常的简单: 仅仅需要一次 free(3)系统调用就可以达成
一般来说, 除非你是在研究或者开发编译器最核心的部分, 才需要关注内存分配的问题 Python 解释器里所有内存分配相关的代码都在 Include/pyarena.h (https://github.com/python/cpython/blob/master/Include/pyarena.h)和 Python/pyarena.c(https://github.com/python/cpython/blob/master/Python/pyarena.c)可以找到
BTW, 这里有一个我很久以前实现的一个定长内存池 (Fixed Sized Pool) 的源码, 代码量很少, 希望可以有助于大家了解内存池的概念: https://github.com/auxten/gkoAlloc/blob/master/memory.cpp
PyArena_New()函数会帮我们创建一个新的 Arena, 并返回一个 PyArena 结构体, 这个结构体将会保存所有分配给此 Arena 的内存的指针在编译器完成工作释放内存退出之前, 都是由 Arena 负责对所有用到的内存进行记账释放内存对应的 API 是 PyArena_Free()基本上, 每个编译器只需要在最后的战略大撤退时调用它一次即可
综上所述, 内存池的设计初衷就是让我们在进行编译器的各项工作的时候不用去关心内存分配的各种细节因此, 我们研究编译器的绝大多数时候也可以先跳过这部分的内容
唯一的一个例外就是在管理 PyObject 的时候由于 Python 使用引用计数的方式进行内存垃圾回收, 所以在 Arena 上增加了一些机制对它进行额外的支持, 以便垃圾回收的时候能正确的处理每一个 PyObject 虽然这种例外是很少见的, 但是如果你在编译器的代码里分配一个 PyObject, 你必须通过调用 PyArena_AddPyObject()来通知 Arena 增加相应的引用计数
从语法树到抽象语法树(AST)
通过调用 Python 源码中的 PyAST_FromNode()函数, 语法树 (参见 Python/ast.c(https://github.com/python/cpython/blob/master/Python/ast.c#L883)) 被转换成抽象语法树(AST)
- mod_ty
- PyAST_FromNode(const node *n, PyCompilerFlags *flags, const char *filename_str,
- PyArena *arena)
- {
- mod_ty mod;
- PyObject *filename;
- filename = PyUnicode_DecodeFSDefault(filename_str); if (filename == NULL) return NULL;
- mod = PyAST_FromNodeObject(n, flags, filename, arena);
- Py_DECREF(filename); return mod;
- }
PyAST_FromNode()函数对语法树进行树形遍历, 在遍历的过程中动态创建出各种类型的 AST 节点简单来说, 就是遍历每一个节点, 为每一个语法节点调用相对应的 AST 节点的构造函数, 以及相关的支持函数, 按照节点的组织方式对他们进行连接
为了继续下面的内容, 我们要简单介绍一下 yacc, 简单来说, yacc 就是编译器的编译器:
yacc(Yet Another Compiler Compiler), 是 Unix/Linux 上一个用来生成编译器的编译器(编译器代码生成器)yacc 生成的编译器主要是用 C 语言写成的语法解析器(Parser), 需要与词法解析器 Lex 一起使用, 再把两部分产生出来的 C 程序一并编译 yacc 本来只在 Unix 系统上才有, 但现时已普遍移植往 Windows 及其他平台
yacc 的输入是巴科斯范式 (BNF) 表达的语法规则以及语法规约的处理代码, Yacc 输出的是基于表驱动的编译器, 包含输入的语法规约的处理代码部分
yacc 是开发编译器的一个有用的工具, 采用 LALR(1)语法分析方法
yacc 最初由 AT&T 的 Steven C. Johnson 为 Unix 操作系统开发, 后来一些兼容的程序如 Berkeley Yacc,GNU bison,MKS yacc 和 Abraxas yacc 陆续出现它们都在原先基础上做了少许改进或者增加, 但是基本概念是相同的
由于所产生的解析器需要词法分析器配合, 因此 Yacc 经常和词法分析器的产生器一般就是 Lex 联合使用 IEEE POSIX P1003.2 标准定义了 Lex 和 Yacc 的功能和需求
摘自 Wikipedia
需要格外注意的是, 在语法规范和解析树中的节点之间没有自动化或符号连接这点上 Python 解释器和 yacc 不同
例如, 就像我们处理 if 这个语法结构时, 必须关注: 这个 token 出现的位置, 来决定 if 后面的条件语句的结束位置一样跟踪我们正在使用解析树中哪个节点是十分必要的
调用从解析树生成 AST 节点的函数都被命名为 ast_for_xx, 其中 xx 是函数处理的语法规则 (但是, alias_for_import_name 这个函数是个例外) 这些 ast_for_xx 函数会依次调用由 ASDL 语法定义的构造函数以及包含在 Python/Python-ast.c(https://github.com/python/cpython/blob/master/Python/Python-ast.c)(由 Parser/asdl_c.py(https://github.com/python/cpython/blob/master/Parser/asdl_c.py)生成)的构造函数以创建 AST 的节点这样下来, 所有的 AST 节点就全部存储在 asdl_seq 结构体中了
创建和使用 asdl_seq * 类型的函数和宏都在 Python/asdl.c(https://github.com/python/cpython/blob/master/Python/asdl.c) 和 Include/asdl.h(https://github.com/python/cpython/blob/master/Include/asdl.h)中:
asdl_seq *_Py_asdl_seq_new(Py_ssize_t size, PyArena *arena);
在 arena 上分配 size 个长度的 asdl_seq
asdl_seq_GET(S, I)
获取 S(类型是 asdl_seq*)的 I 位置的元素
asdl_seq_SET(S, I, V)
把 S 的指定位置 I 上的元素置为 V
asdl_seq_LEN(S)
返回 S 的长度
如果你正在处理 Python 的代码语句, 代码语句的行号是一个绕不开的问题目前来说, 行号作为最后一个参数传递给每个 stmt_ty 函数的这点在以后的 Python 解释器实现中可能会有改变
来源: http://www.jianshu.com/p/835bb0e410c4