CPython词法语法 - WinChua/blog GitHub Wiki

CPython的执行过程包括了，将.py编译成为.pyc字节码文件，然后由python的虚拟机执行字节码。parser跟compiler主要作用在生成.pyc的过程：

1. 将py文件转换成为parse tree： 这部分工作主要由Parser/parser.c 完成；这里的parse tree是由struct node构成的一个中间表示，struct node定义在 Include/node.h Parser/node.c 中
2. Python/ast.c 将parse tree 转换成为 AST
3. Python/compile.c 将AST转成Control Flow Graph, 再将Control Flow Graph 生成字节码文件pyc

第一步，从py文件转换成为parse tree的过程中需要用到tokenizer，grammar涉及到的文件包括：

Parser状态的起点:

1. single_input, 每次parse一行，主要用在interactive
2. file_input, 从文件中parse
3. eval_input, parse eval函数的输入
4. func_type_input

pgen通过读取 Grammar/Grammar以及Grammar/Tokens生成 Include/graminit.h以及 Python/graminit.c文件.

• Include/graminit.h： 包含了所有dfa类型type值的宏定义
• Python/graminit.c: 包含了所有dfa的定义， 以及用于表示语法的全局变量： _PyParser_Grammar

pgen之前是用c完成的，大概2019.05的时候用python改写成为一个module， 生成两个graminit文件的命令是：

python -m Parser/gen Grammar/Grammar Grammar/Tokens Include/graminit.h Python/graminit.c

*.py文件会被parser读取，进行tokenizer，再根据grammar生成一个parse tree， 这里主要描述如何观察这个过程， 需要的前置条件是，自行用 --with-pydebug编译python。

#include <stdio.h>
#include <Python.h>
#include <node.h>
#include <graminit.h>
#include <compile.h>
#include <grammar.h>
#include <parsetok.h>
#include <Include/internal/pycore_pystate.h>

extern grammar _PyParser_Grammar;

int main() {
    setenv("PYTHONHOME", "/home/winchua/cpython", 1);    
    setenv("PYTHONPATH", "/home/winchua/cpython/Lib", 1); // PyNode_ListTree 需要使用到  _PyInterpreterState_GET_UNSAFE，如果没有调用 Py_Initialize，会coredump, 而调用Py_Initialize需要这两个环境变量
    Py_Initialize();
    //Py_DebugFlag = 1;  // Py_DebugFlag 用来打印调试信息
    printf("Hello\n");
    node * p;
    perrdetail err;
    p = PyParser_ParseString("a = 1", &_PyParser_Grammar, single_input, &err);
    printf("error is %d\nlineno is %d\noffset is  %d\ntext is %s\ntoken is %d\nexpected is %d\n", err.error, err.lineno, err.offset, err.text, err.token, err.expected);
    //printf("strerror %s\n", strerror(err.error));
    printf("STR(p) is %s\n", STR(p));  // STR, NCH, TYPE, LINENO, 这些都是node的宏定义操作
    printf("NCH(p) is %d\n", NCH(p));
    printf("TYPE(p) is %d\n", TYPE(p));
    printf("LINENO(p) is %d\n", LINENO(p));
    printf("Listing Node\n");
    PyNode_ListTree(p);
    printf("inttialized is %d\n",_PyRuntime.initialized);  //如果调用了Py_Initialize，这些变量就会是1，
    printf("preinttialized is %d\n",_PyRuntime.preinitialized);
    printf("core_initialized is %d\n",_PyRuntime.core_initialized);
    printf("Ending Node\n");
    //PyParser_SetError(&err);
    //PyCompilerFlags localflags = _PyCompilerFlags_INIT;
    return 0;
}

INC=-I/home/winchua/cpython/ -I/home/winchua/cpython/Include/  -DPy_BUILD_CORE
LIB=-L/home/winchua/cpython -lpython3.9d  -lm -lpthread -ldl -lutil
CC=gcc
all:
        $(CC) -g $(INC) main.c  $(LIB)

一些数据结构

1. growable_comment_array;

流程：

初始化 growable_comment_array之后， 通过PyParser_New 产生一个新的parser, 入参数是: grammar, start

start是什么？

parser_state *ps

typedef struct {
  stack p_stack;
  grammar *p_grammar;
  node *p_tree;
} parser_state

Parser_state 记录了当前的使用的grammar, 生成的parse tree

1. LL(1) parser: top-down parser, 从左向右解析, 最多使用1 token lookhead
2. parsing table： 被某个parser impl消费用于解析一个上下文无关文法。 包括了DFA，first set（由文法计算出来的），keyword，transition label
3. grammar：A grammar is defined by production rules that specify which symbols may replace which other symbols;. 这些rule用来生成字符串或者用来解析字符串。
4. context-free grammar: is a grammar in which the left-hand side of each productions consists of only a single nonterminal symbol.
5. Terminal symbol ： 终止符号：是一些可能会出现在输出字符串的符号；对一串字符串递归应用一个grammar中的rule，最终会得到一串只包含终止符号的输出；
6. Nonterminal symbol： 是那些可以被替代的symbol；grammar包含了一些被指定的start symbol。一门语言中的所有string可以通过在这些start symbol上面apply grammar中设置的rule得到；
7. the language defined by the grammar is defined as the set of terminal strings that can be derived using the production rules.
8. the first sets of a run are defined to be the set of terminals that can appear in the first position of any string derived from the rule. This is useful for LL(1) parsers as the parser is only allowed to look at the next token in the input to know which rule needs to parse.

python的grammar文件的grammar:

grammar: (NEWLINE | rule)* NEWLINE
rule: NAME ':' rhs NEWLINE
rhs: items ( '|' items)*
items: item+
item: '[' rhs ']' | atom [ '+' | '*' ]
atom: '(' rhs ')' | NAME | STRING

graph LR
 	 subgraph init
   t{{tokens}}
   o{{opmap}}
   d{{dfas}}
   s{{startsymbol}}
   f{{first_set}}
   d --> f
   end
   subgraph make_grammar
   g{{"grammar.Grammar()"}}
   c{{"all_labels"}}
   g --> c
   end

   
   f --> g