Python内核阅读(二十四): 语法分析器

Python,C/C++ 2018-09-13

起步

上一篇的词法分析忘记说了一个概念, 就是 物理行逻辑行 .

  1. 物理行: 由 回车字符 结尾的字符序列组成一个物理行.
  2. 逻辑行: 由一个或者多个物理行组成,可以明确地使用反斜杠(\)来连接多行物理行.

在python中, 允许跨多行的除了明确地使用反斜杠(\)来表示, 还可以用 圆括号,中括号,花括号 来跨行, 但是被当做是一个逻辑行:

s = "hello \
 wolrd"

s = """
hello
world
""" 
l = [
    1,
    2,
]

d = {
    "a": 1,
    "b": 2,
}

词法分析器是面向逻辑行的, 也就是说, 对于词法分析器而言, 只有逻辑行才算是一行, 它只在逻辑行结束之处才产生NEWLINE这个单词或者说token.

好了, 这只是一个补充, 也没什么太大影响. 本章来谈谈python的语法分析.

Grammar 文件

python源代码中有个 Grammar 文件, 里面以比较接近人能理解的形式展现了python的语法结构. 相信用过 yacc 的人能更容易理解. 这里面定义了python的各个语句, if语句, import语句, for语句等的形式.

比如里面的if语句:

[Grammar]
if_stmt: 'if' test ':' suite ('elif' test ':' suite)* ['else' ':' suite]

解析这个文件所需要的数据结构在 grammar.h 中定义. 给所有语法规则的 DFA(确定有限自动状态机) 提供类型.

Lable

[grammar.h]
typedef struct {
    int      lb_type;
    char    *lb_str;
} label;

label 是用来定义从一个状态到另一个状态所对应边所对应的符号, 很绕口吧. 简单的是, 如果标签 label(NAME, 'if') 就表示了遇到标识符 if , 就要移动到另一个状态. label在DFA图中表示 边对应的符号 .

arc

typedef struct {
    short   a_lbl;      /* Label of this arc */
    short   a_arrow;    /* State where this arc goes to */
} arc;

arc 表示了从一个状态到另一个状态的 . 其中 a_lbl 表示对应的label, a_arrow 表示目标状态, arc不关心来源状态.

state

/* A state in a DFA */
typedef struct {
    int      s_narcs;
    arc     *s_arc;     // 出发边的集合
    /* Optional accelerators */
    int      s_lower;   /* Lowest label index */
    int      s_upper;   /* Highest label index */
    int     *s_accel;   /* Accelerator */
    int      s_accept;  /* Nonzero for accepting state */
} state;

state 代表这 DFA 中的状态节点. 每个state记录了出发边的集合, 其他s_lower, s_upper, s_accel, s_accept记录了state所对应的 Accelerator , 这部分是在运算时计算出来的,

dfa

typedef struct {
    int      d_type;    /* Non-terminal this represents */
    char    *d_name;    /* For printing */
    int      d_initial; /* Initial state */
    int      d_nstates;
    state   *d_state;   /* Array of states */
    bitset   d_first;
} dfa;

dfa 结构中记录所有状态的集合 d_state . 单独记录开始状态 d_initial .

grammar

typedef struct {
    int      g_ndfas;
    dfa     *g_dfa;     /* Array of DFAs */
    labellist    g_ll;
    int      g_start;   /* Start symbol of the grammar */
    int      g_accel;   /* Set if accelerators present */
} grammar;

代表了Grammar所有语法, 记录了所有label, g_start 表示python语法的起始标识, 一般是 single_input, 也可以是 file_input , eval_input 中的一个.

语法结构的搭建

python运行语法分析需要静态数据, 这部分数据固化在 graminit.c 中:

static arc arcs_0_0[3] = {
    {2, 1},
    {3, 1},
    {4, 2},
};
static arc arcs_0_1[1] = {
    {0, 1},
};
static arc arcs_0_2[1] = {
    {2, 1},
};

arcs_0_0 表示DFA0从状态0出发的 arc, arcs_0_1 表示从DFA0中状态1出发的所有arc, 以此类推. 如 arcs_0_0 中第一条 {2, 1} 则表示状态0到状态1, label编号为2.

接下来定义了所有dfa数组:

static dfa dfas[86] = {
    {256, "single_input", 0, 3, states_0,
     "\004\050\340\000\002\000\000\000\012\076\011\007\262\004\020\002\000\300\220\050\037\102"},
    {257, "file_input", 0, 2, states_1,
     "\204\050\340\000\002\000\000\000\012\076\011\007\262\004\020\002\000\300\220\050\037\102"},
    ...
};

以第一个成员为例, 256和 "simple_input" 其实是对应 graminit.h#define single_input 256, 最后一长串的表示了非终结符的 firstset .

接下来定义所有的 lable :

static label labels[176] = {
    {0, "EMPTY"},
    {256, 0},
    {4, 0},
    {270, 0},
    ...
};

"EMPTY" 是个特殊的符号, 该是状态是 accept 状态, 代表DFA的结束.

最后定义 grammar:

grammar _PyParser_Grammar = {
    86,
    dfas,
    {176, labels},
    256
};

Accelerators

这部分是用于加速语法分析速度的数据. 如果没有加速, 我们必须遍历每一条边来判断应该走那条边, 而且如果遇到边的符号是非终结符, 将很难判定是否要跳转到该非终结符对象的DFA, 这会导致不得不扫描该DFA的firstset.

Accelerators 在每个state上都定义了一个数组, 对于每个label都定义转移的目标状态和DFA, 因此是通过做一个简单的索引操作来确定转移的目标状态和DFA, 省去遍历.

graminit.c 中并没有定义 Accelerator 的信息, 其实这部分是在parser初始化后通过运算得来的, 具体实现在 acceler.c 中, Python的解析Parser在初始化时会检查 grammar 中的 g_accl 是否为0, 为0的话就表示 Accelerator 没有计算, 这时会调用 PyGrammar_AddAccelerators 对Grammar进行处理:

[acceler.c]
void PyGrammar_AddAccelerators(grammar *g)
{
    dfa *d;
    int i;
    d = g->g_dfa;
    for (i = g->g_ndfas; --i >= 0; d++)
        fixdfa(g, d);
    g->g_accel = 1;
}

简单粗暴, 依次处理所有的 DFA , 然后设置 g->g_accel 表示已经计算完毕.

fixdfa 对每个 state 进行处理:

[acceler.c]
static void fixdfa(grammar *g, dfa *d)
{
    state *s;
    int j;
    s = d->d_state;
    for (j = 0; j < d->d_nstates; j++, s++)
        fixstate(g, s);
}

主要的实现在 fixstate 中, 这个部分的处理流程大致是这样的:

  1. 申请一个与 labels 个数相等的int数组空间, 让 accel 变量指向这个内存空间, 每个元素都初始为 -1 .
  2. 处理 state 的每条边 arc . 这个处理又分为3个情况:
      1. 如果该边的 label 是终结符, 则设置 accel[ibit] = a->a_arrow , 即目标状态, 这种情况下, 不会进入到另一个 DFA.
      1. 如果这条边的 label 是非终结符, 则找到对应的 DFA, 对 firstset 中每个 labelibit 设置 accel[ibit] = 目标DFA+该边的目标状态
      1. 如果该边的 label"EMPTY" , 则设置 s_accept=1 表明该状态为结束状态.
  3. 最后, 计算出 accel 数组中的最小边界和最大边界, 放到 s_lowers_upper 中. 小于 s_lower 和大于 s_upper 的数组位置都是没有初始化过的, 因此此时的这部分没有意义了, 用 copy 把处于 [s_lower : s_upper+1] 之间内容取出. 计算一个 state 完毕.

当python处理每个 state , 就算完成了加速器所需要的准备工作了. 接下来由 PyParser 来进行语法分析了.

PyParser

PyParser 根据Token创建CST(具体语法树), 具体语法树CST其实就是语法分析树(常简称为parse tree), 其实还有AST(抽象语法树), CST和AST而欧式语法分析所得到的中间产物.

[CST图]

在具体语法树中, 树的内部节点表示非终结符, 叶子节点全部为终结符, 这些终结符构成了可以对应的产生式推导出来的输入串.

[AST图]

抽象语法树AST是一种数据结构, 在表达式的AST中, 每个节点代表一个操作符, 而内部节点的子节点代表该操作符的操作数.

对比AST和CST可知, AST省略了很多出现在CST中的辅助符号, 这使得AST显得更简洁, 在编译器实现语法分析时, 处理AST显得更高效.

python的语法分析是LL(1)的自顶向下分析. CST的节点成为 node , 这个结构在 node.h 定义:

[node.h]
typedef struct _node {
    short       n_type;
    char        *n_str;
    int         n_lineno;
    int         n_col_offset;
    int         n_nchildren;
    struct _node    *n_child;
} node;

成员代表着:

成员 说明
n_type 结点类型,终结符定义在token.h中,而非终结符定义在graminit.h中
n_str 结点所对应的字符串的内容
n_lineno 对应的行号
n_col_offset 列号
n_nchildren 子结点的个数
n_child 子结点数组,动态分配内存

PyParser 所做的事情就是根据 token 生成 CST. 整个生成树的过程就是一个遍历语法图的过程. 语法图是由多个DFA组成的, 而输入的token和当前的所处的状态节点可以决定下一个状态节点. 由于PyParser 是在多个DFA中遍历, 因此当结束了某个DFA的遍历, 需要回到上一个DFA, 因此, 由一个专门的栈保存着:

[parser.h]
#define MAXSTACK 1500

typedef struct {
    int      s_state;   // 当前dfa中的状态
    dfa     *s_dfa;     // 当前的dfa指针
    struct _node    *s_parent;  // 当前的父节点, PyParser会把新的结点作为Child加到栈顶状态的s_parent结点中去
} stackentry;

typedef struct {
    stackentry  *s_top;     /* Top entry */
    stackentry   s_base[MAXSTACK];/* Array of stack entries */
                    /* NB The stack grows down */
} stack;

typedef struct {
    stack       p_stack;    // PyParser状态栈
    grammar     *p_grammar; // 语法图指针
    node        *p_tree;    // CST根节点
    unsigned long   p_flags;// PyParser的flags
} parser_state;

PyParser 所对应的结构是 parser_state , PyParser 所支持的成员函数如下:

[parser.h]
parser_state *PyParser_New(grammar *g, int start);
void PyParser_Delete(parser_state *ps);
int PyParser_AddToken(parser_state *ps, int type, char *str, int lineno, int col_offset,
                      int *expected_ret);
void PyGrammar_AddAccelerators(grammar *g);

PyParser_NewPyParser_Delete 显然是创建和销毁解析器PyParser用的. PyGrammar_AddAccelerators 则是用来处理python的Grammar数据生成的加速器来加快语法分析的速度. 在这些函数中, 最核心的是 PyParser_AddToken , 这个函数的作用是根据词法解析所得的token和当前的DFA状态, 跳转到下一个状态, 并添加到CST中. 因此在 parsetok 函数内的创建解析器步骤中有:

[parsetok.c parsetok]
// 省略了很多代码
ps = PyParser_New(g, start);
for (;;) {
    char *a, *b;
    int type;
    size_t len;
    char *str;
    int col_offset;

    type = PyTokenizer_Get(tok, &a, &b);
    PyParser_AddToken(ps, (int)type, str,
                               tok->lineno, col_offset,
                               &(err_ret->expected))
}

这段代码可以看到, 它会反复调用 PyTokenizer_Get 获得下一个token, 然后将反复获得的token传给 PyParser_AddToken 来逐步构造整个CST, 当所有token都处理过了之后. 整棵树也就建立完毕了.

PyParser API

我们把解释器分为前端和后端, 词法分析和语法分析都属于前端. python的后端不会直接调用 PyParser 或者 PyTokenizer 的函数, 而是通过下面的API来获得前端的信息:

[parsetok.h]
PyAPI_FUNC(node *) PyParser_ParseString(const char *, grammar *, int,
                                              perrdetail *);
PyAPI_FUNC(node *) PyParser_ParseFile (FILE *, const char *, grammar *, int,
                                             const char *, const char *,
                                             perrdetail *);

PyAPI_FUNC(node *) PyParser_ParseStringFlags(const char *, grammar *, int,
                                              perrdetail *, int);
...

PyAPI_FUNC 是python里用来定义公共的python API, 表明这些函数都是可以被外界调用的. 以 PyParser_ParseFile 为例, 该函数分析传入的FILE返回生成的CST. 其他的函数与此类似, 只是分析的对象不同和传入参数的不同.

PyParser_AddToken

PyParser_AddToken 会调用3个内部函数来做处理:classify , push , shift .

classify 会根据type和str来确定对应的Lable. 会针对 NAME 的token做一些特殊处理. 有两种 NAME , 一种是标识符, 一种是关键字. 语法图中, 标识符的str是 NULL . 而关键字的str是有值的, 不同的关键字对应着不同的语句, 因此需要进行比较. 在classify优先处理关键字的情况, 发现不是关键字再将它视为标识符处理.

两种情况都需要遍历整个 LableList 来确定lable的ID, 唯一不同的是关键字情况下可以用一个数组来做索引, 直接根据type查找到id. 在关键字的情况下至少可以吧关键字作为一个单独的token(非终结符)来识别.

shift 改变当前栈顶的状态, 注意并不跳转到其他的dfa, 这个改变只限于单个dfa中, 跳转到其他dfa需要调用push压栈. shift会把当前的 type/str 作为一个新的子节点加入到栈顶的 s_parent 节点, 通常 s_parent 节点对应着当前的dfa的节点.

push 同样会把 type/str 作为新的子节点n加入到当前 s_parent 节点并改变当前栈顶的状态为 newstate . 但是, newstate并不是下一个状态, 而是当新的dfa遍历完毕后退栈才回到. 然后把目标dfa压栈. 新生产的子节点n作为s_parent.


本文由 hongweipeng 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。

如果对您有用,您的支持将鼓励我继续创作!