Lecture Notes: Compiler Construction

COMP3173 Compiler Construction

Dr. Goliath Zhiyuan LI

Lecture 1

编译器核心概念 (Core Concepts of a Compiler)

1. 编译器的定义 (Definition of a Compiler)

• 一个 compiler (编译器) 是一个程序，它读取用一种语言（source language，源语言）编写的程序，并将其翻译成另一种语言（target language，目标语言）的 等价 (equivalent) 程序。

• “等价” 意味着目标程序的行为与源程序完全一致。

• 目标语言可以是：

  • 其他高级语言，如 C, C++, Java。
  • 微处理器能理解的 machine language (机器语言)。
  • 领域特定语言，如打印机用的 PostScript。

• 编译器的一个重要功能是 错误处理 (Error Handling)。如果源程序有错，编译器必须检测并报告这些 errors。

2. 编译器的主要阶段 (Main Phases)

一个编译器通常被分为三个

1. 分析 / 前端 (Analysis / Front-end): 负责理解源程序。
2. 中间代码生成器 (Intermediate Code Generator): 在前端和后端之间架起一座桥梁。
3. 综合 / 后端 (Synthesis / Back-end): 负责生成目标程序。

---

前端的三个阶段 (Analysis / Front-end)

前端的工作是将源代码分解并分析其结构和含义，它包含三个步骤：

3.1. 词法分析 (Lexical Analysis)

• 执行者: lexer 或 scanner (词法分析器)。

• 工作内容:

  1. 以字符流 (stream of characters) 的形式读取源程序。
  2. 将字符流分割成有意义的单元，称为 lexemes (词素)。
  3. 将每个 lexeme 分类为一个 token (标记)。
  • 这个过程类似于自然语言处理中的 tokenizer，负责把句子切分成单词。
  • 在多数语言中，lexer 会跳过空格和注释。

• 使用工具: 通常使用 regular expressions (正则表达式) 来定义 tokens 的规则。

• 例子: 对于 C 代码 num=1+23;

  • Lexemes: num, =, 1, +, 23, ;
  • Tokens: identifier, ass_opt, int_literal, plus_opt, int_literal, semicolon

3.2. 语法分析 (Syntax Analysis)

• 执行者: parser (语法分析器)。

• 工作内容:

  1. 使用一套 grammar (语法) 规则来分析 token 序列的结构。
  2. 将 tokens 组织成一个有层次的嵌套结构，称为 parse tree (语法分析树) 或 syntax tree (语法树)。
  • Parse tree 完整地展示了语法结构，而 syntax tree 是其简化版本，更像一个表达式树 (expression tree)。

• 例子: 对于 num=1+23;，其语法树 (syntax tree) 可能如下：

        =
       / \
  identifier(num)  +
                 / \
           int_literal(1) int_literal(23)

3.3. 语义分析 (Semantic Analysis)

• 输入: parse tree 或 syntax tree。

• 工作内容: 检查程序的“含义”(meaning)是否正确。这是发现逻辑错误的阶段。

• 检查项举例:

  • 变量是否在使用前被定义 (undefined variables)。
  • 变量类型是否匹配操作 (types of variables)。例如，不能把一个字符串赋值给一个整型变量。
  • 变量是否被重复定义 (multiple declaration)。

• 此阶段还会执行隐式的 type conversions (类型转换)，例如在 C 语言中，将 float 赋值给 int 时，编译器会自动插入一个转换操作。

---

中间代码 (Intermediate Code)

• 目的:

  1. 前端产生的 parse tree 太高级，直接转换成低级目标代码很困难。中间代码是一个更易于处理的过渡形式。
  2. 解耦 (Decoupling): 中间代码充当了前端和后端之间的 interface (接口)。这使得编译器可以轻松支持多种源语言和目标平台。例如，GCC 可以为 C, C++, Java 等多种语言生成不同平台（Windows, Linux）的代码，因为它共享了相同的中间表示。

• 本课程使用的类型: three-address code (三地址码)。它比工业界常用的 Single Static Assignment (SSA) 更简单。

• 三地址码特点: 每条指令最多包含一个操作符和三个地址（变量）。

• 例子: id1 = id2 + id3 * 2; 会被翻译成：

  temp1 = float(2)
  temp2 = id3 * temp1
  temp3 = id2 + temp2
  id1 = temp3

---

后端的两个阶段 (Synthesis / Back-end)

后端负责将优化后的中间代码转换成最终的目标代码。

5.1. 代码优化 (Code Optimization)

• 目的: 改进中间代码，使其运行得 faster (更快) 或体积 smaller (更小)。

• 这是一个非常复杂的领域，有些优化可能需要数小时才能完成。

• 例子: 上面的三地址码可以被优化为：

  temp1 = id3 * 2.0
  id1 = id2 + temp1

  这里将整数 2 提前转换成了浮点数 2.0，并减少了一个临时变量。

5.2. 代码生成 (Code Generation)

• 目的: 将优化后的中间代码翻译成目标语言（通常是汇编或机器码）。

• 包含三个核心且非常困难的任务 (都是 NP-hard 问题):

  1. 指令选择 (Instruction selection): 为一个操作选择最合适的机器指令。例如，x * 2 可以用乘法指令，也可以用更快的位左移指令 x << 1。
  2. 指令调度 (Instruction scheduling): 重排指令顺序以适应处理器的 pipelining (流水线)，从而提高执行效率。
  3. 寄存器分配 (Register allocation): 决定哪些变量在何时存放在 CPU 中极其有限但速度飞快的 registers (寄存器) 中。

---

贯穿始终的组件 (Other Components)

这些组件在编译的各个阶段都会被调用。

• 符号表管理器 (Symbol Table Manager):

  • Symbol table (符号表) 是一个数据结构，用于存储程序中所有 identifiers (标识符，如变量名、函数名) 的信息，例如它的类型 (type)、作用域 (scope) 等。
  • 前端用它来检查语义错误，后端用它来分配内存。

• 错误处理器 (Error Handler):

  • 当发现错误时，一个好的编译器不会立即停止，而是会尝试 recover (恢复)，以便在一次编译中尽可能多地找出错误。

---

编译的全景图 (The Whole Picture)

在实际应用中，编译器只是工具链中的一环。

1. 预处理器 (Preprocessor): 在编译前处理宏 (#define)和文件包含 (#include)。它基本上是做文本替换。
2. 编译器 (Compiler): 将预处理后的代码翻译成汇编代码。
3. 汇编器 (Assembler): 将汇编代码转换成可重定位的 object code (目标代码)。
4. 链接器 (Linker): 将多个目标文件和库文件 (libraries) 合并在一起，解决地址问题，最终生成一个可执行文件 (absolute executable code)。