第二章——编译和链接

2.1 被隐藏了的过程
    C语句的经典，“Hello World”程序几乎是每个程序员闭着眼睛都能写出的，编译运行一气呵成，基本成了程序入门和开发环境测试的默认标准。

#include <stdio.h>

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

    在Linux下，我们用GCC来编译该程序时，只需使用简单的命令（假设源文件名为test.c）：
    
    事实上，上述过程可以分解为4个步骤，分别是预处理（Prepressing）、编译（Compilation）、汇编（Assembly）和链接（Linking）。具体如下图所示。
    

2.1.1 预处理
    首先是源代码文件test.c和相关的头文件，如stdio.h等被预处理器cpp预处理成一个.i文件。第一步预处理的过程相当于如下命令（-E表示只进行预处理）：

gcc -E test.c -o test.i

    预处理过程主要处理那些源代码文件只能够的以"#"开始的预编译指令。比如“#include”、“#define”等，主要处理规则如下：
    （1）将所有的“#define“删除，并且展开所有的宏定义；
    （2）处理所有条件预编译指令，比如”#if“、”#ifdef“、”#elif“、”#else“、#endif；
    （3）处理”#include“预编译指令，将被包含的文件插入到该预编译指令的位置。注意：这个过程是递归进行的，也就是说被包含的文件可能还包含其他文件；
    （4）删除所有的注释”//“和”、”/**/“；
    （5）添加行号和文件名标识，比如#2 "test.c" 2，以便于编译时编译器产生调试用的行号信息及用于编译时产生编译错误或警告时能够显示行号；
    （6）保留所有的#pragma编译器指令，因为编译器需要使用它们；
    经过预编译后的.i文件不包含任何宏定义，因为所有的宏已经被展开，并且包含的文件也已经被插入到.i文件中。所以当我们无法判断宏定义是否正确或头文件包含是否正确时，可以查看预处理后的文件来确定问题。

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

gcc -S test.i -o test.s

    现在版本的GCC把预处理和编译两个步骤合并成一个步骤，使用一个叫ccl的程序来完成两个步骤。我们可以直接使用如下命令：

gcc -S test.c -o test.s

    都可以得到汇编输出文件test.s。对于C语言代码来说，这个预处理和编译的程序是ccl，对于C++来说，有对应的程序叫做cclplus。
    所以实际上gcc这个命令只是这些后台程序的包装，它会根据不同的参数要求取调用预处理编译程序ccl、汇编器as、链接器ld。

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

as test.s -o test.o
或者
gcc -c test.s -o test.o

    或者使用gcc命令从C源代码文件开始，经过预处理、编译和汇编直接输出目标文件：

gcc -g test.c -o test.o

2.1.4 链接
    为什么汇编器不直接输出可执行文件而是输出一个目标文件呢？链接过程到底包含了什么内容？为啥要链接？我们可以调用ld产生一个能够运行的可执行程序。即需要将一大堆文件链接起来才可以得到“a.out”，即最终的可执行文件。

2.2 编译器做了什么
    从最直观的角度来讲，编译器就是将高级语言翻译成机器语言的一个工具。比如我们可以用C/C++语言写的一个程序可以使用编译器将其翻译成机器可以执行的指令及数据。
    编译的过程一般分为6步：扫描（词法分析）、语法分析、语义分析、源代码优化、代码生成和目标代码优化。整个过程如下图所示。
    
    我们将结合上图来简单描述从源代码到最终目标代码的过程。以一段很简单的C语义的代码为例子来讲述这个过程。比如我们有一行C语义的源代码如下：

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

2.2.1 词法分析
    首先源代码程序被输入到扫描器，扫描器的任务很简单，它只是简单地进行词法分析，运用一种类似于有限状态机的算法可以很轻松的将源代码的字符序列分割成一系列的记号。比如上面的那行程序，总共包含了28个非空字符，经过扫描后，产生了16个记号，如下表所示。
    
    
    词法分析产生的记号一般可分为如下几类：关键字、标识符、字面量（包含数字、字符串等）和特殊记号（如加好、等号）。在识别记号的同时，扫描器也完成了其他工作。比如将标识符存放到符号表中，将数字、字符串常量存放到文字表等，以备后面的步骤使用。
    有一个叫lex的程序可以实现词法扫描，它会按照用户之前描述好的词法规则将输入的字符串分割成一个个记号。
    另外对于一些有预处理的语言，比如C语言，它的宏替换和文件包含等工作一般不归入编译器的范围而交给一个独立的预处理器。

2.2.2 语法分析
    接下来语法分析器将对由扫描器产生的记号进行语法分析，从而产生语法树。整个分析过程采用了上下文无法语法的分析手段。简单的讲，由语法分析器生成的语法树就是以表达式为节点的树。我们知道，C语言的一个语句是一个表达式，而复杂的表达式由很多表达式组合。它在经过语法分析器以后形成如下图所示的语法树。
    
    从上图可以看到，整个语句被看作一个赋值表达式：赋值表达式的左边是一个数组表达式，它的右边是一个乘法表达式；数组表达式又由两个符号表达式组成，等等。符号和数字是最小的表达式，它们不是由其他的表达式来组成的，所以通常为整个语法树的叶节点。在语法分析的同时，很多运算符的优先级和含义也被确定下来。比如乘法表达式的优先级比加法高，而圆括号表达式的优先级比乘法高等等。如果出现了表达式不合法，比如各种括号不匹配、表达式中缺少操作符等等，编译器就会报告语法分析阶段的错误。
    语法分析也有一个现成的工具叫yacc。它也像lex一样，可以根据用户给定的语法规则对输入的记号序列进行解析，从而构建一棵语法树。

2.2.3 语义分析
    语义分析，由语义分析器完成。语法分析仅仅是完成了对表达式的语法层面的分析，但是它并不了解这个语句是否真正有意义。比如C语言里面两个指针做乘法运算是没有意义的，但是这个语句在语法上是合法的。编译器所能分析的语义是静态语义。所谓静态语义是指在编译期间可以确定的语义。与之对应的动态语义就是只有在运行期间才能确定的语义。
    静态语义通常包括声明和类型的匹配，类型的转换。比如当一个浮点型的表达式赋值给一个整型的表达式时，其中隐含了一个浮点型赋值给一个指针的时候，语义分析程序会发现这个类型不匹配，编译器将会报错。
    动态语义一般指在运行期间出现的语义相关的问题，比如将0作为除数是一个运行期语义错误。
    经过语义分析阶段后，整个语法树的表达式都被标识了类型，如果有些类型需要做隐式转化，语义分析程序会在语法树中插入相应的转换节点。上面描述的语法树在经过语义 分析阶段以后成为了如下图所示的形式。
    
    可以看到，每个表达式（包括符号和数字）都被标识了类型。我们的例子中几乎所有的表达式都是整型的，所以无需做转换。
    语义分析器还对符号表里的符号类型也做了更新。
 
2.2.4 中间语言生成
    现代的编译器有着很多层次的优化，往往在源代码级别会有一个优化过程。我们这里所描述的源码级优化器在不同编译器中可能会有不同的定义或一些其他差异。源代码优化器会在源代码级别进行优化。在上例中，可以发现，（2+6）这个表达式可以被优化掉，因为它的值在编译期间就可以被确定。
    经过优化的语法树如下图所示。
    
    可以看到（2 + 6）这个表达式被优化成8.其实直接在语法树上作优化比较困难，所以源代码优化器往往将整个语法树转换成中间代码，它是语法树的顺序表示，其实它已经非常接近目标代码了。但是它一般跟目标机器和运行时环境是无关的，比如不包含数据的尺寸、变量的地址和寄存器的名字等。中间代码有很多种类型，在不同的编译器中有着不同的形式，比如三地址码等。
    中间代码使得编译器可以被分成前端和后端。编译器前端负责产生机器无关的中间代码，编译器后端将中间代码转换成目标机器代码。这样对于一些可以跨平台的编译器而言，它们可以针对不同的平台使用同一个前端和针对不同的机器平台的数个后端。

2.2.5 目标代码生成与优化
    源代码级优化器产生中间代码标志着下面的过程都属于编译器后端。编译器后端主要包括代码生成器和目标代码优化器。
    代码生成器将中间代码转换成目标机器代码，这个代码十分依赖于目标机器，因为不同的机器有着不同的字长、寄存器、整数数据类型和浮点数数据类型等。
    对于上面例子的中间代码，代码生成器可能生成下面的代码序列：
    
    最后目标代码优化器对上面目标代码进行优化，比如选择合适的寻址方式、使用位移来代替乘法等。

    经过这些扫描（词法分析）、语法分析、语义分析、源代码优化、目标代码生成和目标代码优化，编译器经过这么多步骤，源代码终于被编译成了目标代码。但是这个目标代码中有一个问题：index和array的地址还没有确定。如果我们把目标代码使用汇编器编译成真正能够在机器上执行的指令，那么index和array的地址从哪里得的呢？如果index和array定义在跟上面的源代码同一个编译单元里面，那么编译器可以为index和array分配空间，确定它们的地址；那如下是定义在其他的程序模块中呢？
    目标代码中有变量定义在其他模块该怎么办？事实上，定义其他模块的全局变量和函数在最终运行时的绝对地址都要在最终链接的时候才能确定。所以现代的编译器可以将一个源代码文件编译成一个未链接的目标文件，然后由链接器最终将这些目标文件链接起来形成可执行文件。

2.3 链接器年龄比编译器长
2.4 模块拼装——静态链接
    人们把每个源代码模块独立地编译，然后按照要将它们“组装”起来，这个组装模块的过程就是链接。链接的主要内容就是把各个模块之间相互引用的部分都处理好，使得各个模块之间能够正确的衔接。
    但从原理上讲，它的工作无非就是把一些指令对其他符号地址的引用加以修正。链接过程主要包括了地址和空间分配、符号决议和重定位等这些步骤。
    最基本的静态链接过程如下图所示。每个模块的源代码文件（如.c）文件经过编译器编译成目标文件（如.o），目标文件和库一起链接形成最终可执行文件。而最常见的库就是运行时库，它是支持程序运行的基本函数集合。
    库其实就是一组目标文件的包，就是一些最常用的代码编译成目标文件后打包存放。
    
    在链接过程中，对其他定义在目标文件中的函数调用的指令需要被重新调整，对实用其他定义在其他目标文件的变量来说，也存在同样问题。
    让我们结合具体的CPU指令来了解这个过程。假设我们有个全局变量叫做var，它在目标文件A中。我们在目标文件B里面要访问这个全局变量，比如我们在目标文件B里面有这么一条指令：

movl $0x2a, var

    这条指令就是给这个var变量赋值0x2a，相当于C语言中的语句var = 42。然后我们编译目标文件B，得到这条指令机器码，如下图所示。
    
    由于在编译目标文件B的时候，编译器并不知道变量var的目标地址，所以编译器在没法确定地址的情况下，将这条mov指令的目标地址设为0，等待链接器在将目标文件A和B链接起来的时候再将其修正。假设A和B链接后，变量var的地址确定下来为0x1000，那么链接器将会把这个指令的目标地址部分修改成0x10000。这个地址修正的过程也叫做重定位，每个要被修正的地方叫一个重定位入口。

    PS：每个目标文件除了拥有自己的数据和二进制代码外，还提供了三个表：未解决符号表、导出符号表、地址重定向表。
    （1）未解决符号表提供了所有在该编译单元里引用但是定义并不是在本编译单元的符号以及其出现的地址；
    （2）导出符号表提供了本编译单元具有定义，并且愿意提供给其他单元使用的符号及其地址；
    （3）地址重定向表提供了本编译单元所有对自身地址的引用的记录；
    编译器将extern声明的变量置入未解决符号表，而不置入导出符号表；----外部链接
    编译器将static声明的全局变量不置入未解决符号表，也不置入导出符号表，因此其他单元无法使用；----内部链接
    普通变化及其函数被置入导出符号表；

    
    通过读了一遍这一章节，然后又记录了下来，对编译和链接有了初步的了解，但是只是皮毛而已，再接再厉。
    
    引自：《程序员自我修养》、网络等
    感谢