第六章 中间代码生成

是B的第一条指令。我们在这里使用变量而不是属性，是因为begin是这个产生式的语义规则的局部量。继承属性S.next标记了当B为假时控制流必须转向的标号；因而，B.false被设置为S.next。在S1的第一条指令上附加了一个新标号B.true。B的指令中的跳转指令在B为真时跳转到这个标号。我们在S1的代码之后放置了一条指令goto begin，它跳回到布尔表达式的代码的开始处。请注意S1.next被设置为标号begin，因此从S1.code中跳出的指令可以直接跳转到begin。

S→S1S2的代码包含了S1的代码，然后是S2的代码。相应的语义规则主要处理标号；S1的代码之后的第一条指令就是S2的代码的起始指令。紧跟在S2的代码之后的指令也是跟在S的代码之后的指令。

我们将在6.7节中进一步讨论控制流语句的翻译。在那里我们将使用另一种被称为回填的方法，它可以在一趟中生成各个语句的代码。

6.6.4 布尔表达式的控制流翻译

图6.37中针对布尔表达式的语义规则是图6.36中语句的语义规则的一个补充。如图6.35中的代码布局方案所示，翻译一个布尔表达式B得到的三地址代码将使用条件或无条件跳转指令来表示B的求值。这些转移指令的目标是两个标号之一：当B为真时是B.true，B为假时是B.false。

PRODUCTION 产生式 SEMANTIC RULES 语义规则 图6.37： 为布尔表达式生成三地址代码 图6.37中的第四个产生式，即B→E1 rel E2，直接被翻译成三地址比较指令，跳转到正确的位置。例如，a

if a

B的其余产生式按照下面的方法翻译：

1. 假定B的形式为B1||B2。如果B1为真，那么我们立刻知道B本身也为真，因此B1.true

和B.true相同。如果B1为假，那么就必须对B2求值，因此我们将B1.false设置为B2的代码的第一条指令的标号。B2的真假出口分别等于B的真假出口。 2. B1&&B1的翻译方法类似于1。

3. 不需要为B→!B1产生新的代码：只需要将B中的真假出口对换，就可分别得到B1的真

假出口。

4. 将常量true和false分别翻译成目标为B.true和B.false的跳转指令。

例6.22：重新考虑例6.21中的下列语句：

if (x<100 || x>200 && x!=y ) x=0； （6.13）

使用图6.36和6.37中的语法制导定义，我们可以得到图6.38中的代码。

图6.38：一个简单的if语句的控制流翻译结果 语句(6.13)是图6.36中的产生式P→S生成的一个程序。这条产生式的语义规则生成了S的代码之后的第一条指令的新标号L1。语句S的形式为if(B) S1，其中S1是x=0。因此图6.36中的规则生成了一个新标号L2，并将它附加到S1.code的第一条（在这个例子中也是唯一的）指令，即x=0。

因为||的优先级低于&&，（6.13）中的布尔表达式的形式为B1||B2，其中B1是x<100。按照6.37中的规则，B1.true是L2，即语句x=0的标号；B1.false是一个新的标号L3，它附加在B2的代码的第一条指令上。

值得注意的是，生成的这个代码不是最优的，这个翻译结果比例子6.21中的代码多出三条（goto）指令。指令goto L3是冗余的，因为L3恰巧就是下一条指令的标号。如果象例子6.21中那样使用ifFalse指令，而不使用if指令，两条goto L1指令也可以被消除。□

6.6.5 避免冗余的goto指令

在例子6.22中，比较表达式x>200被翻译成如下代码片段： if x > 200 goto L4 goto L1 L4: …

可以将上面的指令替换为如下指令： ifFalse x > 200 goto L1 L4: …

这个ifFlase指令利用了控制流在指令序列中会从一个指令自然流动到下一个指令的性质，因此当x>200不成立时，控制流直接“穿越”到标号L4，从而减少了一个跳转指令。

在图6.35中显示的if-和while-语句的代码布局方案中，S1的代码紧跟在布尔表达式B的代码之后。通过使用一个特殊标号“fall”（即不要生成任何跳转指令），我们可以修改图6.36和6.37中的语义规则，允许控制流从B的代码直接穿越到S1的代码。图6.36中的产生式S?if (B) S1;的新语义规则将B.true设为fall： B.true = fall

B.false = S1.next = S.next S.code= B.code||S1.code

类似地，if-else-和while-语句的规则也将B.true设为fall。

现在我们将修改布尔表达式的语义规则，使之尽可能地允许控制流穿越。在B.true和B.false都是显式的标号时，也就是说它们都不等于fall时，图6.39中的B→E1 rel E2的新规则和图6.37中一样，将产生两条指令。否则如果B.true是显式的标号，那么B.false一定是fall，因此它们产生一条if指令，使得当条件为假时控制流穿越到下一条指令。反过来，如果B.false是显式的标号，那么它们产生一条ifFalse指令。在其余情况中B.true和B.false都是fall，

因此不产生任何跳转指令10。

图6.40中显示的B→B||B1的新规则中，请注意B的fall标号和B1的fall标号具有不同的含义。假定B.true为fall；即如果B为真时控制流穿越B。虽然当B1为真时B的值必然为真，B1.true必须保证控制流跳过B2的代码，直接到达B之后的下一条指令。

另一方面，如果B1的值为假，B的真假值就由B2的值决定。因而图6.40中的规则保证B1.false对应于控制流穿越B1直接到达B2的代码的情况。

B→B1&&B2的语义规则和图6.40中的类似，我们将其留作练习。

图6.39： B→E1 rel E2的语义规则 图6.40：B→B1||B2的语义规则 图6.41：使用控制流穿越技术翻译的if语句

例6.23：使用了特殊标号fall的语义规则将例6.21中的程序（6.13）

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

翻译成图6.41所示的代码。

和例子6.22一样，产生式P→S的语义规则创建标号L1。和例6.22不同的是，当应用B→B1||B2的语义规则时，继承属性B.true是fall（B.false为L1）。图6.40中的规则创建一个新标号L2，使得当B1为真时有一个跳转指令可以跳过B2的代码。因此B1.true为L2而B1.false为fall，因为B1为假时必须计算B2的值。

因此当开始处理由产生式B→E1 rel E2生成的表达式x<100时，B.true=L2且 B.false=fall。因此图6.39中的规则使用这些继承属性生成了一条指令if x<100 goto L2。□

6.6.6 布尔值和跳转代码

本节讨论的重点是用于改变语句中控制流的布尔表达式。一个布尔表达式的目的也可能就是要求出它的值，诸如x=true；或x=a

处理布尔表达式的这两种角色的一种简单思路是首先建立表达式的语法树，然后使用下面的两种方法之一：

1. 使用两趟处理的方法。为输入构造出完整的语法树，然后以深度优先顺序遍历这棵语法

树，依据语义规则的描述计算得到翻译结果。 10

在C和Java中，表达式中可能包含赋值语句，因此即使B.true和B.false都为fall也必须为E1和E2生成代码。如果必要，无用代码可以在优化阶段被清除。

2. 对语句进行一趟处理，但对表达式进行两趟处理。使用这种方法时，我们将首先翻译语

句while(E) S1中的E，然后再处理S1。然而，对E的翻译需要首先建立它的语法树然后再遍历它。

下列文法中用单个非终结符E来代表表达式：

S→id =E; | if (E) S | while (E) S | S S

E→E||E | E&&E | E rel E | E+E | (E) | id | true | false 非终结符E支配了S→while (E) S1的控制流。同一个非终结符E在S→id=E和E→E+E中则表示一个值。

我们可以使用不同的代码生成函数处理表达式的这两种角色。假定属性E.n表示对应于表达式E的语法树结点，并且语法树中的结点都是对象。令例程jump产生一个表达式结点的跳转代码，并令例程rvalue产生计算结点的值的代码，该代码还把得到的值存储在一个临时变量中。

对于出现在S→while (E) S1中的E，调用结点E.n上例程jump。例程jump的实现是基于图6.37中给出的关于布尔表达式的语义规则。确切地说，跳转代码是通过调用E.n.jump(t,f)生成的，其中t是指向S1.code的第一条指令的新标号，而f就是标号S.next。

对于出现在S→id=E中的E，调用结点E.n上的例程rvalue。如果E的形式为E1+E2，例程调用E.n.rvalue()按照6.4节中讨论的方法生成代码。如果E的形式为E1&&E2，我们首先为E生成跳转代码，然后在跳转代码的真假出口分别将true和false赋给一个临时变量t。

例如，赋值语句x=a

图6.42：通过计算一个临时变量的值来翻译一个布尔类型的赋值语句

6.6.7 6.6节的练习

练习6.6.1: 在图6.36的语法制导定义中添加处理下列控制流结构的规则： a) 一个repeat语句，repeat S while B。 b) 一个for-循环语句，for (S1; B; S2) S3。

练习6.6.2: 现代计算机试图在同一时刻执行多条指令，这也包括各种分支指令。因此，当计算机投机性地沿着某个分支执行，但实际上控制流却进入另一分支时（所有的投机工作将被抛弃），付出的代价是很大的。因此我们希望尽可能地减少分支数量。请注意图6.35(c)中while-loop语句的实现中，每个迭代有两个分支：一个是从条件B进入到循环体中，另一个跳转回B的代码。基于尽量减少分支的考虑，我们通常更倾向于将while(B) S当作 if (B) {repeat S until !(B)}来实现。给出这种翻译方法的代码布局，并修改图6.36中while-循环语句的规则。

！练习6.6.3：假设C中存在一个异或操作（当且仅当两个分量恰有一个为真时，表达式为