第六章 中间代码生成

6.9 过程的中间代码

过程及其实现将在第7章中与运行时刻的变量存储管理一并更加详细地讨论。本节我们使用术语函数来表示带有返回值的过程。我们将简单讨论函数声明以及进行函数调用的三地址代码。在三地址代码中，函数调用被拆分为准备进行调用时的参数求值，然后是调用本身。为简单起见，我们假定参数使用值传递的方式。1.6.6节中曾讨论过参数传递方法。

例6.25：假定a是一个整数数组，并且f是一个从整数到整数的函数。那么赋值语句

n=f(a[i]);

可以被翻译成如下的三地址代码。

1） t1=i*4 2） t2=a[t1] 3） param t2 4） t3 = call f, 1 5） n = t3

如6.4节中讨论的，前两行计算表达式a[i]的值，并存放到临时变量t2中。第3行将t2作为实在参数用于第4行中对f的调用。这个调用只带有一个参数。第4行中函数调用的返回值被赋给t3。第5行将返回值赋给n。□

图6.52中的产生式可以生成函数定义和函数调用。（这个文法会在最后一个参数之后生成一个不必要的逗号，但是它已经足以演示翻译的方法了。）如6.3节中所述，非终结符号D和T分别生成声明和类型。由D生成的函数定义包含了关键字define，返回类型，函数名，括号中的形式参数以及由一个语句组成的函数体。非终结符号F生成0个或多个形式参数，每个形参包括一个类型和一个标识符。非终结符号S和E分别生成语句和表达式。S的产生式增加了一条返回表达式值的语句。E的产生式中增加了函数调用，调用中的实在参数由A生成。一个实在参数就是一个表达式。

图6.52：在源语言中加入函数 函数定义和函数调用可以用本章中已经介绍过的概念进行翻译。

? 函数类型。一个函数类型必须包含它的返回值类型和形参类型。令void是一个表示没

有参数或没有返回值的特殊类型。因此返回一个整数的函数pop( )的类型是“从void到integer的函数”。函数类型可以在返回值类型和有序的参数类型序列上应用函数构造算子fun来表示。

? 符号表。设编译器处理到一个函数定义时，最上层的符号表为s。函数名被放入s，以

便在程序的其它部分使用。函数的形式参数可以用类似于记录域名的方式来处理（见图6.18）。在D的产生式中，在看到关键字define和函数名之后，我们将s压栈并建立新的符号表。

Env.push(top); top = new Env(top);

新表被称为t。注意，top被作为参数传递到new Env(top)，因此新的符号表t可以被连接到先前的符号表s。新的符号表用于这个函数的函数体的翻译。在这个函数体被翻译完成之后，我们恢复到先前的符号表s。

? 类型检查。在表达式中，一个函数和一个运算符的处理方法相同。因此在6.5.2中的讨

论的类型检查规则，包括强制规则，仍然可用。例如，如果f是一个带有一个实数型参数的函数，那么在函数调用f(2)中，整数2将被转换成实型数。 ? 函数调用。当为一个函数调用id(E,E,…,E)生成三地址代码的时候，只需要生成对参数E

求值的三地址指令，或者生成将参数E还原为地址的三地址指令，然后再为每个参数生成一条param指令。如果我们不愿将参数计算指令和param指令混在一起，可以将每个表达式E的属性E.addr存放到一个数据结构，比如队列。一旦所有的表达式都被翻译完成，我们就可以在清空队列的同时生成param指令。

过程是程序设计语言中重要且频繁出现的编程结构。因此编译器必须为过程调用和返回生成良好的代码。用于处理过程的参数传递、调用和返回的运行时刻子程序是运行时刻支持系统的一部分。运行时刻支持机制将在第7章中讨论。

6.10 第6章的总结

本章的技术可以被综合起来，构造一个简单的编译器前端，比如象附录A中的那个程序。编译器的前端可以增量式地进行构造：

? 选择一个中间表示形式（Pick an intermediate representation）：中间表示形式通常是一个

图形表示方法和三地址代码的组合。比如在语法树中，图例中的结点表示一个程序构造；而各个子结点表示其子构造。三地址代码的名字来源于它的x=y op z的形式。每条指令至多有一个运算符。另外还有一些用于控制流的三地址指令。

? 翻译表达式(Translate expressions)：通过在各个形如E→E1 op E2的产生式中加入语义动

作，带有复杂运算的表达式可以被分解成一个由单一操作组成的序列。这些动作或者创建一个E的结点，此结点的子结点为E1和E2；或者生成一条三地址指令，该指令对E1和E2的地址应用运算符op，并将其运算结果放入一个临时变量中。这个临时变量就成了E的地址。

? 检查类型(Check types)：一个表达式E1 op E2的类型是由运算符op以及E1和E2的类型

决定的。强制（coercion）是指隐式的类型转换，例如从integer转换到float。中间代码中还包含了显式的类型转换，以保证运算分量的类型和运算符的期待类型精确匹配。 ? 使用符号表来实现声明(Use a symbol table to implement declarations)：一个声明指定了一

个名字的类型。一个类型的宽度是指存放该类型的变量所需要的存储空间的数量。使用宽度，一个变量在运行时刻的相对地址可以计算为相对于某个数据区域的开始地址的偏移量。每个声明都会将一个名字的类型和相对地址放入符号表，这样当这个名字之后出现在一个表达式中时，编译器就可以获取这些信息。

? 将数组扁平化(Flatten arrays)：为实现快速访问，数组元素被存放在一段连续的空间内。

数组的数组可以被扁平化，当作各个元素的一维数组进行处理。数组的类型被用来计算一个数组元素相对于数组基地址的偏移量。

? 为布尔表达式产生跳转代码(Generate jumping code for Boolean expressions)：在短路或者

说跳转代码中，布尔表达式的值被隐含在代码所到达的位置中。因为布尔表达式B常常被用于决定控制流，例如在if（B）S中就是这样，因此跳转指令是有用的。只要使得程序正确地跳转到代码t=true或t=flase处，就可以计算出布尔值，其中的t是一个临时变量。使用跳转标号，通过继承属性来传递对应于一个布尔表达式的真假出口的标号，就可以对布尔表达式进行翻译。常量true和false分别被翻译成跳转到真值出口和假值出口的指令。

? 用控制流实现语句(Implement statements using control flow)：通过继承next标号就可以

实现语句的翻译，其中next标记了这个语句的代码之后的第一条指令。翻译条件语句S→if (B)S1时，只需要将一个标记了S1代码的起始位置的新标号和S.next分别附加到B的真值出口和假值出口。

? 也可以选择使用回填技术(Alternatively, use backpatching)：回填是一种为布尔表达式和

语句进行一趟式代码生成的技术。其基本思想是维护多个由不完整跳转指令组成的列表，在同一列表中的指令将具有同样的跳转目标。当目标位置变得已知时，相应列表中的所有指令将被填入这个目标。

? 实现记录(Implement records)：记录或类中的域名可以当作声明序列进行处理。一个记

录类型包含了关于它的各个域的类型和相对地址的信息。可以使用一个符号表来实现这个目的。

6.11 第6章参考文献

本章中的大部分技术来自于围绕Algol60进行的设计和实现活动。在Pascal[11]和C[6,9]产生的时候，生成中间代码的语法制导翻译已经很成熟了。

从20世纪50年代开始，人们就开始寻求一种虚构的中间语言 ——UNCOL（面向所有编译器的语言）。如果有一个UNCOL，我们可以把针对一种给定的源语言的前端和针对一种给定目标语言的后端连接起来，构建出一个编译器[10]。报告[10]中的指导性技术常常被用于将编译器重定向。

人们用很多种方法来实现UNCOL思想，即将多个前端和后端混合并相互匹配。一个可重定目标的编译器包括一个前端，该前端可以和不同的后端结合起来，在不同机器上实现同一种给定的语言。Neliac语言是一个带有重定目标编译器[5]的早期例子，这个编译器就使用Neliac本身编写。另一种方法是为一个新的语言建立一个前端，将其翻译到一个已有的编译器上。Fedman[2]描述了在C编译器上加入Fortran的前端的方法[6][9]。GCC，即GNU的编译器集合[3]，支持包括C、C＋＋、Fortran、java、ada等语言的前端。

值编码方法及其基于hashing的实现来自于Ershov [1]。

在Java字节码中使用类型信息来提高安全性的技术由Gosling[4]描述。

使用合一方法了求解方程组，并进行类型推导的技术被人们多次重复发现；它在ML上的应用由Milner[7]描述。要对类型进行更全面的处理，可参见Pierce[8]。