第六章 中间代码生成

S→if (B) M1 S1 N else M2 S2

我们将对应于B为真的跳转指令回填为M1.instr，也就是S1的代码的开始位置。类似地，我们将回填那些对应于B为假的跳转指令，使它们跳转到S2的代码的开始位置。S.nextlist包含了所有从S1和S2中跳出的指令，同时也包括由N产生的跳转指令。（变量temp是仅用于合并列表的临时变量。）

语义动作（8）和（9）处理语句序列。在

L→L1 M S

中，按照执行顺序紧跟在L1的代码之后的是S的开始指令。因此，列表L1.nextlist被回填为S代码的开始位置，该位置由M.instr给出。在L→S中，L.nextlist和S.nextlist相同。

请注意，除了语义规则（3）和（7），这些语义规则中的任何地方都没有产生新的指令。其它所有的代码都是由赋值语句和表达式相关的语义动作产生的。我们根据控制流进行了正确的回填，因此赋值语句和布尔表达式的求值过程被正确地连接了起来。

6.7.4 Break-, Continue-和Goto-语句

用于改变程序控制流的最基本的程序设计语言结构是goto-语句。在C中，一个像goto L这样的语句将控制流转到标号为L的指令——在相应作用域内必须恰好存在一条标号为L的语句。在实现goto语句时，可以为每个标号维护一个未完成指令的列表，然后在知道这些指令的目标之后进行回填。

Java废除了goto语句。但是Java允许一种规范的跳转语句，即break-语句。它将控制流跳离外围的语言结构。Java中还允许使用continue-语句。这个语句的作用是触发外围循环的下一轮迭代。下面的代码摘自一个语法分析器。它演示了简单的break-和continue-语句。

1） for( ; ; readch( ) ) { 2） if(peek == ? ? || peek == ?\\t?) continue; 3） else if (peek == ?\\n?) line = line + 1; 4） else break; 5） }

控制流会从第4行中的break-语句跳出到外围循环之后的下一个语句。控制流也会从第2行中的continue-语句跳转到计算reach( )的代码，然后再转到第2行中的if语句。

如果S表示外围的语言结构，那么一条break语句就是跳转到S代码之后第一条指令的跳转指令。我们可以按照下面的步骤为break生成代码（1）跟踪外围语句S，（2）为该break语句生成未完成的跳转指令，（3）将这些指令放到S.nextlist中，其中nextlist就是6.7.3节中讨论的列表。

在一个通过两趟扫描构建语法树的比编译器前端中，S.nextlist可以被实现为对应于语句S的结点的一个域。我们可以在符号表中将一个特殊的标志符break映射为表示外围语句S的结点，以此来跟踪S。这种方法同样可以处理java中带标号的break语句，因为符号表同样可以被用来将这个标号映射为对应于外围语句的语法树结点。

如果不使用符号表来访问S的结点，我们还可以在符号表中设置一个指向S.nextlist的指针。现在当碰到一个break语句时，我们生成一个未完成的指令，并通过符号表查找到nextlist，然后把将这个跳转指令加入到这个列表中。这个nextlist将按照6.7.3节中讨论的方法进行回填。

Continue-语句的处理方法和处理break-语句的方法类似。两者之间的主要不同之处在于生成的跳转指令的目标不同。

6.7.5 6.7节的练习

练习6.7.1: 使用图6.43中的翻译方案翻译下列各个表达式。给出每个子表达式的truelist和falselist。你可以假设第一条被生成的指令的地址是100。 a) a==b && (c==d || e==f) b) (a==b || c==d) || e==f

c) (a==b && c==d) && e==f

练习6.7.2：图6.47（a）中是一个程序的摘要。6.47(b)概述了使用图6.46中的回填翻译方案生成的三地址代码的结构。这里，i1到i8是每个code区域的第一条被生成指令的标号。当我们实现这个翻译时，我们为每个布尔表达式E维护了两个列表，表中是E的代码中的一些位置。我们分别用E.true和E.false来表示这两个列表。对于E.true列表中的那些指令位置，我们最终要加入当E为真时控制流应该到达的语句的标号。E.false是类似的存放特定位置号的列表，我们要在这些位置上加入当发现E为假时控制流应该到达的标号。同时，我们还为语句S维护了一个位置的列表。我们必须在这些位置上加入当S执行完毕之后控制流应该到达的标号。请给出最终将代替下列各个列表中的位置的值（即i1到i8中的某个标号）。

(a) E3.false (b)S2.next (c)E4.false (d)S1.next (e)E2.true

图6.47：练习6.7.2的程序的控制流结构

练习6.7.3：当使用图6.46中的翻译方案对图6.47进行翻译时，我们为每条语句创建S.next列表。一开始是赋值语句S1，S2，S3，然后逐步处理越来越大的if-语句，if-else-语句，while-语句和语句块。在图6.47中有5个这种类型的结构语句： S4：while(E3) S1。 S5：if(E4) S2。

S6：包含S5和S3的语句块。 S7：语句if S4 else S6。 S8：整个程序

对于每些结构语句，都有一个规则使我们可以用其它的Sj.next列表以及程序中的表达式的列表Ek.true和Ek.false构造出Si.next。给出计算下列next列表的规则 (a)S4.next (b)S5.next (c)S6.next (d)S7.next (e)S8.next

6.8 Switch-语句

很多语言可以使用“switch”或“case”语句。我们的swtich-语句的语法如图6.48所示。语句中包含一个待求值的选择表达式E，后面是该表达式可能取的n个常量值V1, V2, …, Vn。语句中也可能包含一个缺省“值”，当其它值都不和选择表达式的值匹配时，这个缺省值就总是匹配。

图6.48：Switch语句的语法 6.8.1 Switch语句的翻译

一个Switch语句的预期翻译结果是完成如下工作的代码： 1. 计算表达式E的值。

2. 在case列表中寻找与表达式值相同的值Vj。回顾一下，当在case列表中明确列出的值

都不和表达式匹配时，缺省值就和表达式匹配。 3. 假设和找到的值关联的语句是Sj，执行这个语句。

步骤（2）是一个n路分支，它可以采取多种方法实现。如果case的数目较少，比如不多于10个，那么使用一个条件跳转指令序列来实现就是很自然的事。每一个条件跳转指令都测试一个常量值，并跳转到这个值对应的语句的代码。

实现这个条件转移指令序列的一个简洁的方法是创建一个对照关系表。表中的每一个关系都包含了一个常量值和相应语句代码的标号。在运行时刻，表达式自身的值以及缺省语句的标号被放在对照表的末端。编译器生成一个简单循环，把表达式的值和表中的每个值进行比较。我们已经保证了当没有找到其它匹配时，最后一个条目（缺省值条目）一定会匹配。

如果值的个数超过10个或更多，更高效的方式是为这些值构造一个哈希表。这个表以各个分支语句的标号作为条目。如果没有找到对应于swtich表达式的值的条目，就会有一条跳转指令转到缺省语句。

还有一种常见的特殊情况，它的实现可以比n路分支更加高效。如果表达式的值都位于某个较小的范围内，比如从min到max，并且不同常量值的总数大约等于max-min。那么我们可以构造一个包含max-min个“桶”的数组，其中桶j-min包含了对应于值j的语句的标号；任何没有被填入对应标号的“桶”中包含了缺省标号。

执行switch语句时，首先计算表达式并获得值j；检查它是否在min到max的范围之内，如是则间接跳转到偏移量为j-min的条目中的标号。例如，如果表达式的类型是字符型，我们可以创建一个包含128个条目（根据具体的字符集，条目个数可有不同）的表，并且不进行范围检查直接进行控制流跳转。

6.8.2 Switch语句的语法制导翻译

图6.49中的中间代码是图6.48中的switch语句的一个近似翻译结果。所有的测试都出现在代码的最末端，因此一个简单的代码生成器就可以识别出多路分支，并使用本节开始时介绍的多种实现方法中最合适的实现方法，生成高效的代码。

图6.49：一个Switch语句的翻译结果 图6.50中显示的是一个更直接的代码序列。它要求编译器进行更加深入的分析，才能找到最高效的实现。值得注意的是，在一趟式编译器中，将分支语句放在开始的位置会不方便，因为编译器此时还没有碰到各个语句Si，无法生成转向各个语句的代码。

为了翻译成如图6.49所示的形式，当我们看到关键字switch的时候，我们生成两个新标号test和next以及一个临时变量t。然后当我们分析表达式E的时候，我们生成的代码将计算E值并将其保存到t。处理完E之后，产生跳转指令goto test。

然后，当我们看见各个case关键字时，我们创建一个新的标号Li，并将其加入符号表。我们将在一个仅用于存放case分支的队列中放入一个值-标号对。这个值-标号对由常量值Vi和Li（或者是指向符号表中Li的条目的指针）组成。我们逐个处理语句case Vi: Si，生成附加于Si的代码上的标号Li。最后生成跳转指令goto next。

图6.50：一个switch语句的另一种翻译 当编译器到达switch语句的末端时，我们已经可以生成n路分支的代码了。读取值-标号对的队列，我们就可以生成形如图6.51所示的三地址代码序列。其中t是一个保存选择表达式E的值的临时变量，Ln为缺省语句的标号。

图6.51：用来翻译switch语句的case三地址代码指令 指令case t Vi Li和图6.49中的if t=Vi goto Li含义相同。但是case指令更加容易被最终的代码生成器探测到，有可能对这些指令进行某种特殊处理。在代码生成阶段，根据分支的个数以及这些值是否在一个狭小的范围内，这些case语句的序列可以被翻译成最高效的n路分支。

6.8.3 6.8节的练习

！练习6.8.1：为将switch语句翻译成一个如图6.51所示的case语句序列，翻译器需要在处理switch的源码时创建一个由值-标号对组成的列表。我们可以使用一个附加的翻译方案来做到这一点，这个方案只搜集这些值-标号对。给出一个语法制导定义的概要描述。该SDD可以生成值-标号对照表，并且同时还为各个语句Si生成代码。这里的Si是各个case对应的动作。