下载掌阅APP，畅读海量书库
立即打开
编译器的任务是将源代码翻译为目标机器上的目标代码。图1.2中展示的三段式编译器架构把编译过程分为前端、中端与后端：前端与目标机器无关，其对源代码进行一系列的分析和检查，在保证源代码词法、语法、语义正确性的前提下，将源代码翻译为中间代码；中端进行一系列的静态检查与代码优化，检测并报告程序内部可能存在的缺陷，去除冗余代码；后端将中间代码翻译为目标代码，分配寄存器，进行代码的汇编与链接。设计一门新的程序设计语言时，开发者只需要开发针对语言的前端，复用已有的编译器后端，就能将语言源代码翻译为目标机器的机器指令，大大增强了编译器模块的可复用性。同时，语言设计者不需要掌握后端开发的相关技术，降低了语言设计的难度。
图1.2 三段式编译器架构
编译的每个阶段中包含了不同的步骤，编译器完成步骤时将代码从一种表示形式转换成另一种表示形式，如图1.3所示。通常，编译器前端包含三个步骤：词法分析、语法分析和语义分析。词法分析器将源代码拆成词素，分析每个词素是否满足词法规则，并把词素组合为词法单元流；语法分析器读入词法单元流，基于语言的语法规则推导并构建语法分析树；语义分析器分析程序是否满足语义规则（如变量的类型等）并在语法分析树上添加注释。编译器中端将词法、语法、语义正确的，代表程序的注释语法树翻译为中间代码，部分编译器基于中间代码设计优化管道，进行针对中间代码的优化。编译器后端接受中间代码，将其翻译为目标机器相关的目标代码，并进行针对目标代码的相关优化。
图1.3 编译器各模块及中间产物
本书使用一种类C语言 （C--语言） 来说明编译器如何完成编译过程。
词法分析 是编译的第一个步骤。 词法分析器 读入源程序的字符信息，将它们按照一定规则组成 词素 ，并检查每一个词素是否符合 词法规则 。若所有词素均符合词法规则，词法分析器生成并输出 词法单元流 。
程序设计语言通常只包含几种有限的词法单元类型，用于表示程序内部的变量、数据结构、运算符、控制流和表达式等。例如，对于我们使用的C--语言，源代码中有如下的赋值语句：
赋值语句中包含如下的词素：
● int 是一个词素，表示变量的类型，映射为词法单元 TYPE 。
● i 是一个词素，表示一个变量，映射为词法单元 ID 。
● = 是一个赋值运算符，表示赋值关系，映射为词法单元 ASSIGNOP 。
● 123 是一个词素，表示一个整数，映射为词法单元 INT 。
● ； 是一个词素，表示一条语句的结束，映射为词法单元 SEMI 。
于是，赋值语句所对应的词素可以组成如下的词法单元流：
每个词法单元都有对应的词法规则，如C--词法规则中，能够表示为词法单元 INT 的词素只包含一连串的数字，不能出现其他符号。词法分析器是一个有限状态机，当一个词素不满足当前程序设计语言的所有词法规则时，将输出词法错误报告。
同时，如果一个词素是一个变量，词法分析器会收集变量的符号属性（类型信息等），记录到一个符号表中，符号表中的条目可用于语义分析和中间代码生成。
在第2章中，我们将讨论以下内容：
●使用正则表达式描述词素模式，正则表达式能够精准高效地描述词法规则。
●使用有限状态自动机进行词法规则匹配。
●从 NFA （非确定性有限状态自动机）到 DFA （确定性有限状态自动机）的转换算法。
●状态最小化算法，最终设计构造一个简洁且高效的词法分析器。
语法分析 是编译的第二个步骤。 语法分析器 读入词法单元流，基于语言的语法规则推导并构建 语法分析树 ，若输入的词法单元流在语法规则下能够被推导并构建为语法分析树，则认为该程序不包含语法错误，语法分析器输出语法分析树，交予语义分析器进行语义检查。
例如，对于词法分析获得的词法单元流：
其通过语法分析构造的语法分析树如下：
语法分析器分析得知，这条语句是一条赋值语句，首先声明了变量 i （ VarDec ），然后给 i 赋值为 123+b＊c 。语法推导过程中，符号的归约具有 优先级 ，例如乘法的运算优先级高于加法，乘法应当在加法之前进行计算，因此首先归约 b＊c ，然后归约 123+b＊c 。
在第2章中，我们将讨论以下内容：
●上下文无关文法，几乎所有程序设计语言的语法规则都是通过上下文无关文法来定义的。
●自顶向下的语法分析算法。
●自底向上的语法分析算法。
语义分析器 将语法分析树与词法分析中构造的符号表相关联，检查源程序是否满足语言所定义的语义规则。语义分析器同时提取变量的类型信息，以便于中间代码的生成。语义分析器输出修饰语法树，给语法树赋予了语义信息。
例如，对于语法分析树：
语义分析器分析等号右端表达式的类型是否与被赋值的变量 i 一致。当 i 、 b 、 c 均为 INT 类型时符合语义规则。
语义分析的一个重要工作是做类型检查，语义分析器检查构成表达式的每个运算分量是否具有符合语义规则的类型，如下标应为整数，等号两侧的值类型应当相同等。
在第3章中，我们将讨论以下内容：
● 属性文法 ，属性文法是一种形式化方法，通过在语法分析树上添加属性，并基于添加的属性进行计算和推导，若推导结果有矛盾则存在语义错误。
● 语法制导的定义 ，语法制导的定义将属性文法和翻译方案结合起来，并能够快速反馈到源代码层面，有助于快速修复源代码中的错误。
●实现属性文法和语法制导的算法。
在编译的过程中会生成多种中间表示形式，如语法树、词法单元流等，不同的中间表示形式可满足编译各任务的需要，比如语法分析树有利于在编译过程中进行静态检查。
在完成语义分析后，编译器前端的工作告一段落。编译器将语法分析树转化为更适合代码优化及目标代码生成的形式，这一过程被称为中间代码生成。我们关注一种中间表达形式： 三地址码 ，每个指令具有不多于三个的运算分量，这种形式与机器码中寄存器的读取和计算类似。
例如，对于语法树：
生成的三地址码为：
中间代码生成器按照表达式的执行顺序（后序遍历语法树），将语法树转化为中间代码。在第4章中，我们将讨论以下内容：
● 中间代码的表示形式 ，不同的中间代码表示形式及其优劣。
● 类型和声明的相关概念 （例如，类型表达式、类型等价、局部变量名的存储布局、类型声明和类型记录等表达式的生成）。
● 表达式翻译策略 。
目标代码生成器将中间代码转化为机器相关的目标代码，并为变量进行寄存器的分配。分配寄存器之后，将目标代码转化为机器指令。完成目标代码生成后，程序从人类能够理解运用的源代码转化为机器能够执行的机器指令。
例如，对于中间代码：
生成的目标代码为：
程序依序将变量 b 和 c 的值存储到寄存器中，首先进行乘法的计算，然后进行加法的计算，最后执行赋值语句，存储运行结果。
在第5章中，我们将讨论以下内容：
● 寄存器分配算法 ，寄存器的合理分配和使用是目标代码生成的重要一环。
● 目标代码优化策略 。
● 代码生成器构建过程 。
基于中间代码的优化不需要考虑源语言与目标语言之间存在的差异，是独立于前端和后端进行优化的全部过程。一系列连续重写中间代码以消除效率低下和无法轻易转换为机器代码的代码片段的方法或函数构成了编译器的中间代码优化模块。不同编译器对优化管道及优化模块的执行顺序的设计都不同，这也导致了不同的优化效果与时空开销。
例如，对于中间代码：
其进行子表达式消除与无用代码消除后的中间代码为：
在第6章中，我们将讨论以下内容：
● 数据流分析框架 ，中间代码优化器使用此框架作为优化算法的模板。
● 数据流分析模式 ，优化器基于分析模式构造优化算法。
● 中间代码优化各模块 （常量传播、公共子表达式消除、无用代码消除、循环不变代码外提、归纳变量强度削减等） 的实现技术 。