编译原理概述

=谁能想到，有一天，百度百科上的资料，竟然也有料……

编译过程概述1

源程序是给人看的，本质上就是文本文件，可以用文本编辑程序打开、编辑，但计算机无法直接执行源程序，需要通过一个专门的程序将源程序编译为计算机可执行程序，这个专门的程序就是 编译器 。

编译过程主要分为词法分析、语法分析、中间代码生成、目标代码生成等。

词法分析

我们眼中看到的源代码，如下：

int fun(int a, int b);
int m=10;
int main()
{
int i=4;
int j=5;
m = fun(i,j);
return 0;
}
int fun(int a, int b)
{
int c=0;
c=a+b;
return c;
}

而它在计算机中存储的形式（十六进制形式）如下：

很显然，这里是看不出关键字、运算符、标识符，甚至看不出哪几个字符属于同一个符号。

与人相比，现在计算机的智能还是相当低的，无法像人那样同时看多个字符，只能依据一个非常机械的“电子版”词法，一个字符一个字符地识别。

词法分析器从源程序的字符串中识别出一个个符号（token），并按顺序保存。词法分析的结果如下：

在词法分析阶段能够识别出一些符号的含义，它们包括关键字、数字、字符串、分隔符，这些符号的含义不需要其他符号的辅助就能确定本身的含义。比如， int 一定代表整数类型，它不可能是一个变量名称，也不可能是一个运算符。

而另外一些符号则需要通过前后的其他符号才能确定出准确的含义。比如 m ，在词法阶段仅能判断这是一个标识符，但是如果不对所在的句做分析，就无法得知这个标识符代表一个变量还是一个函数。更多详细的信息需要对符号所在的句型做分析才能获得，这部分的工作由语法分析来完成。

语法分析

如果说词法分析的作用是从连续的字符中识别出标识符、关键字、数字、运算符并存储为 符号（token）流 ，语法分析的作用就是从词法分析识别出的符号流中识别出符合 C 语言规范的语句。

因为计算机无法像人那样同时看多个标识符、关键字、数字、运算符，无法像人那样一眼看出这是一个函数声明，那是一个 if 语句，只能非常笨拙地一个符号一个符号去识别。

与词法分析器有些类似，语法分析器也是依据用计算机表示的语法，一个符号一个符号地识别出符合 C 语言语法的语句。

语法的计算机表示就是 产生式 ，在语法分析器中把通过 产生式 产生的 C 语言语法映射成一套模板，并把这套模板融汇在语法分析器的程序中。语法分析器的作用就是将词法分析器识别出的符号（token）一个一个地与这套模板进行匹配，匹配上这套模板中的某个语法，就可以识别出一名完整的语句，并确定这条语句的语法。

我们以案例中 int fun(int a, int b); 这条函数语句为例描述这个过程，它与语句模板的匹配情况如下：

Figure：fun 函数声明语句与模板匹配的结果

这段 token 流最终与函数声明模板相匹配，在匹配成功后，计算机就认为此语句为函数声明语句，并以 语法树 的形式在内存中记录下来，如下：

Figure：fun 函数声明语句生成的语法树

以树型结构来记录分析出的语句是一个非常巧妙、深谋远虑、通盘考虑的选择。一方面，树型结构能够“记住”源程序全部的“意思”，另一方面，树型结构更容易对应到运行时结构。

从语法树到中间代码再到目标代码

至此，语法树已经承载了源程序的全部信息，后续的转换工作就和源程序没关系了。

如果希望一步到位，从语法树转换为目标代码，理论上和实际上都是可行的。但计算机存在多种 CPU 硬件平台，考虑到程序在不同 CPU 之间的可移植性，先转换成一个通用的、抽象的“CPU 指令”，这就是中间代码最初的设计思想。然后根据具体选定的 CPU ，将中间代码落实到具体 CPU 的目标代码。

语法树是个二维结构，中间代码是准一维结构，语法树到中间代码的转换过程，本质上是将二维结构转换为准一维结构的过程。中间代码特别是 RTL 已经可以和运行时结构一一对应了，如下图：

Figure：中间代码与目标代码对应的情景示意

运行时结构也是一维的，上图左侧部分的转换结果将更贴近运行时结构。

选定具体的 CPU、操作系统后，中间代码就可以转换为目标代码 – 汇编代码（这里我们配置的是 AT&T 汇编），这时操作系统是影响还比较小。然后由汇编器依照选定操作系统的目标文件格式，将 .s 文件转换为具体的目标文件，对于 Linux 而言是 .o 文件，对于 Windows 而言是 .obj 文件，目标文件中已经是选定的 CPU 的机器指令了。

最后，链接器把一个或多个目标文件（库文件本质上也是目标文件）链接成符合操作系统指定格式的可执行文件。

通过操作系统，可执行程序就可以被载入内存执行，形成运行时结构。

后续内容将详细讲解编译的主要过程：词法分析、语法分析、中间代码到目标代码，然后是汇编与链接，最后讲解预处理。

案例二2

让我们再来看一个具体案例来深化一下对编译过程的认识。

编辑器从逻辑上可以分为若干个阶段，每个阶段将源程序从一种表示变换成另一种表示（如下图），我们以将 Pascal 语言的 position := initial + rate * 60 为例子介绍编译的各个阶段。

1.词法分析

词法分析，又叫线性分析或者线性扫描。

逐个读取源程序的字符，把它们组成词法记号（token）流，并且把词法单元填入称号表。在这个阶段会删除掉分隔记号的空格，如下：

2.语法分析

语法分析，又叫层次分析。

将词法记号流按照语法结构进行层次分组，形成语法短语，语法短语常用分析树表示：

层次结构遵循的规则：

• 任何一个标识符都是表达式；
• 任何一个数都是表达式；
• 如果 e1 和 e2 都是表达式，那么 e1 + e2 、 e1 * e2 、 (e1) 也都是表达式。

3.语义分析

进行主义分析，生成语法树。其作用如下：

• 进行主义检查（其中包括类型检查），保证各部分能有意义的集合在一起；
• 搜集类型信息。

4.中间代码生成

经过语法分析和语义分析之后，某些编译器生成源程序的显示中间表示（易于产生、翻译成目标程序）。其功能如下：

• 需决定运算完成的次序；
• 必须产生临时变量名（保留每个语句的计算结果）；
• 必须处理控制流结构和过程调用。

中间表示的常用形式：三地址代码，如下：

*注： 三地址代码 由三地址语句序列组成，最多三个操作数。

5.代码优化

试图改进代码，产生执行较快的机器代码。

6.代码生成

生成可重定位的机器代码或者汇编码，其功能如下：

• 为源程序所用的每个变量选择存储单元（寄存器分配）；
• 将中间代码生成等价的机器指令序列。

7.编译的总过程

8.相关扩展

8.1 符号表管理

符号表：为每一个标识符保存一个记录的数据结构，记录的域是标识符的属性（标识符的存储分配、类型和作用域信息）。

8.2 错误诊断与报告

每个阶段都有可能发现源程序的错误，在发现错误之后，该阶段必须处理此错误，使得编译可以继续进行，以便进一步发现源程序的其他错误。具体：

• 词法分析阶段：诊断当前被扫描的字符串不能形成语言的词法记号；
• 语法分析阶段：诊断记号流违反的语法规则；
• 语义分析阶段：找到对所含操作无意义的结构。

8.3 阶段分组（前端和后端）

在实际编译中，若干阶段可以组合在一起，各阶段之间的中间表示也无需显示构成。通常所有阶段分为前端和后端：

（1）编译前端

只依赖于源程序，由几乎独立于目标机器的阶段或者阶段的一部分组成，包括：词法分析、语法分析、符号表建立、语义分析、中间码生成、部分代码优化以及与这些阶段同时完成的错误处理。

（2）编译后端

依赖于目标机器，一般独立于程序，而与中间代码有关。包括：代码优化、代码生成以及伴随着这些阶段的符号操作和错误处理。

8.4 一遍扫描

编译的几个阶段常用一遍扫描来实现，一遍扫描包括读一个输入文件和写一个输出文件。

把几个阶段组成一遍，并且这些阶段的活动可以在该遍扫描中交错进行。例如，可以把语法分析看成主导，当它需要记号时，调用词法分析器去下一个记号。如果已经看出一个语法结构，语法分析器则激活中间代码生成器，以完成语义分析和生成中间代码。

8.5 相关工具

翻译器 是一种能够将一种语言（源语言）变换成另一种语言（目标语言）的软件。

编译器 是一种翻译器，将高级语言变换成一种低级语言的软件，特点在于目标语言比源语言低级。

解释器 也需要对源程序进行词法、语法和语义分析，中间代码生成。但是不生成目标代码，而是直接执行源程序所指定的运算。

编译原理三大经典

龙书是 Alfred V.Aho 等人于 1986 年出版的，由于出版年代较早，其中包含部分过时的技术并且没有反映一些新的编译技术。新编的《编译原理》抛弃诸如算符优先分析等过时技术，增加面向对象编译、类型检查等新技术。

虎书出版比较晚，与《编译原理》的知识点差不多，但增加了数据流分析、循环优化、内存管理等内容。与虎书比，《编译原理》更适合国内的编译原理课程教学，有 C 版、Java 版和 ML 版。

鲸书侧重在对编译器后端优化的处理。在本科阶段的编译教学中旨在让学生对程序设计语言的编译全过程有系统的理解，因此会介绍编译器后端的处理技术，但不注重优化技术。鲸书更适合作为研究生的教材或参考书。