分类： C/C++
2008-09-11 12:31:25
上次我们分析了Python中执行程序可分为5个步骤：
本文将介绍Python程序执行的第一步，也就是词法分析。词法分析简单来说就是把源程序的字符分解组合成Token。比如sum=0可以分解成3个token，'sum', '=', '0'。程序中的whitespace通常只作为分隔符用，最终会被忽略掉，因此没有出现在token的列表中。不过在Python之中，由于语法规则的关系，Tab/Space需要用来分析程序的缩进，因此Python中对于Whitespace的处理比一般C/C++编译器的处理会要稍微复杂一些。
在Python中词法分析的实现在Parser目录下的tokenizer.h和tokenizer.cpp。Python的其他部分会直接调用tokenizer.h中定义的函数，如下：
|
extern struct tok_state *PyTokenizer_FromString(const char *); |
这些函数均以PyTokenizer开头。这是Python源代码中的一个约定。虽然Python是用C语言实现的，其实现方式借鉴了很多面对对象的思想。拿词法分析来说，这四个函数均可以看作PyTokenizer的成员函数。头两个函数PyTokenizer_FromXXXX可以看作是构造函数，返回PyTokenizer的instance。PyTokenizer对象内部状态，也就是成员变量，储存在tok_state之中。PyTokenizer_Free可以看作是析构函数，负责释放PyTokenizer，也就是tok_state所占用的内存。PyTokenizer_Get则是PyTokenizer的一个成员函数，负责取得在字符流中下一个Token。这两个函数均需要传入tok_state的指针，和C++中需要隐含传入this指针给成员函数的道理是一致的。可以看到，OO的思想其实是和语言无关的，即使是C这样的结构化的语言，也可以写出面对对象的程序。
tok_state等价于PyTokenizer这个class本身的状态，也就是内部的私有成员的集合。部分定义如下：
|
/* Tokenizer state */ |
最重要的是buf, cur, inp, end, start。这些field直接决定了缓冲区的内容：
buf是缓冲区的开始。假如PyTokenizer处于字符串模式，那么buf指向字符串本身，否则，指向文件读入的缓冲区。
cur指向缓冲区中下一个字符。
inp指向缓冲区中有效数据的结束位置。PyTokenizer是以行为单位进行处理的，每一行的内容存入从buf到inp之间，包括\n。一般情况下 ，PyTokenizer会直接从缓冲区中取下一个字符，一旦到达inp所指向的位置，就会准备取下一行。当PyTokenizer处于不同模式下面，具体的行为会稍有不同。
end是缓冲区的结束，在字符串模式下没有用到。
start指向当前token的开始位置，如果现在还没有开始分析token，start为NULL。
PyTokenizer_FromString & PyTokenizer_FromFile可以说是PyTokenizer的构造函数。从这两个函数的命名可以看出，PyTokenizer支持两种模式：字符串和文件。由于标准输入STDIN也可以看作是文件，因此实际上PyTokenizer支持3种模式：字符串，交互，文件。
PyTokenizer_FromFile的实现和PyTokenizer_FromString的实现大致相同。后者的实现如下：
|
/* Set up tokenizer for string */ |
直接调用tok_new返回一个tok_state的instance，后面的decode_str负责对str进行解码，然后赋给tok->buf/cur/end/inp。
下面我们来分析一下PyTokenizer_Get函数。该函数的作用是在PyTokenizer所绑定的字符流（可以是字符串也可以是文件）中取出下一个token，比如sum=0刚取到了'sum'，那么下一个取到的就是'='。一个返回的token由两部分参数描述，一个是表示token类型的int，一个是token的具体内容，也就是一个字符串。Python会把不同token分为若干种类型，这些不同的类型定义在include/token.h里面以宏的形式存在，如NAME，NUMBER，STRING，NEWLINE等。举例来说，'sum'这个token可以表示成(NAME, 'sum')。NAME是类型，表明sum是一个名称（注意请和字符串区分开）。此时Python并不判定该名称是关键字还是标识符，一律统称为NAME。而这个NAME的内容是'sum'。PyTokenizer_Get返回的int便是token的类型，而两个参数char **p_start, char **p_end是输出参数，指向token在PyTokenizer内部缓冲区中的位置。这里采用返回一个p_start和p_end的意图是避免构造一份token内容的copy，而是直接给出token在缓冲区中的开始和结束的位置。这样做显然是为了提高效率。
PyTokenizer_Get的实现如下，直接调用tok_get函数：
|
Int |
tok_get负责以下几件事情：
缩进的处理只在一行开始的时候。如果tok_state::atbol(at beginning of line)非0，说明当前处于一行的开始，否则不做处理。
|
/* Get indentation level */
if (tok->atbol) {
register int col = 0;
register int altcol = 0;
tok->atbol = 0;
for (;;) {
c = tok_nextc(tok);
if (c == ' ')
col++, altcol++;
else if (c == '\t') {
col = (col/tok->tabsize + 1) * tok->tabsize;
altcol = (altcol/tok->alttabsize + 1)
* tok->alttabsize;
}
else if (c == '\014') /* Control-L (formfeed) */
col = altcol = 0; /* For Emacs users */
else
break;
}
tok_backup(tok, c); |
上面的代码负责计算缩进了多少列。由于tab键可能有多种设定，PyTokenizer对tab键有两套处理方案：tok->tabsize保存着"标准"的tab的大小，缺省为8（一般不要修改此值）。Tok->alttabsize保存着另外的tab大小，缺省在tok_new中初始化为1。col和altcol保存着在两种不同tab设置之下的列数，遇到空格+1，遇到\t则跳到下一个tabstop，直到遇到其他字符为止。
|
if (c == '#' || c == '\n') {
/* Lines with only whitespace and/or comments
shouldn't affect the indentation and are
not passed to the parser as NEWLINE tokens,
except *totally* empty lines in interactive
mode, which signal the end of a command group. */
if (col == 0 && c == '\n' && tok->prompt != NULL)
blankline = 0; /* Let it through */
else
blankline = 1; /* Ignore completely */
/* We can't jump back right here since we still
may need to skip to the end of a comment */
} |
接下来，如果遇到了注释或者是空行，则不加以处理，直接跳过，这样做是避免影响缩进。唯一的例外是在交互模式下的完全的空行（只有一个换行符）需要被处理，因为在交互模式下空行意味着一组语句将要结束，而在非交互模式下完全的空行是要被直接忽略掉的。
|
if (!blankline && tok->level == 0) {
if (col == tok->indstack[tok->indent]) {
// 情况1：col=当前缩进，不变
}
else if (col > tok->indstack[tok->indent]) {
// 情况2：col>当前缩进，进栈
tok->pendin++;
tok->indstack[++tok->indent] = col;
tok->altindstack[tok->indent] = altcol;
}
else /* col < tok->indstack[tok->indent] */ {
// 情况3：col<当前缩进，退栈
while (tok->indent > 0 &&
col < tok->indstack[tok->indent]) {
tok->pendin--;
tok->indent--;
}
}
} |
最后，根据col和当前indstack的栈顶（也就是当前缩进的位置），确定是哪一种情况，具体请参看上面的代码。上面的代码有所删减，去掉了一些错误处理，加上了一点注释。需要说明的是PyTokenizer维护两个栈indstack & altindstack，分别对应col和altcol，保存着缩进的位置，而tok->indent保存着栈顶。
代码很简单，在此不做说明。
反复调用tok_nextc，获得下一个字符，依据字符内容判定是何种token，然后加以返回。具体的过程比较长，但是logic还是比较简单的。
下面举一个处理标识符（变量和关键字）的例子
|
/* Identifier (most frequent token!) */
if (isalpha(c) || c == '_') {
/* Process r"", u"" and ur"" */
switch (c) {
case 'r':
case 'R':
c = tok_nextc(tok);
if (c == '"' || c == '\'')
goto letter_quote;
break;
case 'u':
case 'U':
c = tok_nextc(tok);
if (c == 'r' || c == 'R')
c = tok_nextc(tok);
if (c == '"' || c == '\'')
goto letter_quote;
break;
}
while (isalnum(c) || c == '_') {
c = tok_nextc(tok);
}
tok_backup(tok, c);
*p_start = tok->start;
*p_end = tok->cur;
return NAME;
} |
假如当前字符是字母或者是下划线，则开始当作标示符进行分析，否则，继续执行下面的语句，处理其他的可能性。不过还有一种可能性，Python中字符串可以是用r或者u开头，比如r"string", u"string"。r代表raw string，u代表unicode string。一旦遇到了r或者u的情况下，直接跳转到letter_quote标号处，开始作为字符串进行分析。如果不是r/u，反复拿到下一个字符直到下一个字符不是字母，数字或者下划线为止。由于最后一次拿到的字符不属于当前标示符，应该被放到下一次进行分析，因此调用tok_backup把字符c回送到缓冲区中，类似ungetch()。最后，设置好p_start & p_end，返回NAME。这样，返回的结果表明下一个token是NAME，开始于p_start，结束于p_end。
tok_nextc负责从缓冲区中取出下一个字符，可以说是整个PyTokenizer的最核心的部分。
|
/* Get next char, updating state; error code goes into tok->done */
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。一旦tok->cur==tok->inp，tok_nextc会读入下一行。根据PyTokenizer处于模式的不同，处理方式会不太一样：
字符串的处理是最简单的一种情况，如下：
|
char *end = strchr(tok->inp, '\n');
if (end != NULL)
end++;
else {
end = strchr(tok->inp, '\0');
if (end == tok->inp) {
tok->done = E_EOF;
return EOF;
}
}
if (tok->start == NULL)
tok->buf = tok->cur;
tok->line_start = tok->cur;
tok->lineno++;
tok->inp = end;
return Py_CHARMASK(*tok->cur++); |
尝试获得下一行的末尾处作为新的inp，否则，说明下一行结尾处没有\n换行符（说明这是最后一行）或者当前行就是最后一行。在前者的情况下，inp就是字符串\0的位置，否则，返回EOF。当获得了下一行之后，返回下一个字符Py_CHARMASK(*tok->cur++)。
代码如下：
|
char *newtok = PyOS_Readline(stdin, stdout, tok->prompt);
if (tok->nextprompt != NULL)
tok->prompt = tok->nextprompt;
if (newtok == NULL)
tok->done = E_INTR;
else if (*newtok == '\0') {
PyMem_FREE(newtok);
tok->done = E_EOF;
}
#if !defined(PGEN) && defined(Py_USING_UNICODE)
else if (tok_stdin_decode(tok, &newtok) != 0)
PyMem_FREE(newtok);
#endif
else if (tok->start != NULL) {
size_t start = tok->start - tok->buf;
size_t oldlen = tok->cur - tok->buf;
size_t newlen = oldlen + strlen(newtok);
char *buf = tok->buf;
buf = (char *)PyMem_REALLOC(buf, newlen+1);
tok->lineno++;
if (buf == NULL) {
PyMem_FREE(tok->buf);
tok->buf = NULL;
PyMem_FREE(newtok);
tok->done = E_NOMEM;
return EOF;
}
tok->buf = buf;
tok->cur = tok->buf + oldlen;
tok->line_start = tok->cur;
strcpy(tok->buf + oldlen, newtok);
PyMem_FREE(newtok);
tok->inp = tok->buf + newlen;
tok->end = tok->inp + 1;
tok->start = tok->buf + start;
} |
首先调用PyOs_Readline，获得下一行。注意newtok所对应的内存是被malloc出来的，最后需要free。由于在交互模式下，第一句话的prompt是>>>，保存在tok->prompt中。从第二句开始提示符是...，保存在tok->nextprompt中，因此需要设置tok->prompt = tok->nextprompt。最后一个else if (tok->start != NULL)的作用是，一旦当读入下一行的时候，当前token还没有结束（一个典型的例子是长字符串"""可以跨越多行），由于buf原来的内容不能丢弃，下一行的内容必须加到buf的末尾，。PyTokenizer的做法是调用realloc改变buf的大小，然后把下一行的内容strcpy到buf的末尾。这样做虽然效率不高，由于一般情况下此种情况发生并不频繁，而且是处于交互模式下，因此性能上面没有问题。
文件模式下的处理比上面两种模式都复杂。主要原因是文件模式下一行可能比BUFSIZE大很多，因此一旦BUFSIZE不够容纳一整行的话，必须反复读入，realloc缓冲区buf，然后把刚刚读入的内容append到buf的末尾，直到遇到行结束符为止。如果tok->start != NULL，说明当前正在读入token之中，同样的当前的buf不能丢弃，因此读入的新一行的内容同样也要append到buf的末尾，否则，新一行的内容直接读入到buf中。由于代码比较多，这里就不给出了。
作者: ATField
E-Mail:
Blog: http://blog.csdn.net/atfield
发表于 @ 2006年12月12日 00:20:00|评论(2 )|编辑
评论
我最近在看龙书，上面有一个用DFA来识别字串的简单算法，我用Python写了一下，没问题，接下去有一个NFA转DFA的算法，用到了subset-construction来实现epsilon-closure的，也用Python写出来了，但是生成的DFA不知道如何使用，因为这个DFA的每一个状态，都对应着NFA的一个状态集，我不是计算机科班出身的没有理论基础，所以到这一步就不理解了，一个状态对应一个状态集？这样的DFA如何用？
不知楼主有空时能否讲解一下？
我在网上下载了几个Python的Parser，其中一个也用到了epsilon的算法来构造DFA，但还没来得及细看。
现在也就是简单地一问，先把心中的疑惑提出来，呵呵