中间代码生成——基础内容
中间代码生成是编译器前端部分的最后内容，负责生成可以为链接器所用的中间表示。 这种中间表示比源语言更加低级且接近计算机底层，但是又不像汇编语言那样可以直接在硬件上执行。 这种中间表示通常以抽象语法树或三地址代码的形式出现，我们在本部分内容中将详细介绍这两者及其变种。 除此之外，中间代码生成时通常还会进行一些静态检查，比如检查各种语句的位置是否正确、类型是否匹配等，本部分也会处理这些内容。
编译器可能会使用从高级到低级的多种中间表示，高级的中间表示更适合进行静态检查，而低级的中间表示更适合生成代码。 中间表示也不一定以抽象的数据结构或自行创造的语言出现，C语言，由于其较强的表示力和易于编译成机器代码的特性，也常常作为中间语言出现。 用C语言作为中间语言的编译器包括Cfront（早期C++编译器）、GHC（Haskell编译器）和Cython（Python编译器）等。
抽象语法树及其变体
正如我们此前所介绍的，抽象语法树，简称语法树，可以相当容易地从语法分析中生成，且能够保留程序的逻辑关系，因此是常见的中间表示。 本节中我们将介绍利用有向无环图（Directed Acyclic Graph, DAG）表示抽象语法树的变种，这种变种可以识别并优化公共子表达式。
表达式的有向无环图
考虑表达式a+a*(b-c)+(b-c)*d。
这个表达式当中，子表达式a出现了两次，而(b-c)也出现了两次。
在通常的语法树中，这会导致多个相同子树的出现。
如果我们重用这些子树，就会把抽象语法树转化成一个有向无环图，如下图所示：
我们知道，可以用以下SDD生成抽象语法树：
| 产生式 | 语义规则 |
|---|---|
| $E \to E_1 + T $ | E.node = new Node('+', E1.node, T.node) |
| $E \to E_1 - T $ | E.node = new Node('-', E1.node, T.node) |
| $E \to T $ | E.node = T.node |
| $T \to T_1 * F $ | T.node = new Node('*', T1.node, F.node) |
| $T \to (E) $ | T.node = E.node |
| $T \to \mathbf{id} $ | T.node = new Leaf(id, id.entry) |
| $T \to \mathbf{num} $ | T.node = new Leaf(num, num.val) |
这个SDD在利用产生式生成抽象语法树时，对每个表达式都会生成一个新的结点。
实际上，我们只需要稍稍修改Node和Leaf两个构造函数即可。
我们在构造新的结点之前，首先检查是否已经生成过一样的结点，如果已经生成过了，就直接返回原结点，而不重新构造新的结点即可。
语法树或DAG的结点通常保存在一个记录（即结构体）数组之中，其中的每一个元素表示一个结点。 这个记录的第一个字段通常是运算符代码，即这个结点的标号。 对叶子节点，其还有一个额外的字段，指向符号表的条目或者一个常数值； 对内部节点，其有两个（可能有更多）额外的字段，保存指向其叶节点的指针（或数组下标）。
如果所有结点都被这样保存在一个数组之中，那么我们可以用数组的下标来指向一个结点，表达式根节点的整数下标称作表达式的值编码。 实现中我们通常使用指针或引用，出于习惯也把它们称作值编码。
出于由表达式快速寻找值编码的要求，我们可以用哈希表（也称散列表）来保存每个表达式的值编码，为此我们需要为结点的数据设计一个哈希函数。
三地址代码
在三地址代码中，一条指令的右侧最多只有一个运算符和两个运算分量，而不允许出现组合的算数表达式。
因此，像x+y*z这样的表达式必须被翻译成两条三地址代码：t=y*z; r=x+t，其中t和r都是生成的临时名字。
三地址代码拆分了表达式和控制流语句的嵌套结构，因此常见于目标代码的生成和优化。
上文所述的DAG可以被翻译成如下三地址代码：
t1 = b - c
t2 = a * t1
t3 = a + t1
t4 = t1 * d
t5 = t3 + t4
三地址代码的约定
三地址代码基于两个基本概念：地址和指令。
地址通常就是指令的操作数，通常具有以下形式之一：
- 名字：即源程序中的各种名字，在实现中通常以指向符号表的指针替代；
- 常量或字面量：常量涉及不同类型中的转型问题，这一问题将在下面的文章中介绍；
- 临时变量：编译器为每个需要的临时变量生成一个新的名字，然后在分配寄存器时尽可能地把它们合并起来。
而指令通常具有以下形式：
- 运算并赋值：形如
x = y op z或x = op y的指令，前者为双目运算符，包括常见的算数和逻辑运算；后者为单目运算符，包括单目减、逻辑非和转型运算。 - 复制：形如
x = y、x[i] = y或x = y[i]、x = &y或*x = y等的指令。x = y：直接赋值，可类比于寄存器寻址；x[i] = y或x = y[i]：类似C中的数组访问，x[i] = y表示把距xi个内存单元的地址复制为y的值，可类比于偏移寻址；x = &y、*x = y或x = *y：类似C中的指针，把一个地址当作指针进行复制，可类比于间接寻址。
- 控制流指令：包括分支和函数调用：
- 分支指令：包括无条件跳转指令
goto Label、条件跳转指令if x goto Label、if False x goto Label和if x relop y goto Label； - 过程调用：
param x表示把x作为参数压栈、call y, n和x = call y, n表示调用函数y，使用栈上的n个参数并把参数出栈，然后返回值（若有）保存到x中，return y表示从过程中返回。 我们在此处不具体描述其实现。
- 分支指令：包括无条件跳转指令
考虑语句：
do i = i + 1； while(a[i] < v);
可以翻译成三地址代码：
L: t1 = i + 1
i = t1
t2 = i * 8
t3 = a[t2]
if t3 < v goto L
这里假设数组一个元素占用8个字节。 除了只为需要跳转到的指令编号之外，我们还可以为每一条指令从前到后依次标号，然后直接用标号进行跳转。
四元式与三元式
我们已经描述了三地址代码的各种组成，但是还没有描述其实现方法。 在这一节中，我们将描述两种实现三地址代码的数据结构：四元式和三元式，以及三元式的变体，间接三元式。
四元式
四元式是一种简单的表示方法。 考虑到三地址代码中至多只有两个运算分量、一个结果分量和一个运算符，四元式足以表示所有情况。
一个四元式（Quadruple）有四个字段：op、arg1、arg2和result。
对于通常的三地址代码x = y + z，其字段result为x，arg1和arg2分别为y和z，而op为+。
如果三地址代码只有一个运算分量，那么我们规定其占用arg1而把arg2留空。
如果三地址代码没有结果分量（如param），那么我们把result也留空。
如果三地址代码表示跳转，那么我们约定标号保存在result的位置。
只有三地址代码表示复制（如x = y）时，我们才把op设为=，其余情况下赋值是隐含的。
考虑赋值语句a = b * -c + b * -c，其三地址代码（没有任何优化，单目减用minus以区别于双目减）为：
t1 = minus c
t2 = b * t1
t3 = minus c
t4 = b * t3
t5 = t2 + t4
a = t5
那么其对应的四元式为：
| op | arg1 | arg2 | result |
|---|---|---|---|
| minus | c | t1 | |
| * | b | t1 | t2 |
| minus | c | t3 | |
| * | b | t3 | t4 |
| + | t2 | t4 | t5 |
| = | t5 | a |
实现时通常用符号表的指针表示程序中的变量，而用一个特殊类型（如Temp）的实例来表示生成的临时变量。
三元式
我们注意到在四元式中存在大量用来保存临时变量的字段，而这些临时变量通常是用来保存三地址代码的中间结果的。 我们可以直接引用这个三地址代码从而获取其中间值，而不必生成临时变量。
在三元式（Triple）中，我们用三个字段op、arg1和arg2来描述一个算数运算，而如果需要使用其他三元式的中间结果，则直接引用那条指令即可。
实际上，对于表达式而言，三元式表示几乎和DAG表示等价：在DAG中，每个结点有指向子表达式的指针，而在三元式中，也使用这样的指针访问中间结果。
但是对控制流指令，三元式和DAG就大不相同了。
对于复制语句x = y，我们把x放在arg1里面，y放在arg2里面。
对于需要更多运算分量的三地址代码，可以拆分成两个三元式。
比如对于x[i] = y，可以把x[i]放在一个三元式里面，然后把y放在另一个里，然后在第二个三元式的arg1中引用第一个。
对于同一个表达式，其三元式为：
| 序号 | op | arg1 | arg2 |
|---|---|---|---|
| 0 | minus | c | |
| 1 | * | b | (0) |
| 2 | minus | c | |
| 3 | * | b | (2) |
| 4 | + | (1) | (3) |
| 5 | = | a | (4) |
我们用括号中的序号表示引用某条三元式的结果。
三元式相较于四元式的最大缺点在于其依赖于三元式的顺序。 在优化时，我们会经常交换一些表达式的顺序甚至删去或添加一些表达式，这会导致表格中的引用失效。 为了解决这个问题，我们引入间接三元式的概念。
在间接三元式中，我们不直接操作三元式，而是把所有生成的三元式单独储存起来，然后生成程序的指令列表中并不含有具体的三元式，而是含有指向三元式的指针。 这样，当我们操作指令列表时，就只是操作这些指针，而不会操作具体的三元式，从而不会打乱三元式之间的相对顺序。
静态单赋值形式
静态单赋值形式（Static Single Assignment form, SSA）是一种和三地址代码相似的中间表示形式。 SSA和三地址代码最大的不同就是其所有赋值是一次性的，也就是说所有变量都是静态的，且只接受了一次赋值。 这种表示形式可以简化优化工作。
对三地址代码：
p = a + b
q = p - c
p = q * d
p = e - p
q = p + q
同一程序的SSA形式可能为：
p1 = a + b
q1 = p1 - c
p2 = q1 * d
p3 = e - p
q2 = p3 + q1
注意每次重新赋值时，SSA都会使用不同的变量名，以确保静态单赋值的特点。
然而，静态单赋值并不总是可能的，考虑以下C语言代码：
int x = (foo > 0 ? 114 : 514);
此时，根据控制流的不同，x可能具有不同的值，因此无法生成SSA形式的代码。
为了解决这个问题，引入了$\phi$函数，这一函数表示将两个值根据控制流不同合并起来。
此时，上面的代码可以写成：
if(foo > 0)
x1 = 114;
else
x2 = 514;
x3 = φ(x1, x2);
类型和声明
在中间代码生成中，类型在翻译和静态检查中都有非常重要的作用。 在翻译中，我们需要知道关于类型的信息才能生成正确的中间代码，比如生成数组相关代码时就需要数组元素的大小和数组的长度； 在静态检查中，我们需要保证运算符和运算分量的类型匹配、函数声明和其返回值的类型匹配等，尤其是对静态类型的语言。
在这一节中，我们将主要考察前者，即如何利用类型的信息生成中间代码。
类型表达式
各种语言之中都存在复合类型，而这些复合类型的声明也符合各种结构，因此，类比算术表达式，我们提出类型表达式的概念。 类型表达式可以是各种基本类型（即“一类公民”）或是类型构造算子作用在类型表达式上产生的表达式。
比如，C语言类型int [2][3]表示由两个数组组成的数组，其中每个数组各自包含三个整数。
用类型表达式，可以写成array(2, array(3, int))。
这种表达式也可以组织成抽象语法树的形式，只是相较于一般算数表达式（中缀表达式），这种表达式常常是以前缀的形式出现的。
我们递归地类型表达式：
- 基本类型是一个类型表达式，我们约定其中包括
boolean、char、integer、float和void。 - 每个类名（结构体名）是一个类型表达式，也可以用类型构造算子
record构造新的记录（结构体）。 使用record构造记录时，必须指明每个字段的类型和名称，我们将在声明一节给出其语法。 - 将类型构造算子
array作用于一个非负整数和类型表达式上，可以产生一个类型表达式，表示数组。 - 使用类型构造算子
→可以构造函数类型的类型表达式。 比如integer → float表示从整数到浮点数的一个函数。 - 类型表达式的笛卡尔积也是类型表达式，这可以用来构造列表或元组以及函数的参数列表。
- 类型表达式可以含有取值为类型表达式的变量（类似C++中的模板）。
在实际语言中，时常能看到“递归类型”。 考虑以下C++代码：
class Cell
{
int data;
Cell * next;
}
这个代码中递归地使用了Cell这一类型，以实现一个单向链表。
本节介绍的处理技巧也适用于这种递归类型。
类型等价
我们在检查类型时，时常会遇到要求某两个类型表达式所表示的类型相同的情况。
这个问题的复杂之处在于，一个类型表达式中的类型可能是另一个类型表达式的别名，正如C语言中typedef关键字所作的那样。
为此，我们定义两个等价关系：结构等价（Structurally equivalent）和名称等价（Name equivalent）。
两个类型结构等价，当且仅当：
- 它们是相同的基本类型，或
- 它们是由结构等价类型通过相同的类型构造算子构造出的，或
- 其中一个类型是另一个的别名。
如果所有类型名都只代表其自身，而非另一个类型的别名，那么两个类型名称等价，当且仅当：
- 它们是相同的基本类型，或
- 它们是由名称等价类型通过相同的类型构造算子构造出的，或
如果我们以DAG的形式组织类型表达式，那么名称等价关系可以很容易地用哈希表校验。 结构等价的判定比较复杂，尤其是类型表达式中含有类型变量的情况，其判定需要使用并查集，我们在类型检查一节再仔细介绍它。
存储布局
我们研究由下面这个简化的文法组成的类型声明： \(\begin{aligned} D \quad &\to \quad T \ \mathbf{id}; D \; \vert \; \epsilon \\ T \quad &\to \quad B C \; \vert \; \mathbf{record} '\{' D '\}' \\ B \quad &\to \quad \mathbf{int} \; \vert \; \mathbf{float} \\ C \quad &\to \quad \epsilon \; \vert \; [\mathbf{num}] C \end{aligned}\) 为了区别花括号和语义动作，我们给它们加上一对引号。
我们可以通过变量类型得出其在运行时所需的内存数列，从而在编译时我们就可以为它们确定相对地址（绝对地址在链接时才能确定）。 这些信息可以保存在变量的符号表条目之中。 传统上，动态分配的内存应当位于堆内存区，且在编译时不能确定。 为此，我们可以为其预留一个指针的位置。
类型的宽度（Width）是类型的一个对象或实例所需的存储单元（通常是字节）的数量。 一个基本类型的宽度总是整数，而为数组或类（或记录）所分配的空间通常是连续的。 大部分语言中，指针是一个特殊的类型，其大小与所指的类型无关。
在为类型分配存储空间时，还要特别考虑对齐的问题。 对大部分处理器，其处理的数据的地址总是按2的次方对齐的，其中大部分是按4字节对齐的。 这就是说，所有类型的首字节所在的地址总是能被4整除的。 因此，假设一个聚合类型的理论宽度为10字节，实际上它的一个对象通常会占用12字节。 如果运行空间比较宝贵，编译器可能对数据进行压缩，此时不再为对齐而插入额外的字节。 但是处理器通常不能处理这种数据，因此在使用时还需要执行额外的指令进行转化。 在这一节中，我们暂时不考虑对齐的问题。
我们首先考虑单个声明，没有聚合类型（记录）的情况。 以下翻译方案可以求出声明的类型和类型的宽度。 \(\begin{aligned} T \quad &\to \quad B \; \{ C.t = B.type; C.w = B.width \} \; C \; \{ T.type = C.type; T.width = C.width\} \\ B \quad &\to \quad \mathbf{int} \; \{ B.type=integer; B.width=4 \} \\ B \quad &\to \quad \mathbf{float} \; \{ B.type=float; B.width=8 \} \\ C \quad &\to \quad \epsilon \; \{C.type = C.t; C.width = C.w\} \\ C \quad &\to \quad [\mathbf{num}] \; \{C_1.t = C.t; C_1.w = C.w \} \; C_1 \\ & \{C.type = array(num, C_1.type); C.width = C_1.width \} \\ \end{aligned}\) 正如我们此前介绍的那样，我们先把$B$的属性用继承的方式不断向下传递，最后通过$C$的综合属性求值。
声明的序列
我们接下来考虑一串连续的声明，在这种声明中，不仅需要计算每个对象所占用的空间，还需要在符号表中分配它们的相对位置，即确定偏移。
虽然对一般的连续声明，我们并不一定需要让被声明的变量严格顺序排列，但计算它们的偏移可以用来为聚合类型分配空间。
我们可以向SDT中加入以下代码：
\(\begin{aligned}
P \quad &\to \quad \{\text{offset} = 0\} \; D \\
D \quad &\to \quad T \ \mathbf{id} \ ; \; \{insert(\mathbf{id}.lexeme, T.type, \text{offset}); \text{offset} = \text{offset} + T.width\} \; D_1 \\
D \quad &\to \quad \epsilon
\end{aligned}\)
insert表示向符号表中插入一个条目，给出这个条目的类型和偏移。
聚合类型
接下来考虑聚合类型（即类和记录）的分配。 为方便起见，我们假设每个记录都有自己的符号表，其中保存了每个字段的类型和（相对记录首字节的）偏移。
我们继续向SDT中加入内容： \(\begin{aligned} T \quad \to \quad & \mathbf{record} \ '\{' \; &\{ Env.push(top); top = new STable(); \\ & & Stack.push(offset); offset = 0 \} \\ & D \ '\}' &\{ T.type = record(top); T.width = offset; \\ & & top = Env.pop(); offset = Stack.pop(); \} \end{aligned}\)
其中$top$是一个指向（记录专有的）符号表的指针，而$record(top)$表示给出一个符号表的指针，返回其对应的类型。
$Env$是符号表指针的栈，$Stack$是偏移的栈。
和C++ STL不同，我们规定栈的pop()函数也返回栈顶元素。
对记录和对类的方法是一致的，因为类中的方法（成员函数）并不占用任何空间。