ecnelises

My blog, collection and entry

构建Mao语言运行器-词法分析

这个世界的本质是无序的。所以编程最广泛也是最常被讨论的用途就是处理在计算机看来什么意义也没有的字符串。而处理编程语言的源代码在其中是很特殊的一种,因为编程语言包含的信息按照一定的规则聚合,解析起来比自然语言容易得多。而处理编程语言的源代码的时候该干什么,取决于软件的目的以及这门语言本身的特性。

好了,言归正传,说说这次的期末作业Mao语言吧。一开始很多同学估计还没反应过来是怎么一回事。以为做一个解释器只要用宏替换就可以了。另外一些人估计连解释器编译器的区别都没有分清楚。讲道理的话,大一的期末项目不太可能要求学生做编译器的,那么多数据结构都没学,汇编也不懂,没法弄。

那么什么是解释器呢?

解释器是能够执行用其他计算机语言编写的程序的系统软件,它是一种翻译程序。 它的执行方式是一边翻译一边执行,因此其执行效率一般偏低,但是解释器的实现较为简单,而且编写源程序的高级语言可以使用更加灵活和富于表现力的语法。

懂了没?一边翻译一边执行。读入输入然后处理的作业在之前也做过不少,所以有人想到一个一个“单词”地做。关键是,我们处理这些源代码的基本单位是什么?先来看看范例里的一段代码。

c
int a;
double x, y;
int b, c, d;
a=5.5;
x=y=(1+a)*6.44;
a+4;
a=a/2;
print(a);
y=(c+6)*-(1+1);
print(y);
d=a/(2/5);
print(d);

这段代码基本上涵盖了Mao语言所有能用到的符号。仔细观察可以发现,关键字只有int和double,如果把print写死进去那就是三个。程序中可以出现任意的空格,因此我们需要把这些空格要么去掉要么屏蔽掉。变量名可以是一个字母也可以是很多个字母和数字的组合,当作一个char来弄显然也不行。我们需要一个专门的过程来将源代码里的“多个字符”映射到一个单位里。我们理想的结果应该是生成一个更有结构的数据流,其中一个符号(int、变量名或者是运算符)是一个单位,没有空格的存在。这样的话,很多东西就方便很多了。

这个扫描源代码生成结构化数据流的过程就叫做词法分析。大多数编译器或者解释器接收到源代码做的第一件事就是词法分析。词法分析生成的东西叫做token,记号还是符文还是什么,随便翻译。显然,我们要做词法分析,就要把整个源代码字符串遍历一遍,并且扫描完之后就可以把它丢掉了,之后的处理是针对这个数据流而不是纯文本进行的。在整个编译或者解释执行的过程中,对源代码或者它对应的信息我们需要过不止一趟 (pass)。多趟的处理也许对效率有影响,但是实现更加简单。所谓one-pass的编译器,很多时候只是作者的炫技之举。当然,对语法极其简单的Mao语言,这不是不能做,只是写得太杂乱就会失去很多乐趣。

好了,如何定义我们的数据结构呢?比如:

c
struct token {
int type;
char * content;
};

这是最简单的形式。content表示什么自不必说,可以指变量名或者整数浮点数。而更多的固定形式的符号,我们直接用type表示,然后把content设为NULL即可。

```c

define TOKEN_INT 1

define TOKEN_DOUBLE 2

define TOKEN_PRINT 3

define TOKEN_VARIABLE 4

define TOKEN_INTNUM 5

define TOKEN_DOUBLENUM 6

define TOKEN_COMMA 7

define TOKEN_SEMICOLON 8

define TOKEN_ADD 9

define TOKEN_SUB 10

define TOKEN_MUL 11

define TOKEN_DIV 12

define TOKEN_ASSIGN 13

define TOKEN_LPAREN 14

define TOKEN_RPAREN 15

```

整个Mao语言的符号不超过这区区十五种。规定好了token的结构和type的取值,我们就可以开始扫描的过程了。

开始这个扫描的过程应该不算是什么难事。我们从输入的第一个字符开始判断,就像《C程序设计语言》里常用的那样:

c
char ch;
while ((ch = getchar()) != EOF) {
/*
* 对输入字符的类型进行判断
* 如果是一个字符,我们进入处理字母集合(类型、print或变量名)的函数
* 如果是加减乘除等符号,我们进入处理运算符的函数
* 如果是数字或者点号,我们进入处理整数或浮点数的函数
*/
}

那么对此,我们可以声明这样的一堆函数:

c
void type_var(char ch);
void number(char ch);
void symbol(char ch);

这些函数内部是如何运作的呢?举个例子:

c
void type_var(char ch)
{
char tmp[20];
size_t index = 0;
do {
tmp[index++] = ch;
} while ((ch = getchar()) != EOF && isalnum(ch));
tmp[index++] = '\0';
if (!strcmp(tmp, "int")) {
/* 将当前流指向的token设置为TOKEN_INT */
} else if (!strcmp(tmp, "double") {
/* 将当前流指向的token设置为TOKEN_DOUBLE */
} else if (/* 其他情况 */) {
/* 对应的处理 */
} else {
/* 不是关键字,那么定义成变量名,TOKEN_VARIABLE */
}
ungetc(ch, stdin); /* 退回一个字符输入 */
/* 流指针向前进 */
}

显然,这个词法分析程序会自动获取能够最大接收的token,并且不需要手动写,自动就排除掉了空格,并且将每个变量名与逗号分隔了开来。

由于Mao语言的符号数量很少,并且各个类型的token规则特意设置得很简单(浮点数甚至不包含科学计数法的形式)。写一个tokenizer还是非常容易的。不过又一个还没有提到的东西,就是词法分析整数或者浮点数的时候,前面的正负号会被识别成加减号。当然这个问题无关紧要,讲道理的话在后面的语法分析阶段也能解决。不过就当作一个练习吧。

词法分析就到这,下次来说说语法树的事情。