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

第二章 编译和链接

对于平常的应用程序开发，我们很少需要关注编译和链接过程，因为通常的开发环境都是流行的集成开发环境（IDE），比如Visual Studio。这样的IDE一般都将编译和链接的过程一步完成，通常将这种编译和链接合并到一起的过程称为构建（Build）。

被隐藏了的过程

在linux下，当我们使用gcc来编译Hello World程序时，只需用最简单的命令（假设源代码文件名为hello.c）：

$ gcc hello.c
$ ./a.out
Hello World

事实上，上述过程可以分解为4个步骤，分别是预处理（Prepressing）、编译（Assembly）、汇编（Assembly）和链接（Linking）。

预编译

首先是源代码文件hello.c和相关的头文件，如stdio.h等被预编译器cpp预编译成一个.i文件。对于c++程序来说，它的源代码文件的扩展名可能是.cpp或.cxx，头文件的扩展名可能是.hpp，而预编译后的文件扩展名是.ii。第一步预编译的过程相当于如下命令（-E表示只进行预编译）：

$ gcc -E hello.c -o hello.i

或者

$ cpp hello.c > hello.i

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

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

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

编译

编译过程就是把预处理完的文件进行一系列词法分析、语法分析、语义分析及优化后生产相应的汇编代码文件。相当于如下命令：

$ gcc -S hello.i -o hello.c

现在版本的gcc把预编译和编译两个步骤合并成一个步骤，使用一个叫做cc1的程序来完成。在笔者的电脑（ubuntu16.04）中，该文件位于”/usr/lib/gcc/x86_64-linux-gnu/5/“，我们也可以直接调用cc1来完成它：

$ /usr/lib/gcc/x86_64-linux-gnu/5/cc1 hello.c 
 main
Analyzing compilation unit
Performing interprocedural optimizations
 <*free_lang_data> <visibility> <build_ssa_passes> <opt_local_passes> <free-inline-summary> <whole-program> <inline>Assembling functions:
 main
Execution times (seconds)
 phase setup             :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 (20%) wall    1093 kB (65%) ggc
 phase parsing           :   0.01 (50%) usr   0.01 (100%) sys   0.03 (60%) wall     520 kB (31%) ggc
 phase opt and generate  :   0.01 (50%) usr   0.00 ( 0%) sys   0.01 (20%) wall      56 kB ( 3%) ggc
 df scan insns           :   0.01 (50%) usr   0.00 ( 0%) sys   0.00 ( 0%) wall       0 kB ( 0%) ggc
 preprocessing           :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 (20%) wall     218 kB (13%) ggc
 parser (global)         :   0.01 (50%) usr   0.01 (100%) sys   0.02 (40%) wall     286 kB (17%) ggc
 integrated RA           :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 (20%) wall      24 kB ( 1%) ggc
 TOTAL                 :   0.02             0.01             0.05               1687 kB

或者使用如下命令：

$ gcc -S hello.c -o hello.s

都可以得到汇编输出文件hello.s，而对于c++、objective-c、fortran、java等语言都有对应的程序，所以实际上gcc只是这些后台程序的包装，它会根据不同的参数要求去调用预编译器语言cc1、汇编器as、链接器ld。

汇编

汇编器是将汇编代码转变成机器可执行的指令，每一条汇编语句几乎都对应一条机器指令。我们可以调用汇编器as来完成：

$ as hello.s -o hello.o

或者

$ gcc -c hello.s -o hello.o

或者使用gcc命令从c源代码文件来说，经过预编译，编译和汇编直接输入目标文件（Object File）：

$ gcc -c hello.c -o hello.o

链接

链接通常是一个令人费解的过程，为什么汇编器不直接输出可执行文件而是输出一个目标文件呢？链接过程到底包含了什么内容？为什么要链接？

在书上的例子中，如果我们需要调用ld产生一个能够正常运行的Hello World程序：

那么为什么有这么一大堆玩意呢？这些东西涉及到了编译、链接和库，甚至是操作系统一些很底层的内容。在分析这些内容前，我们还是先关注一下编译器在上面这些内容中干了啥

编译器做了什么

用最直观的角度来讲，编译器就是将高级语言翻译成机器语言的一个工具。编译过程一般可以分为6步：扫描、语法分析、语义分析、源代码优化、代码生成和目标代码优化：

我们以一行简单的c语言代码来简单描述从源代码（Source Code）到最终目标代码（Final Target Code）的过程。

CompilerExpression.c

array[index] = (index + 4) * (2 + 6)

词法分析

首先源代码程序被输入到扫描器（Scanner），扫描器只是简单地进行词法分析，用一种类似于有限状态机（Finite State Machine）的算法可以很轻松地将源代码的字符序列分割成一系列的记号（Token）。例如上面的那行程序，共包含了28个非空字符，经过扫描后，产生了16个记号：

记号	类型
array	标识符
[	左方括号
index	标识符
]	右方括号
=	赋值
(	左圆括号
index	标识符
+	加号
4	数字
)	右圆括号
*	乘号
(	左圆括号
2	数字
+	加号
6	数字
)	右圆括号

语法分析产生的记号一般可以分为：关键字、标识符、字面量（包含数字、字符串等）和特殊符号（如加号、等号）。在识别记号的同时，扫描器也完成了将标识符放到符号表，将数字、字符串常量存放到文字表等工作。

有一个叫做lex的程序可以实现词法扫描，它会按照用户之前描述好的词法规则将输入的字符串分割成一个个记号。这样编译器的开发者就无需为每个编译器开发一个独立的词法扫描器，而是根据需要改变词法规则即可。

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

语法分析

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

如何理解上下文无关文法？

简单的将，由语法分析器生成的语法数就是以表达式（Expression）为节点的树。c语言的一个语句是一个表达式，而复杂的语句是很多表达式的组合。上面例子中的语句就是一个由赋值表达式、加法表达式、乘法表达式、数组表达式、括号表达式组成的复杂语句。它经过语法分析器后形成的语法树如下：

我们可以看到整个语句被看作是一个赋值表达式，最小的表达式是符号和数字，通常作为整个语法树的叶节点。在语法分析的同时，很多运算符号的优先级和含义也被确定下来了。另外有些符号具有多重含义，例如星号*在c语言中可以表示乘法表达式，也可以表示对指针内容取内容的表达式，所以语法分析阶段必须对这些内容进行区分，如果出现了表达式不合法，例如各种括号不匹配、表达式中缺少操作符等，编译器就会报告语法分析阶段的错误。

语法分析也有一个现成的工具叫yacc（Yet Another Compiler Compiler），可以根据用户给定的语法规则对输入的记号序列进行解析，从而构建出一颗语法树。对于不同的编程语言，编译器的开发者只需改变语法规则即可，所以它又被称为“编译器编译器（Compiler Compiler）“。

语义分析

语义分析由语义分析器（Semantic Analyzer）来完成。语法分析仅仅是完成了对表达式的语法层面的分析，但是它并不了解这个语句是否真正有意义。例如c语言里两个指针做乘法运算说没有意义的，但是这个语句在语法上是合法的。

编译器所能分析的语义是静态语义（Static Semantic），就是指在编译期间可以确定的语义，与之对应的动态语义（Dynamic Semantic）就是指只有在运行期间才能确定的语义。

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

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

中间语言生成

现代的编译器有很多层次的优化，往往在源代码级别会有一个优化过程。我们这里所描述的源码级优化器（Source Code Optimizer），就会在源代码级别进行优化。优化后语法树如图：

我们可以看到（2+6）这个表达式被优化成8，直接在语法树上优化比较困难，所以源代码优化器往往将整个语法树转换成中间代码（Intermediate Code），它是语法树的顺序表示，接近目标代码，但是一般与目标机器和运行时环境无关。比较常见的中间代码类型有三地址码（Three-address Code）和P-代码（P-Code），以三地址码为例：

最基本的三地址码： x = y op z

这个三地址码表示将变量y和z进行op操作以后，赋值给x。这里的op操作可以是算术操作，也可以是其他任何可以应用到y和z的操作，这样一个三地址码语句里有三个变量地址，三地址码也得名于此。

上例中语法树翻译成三地址码为：

t1 = 2 + 6
t2 = index + 4
t3 = t2 * t1
array[index] = t3

为了使所有的操作都符合三地址码形式，这里利用了几个临时变量，在三地址码的基础上进行优化后：

t2 = index + 4
t2 = t2 * 8
array[index] = t2

中间代码使得编译器可以被分为前端和后端，编译器前端负责产生机器无关的中间代码，编译器后端将中间代码转换成目标机器代码。这样一个编译器可以对不同的平台使用同一个前端和不同的后端。

目标代码生成与优化

编译器后端主要包括代码生成器（Code Generator）和目标代码优化器（Target Code Optimizer）。代码生成器将中间代码转换成目标机器代码，这个过程十分依赖于目标机器，因为不同的机器有不同的字长、寄存器、整数数据类型和浮点数数据类型等。对于上例中的中间代码，代码生成器可能会生成如下代码序列（以x86汇编语言表示，并结社index和array数组都为int型）：

movl index, %ecx				;value of index to ecx
addl $4, %ecx						;ecx = ecx + 4
mull $8, %ecx						;ecx = ecx * 8
movl index, %eax				;value of index to eax
movl %ecx, arrat(,eax,4);array[index] = ecx

mul：无符号数乘法

最后目标代码优化器对上述的目标代码进行优化，例如选择合适的寻址方式、使用位移来代替乘法运算、删除多余的指令等。上例中乘法由一条相对复杂的基址比例变址寻址（Base Index Scale Addressing）的lea指令来完成，最后由一条mov指令完成最后的赋值操作，这条mov指令的寻址方式和lea一样。

movl index, %edx
leal 32(,%dex,8), %eax
movl %eax, array(,%edx,4)

我们获得了目标代码，但是代码并不能直接执行，因为还存在一个问题：index和array的地址还没有确定。那么应该从哪里获得地址呢？如果index和array的定义和上面的源码在同一个编译单元里面，那么编译器可以为index和array分配空间。

当一个c或cpp文件在编译时，预处理器首先递归包含头文件，形成一个含有所有必要信息的单个源文件，这个源文件就是一个编译单元。

但如果定义在其他的程序模块呢？

事实上，定义在其他模块的全局变量和函数在最终运行时的绝对地址都要在最终链接时才能确定。所以现代的编译器可以将一个源代码文件编译成一个未链接的目标文件，然后由连接器最终将这些目标文件链接起来形成可执行文件。

链接器年龄比编译器大

最开始程序其实是以0、1的形式写在一条纸带上的，但是程序需要修改，便需要重新计算各个目标的地址，即重定位（Relocation），后来产生了汇编语言，可以使用符号（Symbol）来表示一个地址，这个地址可能是一段子程序（函数）的起始地址，也可以是一个变量的起始地址。

后来需要把代码按照功能或性质划分，例如java每个类是一个基本的模块，若干个类模块组成一个包（Package），若干个包组合成一个程序。

在一个程序被分割成多个模块之后，这些模块之间如何组合形成一个单一的程序呢？这个模块的拼接过程便是链接（Linking）。

模块拼装——静态链接

链接的主要内容就是把各个模块之间相互引用的部分都处理好，使得各个模块之间能够正确的链接。从原理上来讲，链接器的工作就是把一些指令对其他符号地址的引用加以修正，链接过程主要包括地址和空间分配（Address and Storage Allocation）、符号决议（Symbol Resolution）和重定位（Relocation）这些步骤。

符号决议：简而言之，就是确保全部目标文件中的符号引用都有惟一的定义

最基本的静态链接过程如图：

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

我们对于Object文件并没有找到一个很合适的中文名称，把它叫做中间目标文件比较合适，简称为目标文件，很多时候我们也把目标文件称为模块。