CPython词法语法过程 - WinChua/blog GitHub Wiki

CPython asdl

Parser/pgen.c 把源码解析成为一个 parse tree， python/ast.c 把parse tree 转化成为一颗抽象语法树， python/compile.c 把抽象语法树转化成为流程控制图， 之后再基于抽象控制图生成对应的字节码

*.py => parse tree => ast.=> control flow graph => bytecode

  1. Python 's parser: LL(1)
文件名 文件信息
Parser/pgen.c 把py文件转换成为parse tree
python/ast.c 将parse tree 转换成为AST
python/compile.c 将AST转化成为control flow graph， 同时更具cfg生成byte code
Grammar/Grammar 语法文件
Include/graminit.h 语法规则的值
Grammar/Tokens token字面量
Include/token.h token字面量对应的数值
Include/node.h parse tree 由 node * 构成， struct node 定义在这个文件
Parser/Python.asdl definition of the last nodes for python
  1. Include/node.h 定义的宏
宏定义 操作语义
CHILD(node *, int) zero-offsets， 返回树的第n个子节点
RCHILD(node *, int) 使用负数索引，从右边返回第n个子节点
NCH(node *) 返回子节点的数量
STR(node *) 生成节点的string表示
TYPE(node *) 返回node的type，type在Include/graminit.h中定义
REQ(node *, TYPE) asset node是某个TYPE
LINENO(node *) 返回生成当前node的源码位置
  1. Parse tree to AST

源码生成由node构成的parse tree， parse tree 生成AST; AST 的生成过程在 Python/ast.c 中，由PyAST_FromNode() 函数生成，函数遍历整个parse tree， 对于每遍历过的地方生成一个AST Node， 每一个Node使用适当的生成函数生成。

AST的生成函数都具有类似的名称： ast_for_xx, 其中xx表示了对应的语法规则， 这些函数都放在了Python/Python-ast.c中（该文件由Parser/asdl_c.py生成的）, 这些函数都生成了一些结构存储在asdl_seq结构中。

Function and macros用于create 以及操作 asdl_seq * 类型定义在Python/asdl.c以及Include/asdl.h 中， 包括了

function or macros 含义
_Py_asdl_seq_new(Py_ssize_t, PyArena *) 给asdl_seq分配一定数量的内存
asdl_seq_GET(asdl_seq *, int) 获取第n个asdl
asdl_seq_SET(asdl_seq *, int, stmt_ty) seta
asdl_seq_LEN(asdl_seq *) 获取长度

python的词法生成以及语法生成

以前是 Parser/pgen.c ， 现在是 Parser/pgen 这个Python module，

生成的过程：

读取 Grammar/Grammar, Grammar/Token 文件中的内容， 生成 graminit.h graminit.c 文件

python -m Parser.gen Grammar/Grammar Grammar/Token xxx.h xxx.c

Parser.gen从Grammar文件中读取一条条的production rule, 生成对应的nfa, 然后simply成为一个dfa; 从Token文件中读取定义的每一个Token,生成每一个Token的数值表示, 以及数值对应Token名称表示。

Parser 从Grammar中生成了一条条的nfa，

Grammar => nfa => dfa

一些名词解释：

  1. DFA： deterministic finite automata 是一种遵守以下规则的有限状态机
    1. 下一个状态的跳转只由当前状态以及输入决定
    2. 每一次的状态跳转都需要一次input
    3. dfa有一个simply算法，用于减少一个dfa状态机中的状态数量， 主要的操作就是：删除从一个初始状态不可达的状态；
  2. NFA： 不确定的状态机， 具有以下的特点：
    1. 当前状态消费同一个input，可能会跳转到不同的状态
    2. 当前状态在不消费input的条件下，也有可能产生状态的跳转
  3. nfa -> dfa: 合并同一个input的target 状态， 合并可能产生 epsilon 跳转的状态