【C语言】编译和链接

一、被隐藏的过程

#include <stdio.h>
int main()
{
    printf("Hello World\n");
    return 0;
}

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

gcc hello.c                         // 生成a.exe文件

a.exe

输出：

Hello World

事实上，上述过程可以分解成4个步骤，分别是预处理、编译、汇编和链接。 如下图。

 1.1 预编译

在预编译阶段，源文件和头文件会被处理成.i为后缀的文件。

对hello.c文件预编译成.i文件，命令如下( -E表示只进行与编译 )：

gcc -E hello.c -o hello.i

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

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

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

1.2 编译

编译过程就是把预处理完的文件进行一系列词法分析、语法分析、语义分析及优化，生成相应的汇编代码文件。

把hello.i编译成hello.s文件，命令如下：

gcc -S hello.i -o

1.3 汇编

汇编器是将汇编代码转变成机器可以执行的指令，每一个汇编语句几乎都对应一条机器指令。

命令如下：

gcc -c hello.s -o hello.o

 使用gcc命令从C源代码文件开始，结果预编译、编译和汇编直接输出目标文件：

gcc -c hello.c -o hello.o

1.4 链接

链接是一个让人比较费解的过程，为什么汇编器不直接输出可执行文件而是输出一个目标文件？链接过程到底包含了声明内容？为什么要链接？我们用第三章来分析静态链接。下面我们看看怎么样调用ld才可以产生一个能够正常运行的HelloWorld程序：

$ld -static /usr/lib/crtl.o /usr/lib/crti.o

/usr/lib/gcc/i486-linux-gnu/4.1.3/crtbeginT.o

-L/usr/lib/gcc/i486-linux-gnu/4.1.3 -L/usr/lib -L/lib hello.o --start-group

-lgcc -lgcc_eh -lc --end-group /usr/lib/gcc/i486-linux-gnu/4.1.3/crtend.o

/usr/lib/crtn.o

如果把所有路径省略，那么上面的1命令就是：

ld -static ctrl.o ctri.o  crtbeginT.o hello.o -start -group -lgcc -lgcc_en -lc --end-group crtend.o crtn.o

 我们需要将一大堆文件链接起来才可以得到“a.out”，即最终的可执行文件。

二、编译器

 最直观的角度来讲，编译器就是将高级语言翻译成机器语言的一个工具。比如我们用C\C++语言写一个促程序可以使用编译器将其翻译成机器可以执行的指令及数据。

我们知道，使用机器指令或汇编语言编写程序是十分费事及乏味的事情，它们使得程序开发效率十分低下。并且使用机器语言会汇编语言编写的程序依赖于特定的机器，一个为某种CPU编写的程序在另外一个CPU下完全无法运行，需要重新编写，这几乎是令人无法接受的。

所以人们期望能够采用类似于自然语言来描述一个程序，但是自然语言的形式不够精确，所以类似于数学定义的编程语言很快诞生了。20世纪六七十年代诞生了很多高级语言。

高级语言使得程序员能够更加关注程序逻辑本身，而尽量少考虑计算机本身的限制，如字长、内存大小、通信方式、存储方式等。高级编程语言的出现使得程序开发的效率大大提高，高级语言的可移植性也使得它在多种计算机平台下能够游刃有余。据研究，高级语言的开发效率是汇编语言和机器语言的5倍以上。

编译过程一般分为6步：扫描、语法分析、语义分析、源代码优化、代码生成和1目标代码优化。

 我们结合上图来简单描述从源代码到最终目标代码的过程。以一段很简单的代码为例来讲述这个过程。比如我们有一行C语言的源代码如下：

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

2.1 词法分析

首先源代码程序被输入到扫描器，扫描器的任务只是简单的进行词法分析，运用一种类似于有限状态机的三大可以很轻松的将源代码的字符序列分割成一系列的记号。比如上面的那行代码，总共包含28个非空字符，结果扫描以后，产生16个记号，如表：

词法分析产生的记号一般可以分为如下几类：关键字、标识符、字面量（包含数字、字符串等）和特殊符号（如记号、等号）。在识别记号的同时，扫描器也完成看其它工作。比如将标识符存放到符号表，将数组、字符串常量存放到文字表等，以备后面的步骤使用。

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

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

2.2 语法分析

接下来语法分析器将对由扫描器产生的记号进行语法分析，从而产生语法树。整个分析过程采用上下文无关语法的分析手段。如不清楚上下文无关语法，可参考该博客。编译原理学习之：上下文无关文法（Context-free Grammar）和下推自动机（Push-down automata）_上下文无关文法和下推自动机-CSDN博客

 简单的讲，由语法分析器生成的语法书就是以表达式为节点的树。上面例子中的语句就是一个由赋值表达式、加法表达式、乘法表达式、数组表达式、括号表达式组成的赋值语句，他是结果语法分析器以后形成如图的语法树。

 从上图可以看到，整个语句被看作是一个赋值表达式；赋值表达式的左边是一个数组表达式，右边是一个乘法表达式；数组表达式又由两个符号表达式组成，得等等。

2.3 语义分析

接下来进行语法分析，由语法分析器来完成。语法分析仅仅是完成了对表达式的语法层面的分析，但是它并不了解这个语句是否真正有意义。比如C语言里面两个指针做乘法运算是没有意义的，但是这个语句在语法分析上是合法的；比如同样一个指针和一个浮点数做乘法运算是否合法等。

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

静态语义通常包括声明和类型的匹配，类型的转换:

比如当一个浮点型的表达式赋值给一个整型的表达式，其中隐含了一个浮点型到整型转换的过程，语义分析中需要完成这个步骤。

float a = 9.8;
int b = a;//浮点型表达式赋值给整型表达式，隐含了一个浮点型到整型转换的过程

比如将一个浮点型赋值给一个指针的时候，语义分析会发现类型不匹配，编译器将会报错。

float a = 10.8;
float* f = a;//浮点型赋值给一个指针会报错

动态语义一般指运行期间出现的语义相关的问题，比如将0作为除数是一个运行期间语义错误。

结果语义分析阶段以后，这个语法树的表达式都被标识了类型。如果有些类型需要做隐式转换，语义分析程序就会在语法书中插入相应的转换节点。上述描述的语法树在经过语义分析阶段以后称为如下图所示：

 可以看到，每个表达式（包括符号和数字）都被标识了类型。我们的例子中几乎所有的表达式都是整型，所以无须做转换，整个分析过程很顺利。语义分析器还对符号表里的符号类型也做的更新。

2.4 中间语言生成

现代的编译器有很多层次的优化，往往在源代码级别会有一个优化过程，我们这里所描述的源码级优化器在不同的编译器中可能会有不同的定义或有一些其他的差异。源代码级优化器在源代码级别进行优化，在上例中，我们可以发现，（2+6）这个表达式可以被优化掉，因为他的值在编译器就可以被确定。经过优化的语法树如下图。

我们看到（2+6）这个表达式被优化成8。其实总结在语法树上作优化比较困难，所以元大妈优化器往往将整个语法树转换成中间代码，它是语法树的顺序表示，其实它已经非常接近目标代码了。但是它一般跟目标机器和运行时环境是无关的，比如它不包含数据的尺寸、变量地址和寄存器的名字等。中间代码有很多种类型，在不同的编译器中有着不的类型，比较常见由：三地址码 和 P-代码。我们就拿最常见的三地址码来作为例子，最基本的三地址码是这样的：

x = y op z

这个三地址码表示将变量y和z进行o操作以后，赋值给x。这里op操作可以是算数运算，比如加减乘除等，也可以是其他任何可以应用到y和z的操作。三地址码也得名于此，因为一个三地址码运距里面有三个变量地址。我们上面的例子中的语法树可以被翻译成三地址码后是这样的的：

t1 = 2 + 6

t2 = index + 4

t3 = t2 * t1

array[index] = t3

我们可以看到，为了使所有的操作都符合三地址码形式，这里利用了几个临时变量：t1、t2和t3。在三地址吗的基础上进行优化时，优化程序会将2+6的结果计算出来，得到t1=6。然后将后面代码中的t1替换成数字6.还可以省去一个临时变量t3，因为t2可以重复利用。经过优化后代码如下：

t2 = index + 4

t2 = t2 * 8

array[index  = t2

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

2.5 目标文件生成与优化

源代码级优化器产生中间代码标志着下面的过程都属于编辑器后端。编辑器后端主要包括代码生成器和目标代码优化器。让我们先来看看代码生成器。代码生成器将中间代码转换成目标机器代码，这个过程十分依赖于目标机器，因为不同的机器有着不同的字长、寄存器、整数数据类型和浮点数数据类型等。对于上面的例子中的中间代码，代码生成器可能会生成下面的代码序列（我们用x86的汇编语言来表示，并且假设index的类型为int型，array的类型为int型数组）；

movl index, %ecx            ;  valu of index to ecx

addl $4, %ecx                  ;  ecx = ecx+4

mull $8, %ecx                  ;  ecx = ecx + 4

movl index, %eax             ;  value of index to eax

movl %ecx, array(,eax,4)  ;  arrar[index] = ecx

 最后1目标代码优化器对上述的目标代码进行优化，比如选择合适的寻址方式、所以位移来代替乘法运算、删除多余的指令等。上面的例子中，乘法由一条相对复杂的基址比例变址寻址的lea指令完成，随后由一条mov指令完成最后的赋值操作，这条mov指令的寻址方式于lea是一样的。

movl  index, %edx

leal    32(,%edx,8),%eax

movl   %eax, array(,%edx,4)

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

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

这个问题引出一个很大的话题：目标代码中有变量定义在其他模块，该怎么办？

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

三、链接器 

计算机的程序开发并非一开始就有着这么复杂的自动化编译、链接过程。原始的链接概念远在高级程序语言发明之前就已经存在了，在最开始的时候，程序员先把一个程序写在纸上，当然当时没有很高级的语言，有的都是机器语言，甚至没有汇编语言。当程序要被运行时，程序员人工将他写的程序写入到存储设备上，最原始的存储设备之一就是纸带，即在纸带上打相应的孔。

假设有一个计算机，它的每条指令是1个字节，也就是8为。我们假设有一种跳转指令，他的高4位是0001，表示这是一条跳转指令；低4位存放的是跳转目的地的绝对地址。这个程序的第一条指令就是一个跳转指令，他的目的地址是第5条指令（注意，第5条指令的绝对地址是4）。

现在问题来了，程序并不是一成不变的，它可能会检测被修改、删除、移动。当程序修改的时候，这些位置都要重新计算，十分繁琐且耗时，并且容易出错。这种程序计算各个目标的地址过程被叫做重定位。

如果我们有多余纸带的程序，这些程序之间可能会有类似的跨纸带之间的跳转，这种程序经常修改导致跳转目标地址变化在程序拥有多个模块的时候更为严重。人工绑定进行指令的修正以确保所有的跳转目标地址都正确，在程序规模越来越大以后变得越来越复杂和繁琐。

后面先驱者发明了汇编语言，这相比机器语言来说是个很大的进步。汇编语言使用接近人类的各种符号和标记来帮助记忆，比如指令采用两个或三个字母的缩写，记住“jmp”比记住0001XXXX是跳转（jump）指令容易得多。