编译原理笔记

程序如何被机器识别

机器只能识别010101这样的机器码，使用高级语言编写的程序，必须转换成机器码才能够被机器识别。

高级语言程序转换成机器码经历了以下几个步骤：

• 预编译（Propressing）
• 编译（Compilation）
• 汇编（Assembly）
• 链接（Linking）

接下来依次讲解这个几个步骤的详细过程。

1.预编译

对于 C 语言而言，源代码文件 hello.c 和头文件 stdio.h 等会被预编译器 cpp 预编译成一个 .i 文件。

对于 C++ 程序来说，源代码文件拓展名可能是 .cpp 或 .cxx，头文件拓展名可能是 .hh，预编译后的文件拓展名是 .ii。

预编译过程的主要工作

预编译过程主要处理那些源代码文件中的以“#”开头的预编译指令。比如 #include、#define 等。

主要处理规则如下：

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

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

2.编译

编译是整个程序构建的核心部分，也是最复杂的部分之一。编译主要有以下几个步骤：

• 词法分析
• 语法分析
• 语义分析
• 中间代码生成
• 目标代码生成
• 优化

以下面这段 C 语言程序为例，描述从源代码（Source Code）到最终目标代码（Final Target Code）的过程。

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

1.词法分析

首先源代码被输入到扫描器（Scanner），扫描器的任务很简单，只是简单地进行词法分析，运用一种类似于有限状态机（Finite State Machine）的算法将源代码的字符序列分割成一系列的记号（Token）。

以上述代码为例，总共包含了28个非空字符，经过扫描后，产生了16个记号。

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

词法分析输出结果：二元组的形式，即（单词种别，单词自身的值），其中单词种别通常用整数编码来表示。

状态转换图：是一张有限方向图。

• 节点代表状态，用圆圈表示。
• 状态之间用箭弧连接，箭弧上的标记（字符）代表可能出现的输入字符或字符类。
• 一张转换图只包含有限个状态，其中有一个为初态，至少有一个终态。
• 箭头表示初态，双圈表示终态。

若存在一条从初态到某一终态的路线，且这条路线上所有弧上的标记连接成的字符等于 α，则成 α 被该状态转换图所识别（接收）。

示例：从状态1出发，读入一个字母以后，就转入状态2，在状态2上面，如果继续读入的是数字或者字母，就会回到状态2。直到读入一个不是数字或字母的字符，就转到了状态3。状态3是一个终态，表示完成了一个单词的识别。

注：* 号表示最后一个读入的字符不属于这个单词，要把它退回去。

代码实现：

int code, value;
strToken = ""; // 存放字符串
GetChar(); // 读取下一个字符
GetBC(); // 跳过空白符，直至读入非空白符

if (IsLetter()) // 是否是字母
begin
	while (IsLetter() or IsDigit()) // 是否是字母或数字
	begin
		Concat(); // 把字符拼到 strToken 后
		GetChar();
	end
	Retract();
	code := Reserve();
	if (code = 0)
	begin
		value := InsertId(strToken);
		return ($ID, value);
	end
	else
		return (code, -);
end

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

在识别记号的同时，扫描器也完成了其他工作。如：将标识符存放到符号表，将数字、字符串常量存放到文字表等，以备后面的步骤使用。

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

2.语法分析

首先需要掌握几个概念：

终结符与非终结符

非终结符：

非终结符是可以再分解和定义的，非终结符对应语言各层次的句法单位，可以由终结符和非终结符共同组成。非终结符集合和终结符集合是不相交的。一个形式文法中必须有一个起始符号，这个起始符号属于非终结符的集合。

终结符：

详细一点说：终结符是一个形式语言的基本符号。就是说，它们能在一个形式语法的推导规则的输入或输出字符串存在，而且它们不能被分解成更小的单位。确切地说，一个语法的规则不能改变终结符。

类比：

<句子>
=> <主语><谓语><间接宾语><直接宾语>
=> <代词><谓语><间接宾语><直接宾语>
=> He <谓语><间接宾语><直接宾语>
=> He gave <间接宾语><直接宾语>
=> He gave me <代词><直接宾语>
=> He gave me <直接宾语>
=> He gave me <冠词><名词>
=> He gave me a <名词>
=> He gave me a book

这是一个英文句子的语法分析过程，其中<主语><谓语>可以再分解，可以把它们理解为非终结符。

He gave me 是具体的单词，不可以再分解，可以理解为终结符。

上下文无关文法

这里不多说了，直接放图片：

语法分析的方法主要有两类

1.自下而上（Bottom-up）

• 从输入串开始，逐步进行规约，直到文法的开始符号
• 规约：根据文法的产生式规则，把串中出现的产生式的右部替换成左部符号（是推导的逆过程）
• 从叶节点开始，构造语法树
• 算法优先分析法、LR分析法

2.自上而下（Top-down）

• 从文法的开始符号出发，反复使用各种产生式，寻找“匹配”的推导
• 推导：根据文法的产生式规则，把串中出现的产生式的左部符号替换成右部符号
• 从树的根节点开始，构造语法树
• 递归下降分析法、预测分析程序

接下来讲解一下自上而下分析法：

自上而下分析

基本思想：

从文法的开始符号出发，向下推导，推出句子
针对输入串，试图用一切可能的办法，从文法开始符号（根节点）出发，自上而下地为输入串建立一颗语法树
（这个过程本质上是一个试探的过程）

自上而下分析示例

假定有文法 G(S):
	(1) S -> xAy
	(2) A -> **|*    (|表示或)
	
分析输入串 x*y （记为 α）

(1)IP 指针用来读取单词

x*y	 S
↑
IP

(2)把 S 推导为 xAy

x*y	 S
↑      / | \
IP     x A Y
       ↑
       
(3)读取 A

x*y	 S
 ↑     / | \
IP     x A Y
         ↑
	     
(4)把 A 推导为 **

x*y	 S
 ↑     / | \
IP     x A Y
        / \
        *  *
        ↑

(5)继续读取单词 y

x*y	 S
  ↑    / | \
 IP    x A Y
        / \
        *  *
           ↑
	       
(6)不符合，进行回溯

x*y	 S
 ↑     / | \
IP     x A Y
         ↑

(7)把 A 推导为 *

x*y	 S
 ↑     / | \
 IP    x A Y
         |
         *
         ↑

(8)读取下一单词

x*y	 S
  ↑    / | \
 IP    x A Y
         |
         *
         ↑

S已经拓展到了所有叶节点，并且都匹配成功，可以断言这个输入串是一个合格的句子。

自上而下分析面临的问题

1.回溯问题（使分析工作变得复杂）

• 分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的
• 匹配失败时，不得不进行回溯

2.文法左递归问题（使分析工作陷入死循环）

构造不带回溯的自上而下分析算法

• 消除文法的左递归
• 消除回溯

1.消除左递归：把左递归变右递归

P -> Pα|β

左递归的情况：

P => Pα
  => Pαα
  ...
  => βαα...α

最终产生的串是以 β 开头后接 α 的串

解决方法：左递归变右递归

P -> βP’

P’ -> αP’|ε

P => βP'
  => βαP'
  => βααP'
  ...
  => βαα...αP'
  => βαα...α

最终产生的串也是以 β 开头后接 α 的串

左递归会把程序带入死循环，右递归会吗？

右递归的非终结符是在最右边，它的左边 α 会不断地产生终结符，如果分析的句子是一个正确的句子的话，左边的 α 的终结符会跟当前的输入串中的单词进行匹配，从而使得这个输入串不断地被读入，分析进程不断地推进，所以不会陷入一种死循环的地步，因为总有一天所有的单词都会被分析完。

2.消除回溯：提取左公共因子

为了消除回溯必须保证对于文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。

语法分析的过程

语法分析器（Grammar Parser）将对由扫描器产生的记号进行语法分析。从而产生语法树（Syntax Tree）。整个分析过程采用了上下文无关语法（Context-freeGrammar）的分析手段。简单地讲，由语法分析器生成的语法树是以表达式（Expression）为节点的树。

int fun(int a, int b) {
    int c = 0;
    c = a + b;
    return c;
}

以上述代码为例，其中的语句就是一个由赋值表达式、加法表达式、乘法表达式、数组表达式、括号表达式组成的复杂语句，下图所示为该语句经过语法分析器后生成的语法树。

在语法分析的同时，很多运算符号的优先级和含义也被确定下来了。如：乘法表达式的优先级比加法高，圆括号表达式的优先级比乘法高，等等。另外，有些符号具有多重含义，如“*”在C语言中可以表示乘法表达式，也可以表示对指针取内容的表达式，因此语法分析阶段必须对这些内容进行区分。如果出现了表达式不合法，如各种括号不匹配、表达式中缺少操作符等，编译器就会报告语法分析阶段的错误。

有一个名为yacc（Yet Another Compiler Compiler）的工具可以实现语法分析。其根据用户给定的语法规则对输入的记号序列进行解析，从而构建出语法树。对于不同的编程语言，编译器的开发者只需改变语法规则，而无需为每个编译器编写一个语法分析器。因此，其也称为“编译器编译器（Compiler Compiler）”

3.语义分析

语义分析的范围

1. 确定类型：确定标识符所关联的数据类型。

2. 类型检查：按语言的类型规则，检查运算的合法性与运算分量类型的一致性，必要时作类型转换。

3. 识别含义：根据语言的语义定义（形式或非形式），识别程序中各构造成分组合到一起的含义，并作相应的语义处理（生成中间代码或目标代码）。

4. 控制流检查：控制流语句必须转移到合法的地方。如C中，break语句规定跳出最内层的循环或switch语句。

5. 一致性检查：在很多场合要求对象只能被说明一次。如：pascal语言规定同一个标识符在一个分程序中只能被说明一次等。

6. 相关名字检查：如：Ada，循环或块可以有一个名字，它出现在这些结构的开头或结尾。编译程序必须检查这两个地方用的名字是否相同。

7. 其它：如名字的作用域分析等也是语义分析的工作。

语法分析仅仅完成了对表达式的语法层面的分析，但它并不了解这个语句的真正含义，如：C语言里两个指针做乘法运算是没有意义的，但这个语句在语法上是合法的。编译器所能分析的语义是静态语义（Static Semantic），所谓静态语义是指在编译期间可以确定的语义，与之对应的动态语义（Dynamic Semantic）就是只有在运行期才能确定的语义。

静态语义通常包括声明和类型的匹配，类型的转换。比如当一个浮点型的表达式赋值给一个整型的表达式时，其中隐含了一个浮点型到整型的转换过程，语义分析过程中需要完成该步骤。比如讲一个浮点赋值给一个指针时，语义分析程序会发现这个类型不匹配，编译器将会报错。动态语义一般是指在运行期出现的语义相关的问题，比如将0作为除数是一个运行期语义错误。

经过语义分析阶段之后，整个语法树的表达式都被标识了类型，如果有些类型需要做隐式转换，语义分析程序会在语法树中插入相应的转换节点。下图所示为标记语义后的语法树。

语义分析还对符号表里的符号类型做了更新。

4.生成中间代码（优化）

为什么要生成中间代码？

理论上来说，中间代码是可以直接被省略的，因为抽象语法树可以直接转为目标代码(汇编代码)。然而不同的 CPU 架构采用的汇编语法并不一样，如: Intel 架构和 AT&T 架构的汇编码中，源操作数和目标操作数位置恰好相反参考链接。

中间代码可以理解为抽象的代码，一方面它和语言无关，同时也和 CPU 无关，它仅仅只是描述了代码要做的事情，可以将其理解为是全世界通用的语言，任何语言都可以转换为世界语言，而世界语言又能被任何人翻译理解。

要知道，中间代码的存在使得编译器被分为前端和后端。其中编译器前端主要负责产生与机器无关的中间代码，编译器后端主要是将中间代码转换成目标机器代码。因为这意味着针对那些跨平台的编译器而言，可以针对不同的平台使用同一个前端和针对不同机器平台的多个后端。

现代编译器有着很多层次的优化，源码优化器（Source Code Optimizer）则是在源代码级别进行优化。上述例子中，（2 + 6）这个表达式可以被优化掉。因为它的值在编译期就可以被确定。下图所示为优化后的语法树。

事实上，直接在语法树上作优化比较困难，所以源代码优化器往往将整个语法树转换成中间代码（Intermediate Code），它是语法树的顺序表示，其实它已经非常接近目标代码了。但它一般与目标机器和运行时环境是无关的，比如它不包含数据的尺寸、变量地址和寄存器的名字等。

几种常用的中间语言形式

1. 三地址码（Three-address Code）
2. P-代码（P-Code）

三地址码示例：

x = y op z
# 表示将变量y和z进行op操作后，赋值给x。

翻译成三地址码：

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

为了使所有的操作符合三地址码形式，这里使用了几个临时变量：t1、t2和t3。在三地址码的基础上进行优化时，优化程序会将2+6的结果计算出来，得到t1 = 6。因此，进一步优化后可以得到如下的代码：

t2 = index + 4
t2 = t2 * 8
array[index] = t2

中间代码将编译器分为前端（Front End）和后端（Back End）。编译器前端负责产生机器无关的中间代码，编译器后端负责将中间代码转换成目标机器代码。这样，对于一些可跨平台的编译器，它们可以针对不同的平台使用同一个前端和针对不同机器平台的数个后端。比如clange就是一个前端工具，而LLVM则负责后端处理。GCC则是一个套装，包揽了前后端的所有任务。

5.目标代码生成与优化

经过上面生成中间代码步骤之后，这一步骤属于编译器后端。该步骤主要的任务是生成并优化目标代码，目标代码亦称为汇编代码（其实和汇编代码非常接近）。编译器后端主要包括目标代码生成器和目标代码优化。

上述例子的中间代码，经过代码生成器的处理之后可能会生成如下所示的代码序列（以x86汇编为例，假设 index 的类型为 int 型，array 的类型为 int 型数组）：

movl 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 是一样的。如下所示为优化后的目标代码：

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

输出结果：后缀为 .s 的汇编文件。

3.汇编

把汇编语言翻译成机器语言的过程称为汇编。

汇编过程中输入源是汇编代码，输出是二进制机器码。输出的二进制机器码可以直接被 CPU 识别并执行。汇编过程相对于编译器过程而言相对简单些，因为没有复杂的语法、没有语义、不需要做指令优化，根据汇编指令和机器指令的对照表一一翻译即可。

由于汇编更接近机器语言，能够直接对硬件进行操作，生成的程序与其他的语言相比具有更高的运行速度，占用更小的内存，因此在一些对于时效性要求很高的程序、许多大型程序的核心模块以及工业控制方面大量应用。

输出结果：后缀为 .o 的目标文件。

4.链接

参考文章：

计算机那些事(5)——链接、静态链接、动态链接

开发者应知道的编译原理和语言基础知识

这里只做一个简单的概括：

模块化设计是软件开发中最常用的设计思想。链接（Linking） 本质上就是把各个模块之间相互引用的部分处理好，使得各个模块之间能够正确衔接。比如：

我们在模块 main.c 中使用另一个模块 func.c 中的 foo() 函数。我们在 main.c 模块中每一处调用 foo() 时都必须确切知道 foo() 函数的地址。但由于每个模块都是单独编译的。编译器在编译 main.c 的时候并不知道 foo() 函数的地址。所以编译器会暂时把这些调用 foo() 的指令的目标地址搁置，等待最后链接时由链接器将这些指令的目标地址修正。这就是静态链接最基本的过程和作用。

如下图所示为最基本的静态链接过程示意图。每个模块的源代码文件（如.c）文件经过编译器编译成目标文件（Object File，一般扩展名为.o或.obj）。目标文件和库（Library） 一起链接形成最终的可执行文件。

其中，最常见的库就是运行时库（Runtime Library），它是支持程序运行的基本函数的集合。库本质上是一组目标文件的包，由一些最常用的代码编译成目标文件后打包而成。

链接过程主要有以下三个步骤：

1. 地址与空间分配（Address and Storage Allocation）
2. 符号解析（Symbol Resolution）
3. 重定位（Relocation）

什么是重定位

假设有个全局变量叫做 var ，它在目标文件 A 里面。我们在目标文件 B 里面要访问这个全局变量。由于在编译目标文件 B 的时候，编译器并不知道变量 var 的目标地址，所以编译器在没法确定的情况下，将目标地址设置为0，等待链接器在目标文件 A 和 B 连接起来的时候将其修正。这个地址修正的过程被叫做重定位，每个被修正的地方叫一个重定位入口。

链接器就是靠着重定位表来知道哪些地方需要被重定位的。每个可能存在重定位的段都会有对应的重定位表。在链接阶段，链接器会根据重定位表中，需要重定位的内容，去别的目标文件中找到地址并进行重定位。

静态链接

事实上，静态链接的过程就是上文所描述的过程。在Linux中，静态链接器（static linker）ld以一组可重定位目标文件和命令行参数作为输入，生成一个完全链接的、可以加载和运行的可执行目标文件作为输出。输入的可重定位目标文件由各种不同的节组成，每一节都是一个连续的字节序列。

动态链接

静态链接使得进行模块化开发，大大提供了程序的开发效率。随着，程序规模的扩大，静态链接的诸多缺点也逐渐暴露出来，如：浪费内存和磁盘空间、模块更新困难等。在静态链接中，C语言静态库是很典型的浪费空间的例子。关于模块更新，静态链接的程序有任何更新，都必须重新编译链接，用户则需要重新下载安装该程序。

解决空间浪费和更新困难最简单的方法便是将程序的模块相互分割开来，形成独立文件。简而言之，就是不对那些组成程序的目标文件进行链接，而是等到程序要运行时才进行链接。

符号表

符号表的作用：

1. 收集符号属性；（词法分析）
2. 上下文语义的合法性检查的依据；（语法分析）
3. 作为目标代码生成阶段地址分配的依据；（语义分析）
   符号表中语言符号可分为关键字（保留字）符号，操作符符号及标识符符号

符号表中的标识符一般设置的属性项目有：

1. 符号名
2. 符号的类型
3. 符号的存储类别
4. 符号的作用域及可视性
5. 符号变量的存储分配信息
6. 符号的其它属性

实现符号表的常用数据结构

• 一般的线性表：如：数组，链表，等
• 有序表：查询较无序表快，如可以采用折半查找
• 二叉搜索树
• Hash表

符号表的总体组织

1. 多张表：把属性种类完全相同的那些符号组织在一起，构造出多张符号表。
2. 一张表：把所有符号都组织在一张符号表中。
3. 折中组表：根据符号属性的相似程度分类组成若干张表，每张表中记录的符号都有比较多的相同属性。

iOS 开发符号表冲突的问题

场景描述：制作一个 .framework 静态库，静态库引用了 AFNetworking，在 Demo 工程中也引用了 AFNetworking，报了以下错误：

ld: 165 duplicate symbols for architecture x86_64
        
clang: error: linker command failed with exit code 1 (use -v to see invocation)

解决办法：

把 framework 中用到的第三方库的类更改名字。