第六章 中间代码生成

代表，它的set域被设置为空指针。等价类中其它结点的set域（可能通过该集合中的其它结点间接地）指向该等价类的代表结点。在初始时刻，每个结点n自身组成成一个等价类，n是它自己的代表。

nodes s and n represent the same basic type 结点s和n表示相同的基本类型 s is an op-node with children s1 and s2 s是一个带有子结点s1和s2的op-结点 t is an op-node with children t1 and t2 t是一个带有子结点t1和t2的op-结点 s or t represents a variable s或者t表示一个变量 图6.32： 合一算法 如图6.32所示的合一算法在结点上进行如下的两种操作： ? find(n)返回当前包含结点n的等价类的代表结点。 ? union(m,n)将包含结点m和n的等价类合并。如果m和n所对应的等价类的代表结点中

有一个是非变量的结点，则union将这个非变量结点作为合并得到的等价类的代表结点。否则union把任意一个原代表结点作为新的代表。这种非对称性在union的规约中非常重要。因为如果一个等价类中包含了带有类型构造符的表达式或基本类型，我们就不能把一个变量用作该等价类的代表。否则，两个不等价的表达式可能会通过该变量被合一。

集合的union操作的实现很简单，只需要改变一个等价类的代表结点的set域，使之指向另一个等价类的代表结点。为了发现一个结点所属的等价类，我们沿着各个结点的set域中的指针前进，直到到达代表结点（即set域指针为空指针的结点）。

请注意图6.32中的算法分别使用s=find(m), t=find(n)，而不是直接使用m和n。如果m和n在同一个等价类中，那么代表结点s和t相等。如果s和t表示相同的基本类型，则调用unify(m,n)返回true。如果s和t都是代表某个二目类型构造算子的内部结点，我们尝试合并它们的等价类，并递归地检查它们各个子结点是否等价。因为首先进行合并操作，我们在递归检查子结点之前减少了等价类的个数，因此算法终止。

将一个变量置换为一个表达式的实现方法如下：把代表该变量的叶子结点加入到代表该表达式的结点所在的等价类中。假设m或n之一是表示一个变量的叶子结点。同时假设这个结点已经被放入满足下面条件的等价类中。这个等价类中的一个结点代表的表达式或者带有一个类型构造算子，或者是一个基本类型。那么find将会返回一个反映该类型构造算子或基本类型的代表结点。因而一个变量不会和两个不同的表达式合一。□

例6.20：假设例子6.18中的两个表达式可以用图6.33中的两个初始类型图表示，图中的每个结点属于只包含自身的等价类。当应用算法6.19来计算unify(1,9)时，注意到结点1和9都表示同一个运算符。因此将结点1和9合并成同一个等价类，并调用unify(2,10)和unify(8,14)。执行unify(1,9)得到的结果就是前面在图6.31中显示的类型图。□

图6.33： 初始类型图，其中的每个节点在只包含自身的等价类中 如果算法6.19返回true，我们可以按照如下方法构造出一个置换S作为合一替换。对于每

个变量α，find(α)给出α的等价类的代表结点n。n所表示的表达式为S(α)。例如，在图6.31中，我们看到α3的代表结点为4，这个结点表示α1。结点8是α5的代表，这个结点表示list(α2)。置换S的结果如例子6.18中所示。

6.5.6 6.5节的练习

练习6.5.1: 假定图6.26中的函数widen可以处理图6.25(a)的层次结构中的所有类型，翻译下列表达式。假定c和d是字符型，s和t是短整型，i和j为整型，x是浮点型。 a) x = s + c b) i = s + c

c) x = (s + c) * (t + d)

练习6.5.2: 象Ada中那样，我们假设每个表达式必须具有唯一的类型，但是我们根据一个子表达式本身只能确定一个可能类型的集合。也就是说，将函数E1应用于参数E2，其文法产生式为E →E1 (E2)，有如下规则

E.type = {t | 对E2.type中的某个s, s→t 在E1.type中}。

描述一个可以确定每个子表达式的唯一类型的语法制导定义（SDD）。它首先使用属性type，按照自底向上的方式综合得到一个可能类型的集合。并且在确定了整个表达式的唯一类型之后，自顶向下地确定属性unique的值，这个属性表示各个子表达式的唯一类型。

6.6 控制流

对于if-else-语句、while-语句的等类似语句的翻译和对布尔表达式的翻译是结合在一起的。在程序设计语言中，布尔表达式经常会被用来：

1. 改变控制流。布尔表达式被用作语句中改变控制流的条件表达式。这些表达式的值由程

序到达的某个位置隐含地指出。例如，在if (E) S中，如果运行到语句S就意味着E的取值为真。

2. 计算逻辑值。一个布尔表达式的值表示了true或false。这样的布尔表达式也可以像算术

表达式一样，使用带有逻辑运算符的三地址指令进行求值。

布尔表达式的使用意图要根据其语法上下文来确定。例如，跟在关键字if后面的布尔表达式被用来改变控制流，而一个赋值语句右部的表达式表示一个逻辑值。有多种方式可以描述这样的上下文：我们可以使用两个不同的非终结符号，也可以使用继承属性，还可以在分析过程中设置一个标记。我们还可以使用另一种方法，建立一棵语法树并调用不同的过程来处理布尔表达式的两种不同的使用。

本节专门介绍用于改变控制流的布尔表达式。更清楚地说，我们为此目的引入一个新的非终结符B。在6.6.6节中，我们将考虑编译器如何使得布尔表达式表示逻辑值。

6.6.1 布尔表达式

布尔表达式是将布尔运算符作用于布尔变量或关系表达式而构成的。我们使用C语言的方

法，用&&、||、!分别表示AND,OR,NOT运算符。关系表达式的形式为E1 rel E2。其中E1和E2为算术表达式。本节中，我们考虑的是由如下的文法生成的布尔表达式： B→ B || B | B && B | !B | (B) | E rel E | true | false

我们通过属性rel.op来指明rel究竟表示6种比较运算符<、<=、=、!=、>和>=中的哪一种。按照惯例，||和&&是左结合的，||的优先级最低，其次为&&，再其次为！。

给定表达式B1||B2，如果我们已经确定B1为真，我们不用再计算B2就可以断定整个表达式为真。同样的，给定B1&&B2,如果B1为假，则整个表达式为假。

程序设计语言的语义定义决定了是否需要对一个布尔表达式的各个部分都进行求值。如果语言的定义允许（或要求）不对布尔表达式的某个部分求值，那么编译器就可以优化布尔表达式的求值过程，只要已经求值的部分足以确定整个表达式值就可以了。因此，在表达式B1||B2中，B1和B2都不一定要完全地求值。如果B1或B2是具有副作用的表达式（比如它包含了改变一个全局变量的函数），这么做就可能会得到意料之外的结果。

6.6.2 短路代码

在短路（跳转）代码中，布尔运算符&&,||和!被翻译成跳转指令。运算符本身不出现在代码中，布尔表达式的值是通过代码序列中的位置来反映的。

例子6.21：语句

if (x<100 || x>200 && x!=y) x=0;

可以被翻译成图6.34所示的代码。在这个翻译中，如果程序的控制流到达L2就表示这个布尔表达式为真。如果表达式为假，程序控制流将跳过L2和赋值语句x=0，直接转到L1。□ 图6.34： 跳转代码 6.6.3 控制流语句

现在我们考虑在按下列产生式生成的语句的上下文中，如何把布尔表达式翻译成为三地址代码。

S→ if (B) S1

S→ if (B) S1 else S2 S→ while (B) S1

在这些产生式中，非终结符号B表示一个布尔表达式，非终结符号S表示一个语句。

这个文法对我们在例5.19中介绍的关于while语句的连续例子进行了一般化。和那个例子中一样，B和S有综合属性code，该属性给出了翻译得到的三地址代码指令。为简单起见，我们使用语法制导定义来构造得到翻译结果B.code和S.code，结果值是字符串。定义了code属性的语义规则还可以按照下面的方法实现：首先构造语法树，并在遍历树的过程中产生出目标代码。这些规则还可以通过在5.5节中列出的任何方法来实现。

如图6.35(a)所示，对if(B) S1的翻译结果中包含了B.code，其后是S1.code。B.code中存在基于B值的跳转。如果B为真，控制转向S1.code的第一条指令，如果B为假，控制立即转向紧跟在S1.code之后的指令。

图6.35： if-, if-else-, while-语句的代码 B.code和S.code中的跳转标号使用继承属性来处理。我们将布尔表达式B和两个标号：B.true和B.false相关联。当B为真时控制流转到B.true；当B为假时控制流转到B.false。我们将语句S和继承属性S.next相关联。这个属性表示紧跟在S代码之后的指令的标号。在很多情况下，紧跟在S.code之后的指令是一个跳转到某个标号L的跳转指令。使用S.next可以避免在S.code中出现跳转目标为一个以L为目标的跳转指令的跳转指令。

图6.36、6.37给出的语法制导定义可以为if-, if-else-及while-语句的上下文中的布尔表达式生成三地址代码。

PRODUCTION 产生式 SEMANTIC RULES 语义规则 图6.36：控制流语句的语法制导定义

我们假定每次调用newlabel()都会产生一个新的标号，并假设label(L)将标号L附加到即将生成的下一条三地址指令上9。

一个程序包含一条由产生式P→S生成的语句。和这个产生式关联的语义规则将S.next初始化为一个新的标号。P.code包含了S.code，S.code之后是新标号S.next。产生式S→assign中的词法单元assign是一个表示赋值语句的占位符。赋值语句的翻译和6.4节中讨论的方法相同。在本次对控制流的讨论中，S.code就是assign.code。

在翻译S→if (B) S1时，图6.36中的语义规则创建一个新的标号B.true，并将其关联到为语句S1生成的第一条三地址指令，如6.35(a)中所示。因此，B的代码中跳转到B.true的指令将跳转到语句S1对应的代码。不仅如此，通过将B.false设为S.next，我们保证了当B的值为假时，控制流将跳过S1的代码。

在翻译if-else-语句S→if (B) S1 else S2时，布尔表达式B的代码中有一些向外跳转的指令，它们在B为真时跳转到S1的代码的第一条指令；在B为假时跳转到S2的代码的第一条指令如图6.35(b)所示。然后，控制流从S1或S2转到紧跟在S的代码之后的三地址指令——该指令的标号由继承属性S.next指定。在S1的代码之后有一条goto S.next指令，使得控制流越过S2的代码。S2的代码之后不需要goto语句，因为S2.next就是S.next。

如图6.35(c)所示，S→while (B) S1的代码由B.code和S1.code组成。我们使用一个局部变量begin来存放附加在这个while语句的第一条指令上的标号。这个while语句的第一条指令也 9

如果严格地按照上面的语义规则来实现，这些规则将产生很多的标号，并可能在一个三地址指令上附加多个标号。6.7节中介绍的回填技术只在必要的时候创建标号。处理这个问题的另一种方法是在后续的优化步骤中消除不必要的标号。