计算机那些事(3)——程序构建及编译原理
最近在看《程序员的自我修养——链接、装载与库》一书，这本书以前看过一部分，由于难啃，当时没有坚持下去。现在工作了，每天接触的都是业务开发，对底层的一些东西感觉越来越陌生。于是，又把此书翻了出来拜读。为了加深阅读的印象，打算对书中的一些有价值的内容进行整理，也方便后续回顾。
程序构建流程
下面以“Hello World”程序为例，来介绍程序的编译与链接过程。
1
2
3
4
5
6
7// hello.c
#include <stdio.h>
int main() {
printf("Hello World!\n");
return 0;
}
在Linux下，可以直接使用GCC来编译Hello World程序： 1
2
3$ gcc hello.c
$ ./a.out
Hello World!
GCC编译命令隐藏了构建过程中的一些复杂的步骤，主要有4个步骤，如下图所示。
- 预处理（Propressing）
- 编译（Compilation）
- 汇编（Assembly）
- 链接（Linking）
预编译
预编译步骤将源代码文件 hello.c
以及相关头文件，如：stdio.h
等预编译生成一个.i文件。对于C++程序，其源代码文件的扩展名可能是.cpp或.cxx，头文件的扩展名可能是.hpp，预编译生成.ii文件。
预编译步骤相当于执行如下命令（选项-E表示只进行预编译） 1
$ gcc -E hello.c -o hello.i
1
$ cpp hello.c > hello.i
预编译 主要处理源代码中的以“#”开始的预编译指令，如：“#include”、“#define”等，其主要处理规则如下：
- 将所有的“#define”删除，并且展开所有的宏定义。
- 处理所有条件预编译指令，如：“#if”、“#ifdef”、“#else”、“#endif”。
- 处理“#include”预编译指令，将被包含的文件插入到该预编译指令的位置。该过程是递归进行的，因为被包含的文件可能还包含其他文件。
- 删除所有的注释“//”和“/* */”。
- 添加行号和文件名标识，比如#2 “hello.c” 2，以便于编译时编译器产生调试试用的行号信息以及用于编译时产生编译错误或警告时能够显示行号。
- 保留所有的#pragma编译器指令，因为编译器须要试用他们。
预编译生成的.i文件不包含任何宏定义，因为所有的宏已经被展开，并且包含的文件也已经被插入到.i文件中。所以当我们无法判断宏定义是否正确或头文件包含是否正确时，可以查看预编译后的文件来确定问题。
编译
编译 就是把预处理生成的文件进行一系列词法分析、语法分析、语义分析、优化，生成相应的汇编代码文件。这个过程是整个程序构建的核心部分，也是最复杂的部分之一。
编译步骤相当于执行如下命令： 1
$ gcc -S hello.i -o hello.s
1
$ gcc -S hello.c -o hello.s
现在版本的GCC把预编译和编译两个步骤合并成了一个步骤，使用一个叫cc1的程序来完成。该程序位于“/usr/lib/gcc/x86_64-linux-gnu/4.8/”，我们可以直接调用cc1来完成它：
1
$ /usr/lib/gcc/x86_64-linux-gnu/4.8/cc1 hello.c
事实上，对于不同的语言，预编译与编译的程序是不同的，如下所示： - C：cc1 - C++：cc1plus - Objective-C：cc1obj - Fortran：f771 - Java：jc1
GCC是对这些后台程序的封装，它会根据不同的参数来调用预编译程序cc1、汇编器as、链接器ld。
汇编
汇编 就是将汇编代码转换成机器可以执行的指令，每一个汇编语句几乎都对应一条机器指令。汇编过程相对于编译比较简单，其没有复杂的语法、语义，也无需做指令优化，只是根据汇编指令和机器指令的对照表进行翻译。
汇编步骤相当执行如下命令： 1
$ gcc -c hello.s -o hello.o
1
$ gcc -c hello.c -o hello.o
1
$ as hello.s -o hello.o
链接
链接 主要是将前面步骤生成多个目标文件进行重定位等复杂的操作，从而生成可执行文件。链接可分为静态链接和动态链接。
编译器工作原理
编译过程可以分为6个步骤，如下图所示。
- 扫描（Scanning）（又称词法分析）
- 语法分析（Syntax analysis）
- 语义分析（Semantic Analysis）
- 源代码优化（Source Code Optimization）
- 目标代码生成（Target Code Generation）
- 目标代码优化（Target Code Optimization）
下面我们以一行简单的C语言代码为例，简单描述从 源代码（Source
Code） 到 最终目标代码 的过程。代码示例如下：
1
2// CompilerExpression.c
array[index] = (index + 4) * (2 + 6)
以上述代码为例，总共包含了28个非空字符，经过扫描后，产生了16个记号。
| 记号 | 类型 | 记号 | 类型 |
|---|---|---|---|
| array | 标识符 | [ | 左方括号 |
| index | 标识符 | ] | 右方括号 |
| = | 赋值 | ( | 左圆括号 |
| index | 标识符 | + | 加号 |
| 4 | 数字 | ) | 右圆括号 |
| * | 乘号 | ( | 左圆括号 |
| 2 | 数字 | + | 加号 |
| 6 | 数字 | ) | 右圆括号 |
词法分析产生的记号一般可以分为一下几类：关键字、字面量（包含数字、字符串等）和 特殊符号（如加号、等号）。
在识别记号的同时，扫描器也完成了其他工作。如：将标识符存放到符号表，将数字、字符串常量存放到文字表等，以备后面的步骤使用。
有一个名为lex的程序可以实现词法扫描，它会按照用户之前描述好的词法规则将输入的字符串分割成一个个记号。正因为有这样一个程序存在，编译器的开发者就无需为每个编译器开发一个独立的词法扫描器，而是根据需要改变词法规则即可。
语法分析
语法分析器（Grammar Parser） 将对由扫描器产生的记号进行语法分析。从而产生 语法树（Syntax Tree）。整个分析过程采用了 上下文无关语法（Context-freeGrammar） 的分析手段。简单地讲，由语法分析器生成的语法树是以 表达式（Expression） 为节点的树。
以上述代码为例，其中的语句就是一个由赋值表达式、加法表达式、乘法表达式、数组表达式、括号表达式组成的复杂语句，下图所示为该语句经过语法分析器后生成的语法树。
1
2// CompilerExpression.c
array[index] = (index + 4) * (2 + 6)
在语法分析的同时，很多运算符号的优先级和含义也被确定下来了。如：乘法表达式的优先级比加法高，圆括号表达式的优先级比乘法高，等等。另外，有些符号具有多重含义，如“*”在C语言中可以表示乘法表达式，也可以表示对指针取内容的表达式，因此语法分析阶段必须对这些内容进行区分。如果出现了表达式不合法，如各种括号不匹配、表达式中缺少操作符等，编译器就会报告语法分析阶段的错误。
有一个名为yacc（Yet Another Compiler Compiler）的工具可以实现语法分析。其根据用户给定的语法规则对输入的记号序列进行解析，从而构建出语法树。对于不同的编程语言，编译器的开发者只需改变语法规则，而无需为每个编译器编写一个语法分析器。因此，其也称为“编译器编译器（Compiler Compiler）”
语义分析
语法分析仅仅完成了对表达式的语法层面的分析，但它并不了解这个语句的真正含义，如：C语言里两个指针做乘法运算是没有意义的，但这个语句在语法上是合法的。编译器所能分析的语义是 静态语义（Static Semantic），所谓静态语义是指在编译期间可以确定的语义，与之对应的 动态语义（Dynamic Semantic） 就是只有在运行期才能确定的语义。
静态语义通常包括声明和类型的匹配，类型的转换。比如当一个浮点型的表达式赋值给一个整型的表达式时，其中隐含了一个浮点型到整型的转换过程，语义分析过程中需要完成该步骤。比如讲一个浮点赋值给一个指针时，语义分析程序会发现这个类型不匹配，编译器将会报错。动态语义一般是指在运行期出现的语义相关的问题，比如将0作为除数是一个运行期语义错误。
经过语义分析阶段之后，整个语法树的表达式都被标识了类型，如果有些类型需要做隐式转换，语义分析程序会在语法树中插入相应的转换节点。下图所示为标记语义后的语法树。
源代码优化（中间代码生成）
现代编译器有着很多层次的优化，源码优化器（Source Code Optimizer） 则是在源代码级别进行优化。上述例子中，（2 + 6）这个表达式可以被优化掉。因为它的值在编译期就可以被确定。下图所示为优化后的语法树。
事实上，直接在语法树上作优化比较困难，所以源代码优化器往往将整个语法树转换成 中间代码（Intermediate Code），它是语法树的顺序表示，其实它已经非常接近目标代码了。但它一般与目标机器和运行时环境是无关的，比如它不包含数据的尺寸、变量地址和寄存器的名字等。
中间代码有很多种类型，在不同的编译器中有着不同的形式，比较常见的有：三地址码（Three-address
Code）、P-代码（P-Code）。以三地址码为例，最基本的三地址码如下所示：
1
2x = y op z
# 表示将变量y和z进行op操作后，赋值给x。
因此，可以将上述例子的代码翻译成三地址码： 1
2
3
4t1 = 2 + 6
t2 = index + 4
t3 = t2 * t1
array[index] = t31
2
3t2 = index + 4
t2 = t2 * 8
array[index] = t2
目标代码生成
目标代码生成主要由 代码生成器（Code Generator） 完成。代码生成器将中间代码转换成目标机器代码，该过程十分依赖目标机器，因为不同的机器有着不同的字长、寄存器、整数数据类型和浮点数数据类型等。
上述例子的中间代码，经过代码生成器的处理之后可能会生成如下所示的代码序列（以x86汇编为例，假设index的类型为int型，array的类型为int型数组）：
1
2
3
4
5movl 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
目标代码优化
目标代码生成后，由 目标代码优化器（Target Code Optimizer） 来进行优化。比如选择合适的寻址方式、使用位移来代替乘法运算、删除多余的指令等。
上述例子中，乘法由一条相对复杂的 基址比例变址寻址（Base Index
Scale Addressing）
的lea指令完成，随后由一条mov指令完成最后的赋值操作，这条mov指令的寻址方式与lea是一样的。如下所示为优化后的目标代码：
1
2
3movl index, %edx
leal 32(,%edx,8), %eax
movl %eax, array(,%edx,4)
结尾
经过扫描、语法分析、语义分析、源代码优化、目标代码生成、目标代码优化等一系列步骤之后，源代码终于被编译成了目标代码。但是这个目标代码中有一个问题：
index和array的地址还没有确定
如果我们把目标代码使用汇编器编译成真正能够在机器上运行的指令，那么index和array的地址来自哪里？
如果index和array定义在跟上面的源代码同一个编译单元里，那么编译器可以为index和array分配空间，确定地址；但如果是定义在其他的程序模块呢？
事实上，定义其他模块的全局变量和函数在最终运行时的绝对地址都要在最终链接的时候才能确定。所以现代编译器可以将一个源文件编译成一个未链接的目标文件，然后由编译器最终将这些目标文件链接起来形成可执行文件。
后面，我们将继而探讨链接的原理。
（完）