1.6 编译概览

例1.16

编译的各个阶段

An Overview of Compilation

编译器是各种计算机程序中被研究得最仔细的程序。在一个典型的编译器里，编译过程需要通过一系列良好定义的阶段，如图1.2所示。每个阶段找出后续阶段需要的一些信息，或者把程序变换到某种更适合后续阶段的需要的形式。

前面几个阶段（直至语义分析）的作用是挖掘出源程序的意义，有时将它们称为编译器的前端。后面几个阶段的工作是构造出等价的目标程序，有时称它们

图1.2 编译的各个阶段。各个阶段列在右边，在各个阶段之间传递的信息的形式列在左边。符号表服务于整个编译过程，作为有关程序里的各种标识符的公共信息源。

为编译器的后端。编译器中的许多阶段可以通过对源语言或目标语言的某种形式化描述自动构造出来。

例1.17

Pascal里的
GCD程序

有时也会听到人们把编译描述为一系列编译遍（passes），一个编译遍包含一个或几个编译阶段，一个编译遍里的阶段与编译过程的其他工作按前后顺序进行，在前面阶段完成之后才开始工作，在其后续阶段开始之前结束。如果需要，我们可以将一个编译遍写成一个独立的顺序程序，让它从一个文件取得输入，将输出写进另一个文件。编译器一般分成几遍，使其前端可以由多个为不同机器（目标语言）所用的编译器共享，并使其后端可以由多种源程序的编译器共享。在20世纪80年代后期内存规模大大增长之前，有时将编译器分割为几遍也是为了减少存储使用量。当一遍完成后，下一个编译遍就可以重用其代码空间。

1.6.1

1.6.1 词法和语法分析

Lexical and Syntax Analysis

考虑本章开始时介绍的求最大公约数（GCD）的程序。用Pascal写出的这个程序是下面的样子：

例1.18

GCD程序里的单词

扫描和语法分析的作用是识别程序的结构，而根本不管它们的意义。扫描器读入一个个的字符（'p'、'r'、'o'、'g'、'r'、'a'、'm'、' '、'g'、'c'、'd'等等），并将它们组合成单词，也就是程序中最小的有意义的单位。在我们例子里的单词是：

例1.19

上下文无关文法和语法分析

扫描又称为词法分析（lexical analysis）。扫描器的主要作用就是为了简化语法分析器的工作，它能减小输入的规模（组成程序的字符比单词多得多），删除额外的字符。扫描器通常还删去注释，如果需要就生成一个表格，给各个单词做好行列位置标记，以便后续阶段能更容易生成很好的诊断信息。完全可以设计一个直接以字符而不是以单词作为输入的语法分析器，从而完全抛弃扫描器，但这样做的结果将会是笨拙而低效的。

语法分析阶段将单词组织为一棵语法分析树（parse tree），基于程序的各个组成部分表示其高层结构。这些部分的组合方式通过一组可能递归的规则定义，这样的一组规则称为一个上下文无关文法（context-free grammar）。举个例子，我们知道Pascal程序的组成方式：有一个关键字program，随后是一个标识符（程序的名字），一个括起的文件表，一个分号，一系列的定义，而后是主begin…end块，由一个圆点结束：

其中

还有

或者

这里的ε表示空串，说明more_ids可以直接删除掉。当然还需要更多的文法规则，以解释一个程序的所有结构。

例1.20

GCD程序的语法分析树

我们说这种上下文文法定义了语言的语法形式，因此这种分析过程也就是做语法分析。可以写出许多可能的Pascal文法（实际上有无穷多），上面显示的片段是粗略地基于“圆圈和箭头”语法图，在原始的Pascal文本 [JW91] 中可以看到它们。图1.3展示的是上面GCD程序的完整语法分析树（基于并没有在这里给出的完整文法）。这种图的复杂性主要来自于：（1）其中使用了一些像more_stmts和more_exprs一类的人为“结构”，用于表示任意长度的序列；（2）采用了同样人为的term、factor等，以表现出算术表达式里的优先级和结合关系。第2章将讨论文法和语法分析树的更多细节。

在扫描和语法分析过程中，编译器需要检查程序里的所有单词是否都构造良好，单词序列是否符合上下文无关文法所定义的语法。任何畸形的单词（如在Pascal里遇到123abc或$@foo）都将导致扫描器产生错误信息，任何不符合语法的单词序列（如在Pascal里遇到A:=B C D）将导致语法分析器产生错误信息。

1.6.2

1.6.2 语义分析和中间代码生成

Semantic Analysis and Intermediate Code Generation

语义分析也就是确定程序的意义。编译的语义分析阶段需要识别出什么时候同一单词的多个出现引用的是同一个程序实体，并且要保证这些使用的相容性。在大部分语言里，语义分析器需要跟踪标识符和表达式的类型，这既是为了验证使用的相容性，也用于指导后面阶段中的代码生成。

为了支持所需的工作，语义分析器通常构造并维护着一个符号表（symbol table）数据结构，符号表把每个标识符映射到有关它的已知信息。这些信息包括标识符的类型信息、内部结构（如果有的话），以及作用域（程序中的一个部分，在其内部该标识符合法）。

利用这一符号表，语义分析器就能贯彻执行许多分析规则，这些规则是上下文无关文法和语法分析树无法表示的。举例说，它检查并确定以下各项。

¨ 每个标识符在使用之前都已有定义。

¨ 没有标识符被用在不合适的上下文中（例如把整数作为子程序去调用，把一个字符串加到一个整数上，引用一个错误的记录类型里的某个域，等等）。

¨ 为子程序调用提供的是数目和类型都正确的实际参数。

图1.3 对应GCD程序的语法分析树。其中的ε表示空串。本图中很明显的复杂层次结构是人为的，为了让源代码（比较简单）适合上下文无关文法的层次结构。

¨ case语句各个分支的标号是互不相同的常数；

¨ 每个函数里至少包含了一个刻画其返回值的语句。

在许多编译器里，语义分析的工作通过一组语义动作子程序的形式表示，当语法分析器发现自己当时到了某个产生式里的一个特定点时，就会去调用其中的某个子程序。

当然，并不是所有语义规则都能在编译时检查，上面提到的这些称为语言的静态语义（static semantics），必须在运行时检查的就称为语言的动态语义（dynamic semantics）。必须在运行时检查的规则（的例子）包括：

¨ 除非变量已经被给定了值，否则它绝不会在表达式里使用；

¨ 除非指针已经约束到一个合法的对象，否则它绝不会被间接（dereferenced）；

¨ 数组的下标表达式的值位于数组的范围之内；

¨ 每个函数在返回之前都已经确定了返回值。

当编译器无法静态地贯彻某些规则时，通常它就会生成一些代码，让这些代码在运行中执行适当检查。如果某个检查失败，这个程序就会终止或产生一个异常（异常的概念将在第8.5节讨论）。不幸的是，有些规则的贯彻可能带来极高的，甚至根本无法接受的代价，或者根本就是不可能贯彻的，这时语言的实现可能根本就不去检查它们。Ada的参考手册里正式定义了一些不必贯彻的规则，那里说，违背这些规则的程序根本就是错误的程序。在C语言里说这时的行为无定义。

例1.21

GCD程序的抽象语法树

语法分析树有时也被称作具体语法树，因为这种树中的一切都是明示的，完全而又具体，显示了如何根据相应的上下文无关文法推导出特定的单词序列。一旦我们知道了一个单词序列为合法之后，后续的编译阶段就不再需要语法分析树上的许多信息了。在检查静态语义规则的过程中，语义分析器通常还同时把这种语法分析树转换为一棵抽象语法树（又称AST，简称语法树），删除树里的大部分“人为”结点。语义分析器还为剩下的结点标注各种有用的信息，例如加入从标识符到对应符号表项的指针。附在特定结点上的标注被称为它的属性。我们的GCD程序的语法树如图1.4所示。

在许多编译器里，带标注的语法树就是从前端传递到后端的中间形式，而在另一些编译器里，语义分析器最后还要对这棵树做一次遍历，生成另外的某种中间形式。这一形式通常类似于某种特别简单的理想机器的汇编语言。对于一组相

图1.4 GCD程序的语法树和符号表。与图1.3不同，这一语法树里只剩下程序的基本结构了，那些仅仅为了驱动语法分析器的需要而存在的细节都没有了。

关的编译器，几种语言的前端和为几种机器服务的后端可能共享着同一种中间形式。

1.6.3

1.6.3 目标代码生成

Target Code Generation

例1.22

GCD程序的汇编代码

编译器的代码生成阶段把中间形式翻译到目标语言。有了语法树中所包含的各种信息，生成正确的代码一般说并不是很困难的工作（生成好的代码则是很困难的，我们将在第1.6.4节看到这方面情况）。为了生成汇编语言或机器语言，代码生成器需要遍历整个符号表，给各个变量指定位置；还要遍历语法树，为变量引用生成装入和保存动作，插入到适当的算术运算、检测和分支中。图1.5展示的是GCD例子的MIPS汇编语言的朴素代码，这是由一个简单的教学用编译器自动生成的。

汇编语言的助记形式看起来有点像密码，但每行右边的注释（这些当然不是编译器生成的！）应该能把图1.4与图1.5之间的对应关系表示清楚。这里有几点提示：sp、ra、at、a0、v0和t0—t9都是寄存器（特殊的存储位置，数量有限，但可以极其快速地访问）。28(sp)表示从寄存器sp里的地址向下28个字节的存储器位置。jal是子程序调用（jump and link，转跳和连接），第一个参数通过寄存器a0

图1.5 GCD程序的MIPS汇编语言的朴素代码。

传递，返回值由v0送回。nop表示“空操作”，它不做任何有用的工作，但能使程序延迟一个时钟周期，等待一个两周期的装入或分支指令的完成（分支和装入延迟是早期RISC机器的常见特性，我们将在第5.5.1节考虑它们）。算术运算通常对其第二个和第三个参数进行，结果存入第一个参数。

代码生成器常常把符号表也保存起来，以便后面的符号调试器使用。例如可以将符号表包含在目标代码里，作为注释或其他非执行的部分。

1.6.4

1.6.4 代码改进

Code Improvement

代码改进通常被说成是优化（optimization），虽然从所有绝对的意义上看，它很难将任何东西做成最优的。这是编译过程中一个可选的阶段，其目标就是把程序变换到一个新版本，该版本能更有效地计算出同样的结果——速度更快或者使用更少的存储，或者两方面都更好。

例1.23

GCD程序最优化

有些改进是与机器无关的，可以在中间形式上通过一些变换完成。另外一些改进则需要深入了解目标机器（了解目标语言里的程序将如何执行），必须通过对目标语言的变换完成。这样，代码改进将表现为编译过程里的另外两个阶段，一个在刚刚做完语义分析和中间代码生成之后做，另一个在做完目标代码生成之后做。

把一个优秀的代码改进器应用于图1.5的代码，生成的代码将如例1.2（第3页）所示。比较这两个程序就可以看出，改进后的代码版本确实短了许多。最显著的变化是大部分装载和保存指令都不见了。与机器无关的代码改进器可以确定，在整个主循环的执行过程中，i和j的值都可以一直保存在寄存器里（譬如说，如果循环中包含了一个子程序调用，其中有可能使用这些寄存器，或者可能修改i和j的值，那么我们就不能这样做了）。随后，专门针对具体机器的代码改进器就可以为i和j指定目标机器里的实际寄存器。在我们的例子里，专门针对具体机器的代码改进器还能对指令进行调度（重排顺序），删除其中一些空操作指令。仔细检查跟在装入和分支之后的那些指令，可能发现它们确实都可以在装入和分支没有完成之前安全地执行。对于最新的微处理器体系结构，特别是那些通常称为超标量（superscalar）RISC指令集的体系结构（其中有若干个独立的可以并行执行指令的功能单元），编译器生成出的代码通常可以比汇编程序员写的代码更好。

检查你的理解