程序员的自我修养阅读笔记--第二章 编译与链接

1,230 阅读17分钟

编译与链接

对于平时的应用程序开发,我们一般不需要关注编译和链接过程,因为通常的开发环境都是集成开发环境(IDE),比如 Visual Studio、Dlephi 等。这样的 IDE 一般都将编译和链接的过程一步完成,通常将这种编译和链接合并到一起的过程称为构建(Build)

1.被隐藏了的过程

#include <stdio.h>

int main() 
{
    printf("Hello World!\n");
    return 0;
}

使用 GCC 来编译一个简单的 Hello World 程序,这个编译的过程可以分解为 4 个步骤:

  • 预处理(Prepressing)
  • 编译(Compilation)
  • 汇编(Assembly)
  • 链接(Linking)

1.1 预编译

预编译过程主要处理那些源代码文件中的以 # 开始的预编译指令。比如 #include#define 等,主要处理规则如下:

  • 将所有的 #define 删除,并且展开所有的宏定义。
  • 处理所有条件预编译指令,比如 #if#ifdef#elifelse#endif
  • 处理 #include 预编译指令,将被包含的文件插入到该预编译指令的位置。注意,这个过程是递归进行的,也就是说呗包含的文件可能还包含其他文件。
  • 删除所有的注释 ///* */
  • 添加行号和文件名标识,比如 #2 hello.c 2,以便于编译时编译器产生调试用的行号信息及用于编译时产生编译错误或警告时能够显示行号。
  • 保留所有的 #pragma 编译器指令,因为编译器需要使用它们。

经过预编译的 .i 文件不包含任何宏定义,因为所有的宏已经被展开,并且包含的文件也已经被插入到 .i 文件中。所以当我们无法判断宏定义是否正确或者头文件包含是否正确时,可以查看编译后的文件来确定问题。

1.2 编译

编译过程就是把预处理完的文件进行一系列词法分析、语法分析、语义分析及优化后生产相应的汇编代码文件,这个过程往往是我们所说的整个程序构建的核心部分,也是最复杂的部分之一。

1.3 汇编

汇编器是将汇编代码转变成机器可以执行的指令,每一个汇编代码几乎都对应一条机器指令。所以汇编器的汇编过程相对于编译器来讲比较简单,它没有复杂的语法,也没有语义,也不需要做指令优化,只是根据汇编指令和机器指令的对照表一一翻译就可以了。

1.4 链接

链接通常是一个让人费解的过程,为什么汇编器不直接输出可执行文件而是输出一个目标文件呢?链接过程到底包含了什么内容?为什么要链接?我们需要将一大堆文件链接起来才可以得到可执行文件,为什么呢?这也是这本书要介绍的内容,它们看似简单,其实涉及编译、链接和库,甚至是操作系统一些很底层的内容。这些都会在之后的章节一一细说。

2.编译器做了什么

从最直观的角度来讲,编译器就是将高级语言翻译成机器语言的一个工具。

回到编译器本身的职责上,编译过程一般可以分为 6 步:

  • 扫描
  • 语法分析
  • 语义分析
  • 源代码优化
  • 代码生成
  • 目标代码优化

2.1 词法分析

首先源代码程序被输入到 扫描器(Scanner),扫描器的任务很简单,它只是简单地进行词法分析,运用一种类似于 有限状态机(Finite State Machine) 的算法可以很轻松地将源代码的字符序列分割成一系列的记号(Token)

词法分析产生的记号一般可以分为如下几类:关键字、标识符、字面量(包括数字、字符串等)和特殊符号(如加号、等号)。在识别记号的同时,扫描器也完成了其他工作。比如将标识符存放到符号表,将数字、字符串常量存放到文字表等,以备后面的步骤使用。

另外对于一些预处理的语言,比如 C 语言,它的宏替换和文件包含等工作一般不归入编译器的范围而交给一个独立的预处理器。

2.2 语法分析

接下来语法分析器(Grammar Parser) 将对由扫描器产生的记号进行语法分析,从而产生语法树(Syntax Tree)。整个分析过程采用了上下文无关语法(Context-free Grammar) 的分析手段。

简单来说,由语法分析器生成的语法树就是以 表达式(Expression) 为节点的树。我们知道,C 语言的一个语句是一个表达式,而复杂的语句是很多表达式的组合。

2.3 语义分析

语义分析由 语义分析器(Semantic Analyzer) 来完成。语法分析仅是完成了对表达式语法层面的分析,但是它并不了解这个语句是否真正有意义。比如 C 语言里面两个指针做乘法运算是没有意义的,但是这个语句在语法上是合法的;比如同样一个指针和一个浮点数做乘法运算是否合法等。编译器所能分析的语义是 静态语义(Static Semantic) ,所谓静态语义是指在编译期可以确定的语义,与之对应的 动态语义(Dynamic Semantic) 就是只有在运行期才能确定的语义。

静态语义通常包括声明和类型的匹配,类型的转换。比如当一个浮点型的表达式赋值给一个整型的表达式时,其中隐含了一个浮点型到整型转换的过程,语义分析过程中需要完成这个步骤。比如将一个浮点型赋值给一个指针的时候,语义分析程序会发现这个类型不匹配,编译器就会报错。动态语义一般指在运行期的语义相关的问题,比如将 0 作为除数是一个运行期语义错误。

经过语义分析阶段以后,整个语法树的表达式都被标识了类型,如果有些类型需要做隐式转换,语义分析程序会在语法树中插入相应的转换节点。

语义分析器还对符号表里的符号类型也做了更新。

2.4 中间语言的生成

现代的编译器有着很多层次的优化,往往在源代码级别会有一个优化过程。我们这里所描述的 源码级优化器(Source Code Optimizer) 在不同的编译器中可能会有不同的语义或有一些其他的差异。

源代码级优化器会在源代码级别进行优化,比如 (2 + 6) 这个表达式可以被优化成 8。其实直接在语法树上做优化比较困难,所以源代码优化器往往将整个语法树转换成 中间代码(Intermediate Code),它是语法树的顺序表示,其实它已经非常接近目标代码了。但是它一般跟目标机器和运行时环境是无关的,比如它不包含数据的尺寸、变量地址和寄存器名字等。中间代码有很多种类型,在不同的编译器中有着不同的形式,比较常见的有:三地址码(Three-address Code)P-代码(P-Code)

中间代码使得编译器可以被分为前端和后端。编译器前端负责产生机器无关的中间代码,编译器后端将中间代码转换成目标机器代码。这样对于一些可以跨平台的编译器而言,它们可以针对不同的平台使用同一个前端和针对不同机器平台的数个后端。

2.5 目标代码生成与优化

源代码级优化器产生中间代码标志着下面的过程都属于编译器后端。编译器后端主要包括 代码生成器(Code Generator)目标代码优化器(Target Code Optimizer)

让我们先来看看代码生成器。代码生成器将中间代码转换成目标机器代码,这个过程十分依赖于目标机器,因为不同机器有着不同的字长、寄存器、整数数据类型和浮点数数据类型等。

最后目标代码优化器对目标代码进行优化,比如选择合适的寻址方式、使用位移来代替乘法运算、删除多余的指令等。

现代的编译器有着异常复杂的结构,这是因为现代高级编程语言本身非常的复杂,比如 C++ 语言的定义就极为复杂,至今没有一个编译器能够完整支持 C++ 语言标准所规定的所有语言特性。另外现代的计算机 CPU 相当的复杂,CPU 本身采用了诸如流水线、多发射、超标量等诸多复杂的特性,为了支持这些特性,编译器的机器指令优化过程也变的十分复杂。使得编译过程更为复杂的是有些编译器支持多种硬件平台,即允许编译器编译出多种目标 CPU 的代码。比如著名的 GCC 编译器就几乎支持所有 CPU 平台,这也导致了编译器的指令生成过程更为复杂。

经过这些扫描、语法分析、语义分析、源代码优化、代码生成和目标代码优化,编译器忙活了这么多步骤以后,源代码终于被编译成了目标代码。但是这个目标代码中有一个问题是:index 和 array 的地址还没有确定。如果我们要把目标代码使用汇编器编译成真正能够在机器上执行的指令,那么 index 和 array 的地址应该从哪儿得到呢?如果 index 和 array 定义在跟上面的源代码同一个编译单元里,那么编译器可以为 index 和 array 分配空间,确定它们的地址;那如果是定义在其它的程序模块呢?

这个看似简单的问题引出了我们的一个很大的话题:目标代码中有变量定义在其他模块,该怎么办?事实上,定义其他模块的全局变量和函数在最终运行时的绝对地址都要在最终链接的时候才能确定。所以现代的编译器可以将一个源代码文件编译成一个未链接的目标文件,然后由链接器最终将这些目标文件链接起来形成可执行文件。

3.链接器年龄比编译器长

最开始的程序要需要直接手写机器语言,也就是 010101110…… 后来先驱们发明了汇编语言,生产力大大提高,随之而来的是软件的规模也开始日渐庞大,这时程序的代码量也已经开始快速的膨胀,导致人们要开始考虑将不同功能的代码以一定的方式组织起来,使得更加容易阅读和理解,以便于日后修改和重复使用。自然而然,人们开始将代码按照功能或性质划分,分别形成不同的功能模块,不同的模块之间按照层次结构或其他结构来组织。这个在现代的软件源代码组织中很常见,比如在 C 语言中,最小的单位是变量和函数,若干个变量和函数组成一个模块,存放在一个 .c 的源代码文件里,然后这些源代码文件按照目录结构来组织。在比较高级的语言中,如 Java 中,每个类都是一个基本的模块,若干个类模块组成一个 包(Package),若干个包组合成一个程序。

在现代软件开发中,软件的规模往往都很大,动辄数百万行代码,如果都放在一个模块肯定无法想象。所以现代的大型软件往往拥有成千上万个模块,这些模块之间相互依赖又相互独立。这种按照层次化及模块化存储和组织源代码有许多好处,比如代码更容易阅读、理解、重用,每个模块可以单独开发、编译、测试,改变部分代码不需要编译整个程序等。

在一个程序被分割成多个模块后,这些模块之间最后如何组合形成一个单一的程序是须解决的问题。模块之间如何组合的问题可以归结为模块之间如何通信的问题,最常见的属于静态语言的 C/C++ 模块之间通信有两种方式,一种是模块间的函数调用,另外一种是模块间的变量访问。函数访问须知道目标函数的地址,变量访问也须知道目标变量的地址,所以这两种方式可以归结为一种方式,那就是模块间符号的引用。模块间依靠符号来通信类似于拼图版,定义符号的模块多出一块区域,引用该符号的模块刚好少了那一块区域,两者一拼接刚好完美组合。

这个模块的拼接过程就是本书的一个主题:链接(Linking)

4.模块拼装——静态链接

程序设计的模块化是人们一直在追求的目标,因为当一个系统十分复杂的时候,我们不得不将一个复杂的系统逐步分割成小的系统以达到各个突破的目的。一个复杂的软件也如此,人们把每个源代码模块独立地编译,然后按照需要将它们 “组装” 起来,这个组装模块的过程就是 链接(Linking)。链接的主要内容就是把各个模块之间相互引用的部分都处理好,使得各个模块之间能够正确地衔接。从原理上讲,它的工作无非就是把一些指令对其他符号地址的引用加以修正。链接过程主要包括了 地址和空间分配(Address and Storage Allocation)符号决议(Symbol Resolution)重定位(Relocation) 等这些步骤。

符号决议有时候也被叫做符号绑定(Symbol Binding)、名称绑定(Name Binding)、名称决议(Name Resolution),设置还有叫做地址绑定(Address Binding)、指令绑定(Instructiong Binding)的,大体上它们的意思都一样,但从细节角度来区分,它们之间还是存在一定区别的,比如 “决议” 更倾向于静态链接,而 “绑定” 更倾向于动态链接,即它们所使用的范围不一样。在静态链接,我们统一称为符号决议。

每个模块的源代码(如 .c)文件经过编译器编译成 目标文件(Object File,一般扩展名为 .o 或 .obj),目标文件和 库(Library) 一起链接形成最终可执行文件。而最常见的库就是 运行时库(Runtime Library),它是支持程序运行的基本函数的集合。库其实就是一组目标文件的包,就是一些最常用的代码编译成目标文件后打包存放。

现代的编译和链接过程也并非想象中的那么复杂,它还是一个比较容易理解的概念。比如我们在程序模块 main.c 中使用另外一个模块 func.c 中的函数 foo()。我们在 main.c 模块中每一处调用 foo 的时候都必须确切知道 foo 这个函数的地址,但是由于每个模块都是单独编译的,在编译器编译 main.c 的时候它并不知道 foo 函数的地址,所以它暂时把这些调用 foo 的指令的目标地址搁置,等待最后链接的时候由链接器去将这些指令的目标地址修正。如果没有链接器,需要我们手工把每个调用 foo 的指令修正,填入正确的 foo 函数地址。当 func.c 模块被重新编译,foo 函数的地址有可能改变时,我们在 main.c 中所有使用到 foo 的地址的指令将要全部重新调整,这些繁琐的工作将成为程序员的噩梦。使用链接器,你可以直接引用其他模块的函数和全局变量而无需知道它们的地址,因为链接器在链接的时候,会根据你所引用的符号 foo,自动去相应的 func.c 模块中查找 foo 的地址,然后将 main.c 模块中所有引用到 foo 的指令重新修正,让它们的目标地址为真正的 foo 函数的地址。这就是静态链接的最基本的过程和作用。

在链接过程中,对其他定义在目标文件中的函数调用的指令需要被重调整,对使用其他定义在其他目标文件的变量来说,也存在同样的问题。让我们来结合具体的 CPU 指令来了解这个过程。假设我们有个全局变量叫做 var,它在目标文件 A 里面。我们在目标文件 B 里面要访问这个全局变量,比如我们在全局变量中有这么一条指令:

mov1 $0x2a, var

这条指令就是给这个 var 变量赋值 0x2a,相当于 C 语言里面的语句 var = 42。然后我们编译目标文件 B,得到这条指令机器码。

由于在编译目标文件 B 的时候,编译器并不知道变量 var 的目标地址,所以编译器在没法确定地址的情况下,将这条 mov 指令的目标地址置为 0,等待链接器在将目标文件 A 和 B 链接起来的时候再将其修正。我们假设 A 和 B 链接后,变量 var 的地址呗确定下来为 0x1000,那么链接器就会把这个指令的目标地址部分修改为 0x10000。这个地址修正的过程也被叫做 重定位(Resolution),每个要被修正的地方叫一个 重定位入口(Resloution Entry)。重定位所做的就是给程序中每个这样的绝对地址引用的位置 “打补丁”,使它们指向正确的地址。

5.本章小结

在这一章中,我们首先回顾了从程序源代码到最终可执行文件的 4 个步骤:预编译、编译、汇编、链接,分析了它们的作用及相互之间的联系,IDE 集成开发工具和编译器默认的命令通常将这些步骤合并成一步,使得我们通常很少关注这些步骤。

我们还详细回顾了上面这 4 个步骤中的主要部分,即编译步骤。介绍了编译器将 C 程序源代码转变成汇编代码的若干个步骤:词法分析、语法分析、语义分析、中间代码生成、目标代码生成与优化。最后我们介绍了链接的历史和静态链接的一系列基本概念:重定位、符号、符号决议、目标文件、库、运行时库等概念。