编译器概述

编译器定义

编译器是将 程序设计语言 源程序翻译为等价目标程序的程序。

• 源语言：源程序所使用的语言
• 目标语言：目标程序所使用的语言
• 宿主语言：编译器自身的实现语言

交叉编译 重点

在一种平台上运行编译器，生成另一种平台可执行的目标代码。常用于嵌入式开发和跨平台移植。

T 形图 重点

描述编译器自举（Bootstrapping）过程的工具。T 形图的三臂分别表示：

• 左臂：源语言
• 右臂：目标语言
• 底部：宿主语言

多个 T 形图可以组合，描述编译器从低级语言逐步自举到高级语言的过程。

T 形图编译器移植例题

问题：在机器 $M_1$ 上有 C 编译器（源=C，目标=$M_1$，宿主=$M_1$）。欲在 $M_1$ 上生成 $M_2$ 的 C 编译器，如何实现？

解法（三步自举）：

1. 修改 C 编译器后端，生成 $M_2$ 代码（源=C，目标=$M_2$，宿主=$M_1$）→ 得到交叉编译器
2. 用（1）的交叉编译器在 $M_1$ 上编译 C 编译器源码（源=C，目标=$M_2$，宿主=$M_2$）→ 得到 $M_2$ 上的自托管编译器
3. 在 $M_2$ 上用（2）的结果再次编译 C 编译器源码，验证自举成功

重点 T 形图是编译器自举和移植的工具，考试可能出组合题。

编译器七阶段架构 重点

编译器在逻辑上可分为七个阶段，前四个阶段构成前端，后两个阶段构成后端，此外还有两个辅助模块贯穿始终。

前端

1. 词法分析：读入字符流，识别单词，输出 Token 序列（→ 正规式、有限自动机）
2. 语法分析：根据文法将 Token 序列组织为语法树（→ 文法基础、LL1分析、LR分析）
3. 语义分析：检查语义正确性，进行类型检查（→ 语法制导翻译）
4. 中间代码生成：生成独立于机器的中间表示（→ 中间语言、赋值与控制流语句翻译）

后端

5. 代码优化：对中间代码进行等价变换，提高执行效率（→ 基本块与控制流图、循环优化算法）
6. 目标代码生成：将优化后的中间代码转换为目标机器代码

辅助模块

7. 符号表管理：记录源程序中使用的标识符及其属性（→ 符号表与说明语句翻译）
8. 出错处理：检测、报告错误并进行恢复（→ 语法分析中的错误处理）

遍（Pass）的概念 重点

遍是对源程序或其中间表示进行一次完整的扫描。一遍可以包含多个阶段，一个阶段也可以跨越多遍。

• 单遍编译：一次扫描完成所有阶段，速度快但难以优化
• 多遍编译：多次扫描，每遍生成中间文件，便于优化但速度慢

字母表与字符串

字母表

非空有穷符号集合，记为 $\Sigma$。

字符串

字母表上的有穷符号序列。字符串 $w$ 的长度记为 $|w|$。

• 前缀：从字符串头部开始的连续子串
• 后缀：从字符串尾部开始的连续子串
• 子串：字符串中连续的任意子序列
• 连接：将两个字符串拼接，记为 $x\cdot y$ 或 $xy$
• 方幂：字符串自身连接 $n$ 次，记为 $w^n$；${\Sigma }^n$ 表示长度为 $n$ 的所有字符串集合