目录

深入理解程序 | 源文件变成可执行文件的过程

一个C语言文件从源文件到变成可执行文件,主要经过以下四个阶段:预编译(Prepressing),编译(compilation),汇编(assembly),链接(linking)。整个过程如图所示:

https://img.dawnguo.cn/All/image-20200911093244474.png

通常编译和链接合并在一起的过程称为构建(build)

1. 预编译

预编译是指源代码文件 .c 和相关的头文件等被预编译器 cpp 预编译成一个 .i 文件。整个预编译过程主要处理那些源代码文件中的以"#“开始的预编译指令,比如“#include”、“#define”等,相应的处理规则如下所示:

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

经预编译之后的 .i 文件不包含任何宏定义,因为所有的宏已经展开,并且包含的文件也已经插入到 .i 文件中。

下面来看一下如下的 hello world 代码预编译之后会变成什么样:

1
2
3
4
5
6
7
8
#include <stdio.h>
#define A 2

int main() {
  printf("Hello world\n");
  printf("A is %d\n", A);
  return 0;
}

使用如下命令即可只进行预编译

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

或者

1
$ cpp hello.c > hello.i

预编译之后的.i文件如下所示(截取了部分):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
	......
# 912 "/usr/include/stdio.h" 3 4
extern void flockfile (FILE *__stream) __attribute__ ((__nothrow__ , __leaf__));
extern int ftrylockfile (FILE *__stream) __attribute__ ((__nothrow__ , __leaf__)) ;
extern void funlockfile (FILE *__stream) __attribute__ ((__nothrow__ , __leaf__));
# 942 "/usr/include/stdio.h" 3 4

# 2 "hello.c" 2

# 4 "hello.c"
int main() {
 printf("Hello world\n");
 printf("A is %d\n", 2);
 return 0;
}

C++程序来说,源代码文件的扩展名是.cpp或者是.cxx,头文件的扩展名是.hpp,预编译之后的文件扩展名是.ii

2. 编译

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

https://img.dawnguo.cn/All/image-20200911094933803.png

上图中将整个编译过程 6 步:词法分析(扫描)、语法分析、语义分析、源代码优化、代码生成和目标代码优化,其实也就是将优化的过程进行了细分。下面结合上图和下面这段很简单的 C 语言代码为例子来讲述从源代码(source code)到最终目标代码(final target code)的过程

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

词法分析

词法分析由扫描器来完成,首先将源代码程序输入到 scanner(扫描器)中,scanner 的任务很简单,只简单的进行词法分析,运用一种类似于有限状态机的算法可以很轻松地将源代码的字符序列分割成一系列的 token(记号)。

有限状态机(Finite state machine)—我也没学过

上述 C 代码产生的记号如下表所示:

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

词法分析产生的 token 一般分为以下几类:关键字、标识符、字面量(包含数字、字符串等)和特殊符号(如加号、等号)。在识别记号的同时,扫码器也完成了其他工作,比如将标识符放入符号表,数字、字符串常量放入文字表等。

lex 的程序可以实现词法扫描,它可以按照用户之前描述好的词法规则将输入的字符串分割成一个个记号。那么编译器的开发者就可以不用为每个编译器开发一个独立的词法扫描器,而是根据需要改变词法规则就可以了。对于有预处理的语言,比如 C 语言就需要预处理,那么宏替换和文件包含等工作一般是交给一个预处理器,不属于编译的范围。

语法分析

接下去语法分析器(grammar parser)将对由扫描器产生的记号进行语法分析,从而产生语法树(syntax tree)。整个分析过程采用了上下文无关语法(context-freee grammer)的分析手段。语法树是以表达式为节点的树。C 语言的一个语句就是一个表达式,复杂的语句往往是由很多表达式组成的,比如上面的例子就是一个由赋值表达式、加法表达式、乘法表达式、数组表达式、括号表达式组成的复杂语句。那么生成的语法树如下所示:

https://img.dawnguo.cn/All/1_4.jpg

整个语句被看成赋值表达式。符号、数字是最小的表达式。它们不由其他的表达式组成,所以通常作为整个语法树的叶结点。同时,在语法分析的时候,很多运算符号的优先级和含义也被确定下来了(如乘法表达式的优先级比加法高),有多重含义符号的真正用途也被确定下来了(如*号既可以作为取地址内容,也可以作为乘号)。如果在这个过程中出现了表达式不合法,如各种括号不匹配、表达式中缺少操作符等,那么会报语法分析阶段的错误。

yacc是一个现成的语法分析工具,它也可以根据用户给定的语法规则对输入的token序列进行解析,从而构建一颗语法树。对于不同的编程语言,编译器的开发者只需要改变语法规则,而无须为每个编译器开发一个语法分析器。

语义分析

接下去进行语义分析,由语义分析器(semantic analyzer)来完成。**语法分析仅仅完成了对表达式的语法层面的分析(比如检查表达式是否完整等,就仅限于“形状“),但是并不了解这个语句是否真正有意义(比如 C 语言的两个指针做乘法在语法上是合法的,但在语义上是没有意义的)。**编译器所能分析的语义是静态语义(static semantic),即在编译期可以确定的语义,与之对应的是动态语义则只能在运行期才能确定。

**静态语义通常包括声明和类型的匹配,类型的转换(比如一个浮点型的表达式赋值给一个整型的表达式时,就隐含了一个浮点类型到整型转换的过程,语义分析过程需要完成这个步骤)。**比如将一个浮点型赋值给一个指针时,语义分析会发现这个类型不匹配,那么会报错。动态语义一般是指在运行期间出现的语义相关的问题,比如将0作为除数,在静态语义中它是没啥问题的,但它在运行时会出错,所以是一个运行期语义错误。语义分析器对符号表里的符号类型也做了更新。

经过语义分析以后,整颗语法树的表达式都被标识了类型,如果有些类型需要做隐式转换,语义分析程序会在语法树中插入相应的转换节点。上述语法树经过语义分析之后变成如下图所示,可见每个表达式都被标识了类型。由于没有类型转换,所以没有相应的转换节点。

https://img.dawnguo.cn/All/1_5.jpg

优化

中间代码

之后就是优化,现代的编译器有着很多层次的优化,其中一层优化是在源代码级的。比如我们上述代码中,(2 + 6)这个表达式可以被优化掉,因为它的值在编译期就可以被确定。但是直接在语法树上进行优化比较困难,所以源代码优化器先将整个语法树先转换为中间代码(intermediate),之后基于中间代码进行优化,中间代码是语法树的顺序表示,已经非常接近目标代码了,但是它一般跟目标机器和运行时环境是无关的,比如不包含数据的尺寸、变量地址和寄存器的名字等。另外中间代码也有很多种类型,在不同的编译器有着不同的形式,比较常见的有:**三地址码(three-address code)**和 P-代码(P-code)。上述例子中的语法树被翻译成三地址码之后如下所示

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

在三地址的基础上进行优化,优化程序会将 2+6 的结果计算出来,得到 t1=8,然后将后面代码中的 t1 替换成数字 8。那么经过优化之后的代码如下所示:

1
2
3
t2 = index + 4
t2 = t2 * 8
array[index] = t2

最基本的三地址码是这样的x = y op z,y 和z进行操作之后,赋值给x。

另外最最最最重要的是,中间代码使得编译器可以被分为前端和后端。编译器前端负责产生机器无关的中间代码,编译器后端将中间代码转换为目标机器代码。

目标代码&&目标代码优化

中间代码的产生标志着下面的过程都属于编译器后端,编译器后端主要包括代码生成器(code generator)和目标代码优化器(target code optimizer)。

代码生成器将中间代码转换为目标机器代码(个人觉得是汇编代码),这个过程依赖于目标机器,因为不同的机器有着不同的字长、寄存器、整数数据类型和浮点数据类型。上述例子的中间代码经代码生成器会生成下面的代码序列(x86 的汇编语言表示,index 的类型为int型,array 的类型为int型数组):

1
2
3
4
5
movl index, %ecx
addl $4, %ecx
mull $8, %ecx
movl index, %eax
movl %ecx, array(, eax, 4)

之后目标代码优化器对上述的目标代码进行优化,比如选择合适的寻址方式、使用位移来代替乘法运算、删除多余的指令等。那么经过优化之后的代码如下所示,加法和乘法由一条相对复杂的基址比例变址寻址的 lea 指令来完成,mov 指令也进行了优化,采用和 lea 一样的寻址方式。

1
2
3
movl index, %edx
leal 32(, %edx, 8), %eax
movl %eax, array(, %edx, 4)

GCC操作

上述编译的过程相当于使用了如下命令:

1
$ gcc -S hello.i -o hello.s

当然现在的 GCC 命令也可以把预编译和编译两步合并成一个步骤,使用如下命令

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

也可以使用 cc1 的程序来完成预编译和编译这两步,最终得到汇编文件

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
$ /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 (17%) wall    1093 kB (65%) ggc
 phase parsing           :   0.01 (100%) usr   0.00 ( 0%) sys   0.02 (33%) wall     521 kB (31%) ggc
 phase opt and generate  :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.03 (50%) wall      58 kB ( 3%) ggc
 ipa inlining heuristics :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.02 (33%) wall       0 kB ( 0%) ggc
 preprocessing           :   0.01 (100%) usr   0.00 ( 0%) sys   0.02 (33%) wall     219 kB (13%) ggc
 rest of compilation     :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 (17%) wall      14 kB ( 1%) ggc
 TOTAL                 :   0.01             0.00             0.06               1690 kB

对于 C 语言程序来说,这个预编译和编译的程序是 cc1,对于 C++ 来说这个程序是 cc1plus.

3. 汇编

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

汇编的过程使用汇编器 as 来完成:

1
as hello.s -o hello.o

也可以使用 GCC 命令将汇编文件汇编成目标文件(object file),也可以从 C 源代码开始,经过预编译、编译和汇编直接输出目标文件(object file)

1
2
gcc -c hello.s -o hello.o
gcc -c hello.c -o hello.o

object file 没有一个很合适的中文名称,把它叫做中间目标文件比较合适,简称目标文件。有时候目标文件也称为模块。

4. 链接

链接的主要内容就是把各个模块之间相互引用的部分都处理好,使得各个模块之间能够正确地衔接。从原理上来讲,它的工作无非就是把一些指令对其他符号地址的引用加以修正。链接过程主要包括了地址和空间分配、符号决议和重定位等步骤。

符号决议有时也叫符号绑定,大体上绑定和决议的意思是一样的,但是从细节角度来区分的话,它们之间还是存在一定区别的,比如决议更倾向于静态链接,绑定倾向于动态链接。

最基本的静态链接过程如下所示,每个模块的源代码文件(如.c)文件经过编译器编译成目标文件(object file,一般扩展名为.o或.obj),之后目标文件和库(library)一起链接形成最终可执行文件。最常见的库是运行时库(runtime library),是支持程序运行的基本函数的集合,是一组目标文件的包(就是一些最常用的代码编译成目标文件后打包存放)。

https://img.dawnguo.cn/All/image-20200911095950021.png

拿具体的例子来说,就是比如程序模块 mian.c 中使用了另外一个模块 func.c 中的函数 foo(),由于每个模块都是单独编译的,在编译器编译 main.c 的时候并不知道 foo() 函数的地址,所以先暂时把调用 foo 的指令的目标地址搁置,等待最后链接的时候由链接器将这些指令的目标地址修正。链接器在链接的时候,会根据你所引用的符号foo,自动去相应的 func.c 模块中查找 foo 的地址,然后将 main.c 中所有引用 foo 的指令进行修正,使其目标地址为真正的 foo() 函数的地址。同理,引用定义在其他目标文件中变量的指令也需要进行调整。

链接的过程可以使用链接器 ld,示例命令如下所示:

1
ld -static ctr1.o ctri.o crtbeginT.o ... hello.o

5. 总结

整个编译和链接的过程主要如下所示:

  • 预编译:主要是处理 # 开头的内容,比如将所有 #define 删除,并展开所有宏定义,处理 #include,这一步最终将 .c 处理成 .i 文件;

  • 编译:.i 文件经过词法分析、语法分析、语义分析、优化【中间代码生成,中间代码优化(源代码级别)、目标代码生成、目标代码优化(目标代码这边我觉得是汇编语言,虽然没有书中没有讲)】,最终生成汇编文件;

    词法分析主要是负责将处理之后 .i 文件变成一系列 token;语法分析则是将一系列 token 转化成一颗语法树,语法分析更多是检查这条语句是否完整,偏表面(个人理解);语义分析则侧重于这条语句的静态语义是否合理,主要是类型相关的检查,如两个类型进行某种操作是否合理(个人理解)。比如将 0 作为除数,语法上它是完成的,在静态语义中,它的类型检查也是没啥问题的,但它在运行时会出错,而这个错误是运行期语义错误,编译期无法进行动态语义分析。

    优化的一般的过程分为两步:①先将语义分析之后的语法树转换为中间代码,在中间代码上进行源代码级的优化;②之后中间代码转换成目标代码(个人觉得是汇编代码),之后对目标代码进行优化。另外在这个步骤中,中间代码的生成使得编译器分为前后端,产生中间代码之前被称为前端,产生中间代码之后被称为后端。前端主要是词法、语法、语义分析,后端则跟机器平台关系紧密相关。

  • 汇编:将生成的汇编文件汇编成机器码,生成 object file;

  • 链接:将上述生成的 object file 进行链接,在链接过程中需重新计算各个目标的地址(这个过程称为重定位),最终链接成一个可执行程序。

巨人的肩膀

  1. 《程序员的自我修养—链接、装载与库》.俞甲子,石凡,潘爱民