大家好，我是ErikTse，这学期开始学习编译原理，希望通过写一些博客来更好的学习。
我的个人主页：www.eriktse.com
欢迎关注我的b站（Erik_Tse）、知乎账号（Erik Tse），获取更多计算机编程/算法干货知识。🥰

本章主要内容：

• 什么是编译程序？
• 编译过程和编译程序的结构
• 为什么要学习编译程序

什么是编译程序

高级语言程序不能直接被计算机执行，需要通过翻译程序将高级语言程序翻译为机器语言程序，才能被计算机执行。

翻译程序（Translator）

翻译程序能够将某一种语言程序（称为源语言或源语言程序） 转换成另一种语言程序（称为目标语言或目标语言程序），两者在逻辑上等价。

翻译程序根据所处理的对象和实现的途径不同又分为：汇编程序、编译程序和解释程序三种。

汇编程序

如果源语言是某种汇编语言，而目标语言是某种计算机的机器语言，这样的一个翻译程序就是汇编程序。

编译程序

如果源语言是某种高级语言，而目标语言是某种计算机的机器语言，这样的一个翻译程序就是汇编程序。

翻译程序

这是另外一种类型的翻译程序，在翻译过程它按照高级语言源程序在计算机上执行的动态顺序对源程序的语句逐条翻译（解释），边解释边执行直至结束，它不产生目标程序，它的工作结果就是源程序的执行结果，这样的一个翻译程序就称为解释程序。

例如Python语言，就是一种解释型语言，需要使用python解释器来运行，而一般不会产生目标文件。

一些其他概念

• 宿主机（host machine）：运行编译程序的计算机（用于生产程序的机器）。
• 目标机(object machine) ：运行编译程序所产生的目标代码的计算机（用户运行程序的机器）。

编译过程和编译程序的结构

编译过程可以分为5个阶段：词法分析、语法分析、语义分析和中间代码生成、优化、目标代码生成。

第一阶段：词法分析

词法分析的任务是：将构成源程序的字符串进行扫描和分解，识别出一个个的单词。

常见的单词有：

• 保留字（begin、end、if、for、while等）、
• 标识符（x1、s等变量名）、
• 常数(3.14、100等)、
• 算符（+、-、and、or等）、
• 界符（标点符号、左右括号等）。

例如，对于Pascal的循环语句：

for I：＝1 to 100  do

词法分析的结果是识别出如下的单词符号：

• 保留字 for
• 标识符 I
• 赋值号 :=
• 整常数 1
• 保留字 to
• 整常数 100
• 保留字 do

描述词法规则的有效工具是正规式，识别词法规则的有效工具是有限自动机。

第二阶段：语法分析

在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴），如“短语”、“子句”、“句子”（“语句”）、“程序段”和“程序”等。通过语法分析，确定整个输入串是否构成语法上正确的“程序”。

语法分析依循的是语言的语法规则，而语法规则通常使用上下文无关文法描述。🐒

词法分析是一种线性分析，而语法分析是一种层次结构分析。

例如在很多语言中，对于这样一条语句：Z = X + 0.618 * Y。语法分析的任务就是识别出“X + 0.618 * Y”是一个算术表达式的范畴，而整个语句是赋值表达式的范畴。

第三阶段：语义分析和中间代码生成

语义分析的任务是：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译。

中间代码是一种独立于硬件的记号系统。

常用的中间代码：三地址码(四元式，三元式、间接三元式)、逆波兰式，树形表示等。

四元式

格式：(算符 左操作数 右操作数 结果)

例如语句：Z：＝（X＋0.418）* Y ／ W

序号	算符	左操作数	右操作数	结果
1	+	X	0.418	T1
2	*	T1	Y	T2
3	/	T2	W	Z

第四阶段：优化

优化的任务是：对产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。

优化的主要方面有：公共子表达式提取、循环优化、删除无用代码等等。有时，为了便于“并行运算”，还可以对代码进行并行化处理。

优化所依循的原则:程序的等价变换规则。

第五阶段：目标代码生成

目标代码生成的任务是：把中间代码（或经过优化处理之后）变换成特定机器上的低级语言程序。

编译程序的结构

遍（Pass）

受不同源语言、设计要求、使用对象和计算机条件（如主存容量）的限制，往往将编译程序组织为若干遍（Pass）。

所谓遍就是对源程序或源程序的中间结果从头到尾扫描一遍，并作有关的加工处理，生成新的中间结果或目标程序。

通常，每遍的工作是从外存获取上一遍的中间结果（如果是第一遍则获取源程序） ，完成有关工作后，再记录回外存中。

当一遍中包含若干阶段时，各阶段的工作是穿插进行的。例如，我们可以把词法分析、语法分析及语义分析与中间代码产生这三阶段安排成一遍。

这时，语法分析器处于核心位置，当它在识别语法结构而需要下一单词符号时，它就调用词法分析器，一旦识别出一个语法单位时，它就调用中间代码产生器，完成相应的语义分析并产生相应的中间代码。

一个编译程序究竟应分成几遍，如何划分，是与源语言、设计要求、硬件设备等诸因素有关的，因此难于统一划定。

• 遍数多：整个编译程序的逻辑结构可能清晰一点，但势必增加输入／输出所消耗的时间，时间效率不高。
• 遍数少：编译速度快，但对机器的内存要求高。

编译前端和编译后端

• 编译前端：主要由与源语言有关但与目标机无关的那些部分组成。这些部分通常包括词法分析、语法分析、语义分析与中间代码产生，有的代码优化工作也可包括在前端。
• 编译后端：包括编译程序中与目标机有关的那些部分，如与目标机有关的代码优化和目标代码生成等。通常，后端不依赖于源语言而仅仅依赖于中间语言。

可以取编译程序的前端，改写其后端以生成不同目标机上的相同语言的编译程序。为不同的前端配上相同的后端，这样就可为同一台机器生成不同语言的编译程序。然而，由于不同语言存在某些微妙的区别，因此在这方面所取得的成果还非常有限。

为什么要学习编译程序

不重要。