编译器的结构

引言——没有谁是一座孤岛，编译器也一样

程序设计语言是向人以及机器描述计算过程的记号，这个世界依赖于程序设计语言，因为在所有计算机上运行的所有软件都是用某种程序设计语言编写的，但是，在一个程序可以运行之前，他需要先被翻译成计算机可以执行的形式。做这个翻译工作的就是编译器。简单来讲，编译器就是一个程序，他可以阅读某一种语言编写的程序，并把该程序翻译成为一个等价的、用另一种语言编写的程序。

——引自《编译原理（第二版）》第一章引论部分

编译器的基本任务：将源语言程序翻译成等价的目标语言程序

上文中引言可能也会造成些许理解误差，把源语言程序转换成计算机可执行文件有可能不完全是编译器独自完成的，编译器并不是孤军奋战，他也有很多同伴与之携手一同把源代码转换成机器上的可执行文件，在上一章对翻译程序的介绍中我们说过，翻译程序可能有很多部分组成，编译器可能只是其中一部分。创建一个可执行的目标程序可能还需要一些其他程序：

• 预处理器：一个源程序很可能被分成多个模块，并存放在独立的文件中，预处理器可以把源程序聚合在一起，同时还负责把那些称为宏的缩写转换为源语言的语句。
• 编译器：将源语言程序翻译成等价的目标语言程序（可能产生汇编程序作为输出，因为汇编语言比较容易输出和调试）
• 汇编器：将汇编程序转换为可重定位机器代码
• 链接器：大型程序经常被分成多个部分进行编译，因此可重定位的机器代码有必要和其他可重定位的目标文件以及库文件链接在一起，形成真正的机器上运行的代码。链接器就是解决外部内存地址引用的问题。
• 加载器：把所有可执行目标文件放在内存中执行

OK，我们介绍了编译器和编译器的伙伴，那么接下来一起窥探一下编译器神秘表象下的内部结构吧。

编译器内部结构概览

在我么开发者视角上，我们写完代码，之后之间编译运行，其实更多的时候对于编译器是无感知，可能更多的时候点击运行，之后呐喊link start！代码就跑起来了，当然估计没什么人会像这样有仪式感（其实正常人称呼这样的行为是中二）。所以编译器对于我们就像是一个黑盒子，我们把这个盒子打开一点，就可以看到里面包含两个部分：

• 分析部分
• 综合部分

经常分析部分被称为前端，综合部分被称作后端。

分析部分（前端）

分析部分把源程序分解成多个组成要素，并在这些要素之上加上语法结构。然后，它使用这个结构创建该程序的中间表示。当然在这个阶段如果检查出程序的语法错误，或者语义不一致，就必须提供有用的信息，使得用户可以将其改正。

分析部分还会收集有关源程序的信息，并把信息存放在一个称为符号表的数据结构中（后期寒草：“符号表在后面也会多次提到哦～”）。符号表和中间代码表示会作为综合部分的输入。

综合部分（后端）

综合部分根据中间表示和符号表中的信息来构造用户期待的目标程序。

编译器分步骤介绍

在上一段我们把编译器分成了两个阶段：前端和后端。但是如果我们能加详细的研究编译过程，会发现他会顺序执行一组步骤，一个典型的把编译原理分解成多个步骤的方式下面两个图片。当然在实践中，多个步骤可能会被组合在一起，而组合在一起的步骤之间的中间表示不需要被明确构造。存放整个源程序的信息的符号表可以由编译器的各个步骤使用。

其中为了综合部分（后端程序）可以生成更好的目标程序，如果基于未经过优化的中间表示来生成代码，则代码质量会受到影响，所以可能会加入代码优化阶段。图中的两个代码优化阶段可以被省略。

所以我们进行一个简要的总结，其实整个步骤可以大致描述为以下几个阶段：

• 词法分析
• 语法分析
• 语义分析
• 中间代码生成
• 中间代码优化
• 目标代码生成

词法分析

介绍

编译器的第一个步骤是词法分析，词法分析的输入是源程序的字符序列。识别每一个单词及其种类，并将其表示成TOKEN形式：

tip:

• 词法分析阶段不依赖于语言的语法定义
• 词法分析的结果是语法分析的输入

词法分析还可以做到：

• 检测标识符拼写错误
• 去掉代码中的注释

举例

举个例子大家可能就懂了：

float sum, first;
sum = first + 10;

上面是一段简单的代码，那么我们进行词法分析：

可能实现的话有差异，此处为了大家可以理解的更加清楚，所以一切从简，但是我们依然可以按照这个来理解，我想大家可能看完例子，就大概明白了这个过程。

为什么第一个sum变成了标识符 1 呢，其实标识符后面对应的值其实指向了符号表的引用，后面first对应2也是这个道理

词素：语法功能的最小单位，上面 float，sum，first，+ 等都是一个词素。

语法分析

介绍

语法分析是编译器的第二个步骤，语法分析会使用词法分析生成的TOKEN序列，并依据源语言的语法规则生成树形的中间表示。该中间表示给出了词法分析产生的词法单元流的语法结构。

tip：

• 分析时如果发现错误，则输出错误的位置以及类型
• 未发现错误则将语法分析的输入（词法分析的输出）转换为树形中间形式，常用的方法是语法树

语法树：树中的每个内部节点表示一个运算，而该节点的子节点表示该节点的子节点表示该运算的分量。

输入：

• 当词法分析程序时语法分析程序的子程序时：输入为源程序的字符序列
• 当词法分析是独立的：输入是TOKEN序列

举例

继续前面词法分析的例子来看。 首先我们的例子还是sum=first+10。他所对应的词法分析TOKEN序列是：

<标识符，1>  <运算符，=> <标识符，2> <运算符，+> <整形常量，10> <分隔符，；>

其中 1对应sum，2对应first。

语义分析

介绍

编译器的第三个步骤是语义分析，该能力由语义分析器提供，语义分析器使用语法树和符号表中的信息来检查源程序是否和语言定义的语义一致。它同时收集类型信息，并把这些信息存放在语法树或者符号表中，以便在随后的中间代码生成过程中使用。于是语义分析器的作用为：

• 审查源程序是否有语义错误
• 为代码生成收集类型信息

类型检查：类型检查是语义分析的重要组成部分，编译器检查每个运算符是否具备匹配的运算分量，比如：

1. 数组的下标必须是整数，浮点数作为下标会报错。
2. 条件表达式必须是布尔型
3. 赋值语句左右两边类型是否相融
4. ...

自动类型转换：某些程序设计语言会允许某些类型转换，那么在语义分析阶段也会进行自动类型转换，比如：

• 一个二元运算符可以应用于一对整数或者一对浮点数。那么该运算符如果应用于一个浮点数和一个整数，那么这个整数可能被自动转换成浮点数。

举例

语义错误请看注释：

float sum, first;
sum = first + 10;
count = sum; //count无定义
first = sum % 10;//sum是浮点型，不能进行取余数运算

中间代码生成

介绍

在把一个源程序翻译成目标代码的过程中，一个编译器可能构造出一个或者多个中间表示，这个中间表示可以有多种形式。

语法树就是一种中间表示形式，在语法分析和语义分析中使用。

在语法分析和语义分析完成之后，很多编译器会生成一个明确的低级或者类机器语言的中间表示。这个中间表示应该具备两个重要的性质：

• 易于生成
• 可以轻松的翻译为目标机器上的语言

当然这个中间代码可能存在很多种形式：

• 后缀式（栈式）中间代码
• 三地址中间代码（三元式和四元式）
• 图结构的中间代码（树，DAG）

举例

代码：

float sum, first, count;
sum = first + count * 10;

中间代码（四元式）：

(int-to-float, 10, , t1)
(*, count, t1, t2)
(+, first, t2, t3)
(=, t3, , sum)

简单解释一下：

• 真正的中间代码里其中的count，first这种会表示成符号表中的引用。
• (*, count, t1, t2)以这个为例子含义是 t2 = t1 * count

关于三地址指令：

• 每个三地址赋值指令右部最多只有一个运算符，因此这些指令顺序确定了运算的顺序
• 编译器应该生成一个临时名字以存放一个三地址指令计算得到的值（t1，t2...）
• 有些三地址指令的运算分量少于三个，比如上面中间代码的第一条和最后一条。

代码优化

介绍

目的：改进中间代码，意图生成更好的目标代码。

更好通常意味着更快，但是也可能会有其他目标，比如更短的或者能耗更低的代码。

不同的编译器在代码优化过程所做的工作量可能相差很大，那些优化工作做的很多的编译器（即所谓的优化编译器）会在优化阶段花费相当多的时间，有些简单的优化方法可以极大的提高目标程序的运行效率而不会过多的降低编译速度。

常见的优化方式：

• 常量表达式优化
• 公共子表达式优化
• 不变表达式的循环外提
• 削弱运算强度
• ...

举例

中间代码（四元式）：

(int-to-float, 10, , t1)
(*, count, t1, t2)
(+, first, t2, t3)
(=, t3, , sum)

常量表达式优化：

(*, count, 10.0, t2)
(+, first, t2, t3)
(=, t3, , sum)

目标代码生成

介绍

代码生成器以源程序的中间表示形式（中间代码）为输入，并把他映射为目标语言。如果目标语言是机器代码，那么：

1. 必须为程序使用的每个变量选择寄存器或者内存位置。
2. 然后，中间指令被翻译成为能够完成相同任务的机器指令序列。

代码生成的一个至关重要的方面是合理分配寄存器以及存放变量的值。

举例

源程序：

float sum, first, count;
sum = first + count * 10;

汇编代码：

MOV count, R1
MULT R1, #10.0
MOV first, R2
ADD R1, R2
MOV R1, sum

章节小结

根据前文介绍，编译器大体可以分为以下几个步骤：

• 词法分析
• 语法分析
• 语义分析
• 中间代码生成
• 中间代码优化
• 目标代码生成

后面的文章会对各个步骤的细节进行详细介绍，也会使用小的编译器源码作为例子。下图是《编译原理（第二版）》中的图例，我想大家到这里应该已经对编译器的整个流程有了初步的了解，也可以借助这个图片进行一个简单的回顾～

结束语

文章中内容来自：

• 《编译原理（第二版）》
• 母校课件
• 经过本人筛选验证的知乎问答
• 本人的理解（本人理解可能是其中最没有权威可言的部分hhh）