Introduction⚓︎

What, Why and How?⚓︎

编译器(compiler) 是一类将一种语言翻译成另一种语言的程序（由于计算的抽象性）。它是一种复杂程序，由数万乃至数百万行代码构成（比如我们熟知的 gcc 就有 7.5M 行代码）。

编写编译器的原理和技术具有普遍意义，以至于每个计算机科学家的研究生涯中都会反复用到该原理和技术。

Typical Workflow of a Compiler⚓︎

下图展示了编译器完整的工作流程：

两个重要概念：

• 阶段(phases)：在不同的抽象「语言」上运行的单个或多个模块
• 接口(interfaces)：编译器模块之间交换的信息

之所以将编译器划分为多个阶段，是为了：

• 便于理解和实现
• 使组件可复用（因为我们有改变源语言或目标语言的需求）

下面以一个简单的字符串 x = a * 2 + b * (x * 3) 为例带读者过一遍编译器各阶段的内容：

• 词法分析(lexing / scanning / lexical analysis)：将程序字符流分解为记号(token) 序列

  
  • 删除字符串中不必要的部分（如空格）
  • 通常使用正则表达式匹配（DFA 定义）

• 语法分析(parsing / syntactic Analysis)：将记号序列解析为语法结构

  
  • 去除不必要的记号（例如括号）
  • 一般使用抽象语法树（AST）定义

• 语义分析(semantic analysis)：利用属性文法、符号表等决定语法结构的含义；对于本例，需要弄清：

  
  • 变量x , a , b的类型是什么？
  • 运算符 * 和 + 的含义是什么？
  • 读写变量 x 是合法的吗？

• 中间代码生成

  • 中间代码/表示（IR）: 源语言与目标语言之间的桥梁
  

• 优化（基于中间表示）：基于中间表示进行分析与变换，以降低执行时间，减少资源消耗等

  

• 目标代码生成：把中间表示形式翻译到目标语言，涉及到指令选择、寄存器分配、指令调度等阶段

  

Modules and Interfaces in Tiger⚓︎

虎书中介绍的 Tiger 编译器的流程如下图所示：

图中标注的关键部分：

• AST（抽象语法树）：语法分析 + 解析动作 (parsing actions) 生成
• IR 树: 语义分析后按一定规则生成（树型中间表示）
• 规范化(canonicalized) IR 树：方便生成汇编
• Assem: 指令选择器生成（一种特殊的抽象汇编）
• CFG（控制流图 (control flow graph)）：方便进行数据流分析，比如活跃变量分析(liveness analysis) 等
• 冲突图(interference graph)：由活跃变量分析结果构造，用于指导寄存器分配

编译器各阶段的描述（及对应章节编号）：

Tools and Software⚓︎

两种最有用的抽象：

• 用于词法分析的正则表达式
• 用于语法分析的上下文无关文法

两种编译工具：

• Lex 将声明性规范转换为词法分析程序
• Yacc 将文法转换为语法分析程序

书中的编程项目可以使用任何符合 ANSI 标准的 C 编译器编译，同时使用 Lex 和 Yacc。

Data Structures for Tree Languages⚓︎

中间表示(intermediate representation, IR) 是编译程序的一种形式。主流形式是树形表示，有着不同属性的多个节点类型，用类似编程语言的语法描述。书中假想了一套如下所示的简单编程语言的语法：

一些解释：

• Stm：语句
• Exp：表达式
• s1; s2：先执行语句 s1，后执行语句 s2
• i := e：先对 e 求值，然后将结果存储到变量 i 上
• print(e1, e2, ..., en)：显示所有表达式的值，从左到右计算，以空格分隔，以换行符结束
• id：产生变量 id 的当前内容
• e1 op e2：先对 e1 求值，再对 e2 求值，然后作用给定的二元运算符
• (s, e)：类似 C 语言的逗号运算符，在对表达式 e 求值之前，先对语句 s 求值以获取副作用

例子

问题解答

执行以下程序：

a := 5+3; b := (print(a, a-1), 10*a); print(b)

输出内容为：

8 7
80

如何在编译器中表达这段程序？

每个语法符号(grammar symbol) 都能对应数据结构中的类型定义(typedef)，比如：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

typedef char *string;
typedef struct A_stm_ *A_stm;
typedef struct A_exp_ *A_exp;
typedef struct A_expList_ *A_expList;

struct A_stm_ {
    enum {A_compoundStm, A_assignStm, A_printStm} kind;
    union {
        struct {A_stm stm1, stm2;} compound;
        struct {string id; A_exp exp;} assign;
        struct {A_expList exps;} print;
    } u;
};

A_stm A_CompoundStm(A_stm stm1, A_stm stm2);
A_stm A_AssignStm(string id, A_exp exp);
A_stm A_PrintStm(A_expList exps);

语法规则：

• 构造器 (constructor)：属于其左侧符号的联合
• 构造器名称：在右侧指示（括号内）

• 右侧组件：在数据结构中表示

  • CompoundStm 在右侧有两个 \(Stm\)：\(Stm -> Stm; Stm\)
  • AssignStm 有一个标识符和一个表达式：\(id := Exp\)

• 每个语法符号的结构体包含了：

  • 一个用于承载这些值的联合，以及
  • 一个用于指示哪个联合变体是有效的种类字段

• 构造函数

  • 内存分配和初始化数据结构
  • 比如CompoundStm , AssignStm等

  A_stm A_CompoundStm(A_stm stm1, A_stm stm2) {
      A_stm s = checked_malloc(sizeof(*s));
      s->kind = A_compoundStm;
      s->u.compound.stm1 = stm1;
      s->u.compound.stm2 = stm2;
      return s;
  }
  

• \(Binop\) 变得更简单了：\(Binop \rightarrow + | - | \times | /\)

• 构建 \(Binop\) 结构体：

  struct A_binop {
      enum {A_plus, A_minus, A_times, A_div} kind;
  }
  

  但实际上不会包含数据，因此改写为：

  typedef enum {A_plus, A_minus, A_times, A_div} A_binop;
  

评论区