万字长文！让你懂透编译原理(一)——第一章 引论

超长文预警！

系列文章传送门：
万字长文+独家思维导图！让你懂透编译原理(一)——第一章 引论
万字长文！让你懂透编译原理(二)——第二章 高级语言及其语法描述
近三万字长文！让你懂透编译原理(三)——第三章 词法分析
三万多字长文！让你懂透编译原理(四)——第四章 语法分析—自上而下分析
六万多字长文！让你懂透编译原理(五)——第五章 语法分析—自下而上分析
三万五千字长文！让你懂透编译原理(六)——第六章 属性文法和语法制导翻译
六万字长文！让你懂透编译原理(七)——第七章 语义分析和中间代码产生

第一章思维导图

1.1. 什么是编译程序

翻译程序

把某一种语言程序(称为源语言程序)等价地转换成另一种语言程序(称为目标语言程序)的程序

编译程序(compiler)

把某一种高级语言程序(源语言程序)
等价地转换成另一种
低级语言程序（目标语言程序）
(如汇编语言或机器语言程序)的程序。
（如C语言、PASCAL语言等是编译程序）

进一步分类：
诊断编译程序 优化编译程序
交叉编译程序 可变目标编译程序

解释程序

把源语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。（如BASIC语言是解释程序）

编译程序 vs. 解释程序

注意事项与要点归纳：

1. 翻译程序是指将用某种语言编写的程序转换成另一种语言形式的程序的程序，如编译程序和汇编程序等。
2. 编译程序是把用高级语言编写的源程序转换（加工）成与之等价的另一种用低级语言编写的目标程序的翻译程序。
3. 解释程序是解释、执行高级语言源程序的程序。
4. 编译程序是一种翻译程序
5. 用汇编语言或高级语言编写的程序，必须先送入计算机，经过转换成用机器语言表示的目标程序（这个过程叫做编译），才能由计算机执行。执行转换过程的程序叫做编译程序。汇编程序是指没有编译过的汇编语言源文件。编译程序转换过的叫做目标程序，也就是机器语言。

总结归纳

(1) 程序设计语言

机器语言: 由0、1代码构成，不需翻译就可直接执行其程序。
汇编语言: 机器指令助记符（伪代码）形式，汇编后才可执行其程序。
高级程序设计语言: 类自然语言和数学公式形式

(2) 基本术语

1. 源程序(Source Program)：用源语言写的程序。源语言可以是汇编语言，也可以是高级程序设计语言。
2. 目标程序(Target Program)：也称为“结果程序”，是源程序经翻译程序加工以后所生成的程序。目标程序可以用机器语言表示，也可以用汇编语言或其它中间语言表示。
3. 翻译程序(Translating Program)：是指把一个源程序翻译成逻辑上等价的目标程序的程序。源程序为其输入，目标程序为其输出。
4. 汇编程序(Assembler)：是指把一个汇编语言写的源程序转换成等价的机器语言表示的目标程序的翻译程序。
5. 编译程序(Compiler)：若源程序是用高级程序设计语言所写，经翻译程序加工生成目标程序，则该翻译程序就称为“编译程序”，也可称为编译器。
6. 解释程序：是高级语言翻译程序的一种，他将源语言书写的源程序作为输入，解释一句后就提交计算机执行一句，并不形成目标程序，就像外语翻译中的“口译”一样，不产生全文的翻译文本。
7. 运行系统(Running System)：目标程序执行时，需要有一些子程序（如一些连接装配程序及一些连接库等）配合进行工作，由这些子程序组成的一个子程序库称为运行系统。
8. 编译系统(Compiling System)：编译程序和运行系统合称编译系统。

(3) 程序的翻译

除机器语言程序外，用其它语言书写的程序都必须经过翻译才能被计算机识别。这一过程由翻译程序来完成。
编译方式是一种分阶段进行的方式，包括翻译和运行两部分。
前一阶段：翻译
后一阶段：运行，由运行系统配合完成。

1.2. 编译过程

编译程序的工作一般分为五个阶段:

1. 词法分析
2. 语法分析
3. 中间代码产生
4. 优化
5. 目标代码产生

1. 词法分析

任务:

输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号。

依循的原则：

构词规则

描述工具：

正规式和有限自动机

举例

FOR I := 1 TO 100 DO
基本字 FOR
标识符 I
赋值号 :=
整常数 1
基本字 TO
整常数 100
基本字 DO

• 词法分析依照此法规则，识别正确的单词，并将其转换成统一规格（类号、内码），备用。
• 转换规则包括：对基本字、运算符、界限符的转换规则（有限的、可数的），对标识符的转换规则，对常数的转换规则等。

2. 语法分析

任务:

在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。

依循的原则：

语法规则

描述工具：

上下文无关文法

举例：

Z := X + 0.618 * Y
算术表达式，赋值语句

3. 中间代码产生

任务:

对各类不同语法范畴（语句、过程、表达式、函数等）按语言的语义进行初步翻译。

依循的原则：

语义规则

中间代码:

三元式，四元式，逆波兰式、树形结构等

举例：

Z:=X + 0.618 * Y 翻译成四元式为
序号 算符 左操作数 右操作数 结果
(1)      *        0.618        Y          T1
(2)      +          X            T1        T2
(3)     :=          T2           /           Z

4. 优化

任务：

对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目标代码。主要包括：公共子表达式提取、合并已知量、删除无用语句、循环优化等。

依循的原则：

程序的等价变换规则

举例：

5. 目标代码产生

任务:

把中间代码变换成特定机器上的目标代码。

依赖于硬件系统结构和机器指令的含义

目标代码三种形式:

• 绝对指令代码: 可直接运行
• 可重新定位指令代码: 需要连接装配
• 汇编指令代码: 需要进行汇编

举例：

1.3. 编译程序结构

1、编译程序总框

2. 表格和表格管理

常见的表格:

符号名表，常数表，标号表，入口名表，过程引用表。

格式:

3. 出错处理

出错处理程序：

发现源程序中的错误，把有关错误信息报告给用户

错误分类：

• 语法错误
• 语义错误

注：编译程序一般很难检测出逻辑错误!

4. 遍(pass)

所谓"遍"， 就是对源程序或源程序的中间表示从头到尾扫描一次。
阶段与遍是不同的概念。一遍可以由若干段组成，一个阶段也可以分若干遍来完成。

5. 编译前端与后端

编译前端：

与源语言有关，如词法分析，语法分析，语义分析与中间代码产生，与机器无关的优化

编译后端：

与目标机有关，与目标机有关的优化，目标代码产生

优点：

减少对内存容量的要求，程序逻辑结构清晰; 优化更充分，有利于移植。

不足:

编译程序运行的效率低

举例：

1.4.编译程序与程序设计环境

• 程序设计环境
  编辑程序
  编译程序
  连接程序
  调试工具
• 集成化的程序设计环境
  

1.5 编译程序生成

以汇编语言和机器语言为工具
优点: 可以针对具体的机器，充分发挥计算机的系统功能。生成的程序效率高。
缺点: 程序难读、难写、易出错、难维护、生产的效率低。

构造编译程序的前提:

• 掌握源语言
• 掌握目标语言
• 掌握编译方法

总结:

1、词法分析阶段

这个阶段的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词（也称单词符号或符号TOKEN）。
某源程序片断如下：
begin var sum, first, count: real; sum:=first+count10 end.
保留字 begin var real end
标识符 sum first count sum first count
界符 .逗号， 冒号： 分号； 加号+ 乘号 赋值号 ：= 整数10 10

2、语法分析阶段

是编译过程的第二个阶段。语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语，如“程序”，“语句”，“表达式”等等。一般这种语法短语，也称语法单位，或语法成分，或语法范畴。
语法分析所依据的是语言的语法规则，即描述程序结构的规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。

3、语义分析阶段

依据语言的语义规则，对语法分析得到的语法结构分析其含义以及应进行的运算，审查源程序中有无语义错误，为代码生成阶段收集类型信息。

4、中间代码生成

在进行了上述的语法分析和语义分析阶段的工作之后，有的编译程序将源程序转变成一种内部表示形式，这种内部表示形式叫做中间代码。
所谓“中间代码”是一种结构简单，含义明确的记号系统，这种记号系统可以设计为多种多样的形式。
重要的设计原则：一是容易生成；二是容易将它翻译成目标代码。

5、代码优化

任务：对前阶段产生的中间代码系列进行变换或改造。目的是使生成的目标代码更高效，即省时间省空间。例如上例四个四元式可优化为下面两个四元式。

6、目标代码生成

任务：将中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。它的工作与硬件系统结构和指令含义有关。

7、表格管理

编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段的工作都涉及到构造、查找或更新有关的表格，因此需要有表格管理的工作；

8、出错处理

如果编译过程中发现源程序有错误，编译程度应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理。

参考文章

编译原理复习总结及思维导图
编译原理知识汇总