56c170e4019c06c7148f1a7797ac4c55
Python的抽象语法树(二)

Python的抽象语法树(二)

在之前的Python 的抽象语法树(一),我们阐述了一个字符串表达式是如何按照Python的文法定义生成对应的抽象语法书的。

今天我们就借助一个简单的小例子,来感受下Python生成抽象语法书的具体过程:

k = 5
print k

这个例子的词法分析过程在之前的文章已经分析过,读者可自行查阅。

从Token到CST

Python的语法解析相关代码依然是在parsetok,整个程序的逻辑大致如下:

  • 一个循环,不断解析输入的字符串
  • 从字符串中解析初对应的Token
  • 每解析出一个Token,就通过PyParse_AddToken进入CST的创建过程。

这里有两点是需要特别注意的: 在Python

  1. 词法分析并不是全部做完再进入词法分析环节。
  2. 词法分析默认衔接的是CST

那什么是CST呢?就是与抽象语法书对应的具体语法树。为什么要有这两者之分呢?

读者朋友可以回忆下在上一篇语法分析我曾经画的两幅图:

  • 在具体语法树中, 树的内部节点表示非终结符, 叶子节点全部为终结符, 这些终结符构成了可以对应的产生式推导出来的输入串,就是我们之前看到的Grammer文件。

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

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

CST的具体定义

CST的解析其实本质上和我们之前分析的语法书构建没有本质区别,表征树节点的结构叫做node,定义如下:

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,节点种类
  • n_str,节点如果是字符串之类的,保留的字符串内容
  • n_lineno,所在行号
  • n_col_offset,所在列
  • n_nchildren,子节点个数
  • n_child,子节点数组

其实从这个数据结构中,我们就能看出,根节点node已经自发形成了一棵树的结构,如果对此有怀疑的话,我们可以参考PyNode_ListTree,自行解析CST的数据结构:

static void
list1node(FILE *fp, node *n)
{
    if (n == 0)
        return;
    if (ISNONTERMINAL(TYPE(n))) {
        int i;
        for (i = 0; i < NCH(n); i++)
            list1node(fp, CHILD(n, i));
    }
    else if (ISTERMINAL(TYPE(n))) {
        switch (TYPE(n)) {
        case INDENT:
            ++level;
            break;
top Created with Sketch.