第一章 概述

1.1 编译器概述

1.1.1 基本概念

翻译器： 能够完成从一种语言到另一种语言的保语义变换的软件称为翻译器，这两种语言分别称为该翻译器的源语言和目标语言。

编译器： 是一种翻译器，它的特点是目标语言比源语言低级。

编译： 将高级语言翻译成汇编语言或机器语言的过程。

一般高级语言是编译过程中的源语言，汇编语言和机器语言是编译过程中的目标语言。

编译器在语言处理系统中的位置：

预处理器：把存储在不同文件中的源程序聚合在一起，把被称作宏的缩写语句转换为原始语句。

可重定位：汇编器生成的汇编代码在内存中存放的起始位置是不固定的。

加载器：修改可重定位地址，将修改后的指令和数据放到内存中适当的位置。

链接器：将多个可重定位的机器代码文件（包括库文件）连接到一起，解决外部内存地址问题。

外部地址：一个文件中的代码可能会引用另一个文件中的数据对象或过程，那么这些数据对象和过程的地址对于该文件来说是外部地址。

---

机器翻译（编译）过程的理解：

以人翻译英语句子进行类比。

In the room, he broke a window with a hammer.

总体而言，对于这样一个句子，我们如果想要将其翻译成中文，需要对句子进行分析，先能够理解该句子的语义，再使用中文将语义表达出来。

首先确定每个单词的词性，比如，in和with是介词，the和a是冠词，room、window和hammer是名词，he是代词。（对应于编译过程的词法分析阶段）

根据每个单词的词性，可以确定不同单词组合起来后构成的短语，比如，in the room和with a hammer是介词短语，he和a window是名词短语，broke是动词短语。根据不同短语划分句子的成分，he是主语，broke是谓语，a window是宾语，in the room是状语，with a hammer是补语。（对应于编译过程的语法分析阶段）

划分完句子成分后我们再对句子表达的意思进行理解。（对应于编译过程的语义分析阶段）

理解句子这一过程其实可以抽象地理解为将句子的含义以思维的形式呈现在脑海中，这一表达形式对应于编译过程的中间表示。

最后我们再将我们对句子的理解以中文语言的形式呈现出来（对应于编译过程的生成目标语言）

---

编译器的结构：

• 红色部分称为前端（区别于软件开发的“前端”概念）：与源语言相关。
• 蓝色部分称为后端（区别于软件开发的“后端”概念）：与目标语言相关。
• 绿色部分独立于具体语言，起到桥梁的作用。

注意：上面区分的阶段为编译器的逻辑组织方式，在实现过程中，多个阶段可能会被组合在一起：

1. 在实际实现编译器时，语义分析的结果通常直接表示成中间代码的形式，因此语义分析与中间代码的生成通常放在一起实现，称为语义翻译；
2. 在语法分析的同时进行语义翻译，也就是说将语法分析与语义翻译一起实现，这一技术称为语法制导翻译。

语法制导翻译使用上下文无关的语言（CFG）来引导对语言的翻译，是一种面向文法的翻译技术。

1.1.2 词法分析阶段

主要任务：从左到右逐行扫描源程序的字符，识别出各个单词，确定单词的类型，将识别出的单词转换为统一的机内表示 —— 词法单元（$token$）形式。
$$token:<种别码，属性值>$$

并不是所有$token$的属性值都保存值。比如，关键字while对应的$token$的属性值就不保存值，而常量100对应的$token$的种别码为$integer$，属性值为$100$。

“XX分析阶段”描述的主要任务是对对应分析器功能的完整概述，而“XX分析器”中描述的分析器作用只是对比较典型的功能进行列举。因此二者描述的功能并不冲突。

1.1.3 语法分析阶段

主要任务： 从词法分析器输出的$token$序列中识别出各类短语，并构造语法分析树。

语法分析树描述了句子的语法结构。

---

区别分析树与语法树

语法分析树和语法树不是一种东西。习惯上，我们把前者叫做“具体语法树”，其能够体现推导的过程；后者叫做“抽象语法树”，其不体现过程，只关心最后的结果。

语法分析树的定义：

对于 CFG G 的句型，分析树被定义为具有下述性质的一棵树：

1. 根由开始符号所标记；
2. 每个叶子由一个终结符、非终结符或 ε 标记；
3. 每个内部节点都是非终结符；
4. 若 $A$ 是某节点的内部标记，且 $X_1$、$X_2$、…、$X_n$ 是该节点从左到右的所有孩子的标记。则：$A\to X_1{X}_2...X_n$ 是一个产生式。若 A→ε，则标记为 $A$ 的节点可以仅有一个标记为 $\epsilon$ 的孩子。若 $A\to \epsilon$ ，则标记为 $A$ 的节点可以仅有一个标记为 $\epsilon$ 的孩子。

简而言之，利用产生式推导出句型G的过程以树的形式表现。

语法树的定义：

对于 CFG G 的句型，语法树被定义为具有下述性质的一棵树：

1. 根与内部节点由表达式中的操作符标记；
2. 叶子由表达式中的操作数标记；
3. 用于改变运算优先级和结合性的括号，被隐含在语法树的结构中。

简而言之，叶子全是操作数，内部全是操作符，树里没有非终结符也不能有括号。

不妨分别绘制分析树和语法树：

可见，分析树的每一个非叶子节点都是表达式，而语法树的非叶子节点都是运算符。

1.1.4 语义分析阶段

**主要任务：**收集标识符的属性信息，包括：种属、类型、存储位置、长度、值、作用域等，对于过程（函数）还包括参数信息和返回值信息等，将其保存在符号表中；还有就是检查语义错误，包括：变量或过程未经声明就使用、变量和过程名重复声明、运算分量类型不匹配、操作符与操作数之间的类型不匹配。

符号表是用于存放标识符的属性信息的数据结构。

---

符号表中语言符号可分为关键字符号，操作符符号及标识符符号。

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

• 符号名
• 符号的类型
• 符号的存储类别
• 符号的作用域及可视性
• 符号变量的存储分配信息
• 符号的其它属性

符号表的作用：

• 收集符号属性（词法分析）
• 上下文语义的合法性检查的依据（语法分析）
• 作为目标代码生成阶段地址分配的依据（语义分析）

1.1.5 中间代码生成阶段

常用的中间表示形式为三地址码。三地址码由类似于汇编语言的指令序列组成每个指令最多有三个操作数。

中间表示必须具备两个性质：易于产生并且易于翻译成目标程序。

1.1.6 代码优化阶段

为改进代码所进行的等价程序变换，使其运行地更快一些、占用空间更少一些，或者二者兼顾。

代码优化分为与机器无关的代码优化和与机器相关的代码优化，前者是在中间代码层面进行优化，后者是在目标代码层面进行优化。

1.1.7 代码生成阶段

目标代码生成以源程序的中间表示形式作为输入，并把其映射到目标语言。

目标代码生成的一个重要任务是为程序中使用的变量合理分配寄存器。