第一章 编译与链接
一、被隐藏了的过程
1、在linux下，用gcc来编译hello world程序时，假设源代码文件名为hello.c
$gcc hello.c
$./a.out
Hello World
上述过程可以分解为4个步骤：
预处理（Prepressing）、编译（Compilation）、汇编（Assembly）和链接（Linking);
补充：实际上 gcc 这个命令只是一些后台程序的包装，它会根据不同的参数要求去调用 预编译编译程序ccl、汇编器 as、链接器 Id。
2.预编译
对于hello.c 预编译的时候，需要用到预编译器 cpp
第一步预编译的过程相当于如下命令（-E表示只进行预编译）：
$gcc -E hello.c -o hello.i
or
$cpp hello.c > hello.i
预编译过程主要处理那些源代码文件中的以"#“开始的预编译指令。比如”#include"、"#define"等，主要处理规则如下∶
● 将所有的"#define"删除，并且展开所有的宏定义。
●处理所有条件预编译指令，比如"#if"、"#ifdef"、"#elif"、"#else"、"#endif"。
●处理"#include"预编译指令，将被包含的文件插入到该预编译指令的位置。注意，这个过程是递归进行的，也就是说被包含的文件可能还包含其他文件。
● 删除所有的注释"//“和”/* */"。
●添加行号和文件名标识，比如#2"hello.c"2，以便于编译时编译器产生调试用的行号信息及用于编译时产生编译错误或警告时能够显示行号。
●保留所有的#pragma 编译器指令，因为编译器须要使用它们。
经过预编译后的.i文件不包含任何宏定义，因为所有的宏已经被展开，并且包含的文件也已经被插入到.i 文件中。所以当我们无法判断宏定义是否正确或头文件包含是否正确时，可以查看预编译后的文件来确定问题。
3.编译
变异过程就是把预处理完成的文件（hello.i）进行一系列词法分析，语法分析，语义分析，优化后生成相应的汇编代码文件。
$gcc -S hello.i -o hello.s
or
$gcc -S hello.c -o hello.s
现在版本的 GCC 把预编译和编译两个步骤合并成一个步骤，使用一个叫做 ccl 的预编译编译程序来完成这两个步骤。
这个程序位于"/usr/lib/gcc/i486-linux-gnu/4.1/"，我们也可以直接调用 ccl 来完成它∶
$ /usr/lib/gcc/i486-linux-gnu/4.1/ccl hello.c
对于C 语言的代码来说，这个预编译和编译的程序是 ccl；对于 C++来说，有对应的程序叫做cclplus;
Objective-C是cclobj；fortran 是 f771；java是 jcl。
所以实际上 gcc 这个命令只是这些后台程序的包装，它会根据不同的参数要求去调用 预编译编译程序ccl、汇编器 as、链接器 Id。
4、汇编
汇编器是将汇编代码转变成机器可以执行的指令，每一个汇编语句几乎都对应一条机器指令。汇编的过程只需要根据 汇编指令和机器指令对照表一一翻译就可以了。汇编过程可以调用汇编器 as 来完成：
$as hello.s -o hello.o
or
$gcc -c hello.s -o hello.o
or
$gcc -c hello.c -o hello.o
5、链接
用 ld 才可以产生一个能够正常运行的 HelloWorld 程序∶
?$ld -static /usr/lib/crt1.o /ugr/lib/crti.o/uar/lib/gcc/i486-1linux-gnu/4.1.3/crtbeginr.o?-
?L/ugr/lib/gcc/i486-1inux-gnu/4.1.3 -L/ugr/lib-L/1ib hello.o--start-group-1gcc -1gcc_eh -
?1c --end-group /usr/lib/gcc/1486-1inux-gnu/4.1.3/crtend.o/ugr/lib/crtn.o
如果把所有的路径都省略掉，那么上面的命令就是∶
ld -static crt1.o crti.o crtbeginT.o hello.o-start-group -lgcc-lgcc_eh -lc-end-group crtend.o
crtn. o
二、编译器担任的角色
1、编译器做了什么
编译过程一般可分为6步：扫描（词法分析）、语法分析、语义分析、源代码优化、代码生成、目标代码优化。
从现在往下，我们以一个C语言源代码为例：
array[index] = (index + 4) * (2 + 6);
2、词法分析
将源代码输入到扫描器（Scanner）,扫描器将源代码的字符分割成一系列 记号（Token）。
上面程序包含28个非空字符，产生16个记号。
词法分析产生的记号一般可以分为如下几类∶关键字、标识符、字面量（包含数字、字符串等）和特殊符号（如加号、等号）。
在识别记号的同时，扫描器也完成了其他工作：比如 将标识符存放到符号表，将数字、字符串常量存放到文字表等，以备后面的步骤使用。
有一个叫做 lex 的程序可以实现词法扫描，它会按照用户之前描述好的词法规则将输入的字符串分割成一个个记号。
因为这样一-个程序的存在，编译器的开发者就无须为每个编译器开发一个独立的词法扫描器，而是根据需要改变词法规则就可以了。用户设立不同的词法规则，就可以将字符串分割成不同的记号
另外对于一些有预处理的语言，比如 C 语言，它的宏替换和文件包含等工作一般不归入编译器的范围而交给一个独立的预处理器。
3、语法分析
语法分析是完成了对表达式语法层面的分析，不进行表达式是否有意义的判断。
语法分析器（Grammar Parser） 对 扫描器已经产生的记号 进行语法分析，采用了 上下文无关语法（Context-free Grammar） 产生 语法树（Syntax Tree）.语法树是以表达式为节点的树。
上面例子经过语法分析器以后形成的语法树如图：
正如前面词法分析有 lex 一样，语法分析也有一个现成的工具叫做 yacc（Yet Another Compiler Compiler）。
yacc也像 lex 一样，可以根据用户给定的语法规则对输入的记号序列进行解析，从而构建出一棵语法树。
对于不同的编程语言，编译器的开发者只须改变语法规则，而无须为每个编译器编写一个语法分析器，所以它又被称为"编译器编译器（Compiler Compiler)"。
4、语义分析
语义分析器（Semantic Analyzer 来完成语义分析，判断表达式是否有意义。编译器所能分析的语义是 静态语义（Static Semantic）,静态语义就是 在编译期可以确定的语义；动态语义（Dynamic Semantic 就是只有在运行期才能确定的语义。
静态语义 通常包括 声明和类型的匹配，类型的转换。
- 比如当一个浮点型的表达式赋值给一-个整型的表达式时，其中隐含了一个浮点型到整型转换的过程，语义分析过程中需要完成这个步骤；
- 比如将一个浮点型赋值给一个指针的时候，语义分析程序会发现这个类型不匹配，编译器将会报错。
动态语义一般指在运行期出现的语义相关的问题.
- 比如将 0作为除数是一个运行期语义错误。
经过语义分析阶段以后，整个语法树的表达式都被标识了类型，如果有些类型需要做隐式转换，语义分析程序会在语法树中插入相应的转换节点。
5、中间代码生成
现代的编译器有着很多层次的优化，在源代码级别会有一个优化过程。
源代码级优化器（Source Code Optimizer）会在源代码级别进行优化，上面（2＋6）这个表达式可以被优化掉，因为它的值在编译期就可以被确定。
我们看到（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;
为了使所有的操作都符合三地址码形式，这里利用了 t1 t2和 t3 临时变量。
在三地址码的基础上进行优化时，优化程序会将 2+6 的结果计算出来，得到t1=8，然后将后面代码中的t1 替换成数字 8。另外还可以省去一个临时变量 t3，因为 t2 可以重复利用。经过优化以后的代码如下∶
t2 = index + 4;
t2 = t2 * 8;
array[index] = t2;
中间代码使得编译器可以被分为前端和后端。
编译器前端负责产生机器无关的中间代码，编译器后端将中间代码转换成目标机器代码。
这样对于一些可以跨平台的编译器而言，它们可以针对不同的平台使用同一个前端和针对不同机器平台的数个后端。
6、目标代码生成与优化
目标代码生成与优化这整个过程都属于编译器后端。
编译器后端主要包括代码生成器（Code Generator） 和 目标代码优化器（Target Code Optimizer）。
- 代码生成器将中间代码 转换成 目标机器代码，这个过程十分依赖于目标机器，因为不同的机器有着不同的字长、寄存器、整数数据类型和浮点数数据类型等。
对于上面例子中的中间代码，代码生成器可能会生成下面的代码序列（x86 汇编语言）∶
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, array(,eax,4) ; array[index] = ecx
- 最后 目标代码优化器对上述的目标代码进行优化，比如选择合适的寻址方式、使用位移来代替乘法运算、删除多余的指令等。
上面的例子中，乘法由一条相对复杂的基址比例变址寻址（Base Index Scale Addressina） 的 lea指令完成，随后由一条 mov 指令完成最后的赋值操作，这条 mov 指令的寻址方式与 lea 是一样的。
movl index, %edx
leal 32(, %edx, 8), %eax
movl %eax, array(, %edx, 4 )
程序定义其他模块的全局变量和函数在最终运行时的绝对地址都要在最终链接的时候才能确定。
所以现代的编译器可以将一个源代码文件编译成一个未链接的目标文件，然后由链接器最终将这些目标文件链接起来形成可执行文件。
三、链接器年龄比编译器长
1、原来的生活
在以前人们编写程序时，将所有源代码都写在同一个文件中，发展到后来一个程序源代码的文件长达数百万行，以至于人类已经没有能力维护这个程序了。
原始的链接概念远在高级程序语言发明之前就已经存在了，在最开始的时候，程序员先把一个程序在纸上写好，当然 当时没有很高级的语言，用的都是机器语言，甚至连汇编语言都没有。当程序须要被运行时，程序员人工将他写的程序写入到存储设备上，最原始的存储设备之一就是纸带，即在纸带上打相应的孔。
我们假设有一种跳转指令，它的高 4 位是 0001，表示这是一条跳转指令; 低 4位存放的是跳转目的地的绝对地址。
某个程序的第一条指令就是一条跳转指令，它的目的地址是第 5 条指令（注意，第 5 条指令的绝对地址是 4）。
程序并不是一写好就水远不变化的，它可能会经常被修改。
比如我们在第 1条指令之后、第5条指令之前插入了一条或多条指令，那么第 5条指令及后面的指令的位置将会相应地往后移动，原先第一条指令的低4 位的数字将需要相应地调整。在这个过程中，程序员需要人工重新计算每个子程序或跳转的目标地址。当程序修改的时候，这些位置都要重新计算，十分繁琐又耗时，并且很容易出错。这种重新计算各个目标的地址过程被叫做重定位（ Relocation）。
如果我们有多条纸带的程序，这些程序之间可能会有类似的跨纸带之间的跳转，这种程序经常修改 导致 跳转目标地址变化 在程序拥有多个模块的时候更为严重。
2、汇编语言与符号
汇编语言使用接近人类的各种符号和标记来帮助记忆，比如指令采用两个或三个字母的缩写，记住"jump"比记住 0001XXXX 是跳转（jump）指令容易得多了;
汇编语言还可以使用符号来标记位置，比如一个符号"divide"表示一个除法子程序的起始地址，比记住 从某个位置开始的 第几条指令 是除法子程序方便得多。
比如前而面纸带程序中，我们把第5条指令开始的子程序命名为"foo"，那么第一条指今的汇编就是; jmp foo
当然人们可以使用这种符号命名子程序或跳转目标以后，不管这个 “foo” 之前插入或减少了多少条指令 导致"foo" 目标地址发生了什么变化，汇编器在每次汇编程序的时候会重新计算"foo"这个符号的地址，然后把所有引用到 “foo” 的指今 修正到这个正确的地址。
符号（Symbol）这个概念随着汇编语言的普及迅速被使用，它用来表示一个地址，这个地址可能是一段子程序（后来发展成函数）的起始地址，也可以是一个变量的起始地址。
3、代码的模块化&层次结构组织
后来人们开始将代码按照功能或性质划分，分别形成不同的功能模块，不同的模块之间按照层次结构或其他结构来组织。
这个在现代的软件源代码组织中很常见
在 C 语言中，最小的单位是变量和函数，若干个变量和函数组成一个模块，存放在一个"，c"的源代码文件里，然后这些源代码文件按照目录结构来组织。
在Java 中，每个类是一个基本的模块，若干个类模块组成一个包（Package），若干个包组合成一个程序。
现代的大型软件往往拥有成千上万个模块，这些模块之间相互依赖又相对独立。
- 这种按照 层次化 及 模块化 存储 和 组织 源代码 有很多好处，比如代码更容易阅读、理解、重用，每个模块可以单独开发、编译、测试，改变部分代码不需要编译整个程序等。
模块之间如何组合的问题可以归结为模块之间如何通信的问题。
最常见的属于静态语言的C/C++模块之间通信有两种方式，一种是模块间的函数调用，另外一种是模块间的变量访问。
- 函数访向须知道目标函数的地址，变量访问也须知道目标变量的地址，所以这两种方式都可以归结为一种方式，那就是模块间符号的引用。
四、模块拼装——静态链接
人们把每个源代码模块独立地编译，然后按照须要将它们"组装"起来，这个组装模块的过程就是链接(Linking）。
链接的主要内容就是：把各个模块之间相互引用的部分都处理好，使得各个模块之间能够正确地衔接。
链接器所要做的工作 其实跟前面所描述的"程序员人工调整地址"本质上没什么两样，只不过现代的高级语言的诸多特性和功能，使得编译器、链接器更为复杂，功能更为强大。
从原理上来讲，链接器的工作是：把一些指令对其他符号地址的引用加以修正。
链接过程主要包括了地址和空间分配 （Address and Storage Allocation）、符号决议（Symbol Resolution）和重定位（Relocation） 等这些步骤。
符号决议有时候也被叫做符号绑定（Symbol Binding ）、名称绑定（Name Binding ）、名称决议（Name Resolution），甚至还有叫做地址绑定（Address Binding ）、指令绑定（Instruction Binding）的，大体上它们的意思都一样，但从细节角度来区分，它们之间还是存在一定区别的，比如"决议"更倾向于静态链接，而**“绑定” 更倾向于动态链接**，即它们所使用的范围不一样。
在静态链接，我们将统一称为符号决议。
每个模块的源代码文件 （如.c）文件经过编译器编译成目标文件（Object File，一般扩展名为.o 或.obj），目标文件（模块）和库（Library）一起链接形成最终可执行文件。
最常见的库就是运行时库（Runtime Library），它是支持程序运行的基本函数的集合。
库其实是一组目标文件的包，就是一些最常用的代码编泽成目标文件后打包存放。
五、小结
程序在经过 编译： 扫描、语法分析、语义分析、源代码优化、代码生成和目标代码优化 之后，源代码终干被编译成了目标代码。但是这个目标代码中有—个问题是∶ index 和 array 的地址还没有确定。
如果我们要把目标代码使用汇编器编译成真正能够在机器上执行的指令，那么 index 和 array 的地址应该从哪儿得到呢?
假设index 和 array 和 fun() 定义在 a.c文件中，在b.c文件中使用;
- 如果 index 和 array定义在跟上面的源代码同一个编译单元里面（定义和使用在同一个文件里），
那么编译器可以为 index 和 array 分配空间，确定它们的地址;
在编译之后，形成汇编代码，就已经确定了array和index的地址
- 如果index 和 array是定义在其他的程序模块（没有定义在一起，定义和使用不在同一个文件）呢?
b.c 在编译的时候并不知道 调用的 变量或函数 的地址，所以编译器暂时 将 调用这些变量和函数 的指令 的目标地址 搁置，等待 所有的模块（文件）编译汇编之后，链接器将目标地址修正
使用链接器，可以直接引用其他模块的函数和全局变量而无须知道它们的地址，因为链接器在链接的时候，会根据你所引用的符号 index&array&fun ，自动去相应的a.c 模块查找 index&array&fun的地址，然后将 b.c 模块中所有引用到index&array&fun的指令重新修正，让它们的目标地址为真止的index&array&fun的地址。
这就是静态链接的最基本的过程和作用。
目标代码中有变量定义在其他模块，该怎么办?
事实上，定义在其他模块的 全局变量和函数 在 最终运行时 的 绝对地址 都要 在 最终链接 的时候 才能确定。
所以现代的编译器可以将一个源代码文件编译成一个未链接的目标文件，然后由链接器最终将这些目标文件链接起来形成可执行文件。
在这一章中，我们首先回顾了从程序源代码到最终可执行文件的 4个步骤∶预编译、编译、汇编、链接，
分析了它们的作用及相互之间的联系，IDE 集成开发工具 和 编译器 默认的命令 通常将 这些步骤 合并成一步，使得我们通常很少关注这些步骤。
我们还详细回顾了上面这 4 个步骤中的主要部分，即编译步骤。介绍了编译器 将 C 程序源代码 转变成 汇编代码的若干个步骤∶词法分析、语法分析、语义分析、中间代码生成、目标代码生成与优化。
最后我们介绍了链接的历史和静态链接的一系列基本概念∶ 重定位、符号、符号决议、目标文件、库、运行库等概念。