第1章 概论

编译器将高级语言翻译为机器语言，是程序执行的基础工具。本章介绍编译器整体结构、各阶段职责及相关程序。

1.1 为什么要用编译器

• 机器语言 → 数字代码，难编写难维护
• 汇编语言 → 符号形式，依赖特定机器
• 编译器 → 将高级语言翻译为机器语言，提高开发效率
• 历史：FORTRAN（1954-1957, John Backus）首个编译器
• Chomsky 分类体系：0~3 型文法，其中 2 型（上下文无关文法）对程序设计语言最有用

1.2 与编译器相关的程序

1.3 翻译步骤（六个阶段）

编译器的工作分为六个阶段，每个阶段将源程序从一种表示转换为另一种表示。辅助部件（符号表、文字表、错误处理器）与各阶段交互。

各阶段详解

1. 扫描程序（词法分析）：字符序列 → 记号（token）

   • 例：a[index] = 4 + 2 → 8 个记号（a, [, index, ], =, 4, +, 2）

2. 语法分析程序：记号 → 分析树/语法树

   • 分析树：内部节点为非终结符，叶子为终结符
   • 语法树（抽象语法树 AST）：浓缩的分析树，去除不必要节点

3. 语义分析程序：类型检查、声明处理

   • 计算静态语义（编译时确定）
   • 属性（数据类型等）作为注释添加到树中

4. 源代码优化程序：常量合并、代码改进

   • 例：4 + 2 → 6

5. 代码生成器：中间代码 → 目标代码

   • 目标机器特性成为主要因素

6. 目标代码优化程序：选择寻址模式、删除多余操作

1.4 编译器中的主要数据结构

1.5 编译器结构的其他视角

分析和综合

• 分析：词法分析 + 语法分析 + 语义分析（易懂、数学性强）
• 综合：代码生成（需专业技术）

前端和后端

• 前端：依赖源语言（扫描、分析、语义分析）
• 后端：依赖目标语言（代码生成器）
• 中间表示作为前后端交流媒介 → 实现可移植性

遍（pass）

• 一遍编译：速度快但代码效率低（Pascal、C）
• 多遍编译：优化效果好（典型为 3~8 遍）

1.6 自举与移植

T 型图

T 型图描述编译器之间的关系：用 H 语言编写的编译器，将 S 翻译为 T。

自举（bootstrapping）

1. 用汇编写一个"虽快但不佳"的编译器
2. 用这个编译器编译"较好的"编译器
3. 用较好的编译器重新编译自身 → 最终版本

移植

重写后端生成新机器代码 → 交叉编译 → 在新机器上自举

1.7 TINY 样本语言与编译器

• TINY：简单的教学语言
  • 无过程、无声明、所有变量为整型
  • 仅有 if、repeat 控制语句
  • read/write 用于 I/O
• TINY 编译器：4 遍（扫描分析 → 符号表 → 类型检查 → 代码生成）
• TM 机：虚拟目标机器，8 个通用寄存器，RISC 风格

1.8 C-Minus

• C 子集：整型变量、整型数组、函数
• 局部/全局声明、递归函数、if/while
• TM 机作为目标代码

考试重点

★★★ 第一梯队

★★☆ 第二梯队

★☆☆ 第三梯队