编译器的过程,是把程序从一种表现形式转换为另一种表现形式。

程序员编写的称为「源代码」,是可读性很强的文本。先经过预处理器(preprocessor)处理,将「源代码」转换成「最终版源代码」。也就是去除了所有宏指令,最常见的是#include#define。在完成这一文本包含和替换工作之后,才成为一个真正的被编译器接受的文件。

接下来,编译器读取经过预处理的源代码,对它进行词法分析,将源代码识别成一个个的「词素」(token)。比如以下的源代码:

if (a >= 9.8) {
    b = "hello, world!";
}

源代码中包含各种空白符,比如空格和换行,这些都被词法分析器所忽略。

if
(
a
>=
9.8
)
{
b
=
"hello, world!"
;
}

词法分析器将输出上面的结果。因此,对后面的语法分析器来说,它不用烦恼如何处理输入缓冲、分割词素等等细节,这些都是词法分析器该做的事。语法分析器面对的是一个个已经处理的词法单元。

接着,语法分析器读取并根据语法产生式,分析词素,生成一颗抽象语法树(Abstract Syntax Tree)。紧接着的是语义分析,因为符合语法产生式的代码并不一定符合语义,譬如 case 语句只能出现在 switch 语句中,全局数组下标必须是常量表达式等等。语义分析无任何错误后,交由后端处理,后端读取抽象语法树,并生成汇编代码。至此,编译器的工作完成。然而,编译器驱动会继续调用汇编器和链接器,最终生成可执行的机器代码。

整个流程的编程思想有:

  1. 模块化原则。或者说是一个模块只做一件事并把它做好。编译器被分割成预处理、词法分析、语法分析、语义分析、代码生成这几个模块。前一个模块的输出,将作为后一个模块的输入。

如何处理输入


经典的做法是使用双缓冲区

|     buffer1      |           buffer2                      |
                         |                      |
                  当前词素的第一个字符       <指针的当前位置>

文件被读取到 buffer2 分析,但由于词素可能超出 buffer2 的长度,因此需要一个 buffer1 来缓存:每当指针指到 buffer2 的末端时,仍未形成一个完整的词素,就会将当前词素的头部开始到 buffer2 的末端为止的这段文本复制到 buffer1 的末尾,然后继续读取文件到 buffer2,这样就形成连续不断的读取了。

双缓冲区的优点十分明显,就是无论输入文件多大,词素有多长,我们都可以使用一个定长的缓冲区完成词法分析。缺点就是如果词素太长,就需要分配堆内存来保存当前部分词素,待整个词素都读取完毕后合并。当然,编译器为了避免这个缺点,可以人为限制词素的长度,譬如可以限制标识符不能超过64个字符、一行的长度不能超过4096字符等等。这可以满足大部分情况。

另一种更为简单直接的方法是,把整个经过预处理的源文件读取到内存中。优点也十分明显,词法分析将显得十分简洁。缺点就是,源文件可能非常大。当然,现在的机器内存都很大,这种做法也是可以满足大部分情况的。

处理行连接符:’\’


行连接符的存在使得词法分析不再单纯:简单的处理方法是写一个形如 read_char 的函数,处理行连接符并返回真正的字符,这种做法使得代码非常简洁,缺点是速度太慢了。GCC 采用了另一种方法:每次都处理出一个完整的逻辑行(即处理掉行连接符后的行),这样词法分析就依然可以通过字符指针递增来分析 token。GCC 甚至把这个函数(_cpp_clean_line)用 SSE 等汇编指令优化。

小结


词法分析本身很简单,问题大概如上所述,但是对于C语言而言,最重要的部分是预处理器,上面没有涉及,预处理本身看似简单,但却有一些匪夷所思的corner case,除了核心的宏展开算法外,最典型的就是对空格的处理,以及对展开后的token坐标的处理,这将在以后描述。