发布时间 : 星期四 文章第六章 中间代码生成更新完毕开始阅读d381edbdfd0a79563c1e724d
第六章 中间代码生成
在编译器的分析-综合模型中，前端对源程序进行分析并产生中间表示，后端在此基础上生成目标代码。在理想情况下，和源语言相关的细节在前端分析中处理，而关于目标机器的细节则在后端处理。基于一个适当定义的中间表示形式，可以把针对源语言i的前端和针对目标机器j的后端组合起来，构造得到源语言i在目标机器j上的一个编译器。这种创建编译器组合的方法可以节约大量的工作量：只要写出m种前端和n种后端处理程序，就可以得到m×n种编译程序。
本章的内容处理中间代码表示、静态类型检查和中间代码生成。为简单起见，我们假设一个编译程序的前端处理按照图6.1所示方式进行组织，顺序地进行语法分析、静态检查和中间代码生成。有时候这几个过程也可以组合起来，在语法分析中一并完成。我们将使用第二章和第五章中的语法制导定义来描述类型检查和翻译过程。大部分的翻译方案可以基于第五章中给出的自顶向下或自底向上的技术来实现。所有的方案都可以通过生成并遍历抽象语法树来实现。
Parser 语法分析器 Static Checker 静态检查程序 Intermediate code generator 中间代码生成器 intermediate code 中间代码 code generator 代码生成器 front end 前端 back end 后端 图6.1：一个编译器前端的逻辑结构
静态检查包括类型检查，保证运算符被作用于兼容的运算分量。静态检查还包括在语法分析之后进行的所有语法检查。例如，静态检查保证了C语言中的一条break指令必然位于一个while/for/switch语句之内。如果不存在这样的语句，静态检查将报告一个错误。
本章介绍的方法可以用于多种中间表示，包括抽象语法树和三地址代码。这两种中间表示方法都在本书的2.8节中介绍过。名为“三地址代码”的原因是这些指令的一般形式x=y op z具有三个地址：两个运算分量y和z，一个结果变量x。
在将给定源语言的一个程序翻译成特定的目标机器代码的过程中，一个编译器可能构造出一系列的中间表示，如图6.2所示。高层的表示接近于源语言，而低层的表示接近于目标机器。语法树是高层的表示，它刻画了源程序的自然的层次性结构，并且很适合进行诸如静态类型检查这样的处理。
Source Program 源程序 High Level Intermediate Representation 高层中间表示形式 Low Level Intermediate Representation 低层中间表示形式 Target Code 目标代码 图6.2：编译器可能使用一系列的中间表示
低层的表示形式适合进行机器相关的处理任务，比如寄存器分配、指令选择等。通过选择不同的运算符，三地址代码既可以是高层的表示方式，也可以是低层的表示方式。从6.2.3节将可以看出，对表达式而言，语法树和三地址代码只是在表面上有所不同。对于循环语句，语法树表示了语句的各个组成部分，而三地址代码包含了标号和跳转指令，用来表示目标语言的控制流。
不同的编译程序对中间表示的选择和设计各有不同。中间表示可以是一种真正的语言，也可以是编译器的各个处理阶段共享的多个内部数据结构。C语言是一种程序设计语言。它具有很好的灵活性和通用性，可以很方便地把C程序编译成高效的机器代码，并且有很多C的编译器可用，因此C语言也常常被用作中间表示。早期的C++编译器的前端生成C代码，而把C编译器作为其后端。
6.1 语法树的变体
语法树中各个结点代表了源程序的构造；一个结点的所有子结点反映了该结点对应构造的有意义的组成成分。为表达式构建的无环有向图（Directed acyclic graph, 以后简称DAG）指出了表达式中的公共子表达式（多次出现的子表达式）。在本节我们将看到，可以用构造语法树的技术去构造DAG图。
6.1.1 表达式的有向无环图
和表达式的语法树类似，一个DAG图的叶子结点对应于原子运算分量，而内部结点对应于运算符。与语法树不同的是，如果DAG图中的一个结点N表示一个公共子表达式，则N可能有多个父结点。在语法树中，公共子表达式每出现一次，代表该公共子表达式的子树就会被复制一次。因此，DAG不仅更简洁地表示了表达式，而且可以为最终生成表达式的高效代码提供重要的信息。
例子6.1 ：图6.3给出了下面的表达式的DAG图
a+a*(b-c)+(b-c)*d
叶子结点a在表达式中出现了两次，因此a有两个父结点。值得注意的是，结点“-”代表公共子表达式b-c的两次出现。该结点同样有两个父结点，表明该子表达式在子表达式a*(b-c)和(b-c)*d中两次被使用。尽管b和c在整个表达式中出现了两次，它们对应的结点都只有一个父结点，因为对它们的使用都出现在同样的公共子表达式b-c中。□
图6.3：表达式a+a*(b-c)+(b-c)*d的DAG图
图6.4：生成语法树或DAG图的语法制导定义
图6.4给出的SDD（语法制导定义）既可以用来构造语法树，也可以用来构造DAG图。它在例5.11中曾被用于构造语法树。在那时，函数lead和node每次被调用都会构造出一个新结点。要构造得到DAG图，这些函数就要在每次构造新结点之前首先检查是否已存在这样的结点。如果存在一个已被创建的结点，它们就返回这个结点。例如，在构造一个新结点Node(op,left,right)之前，我们首先检查是否已存在一个结点，该结点的标号为op，且其两个子结点为left和right。如果存在，Node函数返回这个已存在的结点；否则它创建一个新结点。
例子6.2: 图6.5给出了构造图6.3中所示DAG图的各个步骤。如上所述，函数node和leaf尽可能地返回已存在的结点。我们假设entry-a指向符号表中a的位置，其它标识符也类似。
图6.5：图6.3所示DAG图的构造过程。 当在第2步上再次调用Leaf(id,entry-a)时，函数返回的是之前已生成的结点，因此p2=p1。类似地，第8步和第9步上返回的结点分别和第3步及第4步中返回的结果相同（即p8=p3， p9=p4）。同样，第10步中返回的结点必然和第5步中返回的相同，即p10=p5。□
6.1.2 构造DAG的值编码方法
语法树或DAG图中的结点通常被存放在一个记录数组中，如图6.6所示。数组的每一行表示一个记录，也就是一个结点。在每个记录中，第一个域是一个运算符代码，也是该结点的标号。在图6.6(b)中，各个叶子结点还有一个附加的域，存放了标识符的字面值（在这里，它是一个指向符号表的指针或一个常量）。而内部结点则有两个附加的域，分别指明其左右子结点。
图6.6：i=i+10的DAG图的结点在数组中的表示
在这个数组中，我们只需要给出一个结点对应的记录在此数组中的整数序号就可以引用该结点。在历史上，这个序号被称为相应结点或该结点所表示的表达式的值编码。例如，在图6.6中，标号为“+”的结点的值编码为3, 其左右子结点的值编码分别为1和2。在实践中，我们可以用记录指针或对象引用来代替整数下标，但是我们仍然把一个结点的引用称为该结点的“值编码”。如果使用适当的数据结构，值编码可以帮助我们高效地构造出表达式的DAG图。下一个算法将给出构造的方法。
假定结点按照如图6.6所示的方式存放在一个数组中，每个结点通过值编码引用。令每个内部结点用一个三元组表示
算法6.3: 构造DAG图的值编码方法。 输入：标号op、结点l和结点r。
输出：数组中具有三元组
方法：在数组中搜索标号为op、左子结点为l且右子结点为r的结点M。如果存在，则返回M结点的数值号。若不存在，则在数组中添加一个结点N，其标号为op，左右子结点分别为l和r；返回新建结点对应的值编码。□
虽然算法6.3可以产生我们期待的输出结果，但是每次定位一个结点时都要搜索整个数组。这个开销是很大的，当数组中存放了整个程序的所有表达式时尤其如此。更高效的途径是使用哈希表，将结点放入若干“桶”中，每个桶通常只包含少量结点。哈希表是能够高效支持词典功能的少数几个数据结构之一2。词典是一种抽象的数据类型，它可以插入或删除一个集合中的元素，可以确定一个给定元素当前是否在集合中。类似于哈希表这样为词典设计的优秀数据结构可以在常数或接近常数的时间内完成上述的操作，所需时间和集合的大小无关。
要给DAG图中的结点构造哈希表，首先需要建立哈希函数h。这个函数为形如
桶可以通过链表来实现，如图6.7所示。一个由哈希值索引的数组保存桶的头。每个头指向列表中的第一个单元。所有其哈希值指向这个桶的结点都存放在这个桶的链表中，链表的各个单元记录了这些结点的值编码。就是说，在以数组的第h(op,l,r)个元素为头的链表中可以找到结点
2
见Aho, A.V., J.E.Hopcroft和J.D.Ullman, Data structures and Algorithms, Addison-Wesley出版社, 1983。其中有一个关于支持词典功能的数据结构的讨论。