程序员的自我修养——编译和链接

编译和链接

在一般的IDE中，编译和链接被合并在了一起，称为构建（build），往往一些本质的东西是无法了解到

被隐藏的过程

在Linux下如果使用gcc编译一个c语言程序，只需最简单的命令：
gcc hello.c
./a.out

事实上，上述的过程可以分为4个步骤：

• 预处理（Prepressing）
• 编译（Compilation）
• 汇编（Assembly）
• 链接（Linking）

预编译

首先是源代码文件hello.c和相关的头文件，如stdio.h等被预编器cpp预编译成一个.i文件。对于C++程序来说，它的源代码文件的扩展名可能是.cpp或.cxx，头文件的扩展名可能是.hpp，而预编译后的扩展文件名是.ii，第一步预编译的过程相当于如下命名：

gcc -E hello.c -o hello.i

其中-E表示只进行预编译

或者：

cpp hello.c > hello.i

预编译过程主要处理那些源代码中的以 “#” 开头的预编译指令，主要处理规则如下：

• 将所有的"#define"删去，并且展开所有的宏定义
• 处理所有的条件预编译指令，如 “#if”、“#ifdef” 等
• 处理"#include"预编译指令，将被包含的文件插入到该预编译指令的位置
• 删除所有的注释
• 添加行号和文件名标识，比如#2"hello.c" 2，以便编译时产生调试用的行号信息，提示错误等等
• 保留所有的"#pragma"编译指令，因为编译器需要使用它们

编译

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

gcc -S hello.i -o hello.s

得到编译输出的汇编文件hello.s

汇编

汇编器将汇编代码转变为机器可以执行的指令，每个汇编语句几乎对应一条机器指令。上面的汇编我们可以调用汇编器as来完成

as hello.s -o hello.o

也可以用gcc直接从c源码输出目标文件

gcc -c hello.c -o hello.o

链接

我们需要把一大堆文件链接起来才能得到"a.out"，即最终的可执行文件，
链接过程会链接一些程序如：crt1.o、crti.o、crtbeginT.o、crtend.o、crtn.o

编译器做了什么

最直观的说，编译器将高级语言转化为机器语言。

细一点说，就是上面提到的词法分析和语法分析那些。

词法分析

首先，源代码程序被输入到扫描器（Scanner）中，扫描器的任务很简单，它只是简单的进行词法分析，运用一种类似于有限状态机（Finite State Machine）的算法可以轻松地将源代码的字符串分割为一系列的记号（Token），有一个叫做lex的程序可以实现词法扫描。

有限状态机

有限状态自动机（FSM “finite state machine” 或者FSA “finite state automaton” ）是为研究有限内存的计算过程和某些语言类而抽象出的一种计算模型。有限状态自动机拥有有限数量的状态，每个状态可以迁移到零个或多个状态，输入字串决定执行哪个状态的迁移。有限状态自动机可以表示为一个有向图。有限状态自动机是自动机理论的研究对象(来源百度)

Lex

Lex 是一种生成扫描器的工具。扫描器是一种识别文本中的词汇模式的程序。 这些词汇模式（或者常规表达式）在一种特殊的句子结构中定义。
一种匹配的常规表达式可能会包含相关的动作。这一动作可能还包括返回一个标记。 当 Lex 接收到文件或文本形式的输入时，它试图将文本与常规表达式进行匹配。 它一次读入一个输入字符，直到找到一个匹配的模式。 如果能够找到一个匹配的模式，Lex 就执行相关的动作（可能包括返回一个标记）。 另一方面，如果没有可以匹配的常规表达式，将会停止进一步的处理，Lex 将显示一个错误消息。
Lex 和 C 是强耦合的。一个 .lex 文件（Lex 文件具有 .lex 的扩展名）通过 lex 公用程序来传递，并生成 C 的输出文件。这些文件被编译为词法分析器的可执行版本。

词法分析产生的记号可以分为如下几类：关键字，标识符，字面量（含数字，字符串）和特殊符号（加号，等号）

如：
array[index] = (index + 4) * 2

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

语法分析

接下来语法分析器（Grammar Parser）将对扫描器产生的记号进行语法分析，从而产生语法树（Syntax Tree）。整个分析采取**上下文无关语法（Context-free Grammar）**的分析手段

上下文无关语法分析手段

由语法分析器生成的语法树就是以**表达式（Expression）**为节点的树。我们知道，C语言的一个语句是一个表达式，而复杂的语句是多个表达式的组合。
以书上的语法树的样子作为一个例子：

这个例子中，整个语句被当做一个赋值表达式，在语法分析的同时，很多的运算符号的优先级和含义也被确定下来了。

语法分析也有一个现成的工具yacc（Yet Another Compiler Compiler）。对于不同的编程语言，编译器的开发者只需要改变语法规则，而无需为每个编译器写一个语法分析器，所以它又被称为**“编译器编译器（Compiler Compiler）”**

yacc
我们看到 Lex 从输入序列中识别标记。 如果你在查看标记序列，你可能想在这一序列出现时执行某一动作。这种情况下有效序列的规范称为语法。Yacc 语法文件包括这一语法规范。它还包含了序列匹配时你想要做的事。
为了更加说清这一概念，让我们以英语为例。 这一套标记可能是：名词, 动词, 形容词等等。为了使用这些标记造一个语法正确的句子，你的结构必须符合一定的规则。 一个简单的句子可能是名词+动词或者名词+动词+名词。(如 I care. See spot run.)

用 Yacc 来创建一个编译器包括四个步骤：
通过在语法文件上运行 Yacc 生成一个解析器。
说明语法：
编写一个 .y 的语法文件（同时说明 C 在这里要进行的动作）。
编写一个词法分析器来处理输入并将标记传递给解析器。 这可以使用 Lex 来完成。
编写一个函数，通过调用 yyparse() 来开始解析。
编写错误处理例程（如 yyerror()）。
编译 Yacc 生成的代码以及其他相关的源文件。
将目标文件链接到适当的可执行解析器库。

语义分析

语义分析由语义分析器（Semantic Analyzer）来完成，语法分析仅仅只是表面的上的分析，但他并不明白这个语句真正有没有含义。编译器能分析的语义是静态语义（Static Semantic），在编译期间可以确定的语义，而对应的**动态语义（Dynamic Semantic）**就只有在运行中才可以确定。

• 静态语义通常包括声明和类型匹配，类型转换。如：浮点数赋值给了一个整型，隐含一个转换，就需要静态语义的分析。

• 动态语义就是分析运行时的语义问题，如：0不能做除数，需要抛出错误异常等，需要动态语义分析

中间语言生成

现代的编译器有很多层的优化，往往在源代码级别会有一个优化过程，称为源码级优化器（Source Code Optimizer）

源码优化器往往会将整个语法树转换为中间代码（Intermediate Code），中间代码很接近目标代码了，只是其与运行的机器的环境无关，如：不包含数据的尺寸，变量地址，寄存器名称。中间代码有很多的类型，比较常见的是三地址码（Three-address Code）和P-代码（P-Code）

最基本的三地址码是这样的：

x = y op z

一般为了使所有的操作都符号三地址码，往往需要添加中间变量

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

// 三地址码

t1 = index + 4
t1 = t1 * 2
array[index] = t1

目标代码的生成

**代码生成器（Code Generator）**将中间代码转换为目标机器代码。

生成目标代码后会进一步的优化，如选择合适的寻址方式，使用移位来代替乘法，删除多余的指令等。

经过扫描，语法语义分析，源代码优化，代码生成和目标代码的优化，源代码被编译为目标代码，但如果想要使用汇编编译成真正能够在机器上执行的指令，还需要考虑一些别的问题：

上述代码中index和array的地址怎么获得

如果只是在一个文件里，直接分配空间就可以确定地址，但如果在别的程序模块里呢？

链接器

当程序设计模块化时，各个模块直接通信依赖的就是链接（Linking），链接又分2种，静态链接和动态链接

链接的主要作用就是把各个模块之间的符号引用部分处理好。它所做的工作就是调地址，修正一些引用。链接的过程主要包括：地址空间分配（Address and Storage Allocation），符号决议（Symbol Resolution），重定位（Relocation）

以c语言为例，当我们在main里引用了再func.c里声明的函数foo()，那么在编译main.c时。编译器并不知道foo函数的地址，所以它就先搁置，等链接时去修正，链接器会把待修正的地址根据在引用的目标文件里查找来修正，这个修正的过程叫重定位，每个修正的地方叫重定位入口（Entry）

静态链接

最基本的静态链接就是把库和目标文件链在一起，最常见的就是运行时库（Runtime Library），库就是一组目标文件的包，把一些常用的代码编译成目标文件然后打包存放起来。

动态链接

为了节省内存，在运行时只装载一部分的文件进入内存，同时保障程序正常运行。常见的.dll文件就是动态链接库

后记——实验环境

我的Linux机又又又炸了，忍无可忍，在windows下用wsl

windows装wsl

在应用商店里搜索Ubuntu，安装应用即可

安装完后按下面的步骤启动Windows对Linux子系统的支持：

• 我的电脑 > 属性 > 控制面板 > 程序 > 启用或关闭Windows的功能，找到适用于Linux的Windows子系统，勾选然后重启。

不行的话

• Enable-WindowsOptionalFeature -Online -FeatureName Microsoft-Windows-Subsystem-Linux

然后按提示重启

然后换源，升级apt，后续的就按你自己的喜好来吧