[Python] CPython1.01源代码阅读笔记(1)

(未完结)
简介
CPython是官方的、使用最广的Python解释器。因为使用C语言实现而得名CPython。非官方的Python解释器还包括JPython(用Java实现)以及PyPy(用Python本身实现)。

关于CPython源码的阅读，网上我见到相关文章有:

• 张羿的Python源码分析
• Robert Chen的CPython源码剖析
  

这两篇侧重点各有不同。前者偏重CPython的词法语法分析，后者偏重解释器的执行机理。我的笔记会和前者重合度较高。事实上我也是参考着前者来的，有部分他略过或是简单提及的地方可能我这里会详细处理。

CPython 1.01是其官方网站上我能找到的最早的版本。这个版本应该是1994年左右release的。所以还是相当初期的时候，规模比较小，便于学习。
解压后我们可以看见它的目录结构包括:

Include/	C源代码的头文件(.h)
Lib/	用Python自己写的Python库文件(.py)
Python/	这里是"编译器"和解释器的源码，Python的核心所在
Grammar/	包括一个Grammar文件，用BNF描述Python语言语法
Parser/	生成pgen这个工具使用Grammar文件

一个编译器运作，必然离不开词法分析和语法分析，所以我们也从这里入手。
词法分析：
所谓词法分析是指将输入的字符流转变为token流。CPython中的token类型被定义在Include/token.h中。比如NAME就是一个token，它对应着关键字以及标识符。"a = b + 10"这个字符流对应的token流为"NAME EQUAL NAME PLUS NUMBER"。

从字符流到token流的转换在Python/tokenizer.c中完成。tokenizer的核心数据结构是tok_state。它的作用是记录当前tokenizer的状态，比如当前输入缓冲区的起始位置(buf)和终止位置(end)以及当前读取到的字符指针(cur)。

如果将tok_state看成tokenizer的成员变量们，你会看到tokenizer.c中还定义了下面这些tokenizer的成员函数:

• tok_new: 创建并返回一个tokenizer实例tok，下面提到的tok都是该tokenizer的实例，可以看成是一个全局的变量。
• tok_setups(str): 调用tok_new并将返回的tok绑定到一个字符串上。
• tok_setupf(f): 调用tok_new并将返回的tok绑定到一个文件上(可以是标准输入stdin，以便互交模式)。
• tok_free(tok): 将tok这个tokenizer实例释放。
• tok_nextc(tok): 从tok绑定的输入中读取下一个字符并返回。
• tok_backup(tok, c): 将c放回tok绑定的输入中(tok->cur--)
• tok_1char(c): 根据单个字符c返回token，比如"<"返回 LESS


• tok_2char(c1,c2): 根据连续两个字符c1, c2返回token， 比如 "<="返回LESSEQUAL


• tok_get(tok, p_start, p_end): 根据tok->cur的返回输入的字符流当前位置的token，以供语法分析。


• tok_dump(int type, char* start, char* end): 打印输出从start到end (均为字符指针)且类型为type的token，以供调试使用。

这些tok开头的函数当中，真正重要的其实就是tok_get--读取当前token。它会在语法分析中反复被调用。 语法分析： Python的语法分析需要借助Parser/目录下pgen这个工具。据Guido老师自己回忆，从Python release到现在，这个pgen是改动最小的部分了。这部分在我看来实现的很精彩。 先说一下python语法分析的基本原理。pgen实现了一个LL(1)的Parser。pgen的输入对象是Grammar/目录下的Grammar文件。 我们可以看一下Grammar文件里到底是如何定义Python语法的。比如其中最重要的几行包括：

stmt: simple_stmt | compound_stmt
simple_stmt: small_stmt (';' small_stmt)* [';'] NEWLINE
small_stmt: expr_stmt | print_stmt  | del_stmt | pass_stmt | flow_stmt | import_stmt | global_stmt | access_stmt | exec_stmt
compound_stmt: if_stmt | while_stmt | for_stmt | try_stmt | funcdef | classdef

它表示每个stmt可以是一个simple_stmt也可以是一个compound_stmt。simple_stmt可以是几个small_stmt的同行并列用";"隔开。 small_stmt可以是expr_stmt, print_stmt, del_stmt等简单语句。而compound_stmt则包括if_stmt, while_stmt等需要跨越多行的复合语句。就这样Python用BNF范式定义了最基本的语法。 现在我们有了这个通俗易懂的Grammar文件以后，pgen负责把这个Grammar转换成NFA，然后再转换为相应的DFA，接着再化简这个DFA，最后保存在gramint.c 和gramint.h这两个文件中。如果你觉得很复杂，你只需要记住我们根据Grammar这个文件得到了一个语法规则就可以了。我们现在来看一下一个py交互模式的运作流程以便于理解：

1. 在pythonmain.c 的realmain()函数中，执行run(stdin, "")
   
2. 进入pythonrun.c的run(fp,filename)调用run_tty_loop
3. 进入pythonrun.c的run_tty_loop(fp, filename)，执行如下循环:
   

   run_tty_loop(fp,filename){
       for (;;) {
           run_tty_1(fp,filename); //不断执行一个“单行”语句
       }
   }

4. 进入pythonrun.c的run_tty_1(fp, filename)，主要执行如下：
   

   run_tty_1(fp, filename) {
   //gram <- graminit将已生成的Python语法规则放进gram，
   //其实不在这个函数里完成，为了理解的方便我就这样写在这里。     
   //根据语法gram以及输入文件fp生成语法树存放在n中     
   node* n = parsefile(fp, filename, &gram, single_input, ...)
   // 执行以n为根节点的语法树
   v = run_node(n, filename, ...) 
   }

给定以上的主要流程，我们来接触更加细节的部分。首先我们来看parsetok.c中的parsefile这个函数，它主要功能包括"

parsefile(fp,filename, g, ...) {
//初始化err_ret
//初始化一个tokenizer(词法分析器)tok
tok = tok_setupf(fp, ...);
return parsetok(tok, g, ...);
}

所以这个函数也相当简单，初始化一个词法分析器然后调用parsetok开始做词法分析。再来看parsetok:

parsetok(tok, g, ...) {
ps = newparser(g, start)
for (;;) {
    type = tok_get(tok, &a, &b);
    addtoken(ps, type, ...);
}
delparser(ps);
}

所以这里就是用一个for循环不停的调用tok_get抓取下一个token供语法分析使用。语法分析里的状态转移以及移进归约在addtoken中实现。