Python内核阅读(二十三): 词法分析器

起步

程序员写的python代码对于Python程序来讲一开始真是字符串的形式. 为了解析源代码, 一般字符流要经过 词法分析 , 语法分析 的步骤来构建语法树. 这部分的解析在cpython的 Parser 文件夹下, 这节先来讲讲词法分析的部分.

词法分析的目标就是将源程序划分成一系列单词符号 (token) . 这些单词是编程语言中具有独立意义的最小单位.

而为了区分每个单词是关键字, 标识符, 运算符, 还是分界符等. 就需要为每一个单词分类.

单词分类

token的类型在 Include/token.h 中定义:

[token.h]
#define ENDMARKER   0
#define NAME        1
#define NUMBER      2
#define STRING      3
#define NEWLINE     4
#define INDENT      5
#define DEDENT      6
...

其中 NAME 就是表示了标识符或关键字. 是的, 关键字也包括在其中, 因此python这词法分析阶段不判定关键字还是标识符, 一律称为 NAME . 其他还有 NUMBER 表示数字, STRING 表示字符串等.

a = b + 10 这个字符流对应的token流为 NAME EQUAL NAME PLUS NUMBER .

字符流到 token 流

从字符流到token流的转换在 Parser/tokenizer.c 中完成. tokenizer的核心数据结构是 tok_state :

[tokenizer.h]
struct tok_state {
    /* Input state; buf <= cur <= inp <= end */
    /* NB an entire line is held in the buffer */
    char *buf;          /* Input buffer, or NULL; malloc'ed if fp != NULL */
    char *cur;          /* Next character in buffer */
    char *inp;          /* End of data in buffer */
    char *end;          /* End of input buffer if buf != NULL */
    char *start;        /* Start of current token if not NULL */
    int done;           /* E_OK normally, E_EOF at EOF, otherwise error code */
    /* NB If done != E_OK, cur must be == inp!!! */
    FILE *fp;           /* Rest of input; NULL if tokenizing a string */
    ...
};

tok_state 它的作用是记录当前tokenizer的状态,比如当前输入缓冲区的起始位置(buf)和终止位置(end)以及当前读取到的字符指针(cur)。 结构里最重要的是 buf , cur , inp , end , start :

  • buf: 缓冲区的开始, 是一段字符串.
  • cur: 指向缓冲区的下一个字符.
  • inp: 指向缓冲区中有效数据的结束位置.
  • end: 缓冲区的结束.
  • start: 指向当前 token 的开始为止. 如果还没开始分析token, 为NULL

tokenizer.c 中提供操作 tok_state 结构的函数族, 这些函数以 tok_* 为前缀的:

  • tok_new(void) : 创建并返回一个tok_state实例 tok ,下面提到的tok都是该tok_state的实例,可以看成是一个全局的变量.
  • tok_nextc(struct tok_state *tok) : 从tok绑定的输入中读取下一个字符并返回
  • tok_backup(struct tok_state *tok, int c) : 将c放回tok绑定的输入中(tok->cur)
  • tok_get(struct tok_state *tok, char **p_start, char **p_end) : 根据 tok->cur 的返回输入的字符流当前位置的token,以供语法分析
  • tok_dump(int type, char *start, char *end) : 打印输出从start到end (均为字符指针)且类型为type的token, 以供调试使用.

宏观上, 我们可以利用 tokenize 模块来得到 .py 文件词法分析后的结果. 我们就以简单的 a = 100 为例:

./python -m tokenize test.py 
0,0-0,0:            ENCODING       'utf-8'        
1,0-1,1:            NAME           'a'            
1,2-1,3:            OP             '='            
1,4-1,7:            NUMBER         '100'          
1,7-1,8:            NEWLINE        '\n'           
2,0-2,0:            ENDMARKER      ''

a被标记为 NAME . = 标记为 OP , 100 标记为 NUMBER . 在CPython中, 负责标记的工作是 PyTokenizer_Get , 它其实 tok_get 的封装, 以 PyTokenizer_* 函数族存在:

[tokenizer.c]
int PyTokenizer_Get(struct tok_state *tok, char **p_start, char **p_end)
{
    int result = tok_get(tok, p_start, p_end);
    if (tok->decoding_erred) {
        result = ERRORTOKEN;
        tok->done = E_DECODE;
    }
    return result;
}

主要的处理集中在 tok_get 当中, 这个函数的目的是要获得下一个token. PyTokenizer_* 函数族有如下几个:

  • struct tok_state *PyTokenizer_FromString(const char *, int);
  • struct tok_state *PyTokenizer_FromUTF8(const char *, int);
  • struct tok_state *PyTokenizer_FromFile(FILE *, const char*, const char *, const char *);
  • void PyTokenizer_Free(struct tok_state *);
  • int PyTokenizer_Get(struct tok_state *, char **, char **);

PyTokenizer_From* 可以看做是词法分析器的构造函数, 返回了一个 tok_state 结构的对象, PyTokenizer_Free 是析构函数, 用来释放 tok_state .

static int tok_get(struct tok_state *tok, char **p_start, char **p_end)
{
    int c;
    int blankline, nonascii;

    *p_start = *p_end = NULL;
  nextline:
    tok->start = NULL;
    blankline = 0;

    // 处理缩进
    if (tok->atbol) {
        // 初始化动作
        int col = 0;
        int altcol = 0;
        tok->atbol = 0;
        for (;;) {
            c = tok_nextc(tok); // 获取下一个字符
            // 跳过空格, tab

            if (c == ' ') {
                col++, altcol++;
            }
            else if (c == '\t') {
                col = (col/tok->tabsize + 1) * tok->tabsize;
                altcol = (altcol/tok->alttabsize + 1)
                    * tok->alttabsize;
            }
            else {
                break;
            }
        }
        tok_backup(tok, c); // 初始化动作结束
    }

    tok->start = tok->cur;

    ...

 again:
    tok->start = NULL;
    /* Skip spaces */
    do {
        c = tok_nextc(tok);
    } while (c == ' ' || c == '\t' || c == '\014');

    // 设置 tok->start
    tok->start = tok->cur - 1;

    // 跳过注释
    if (c == '#') {
        while (c != EOF && c != '\n') {
            c = tok_nextc(tok);
        }
    }

    // 文件结束
    if (c == EOF) {
        return tok->done == E_EOF ? ENDMARKER : ERRORTOKEN;
    }

    /* Identifier (most frequent token!) */
    nonascii = 0;
    if (is_potential_identifier_start(c)) {
        // 处理标识符
        ...
        return NAME;
    }

    /* Newline */
    if (c == '\n') {
        // 新行
        ...
        return NEWLINE;
    }

    /* Number */
    if (isdigit(c)) {
        // 处理数字
        ...
        return NUMBER;
    }

  letter_quote:
    /* String */
    if (c == '\'' || c == '"') {
        // 处理字符串
        ...
        return STRING;
    }

    ...
    /* Keep track of parentheses nesting level */
    switch (c) {
    case '(':
    case '[':
    case '{':
        tok->level++;
        break;
    case ')':
    case ']':
    case '}':
        tok->level--;
        break;
    }
    /* Punctuation character */
    *p_start = tok->start;
    *p_end = tok->cur;
    return PyToken_OneChar(c);
}

大致流程是:

1. 处理缩进

如果 tok->atbol 非0, 说明当前处于一行的开始; 这部分要处理本行代码缩进了多少列, 由于tab的大小有多种设定, 关于tab的大小有两个处理方案, tok->tabsize 保存着"标准"的大小 8; tok->alttabsize 保存着另外大小, 这个值会变化, 在 tok_new 中初始化为1. tok->indent 表示当前缩进数, 初始为0.

colaltcol 保存着在两种不同 tab 设置之下的列数, 并为这两个列都设置了栈, 初始化时设为0:

tok->indstack[0] = 0;
tok->altindstack[0] = 0;

准备工作就算做完毕了. 开读 c = tok_nextc(tok); . 如果遇到空格, colaltcol 各+1. 如果遇到 \t , 要将其转换成各自tabsize格式的列:

col = (col/tok->tabsize + 1) * tok->tabsize;
altcol = (altcol/tok->alttabsize + 1) * tok->alttabsize;

简单的两行就处理完毕了, 并且处理了tab补全的问题, 比如已经有三个空格, 后面跟着tab. 那它表现出来已经是只算一个缩进.

接下来, 如果遇到了注释或者空行, 则不加处理, 直接跳过, 这种空行在文件里没有意义, 但在交互模式下的空行是需要被处理的. 交互模式下我们不考虑.

收集完 colaltcol 后, 开始用到他们的栈 tok->indstacktok->altindstack , tok->indent 指向栈顶的索引:

if (!blankline && tok->level == 0) {
    if (col == tok->indstack[tok->indent]) {
        /* No change */
        if (altcol != tok->altindstack[tok->indent]) {
            // 情况1: col=当前缩进, 不变
        }
    }
    else if (col > tok->indstack[tok->indent]) {
        // 情况2: col > 当前缩进, 进栈
        if (altcol <= tok->altindstack[tok->indent]) {
            if (indenterror(tok)) {
                return ERRORTOKEN;
            }
        }
        tok->pendin++;
        tok->indstack[++tok->indent] = col;
        tok->altindstack[tok->indent] = altcol;
    }
    else /* col < tok->indstack[tok->indent] */ {
        // 情况3: col < 当前缩进, 退栈
        /* Dedent -- any number, must be consistent */
        while (tok->indent > 0 &&
            col < tok->indstack[tok->indent]) {
            tok->pendin--;
            tok->indent--;
        }
    }
}

根据当前的 coltok->indstack 的栈顶(也就是当前缩进的位置). 将空格数与栈顶的空格数对比, 如果大于, 压入当前行的空格数, 并将 tok->pendin++; . 如果小于, 将所有空格数大于当前空格数的出栈, 并将 tok->pendin--; .

tok->pendin 是用来判断究竟是缩进 (INDENT) 还是取消缩进 (DEDENT) . 代码块在其中包裹着.

if (tok->pendin != 0) {
    if (tok->pendin < 0) {
        tok->pendin++;
        return DEDENT;
    }
    else {
        tok->pendin--;
        return INDENT;
    }
}

tok->pendin < 0 意味着这是取消缩进 返回 DEDENT token; 当 tok->pendin > 0 意味着是缩进, 返回 INDENT token.

2. 处理空白和注释

这部分就简单了:

// 跳过空白
do {
    c = tok_nextc(tok);
} while (c == ' ' || c == '\t' || c == '\014');
tok->start = tok->cur - 1;

// 跳过注释
if (c == '#') {
    while (c != EOF && c != '\n') {
        c = tok_nextc(tok);
    }
}

3. 确定 token

这部分一长串的if. 并且在if中反复调用 tok_nextc 去获取完整的单词. 数字类型的返回 NUMBER token. 标识符或关键字的返回 NAME token. 字符串返回 STRING 等.

有一些在python3中才支持的格式, 如数字支持 100_000_000 形式, 这部分的处理在:

static int tok_decimal_tail(struct tok_state *tok)
{
    int c;

    while (1) {
        do {
            c = tok_nextc(tok);
        } while (isdigit(c));
        if (c != '_') {
            break;
        }
        c = tok_nextc(tok);
        if (!isdigit(c)) {
            tok->done = E_TOKEN;
            tok_backup(tok, c);
            return 0;
        }
    }
    return c;
}

获取下一个字符的 tok_nextc

tok_nextc 函数是负责从缓冲区取出一下个字符, 这部分的获取远没想象的那么简单. 但大致处理过程是这样的:

static int tok_nextc(register struct tok_state *tok)
{
    for (;;) {
        if (tok->cur != tok->inp) {
            // cur没有移动到inp,直接返回*tok->cur++
            return Py_CHARMASK(*tok->cur++); /* Fast path */
        }
        if (tok->fp == NULL) {
            // 字符串模式
        }
        if (tok->prompt != NULL) {
            // 交互模式
        }
        else {
            // 磁盘文件模式
        }
    }
}

大部分情况下, tok_nextc 会直接返回 *tok->cur++ , 当 tok->cur 移动到达 tok->inp , 就意味着该读下一行了.

我来评几句
登录后评论

已发表评论数()