China-pub.com 下载 第8章 代码生成 本章要点 ·中间代码和用于代码生成的数据结构 ·商用编译器中的代码生成：两个案例研究 ·基本的代码生成技术 ·TM:简单的目标机器 ·数据结构引用的代码生成 ,TNY语言的代码生成器 ·控制语句和逻辑表达式的代码生成 ·代码优化技术考察 ·过程和函数调用的代码生成 ,TNY代码生成器的简单优化 在这一章中，我们着手编译器的最后工作 用来生成日标机器的可执行代码，这个可执 行代码是源代码语义的忠实体现。代码生成是编译器最复杂的阶段，因为它不仅依赖于源语言 的特征，而且还依赖于目标结构、运行时环境的结构和运行在目标机器的操作系统的细节信息 通过收集源程序进一步的信息，并通过定制生成代码以便利用目标机器，如寄存器、寻址模式、 管道和高速缓存的特殊性质，代码生成通常也涉及到了一些优化或改善的尝试。 由于代码生成较复杂，所以编译器一般将这一阶段分成几个涉及不同中间数据结构的步骤 其中包括了某种称做中间代码(itermediate code)的抽象代码。编译器也可能没有生成真正的可 执行代码，而是生成了某种形式的汇编代码，这必须由汇编器、链接器和装入器进行进一步处 理。汇编器、链接器和装入器可由操作系统提供或由编译器自带。在这一章中，我们仅仅集中 关注于中间代码和汇编代码的生成，这两者之间有很多共同特性。我们不考虑汇编代码到可执 行代码的更进一步的处理，汇编语言或系统的编程文本可以更充分地处理它。 本章的第1节考虑中间代码的两种普遍形式，三地址码和P代码，并且讨论它们的一些属 性。第2节描述生成中间代码或汇编代码的基本算法。接下来的章节讨论针对不同语言特性的 代码生成技术，这包括了表达式、赋值语句、控制语句（如if语句，while语句）以及过程和函 数调用。 之后的一节将应用在前面章节中学到的技术开发TY语言的一个汇编代码生成器。由于 在这种细节水平上的代码生成需要实际的目标机器，因此首先讨论一个目标结构和机器模拟器 TM。附录C提供了源代码清单。然后，我们再描述完整的TNY语言的代码生成器。最后给出 ,个关于标准代码的改善、优化技术的简介，同时描述了怎样将一些简单的技术融入到TNY 代码生成器之中。 8.1中间代码和用于代码生成的数据结构 在翻译期间，中间表示(intermediate representation)或IR代表了源程序的数据结构。迄今为 止，本文使用了抽象语法树作为主要的R。除R外，翻译期间的主要数据结构是符号表，这在 第6章中已学过了。 虽然抽象语法树是源代码完美充分的表述，即使对于代码生成也不过这样（这一点我们将 在后面的章节中看到)，但是它与目标代码极不相像，在控制流构造的描述上尤为如此。在控 制流构造上，目标代码（如机器代码或汇编代码）使用转移语句而不是if和wh11e语句。因此
下载 第8章 代 码 生 成 本章要点 • 中间代码和用于代码生成的数据结构 • 商用编译器中的代码生成：两个案例研究 • 基本的代码生成技术 • TM：简单的目标机器 • 数据结构引用的代码生成 • TINY语言的代码生成器 • 控制语句和逻辑表达式的代码生成 • 代码优化技术考察 • 过程和函数调用的代码生成 • TINY代码生成器的简单优化 在这一章中，我们着手编译器的最后工作——用来生成目标机器的可执行代码，这个可执 行代码是源代码语义的忠实体现。代码生成是编译器最复杂的阶段，因为它不仅依赖于源语言 的特征，而且还依赖于目标结构、运行时环境的结构和运行在目标机器的操作系统的细节信息。 通过收集源程序进一步的信息，并通过定制生成代码以便利用目标机器，如寄存器、寻址模式、 管道和高速缓存的特殊性质，代码生成通常也涉及到了一些优化或改善的尝试。 由于代码生成较复杂，所以编译器一般将这一阶段分成几个涉及不同中间数据结构的步骤， 其中包括了某种称做中间代码 (itermediate code)的抽象代码。编译器也可能没有生成真正的可 执行代码，而是生成了某种形式的汇编代码，这必须由汇编器、链接器和装入器进行进一步处 理。汇编器、链接器和装入器可由操作系统提供或由编译器自带。在这一章中，我们仅仅集中 关注于中间代码和汇编代码的生成，这两者之间有很多共同特性。我们不考虑汇编代码到可执 行代码的更进一步的处理，汇编语言或系统的编程文本可以更充分地处理它。 本章的第1节考虑中间代码的两种普遍形式，三地址码和 P -代码，并且讨论它们的一些属 性。第2节描述生成中间代码或汇编代码的基本算法。接下来的章节讨论针对不同语言特性的 代码生成技术，这包括了表达式、赋值语句、控制语句 (如i f语句，w h i l e语句)以及过程和函 数调用。 之后的一节将应用在前面章节中学到的技术开发 T I N Y语言的一个汇编代码生成器。由于 在这种细节水平上的代码生成需要实际的目标机器，因此首先讨论一个目标结构和机器模拟器 T M。附录C提供了源代码清单。然后，我们再描述完整的 T I N Y语言的代码生成器。最后给出 一个关于标准代码的改善、优化技术的简介，同时描述了怎样将一些简单的技术融入到 T I N Y 代码生成器之中。 8.1 中间代码和用于代码生成的数据结构 在翻译期间，中间表示(intermediate representation)或I R代表了源程序的数据结构。迄今为 止，本文使用了抽象语法树作为主要的I R。除I R外，翻译期间的主要数据结构是符号表，这在 第6章中已学过了。 虽然抽象语法树是源代码完美充分的表述，即使对于代码生成也不过这样 (这一点我们将 在后面的章节中看到 )，但是它与目标代码极不相像，在控制流构造的描述上尤为如此。在控 制流构造上，目标代码 (如机器代码或汇编代码 )使用转移语句而不是 i f和w h i l e语句。因此
306 翁译原理及实践 China-pub.Co 下载 编译器编写者可能希望从语法树生成一个更接近目标代码的中间表示形式，或者用这样一个中 间表示代替语法树，然后再从这个新的中间表示生成目标代码。这种类似目标代码的中间表示 称为中间代码(intermediate code)。 中间代码能采用很多形式，几平有多少种编译器就有多少种中间代码形式。然而所有中间 代码都代表了语法树的某种线性化(linearization)形式，也就是说，语法树用顺序形式表示。中 间代码可以是高水平的，它几乎和语法树一样可以抽象地表示各种操作。它或者还可以非常接 近目标代码。它可以使用或不使用目标机器和运行时环境的细节信息，如数据类型的尺寸、变 量的地址和寄存器。它可以混合或不混合符号表中包括的信息，如作用域、嵌套层数和变量的 偏移量。假如它混合了符号表中包括的信息，目标代码的生成基于中间代码就足够了：否则， 编译器必须保留符号表 当编译器的目标是产生非常高效的代码时，中间代码是极其有用的。如要产生高效的代码 就需要相当数量的目标代码属性分析，使用中间代码能使这变得容易。特别地，虽然从语法 树中直接得到混合细节分析信息的附加数据结构不是不可能的，但它能更容易地从中间代码 中得到。 中间代码在使编译器更容易重定向上也是有用的：假如中间代码与目标机器相对独立，那 么要为不同目标机器生成代码就仅需重写从中间代码到目标代码的翻译器。这比重写整个编译 器要容易。 在本节中我们将学习两个中间代码的普遍形式：三地址码(hrce-addresscode)和P代码(P code)。这两种中间代码以许多不同的形式出现，我们的研究将仅集中在普遍特性上，而不是 代表了某一个版本的细节化描述。这种描述能在本章最后“注意与参考”节所描述的文献中 找到。 8.1.1三地址码 三地址码最基本的用法说明被设计成表示算术表达式的求值，形式如下： x y op z 这个用法说明表示了对y和z的值的应用操作符p,并将值赋给x。这里的p可以是算术运算符， 如+或，也可以是其他能操作于y、z值的操作符。 三地址码这个名字来自于这个用法说明的形式，因为x、y、z通常代表了内存中的3个地 址。但是要注意，x的地址的使用不同于y、z的地址的使用。y、z(x不能)可以代表常量或没 有运行时地址的字面常量。 为了看清这种形式的三地址码如何能表示表达式的计算，考虑下边的算术表达式 2*a+(b-3) 语法树如下： 相应的三地址码如下 七1=2★a
编译器编写者可能希望从语法树生成一个更接近目标代码的中间表示形式，或者用这样一个中 间表示代替语法树，然后再从这个新的中间表示生成目标代码。这种类似目标代码的中间表示 称为中间代码(intermediate code)。 中间代码能采用很多形式，几乎有多少种编译器就有多少种中间代码形式。然而所有中间 代码都代表了语法树的某种线性化 ( l i n e a r i z a t i o n )形式，也就是说，语法树用顺序形式表示。中 间代码可以是高水平的，它几乎和语法树一样可以抽象地表示各种操作。它或者还可以非常接 近目标代码。它可以使用或不使用目标机器和运行时环境的细节信息，如数据类型的尺寸、变 量的地址和寄存器。它可以混合或不混合符号表中包括的信息，如作用域、嵌套层数和变量的 偏移量。假如它混合了符号表中包括的信息，目标代码的生成基于中间代码就足够了；否则， 编译器必须保留符号表。 当编译器的目标是产生非常高效的代码时，中间代码是极其有用的。如要产生高效的代码 就需要相当数量的目标代码属性分析，使用中间代码能使这变得容易。特别地，虽然从语法 树中直接得到混合细节分析信息的附加数据结构不是不可能的，但它能更容易地从中间代码 中得到。 中间代码在使编译器更容易重定向上也是有用的：假如中间代码与目标机器相对独立，那 么要为不同目标机器生成代码就仅需重写从中间代码到目标代码的翻译器。这比重写整个编译 器要容易。 在本节中我们将学习两个中间代码的普遍形式：三地址码 (three-address code)和P -代码( P - c o d e )。这两种中间代码以许多不同的形式出现，我们的研究将仅集中在普遍特性上，而不是 代表了某一个版本的细节化描述。这种描述能在本章最后“注意与参考”节所描述的文献中 找到。 8.1.1 三地址码 三地址码最基本的用法说明被设计成表示算术表达式的求值，形式如下： x = y o p z 这个用法说明表示了对y和z的值的应用操作符o p，并将值赋给x。这里的o p可以是算术运算符， 如+或-，也可以是其他能操作于y、z值的操作符。 三地址码这个名字来自于这个用法说明的形式，因为 x、y、z通常代表了内存中的 3个地 址。但是要注意，x的地址的使用不同于 y、z的地址的使用。y、z(x不能)可以代表常量或没 有运行时地址的字面常量。 为了看清这种形式的三地址码如何能表示表达式的计算，考虑下边的算术表达式 2*a + ( b-3 ) 语法树如下： 相应的三地址码如下 t1 = 2 * a 3 0 6 编译原理及实践 下载
China-pub.com 第8章代码生成 307 下载 t2=b-3 t3=t1+t2 三地址码要求编译器产生临时变量名，在这个例子中的是t1、t2和3。这些临时变量对应于 语法树的内部节点而表示计算值，在这个例子中用临时变量七3表示根节点值⊙。这里并没有说 明如何在内存中分配这些临时变量：它们通常将被分到寄存器中，但也有可能保存在活动记录 里面（参见第7章“临时栈”的讨论）。 三地址码仅代表了从左至右的语法树线性化，因为首先列出了相对于根的左子树的求值的 代码，编译器在某种情况下希望用另一种顺序也是有可能的。我们注意到对于三地址码来说， 是有可能使用另一顺序，即（临时变量有不同的意思）： t1=b-3 t2=2*a t3=t2+t1 很明显，上面所示的这种三地址码形式对于表示所有语言，即使是最小的程序语言的特性也是 不够的。例如一元操作符（如负号）就需要一个三地址码的变种（包含两个地址）如： t2=-t1 为适应标准程序语言的使用结构，必须为每个结构改变三地址码的形式。如果语言中含有 不常见到的特性，那么就必须为表达的这种特性发明另一种三地址码形式。这就是三地址码之 所以没有标准形式的原因（正如语法树没有标准形式一样）。 在这一章余下的章节中我们将逐个处理一些程序语言共有的结构，并显示怎样将这些结构 翻译成三地址码。为了知道其结果，我们给出一个用TNY语言编写的完整示例。 请考虑来自第1章1.7节的TNY例子，该例计算了一个整数的阶乘，我们把它重新放在程序 清单8-1中。 程序清单81TINY程序示例 in TINY language computes factorial fact 1; x:=x-1 unt10 程序清单8-2是这个例子的三地址码。这个代码包含了许多三地址码的不同形式。首先，内 置的输入和输出操作符read和write已被直接翻译成一地址指令。其次，这里有一个条件 转移指令1￡￡a1se,它通常被用来翻译i语句和循环语句，它包含两个地址：被检测的条 诸如1、2的名字仅仅意味着是这种代码通常类型的代表实际上，如果像这里一样使用源代码名字的话 三地址码中的临时变量名必须区别于在实际的源代码中所用的名字
t2 = b - 3 t3 = t1 + t2 三地址码要求编译器产生临时变量名，在这个例子中的是 t 1、t 2和t 3。这些临时变量对应于 语法树的内部节点而表示计算值，在这个例子中用临时变量 t 3表示根节点值 。这里并没有说 明如何在内存中分配这些临时变量；它们通常将被分到寄存器中，但也有可能保存在活动记录 里面(参见第7章“临时栈”的讨论)。 三地址码仅代表了从左至右的语法树线性化，因为首先列出了相对于根的左子树的求值的 代码，编译器在某种情况下希望用另一种顺序也是有可能的。我们注意到对于三地址码来说， 是有可能使用另一顺序，即(临时变量有不同的意思)： t1 = b-3 t2 = 2*a t3 = t2+t1 很明显，上面所示的这种三地址码形式对于表示所有语言，即使是最小的程序语言的特性也是 不够的。例如一元操作符(如负号)就需要一个三地址码的变种(包含两个地址)如： t2 = -t1 为适应标准程序语言的使用结构，必须为每个结构改变三地址码的形式。如果语言中含有 不常见到的特性，那么就必须为表达的这种特性发明另一种三地址码形式。这就是三地址码之 所以没有标准形式的原因(正如语法树没有标准形式一样)。 在这一章余下的章节中我们将逐个处理一些程序语言共有的结构，并显示怎样将这些结构 翻译成三地址码。为了知道其结果，我们给出一个用 T I N Y语言编写的完整示例。 请考虑来自第1章1 . 7节的T I N Y例子，该例计算了一个整数的阶乘，我们把它重新放在程序 清单8 - 1中。 程序清单8-1 TINY程序示例 程序清单 8 - 2是这个例子的三地址码。这个代码包含了许多三地址码的不同形式。首先，内 置的输入和输出操作符 r e a d和w r i t e已被直接翻译成一地址指令。其次，这里有一个条件 转移指令i f _ f a l s e，它通常被用来翻译 i f语句和循环语句，它包含两个地址：被检测的条 第 8章 代 码 生 成 3 0 7 下载 诸如t 1、t 2的名字仅仅意味着是这种代码通常类型的代表。实际上，如果像这里一样使用源代码名字的话， 三地址码中的临时变量名必须区别于在实际的源代码中所用的名字
308 翁译原理及实践 China-pub.com 下载 件值和转移的代码地址。一地址的1abe1指令指示了这个转移地址的位置。有了用以实现三 地址码的数据结构，这些1abel指令可能并不是必需的。halt指令（无地址）用来标志代码的 结束。 程序清单8-2程序清单8-1中TNY程序的三地址码 read x t1=g>0 ig_false ti goto L1 02 t2▣fact·x actt2 t4▣x0 if_false t4 goto L2 halt 最后，我们注意到原代码中的赋值语句导致了如下形式的copy指令 x=y 例如，例程中语句 fact:mfact'x; 翻译成2个三地址码 即使三地址码指令也是足够了，这种情况的技术原因将在8.2节中讲述。 8.1.2用于实现三地址码的数据结构 三地址码通常不被实现成我们所写的文本形式（虽然这是可能的），相反是将其实现为包含 几个域的记录结构。并将整个三地址指令序列实现成链表或数组，它能被保存在内存中并在需 要时可以从临时文件中读写。 最通常的实现是将三地址码按其所显示的内容实现。这意味着有4个域是必需的：1个操作 符和3个地址。对于那些少于3个地址的指令，将一个或更多的地域置成null或“empy”,具体 选择哪个域取决于实现。必须有4个域的三地址码表示叫做四元式(quadruple)。程序清单8-2的 三地址码的四元式在程序清单83中给出。这里我们用数学中的元组概念书写四元式。 程序清单8-3程序清单8-2中的三地址码的四元式实现 (rd,x,--】 (e (amn,1,fact,_)
件值和转移的代码地址。一地址的 l a b e l指令指示了这个转移地址的位置。有了用以实现三 地址码的数据结构，这些 l a b e l指令可能并不是必需的。 h a l t指令(无地址)用来标志代码的 结束。 程序清单8-2 程序清单8 - 1中T I N Y程序的三地址码 最后，我们注意到原代码中的赋值语句导致了如下形式的 c o p y指令 x = y 例如，例程中语句 f a c t : = f a c t * x ; 翻译成2个三地址码 t2=tact *x f a c t = t 2 即使三地址码指令也是足够了，这种情况的技术原因将在 8 . 2节中讲述。 8.1.2 用于实现三地址码的数据结构 三地址码通常不被实现成我们所写的文本形式 (虽然这是可能的)，相反是将其实现为包含 几个域的记录结构。并将整个三地址指令序列实现成链表或数组，它能被保存在内存中并在需 要时可以从临时文件中读写。 最通常的实现是将三地址码按其所显示的内容实现。这意味着有 4个域是必需的：1个操作 符和3个地址。对于那些少于3个地址的指令，将一个或更多的地域置成 n u l l或“e m p t y”，具体 选择哪个域取决于实现。必须有 4个域的三地址码表示叫做四元式 ( q u a d r u p l e )。程序清单8 - 2的 三地址码的四元式在程序清单8 - 3中给出。这里我们用数学中的元组概念书写四元式。 程序清单8-3 程序清单8 - 2中的三地址码的四元式实现 3 0 8 编译原理及实践 下载
China-pub.com 第8章代码生成 309 下载 《aat2,g (amn,t3,x,_) (1ab,1,-,) (ha1t,-,-,-) 程序清单84程序清单8-3中四元式的数据结构的C定义 typedef snum (rd,gt,if_f,aan,lab,mul, d 【Addrkind kind: union ）contentsr 】Addx0ss: typedef struct apiai.aha.aa, ouad: 程序清单84所示的是程序清单8-3中的四元式的C类型定义，在这些定义中，允许地址为 整数、常量或字符串（代表临时变量或一般变量的名字）。由于使用了名字，就必须将其加入到 符号表中，以供进一步处理时查询。另一种替代方法是在四元式中使用指向符号表入口的指针 这将避免额外的查询。这对可嵌套的语言来说有特别的好处，因为这时候的名字查询还需要更 多的嵌套层信息，如果常量也输入符号表，那么将不再需要地址数据类型中的uion 三地址码另一个不同的实现是用自己的指令来代表临时变量，这样地址域从3个减少到了 两个。因此在三地址指令中包含3个地址而日标地址总是一个临时变量⊙。如此的三地址码实现 称为三元式(ple)。它要求：或是通过数组的索引号或是通过链表指针，每个三地址指令都是 可引用的，如程序清单85是程序清单82的三地址码作为三元式实现的抽象表达。在那幅图中， 我们使用了一个数字系统，它对应于代表三元式的数组索引。在三元式内，把三元式引用用圆 括号括起，以同常量相区别。程序清单8-5取消了1abe1指令，代之以三元式引用。 程序清单8-5程序清单8-2中三地址码的三元式表示 (0) (rd,x) (1) (gt,0) (5) (asn,(4),fact) 7 an,(6),x) 日这不是三地址码的固有属性，但能通过实现来保证。例如，程序清单82的代码就是这样的（程序消单83也是）
程序清单8-4 程序清单8 - 3中四元式的数据结构的C定义 程序清单8 - 4所示的是程序清单8 - 3中的四元式的C类型定义，在这些定义中，允许地址为 整数、常量或字符串(代表临时变量或一般变量的名字 )。由于使用了名字，就必须将其加入到 符号表中，以供进一步处理时查询。另一种替代方法是在四元式中使用指向符号表入口的指针， 这将避免额外的查询。这对可嵌套的语言来说有特别的好处，因为这时候的名字查询还需要更 多的嵌套层信息，如果常量也输入符号表，那么将不再需要地址数据类型中的 u n i o n。 三地址码另一个不同的实现是用自己的指令来代表临时变量，这样地址域从 3个减少到了 两个。因此在三地址指令中包含3个地址而目标地址总是一个临时变量 。如此的三地址码实现 称为三元式( t r i p l e )。它要求：或是通过数组的索引号或是通过链表指针，每个三地址指令都是 可引用的，如程序清单8 - 5是程序清单8 - 2的三地址码作为三元式实现的抽象表达。在那幅图中， 我们使用了一个数字系统，它对应于代表三元式的数组索引。在三元式内，把三元式引用用圆 括号括起，以同常量相区别。程序清单8 - 5取消了l a b e l指令，代之以三元式引用。 程序清单8-5 程序清单8 - 2中三地址码的三元式表示 第 8章 代 码 生 成 3 0 9 下载 这不是三地址码的固有属性，但能通过实现来保证。例如，程序清单8 - 2的代码就是这样的(程序清单8 - 3也是)
310 翁译原理及实践 China-pub.com 载 (8) (a,x,0) (住E_￡，(8)，(4) (haissact,-) 三元式是代表三地址码的有效方法，空间数量减少了且编译器不需要产生临时变量名：然 而，三元式也有一个不利因素：用数组索引代表三元式使得三元式位置的移动变得很困难，而 如用链表的话就不存在这个问题。三元式和对三元式的C代码定义的问题仍处于实践价段。 8.1.3P-代码 在70年代和80年代早期，P代码作为由许多Pascal编译器产生的标准目标汇编代码被设计 成称作P-机器(P-machine)的假想栈机器的实际代码。P-机器在不同的平台上由不同的解释器实 现。这个思想使得pascal编译器变得容易移植，只需对新平台重写P.机器解释器即可。P代码 已被证明是一个非常有用的中间代码，它的各种扩展和修改版在许多自然代码的编译器中得到 了使用，其中大多数都是针对类Pascali语言的。 由于将P代码设计成直接可执行的，所以它包含了对特殊环境的明确描述、数据尺寸，还 有P机器大量的特有信息，如果要理解P代码程序，就必须提供上述信息。为避开细节而恰当 地说明问题，在这里只描述P代码的一个简化的抽象版本。各种不同版本的实际P代码的描述 能在本章最后列出的大量参考书中找到。 从我们的目的出发，P机器包括一个代码存储器、一个未指定的存放命名变量的数据存储 一个存放临时数据的栈，还有一些保持栈和支持执行的寄存器。作为P代码的第1个例子， 考虑如下表达式，这个表达式在81.1节中已用过，它的语法树在811节： 2*a+(b-3) 这个表达式的P代码版本如下： 1e2 。1 ad constant 3 er aubstraction ad ；nteger addition 这些指令被看作代表如下的P-机器操作：1dc2首先将值2压入临时栈，然后，1oda将变量a 的值压入栈。指令mP1将这两个值从栈中弹出，使之相乘（按弹出的相反顺序），再将结果压入 栈。接下来两个指令(1。a聊1dc3将b的值和常量3压入栈（现在栈中有3个值），随后，sb: 指令弹出栈顶的两个值，用第1个值去减第2个值，再把结果压入栈中，最后a1指令弹出余下 的两个值并使之相加，再将结果压入栈。代码结束时，栈中只有一个值，它代表了这次运算的 结果。 作为第2个例子，考虑威值语句： x=y+1 对应于如下的P代码指令： load address of x lod y load value of y
三元式是代表三地址码的有效方法，空间数量减少了且编译器不需要产生临时变量名；然 而，三元式也有一个不利因素：用数组索引代表三元式使得三元式位置的移动变得很困难，而 如用链表的话就不存在这个问题。三元式和对三元式的 C代码定义的问题仍处于实践价段。 8.1.3 P- 代码 在7 0年代和8 0年代早期，P -代码作为由许多P a s c a l编译器产生的标准目标汇编代码被设计 成称作P -机器( P - m a c h i n e )的假想栈机器的实际代码。P -机器在不同的平台上由不同的解释器实 现。这个思想使得p a s c a l编译器变得容易移植，只需对新平台重写 P -机器解释器即可。P -代码 已被证明是一个非常有用的中间代码，它的各种扩展和修改版在许多自然代码的编译器中得到 了使用，其中大多数都是针对类P a s c a l语言的。 由于将P -代码设计成直接可执行的，所以它包含了对特殊环境的明确描述、数据尺寸，还 有P -机器大量的特有信息，如果要理解 P -代码程序，就必须提供上述信息。为避开细节而恰当 地说明问题，在这里只描述 P -代码的一个简化的抽象版本。各种不同版本的实际 P -代码的描述 能在本章最后列出的大量参考书中找到。 从我们的目的出发，P -机器包括一个代码存储器、一个未指定的存放命名变量的数据存储 器、一个存放临时数据的栈，还有一些保持栈和支持执行的寄存器。作为 P -代码的第1个例子， 考虑如下表达式，这个表达式在8 . 1 . 1节中已用过，它的语法树在8 . 1 . 1节： 2 * a + ( b - 3 ) 这个表达式的P -代码版本如下： ldc 2 ; load constant 2 lod a ; load value of variable a m p i ; integer multiplication lod b ; load value of variable b ldc 3 ; load constant 3 s b i ; integer substraction a d i ; integer addition 这些指令被看作代表如下的P -机器操作：ldc 2首先将值2压入临时栈，然后，lod a将变量a 的值压入栈。指令m p i将这两个值从栈中弹出，使之相乘 (按弹出的相反顺序)，再将结果压入 栈。接下来两个指令(loa b和ldc 3)将b的值和常量3压入栈(现在栈中有3个值)，随后，s b i 指令弹出栈顶的两个值，用第 1个值去减第2个值，再把结果压入栈中，最后 a d i指令弹出余下 的两个值并使之相加，再将结果压入栈。代码结束时，栈中只有一个值，它代表了这次运算的 结果。 作为第2个例子，考虑赋值语句： x := y + 1 对应于如下的P -代码指令： lda x ; load address of x lod y ; load value of y 3 1 0 编译原理及实践 下载
China-pub.com 第8章代码生成 311 下载 load constant 1 adi ：add ato i store top to address below top s pop both 注意，这段代码首先计算x的地址，然后将表达式的值赋给x,最后执行so命令，这个命令需 要临时栈顶上的两个值：一个是要被存储的值，在它下面的那个是值所要存入的地址。st。指 令也弹出两个值（在这例子中使栈变空）。在x:=y+1中，左边的x的用处和右边的y的用处不 样，相应的P.代码用装入地址(1da)和装入值(1od)作出区别。 作为本节中最后的一个P-代码例子，我们对程序清单8-1中的TNY程序给出P代码的翻译， 如程序清单8-6所示， 其中每条操作都有注释。 程序清单8-6程序清单81中TINY程序的P码指令 E4i on top of atack (s pop it) value of x grt and co mpare top two values push Boolean result load constant 1 sto secon lab L2 1d fact load address of fact 1o8 ve store top to address of second pop ad value subtract e(as before】 nt 0 equ equality fact wri of a stp 程序清单8-6中的P-代码包含了几个新的P-代码指令。首先，无参的rdi和wri指令实现了 TNY中的整型的read和writei语句。rdiP.代码指令要求要读的那个变量地址应位于栈顶， 这个地址作为指令的一部分被弹出。wx1指令要求要写的值地址位于栈顶，这个值作为指令的 一部分弹出。程序清单8-6中出现的另一些新指令是1ab指令，它定义了标签名字的位置：EjP 指令(“false jump”)需要在栈顶有一个布尔值：sbi指令（整数减法）的操作类似于其他算术指 令：gxt指令（大于）和etu(等于)指令需要两个整型值位于栈顶（要被弹出）然后压入他们的布尔
ldc 1 ; load constant 1 a d i ; add s t o ; store top to address ; below top & pop both 注意，这段代码首先计算x的地址，然后将表达式的值赋给x，最后执行s t o命令，这个命令需 要临时栈顶上的两个值：一个是要被存储的值，在它下面的那个是值所要存入的地址。 s t o指 令也弹出两个值(在这例子中使栈变空)。在x : = y + 1中，左边的x的用处和右边的y的用处不一 样，相应的P -代码用装入地址(l d a)和装入值(l o d)作出区别。 作为本节中最后的一个P -代码例子，我们对程序清单8 - 1中的T I N Y程序给出P -代码的翻译， 如程序清单8 - 6所示，其中每条操作都有注释。 程序清单8-6 程序清单8 - 1中T I N Y程序的P -码指令 程序清单8 - 6中的P -代码包含了几个新的P -代码指令。首先，无参的r d i和w r i指令实现了 T I N Y中的整型的r e a d和w r i t e语句。r d i P -代码指令要求要读的那个变量地址应位于栈顶， 这个地址作为指令的一部分被弹出。 w r i指令要求要写的值地址位于栈顶，这个值作为指令的 一部分弹出。程序清单8 - 6中出现的另一些新指令是l a b指令，它定义了标签名字的位置；f j p 指令(“false jump”)需要在栈顶有一个布尔值； s b i指令(整数减法)的操作类似于其他算术指 令；g r t指令(大于)和e t u(等于)指令需要两个整型值位于栈顶 (要被弹出)然后压入他们的布尔 第 8章 代 码 生 成 3 1 1 下载
312 翁译原理及实践 China-pub.co 下载 型结果。stp指令对应于前面三地址码的halt指令。 )P代码和三地址码的比较P代码在许多方面比三地址码更接近于实际的机器码。P代 码指令也需要较少地址：我们已见过的都是一地址或零地址指令，另一方面，P代码在指令数 量方面不如三地址码紧凑，P.代码不是自包含的，指令操作隐含地依赖于栈（隐含的栈定位实 际上就是“缺省的”地址)，栈的好处是在代码的每一处都包含了所需的所有临时值，编译器 不用如三地址码中那样为它们再分配名字。 2)P代码的实现历史上，P代码已经大量地作为文本文件生成，但前面的三元地址码的 内部数据结构描述（三元式和四元式）也能作用于P代码的修改版。 8.2基本的代码生成技术 本节讨论代码生成的基本方法，在下一节，我们将针对单个的语言结构进行代码生成。 8.2.1作为合成属性的中间代码或目标代码 中间代码生成（或没有中间代码的直接目标代码生成）能被看作是一个属性计算，这类似于 第6章中研究的许多属性问题，实际上假如生成代码被看作一个字符串属性（每条指令用换行符 分隔)，这个代码就成了一个合成属性并能用属性文法定义，并且能在分析期间直接生成或者 通过语法树的后序遍历生成。 为了看清楚三地址码或P代码怎样被作为合成属性定义，考虑下边的文法，它代表了C表 达式的一个子集。 exp→id=exp|aep aexp-aexp +factor factor factor-(exp)numl id 这个文法仅包含了两个操作，赋值(=)和加法(+)°。记号i代表简单标识符，记号nm代表了 表示整数的简单数字序列。这两个记号被假设成有一个预先计算过的s1al属性，它可以是字 符串或词（例如“42”是nm, “xtemp”是id), )P代码我们首先考虑P代码的情况，由于不需要产生临时变量名，属性文法会简单些， 然而，嵌套赋值的存在是一个复杂因素。在这种情况下，我们希望保留被存的值作为赋值表达 式的结果值，然而标准的P代码指令st。是有害的，因为所赋的值会丢掉(P代码在这里显示出 了它pascal源，在pascali源代码中不存在嵌套的赋值语句)。我们通过引入一个无害的存储 (nondestructive store)指令stn来解决这个问题，stn和sto一样，都假设栈顶有一个值且下面 有一地址。st将值存入那个地址，但在丢弃那个地址时栈顶上仍保留了那个值。表8-l是使 用这个新的指令后P代码属性的属性文法。在那幅图中，已经用属性名pcod表示P-代码串， 并已把两个不同的符号用于串的连接：+表示所连的串之间不能在同一行，川表示连接一个串 用空格相隔。 我们将跟踪某个例子的pcode属性计算留给读者并写出来，例如：表达式(x=x+3)+4有如 下的pcode属性： 。这个例子中的赋值有如下的语义：x=心将e的值存入x,该赋值的结果值是。：
型结果。s t p指令对应于前面三地址码的h a l t指令。 1) P -代码和三地址码的比较 P -代码在许多方面比三地址码更接近于实际的机器码。 P -代 码指令也需要较少地址；我们已见过的都是一地址或零地址指令，另一方面， P -代码在指令数 量方面不如三地址码紧凑， P -代码不是自包含的，指令操作隐含地依赖于栈 (隐含的栈定位实 际上就是“缺省的”地址 )，栈的好处是在代码的每一处都包含了所需的所有临时值，编译器 不用如三地址码中那样为它们再分配名字。 2) P -代码的实现 历史上，P -代码已经大量地作为文本文件生成，但前面的三元地址码的 内部数据结构描述(三元式和四元式)也能作用于P -代码的修改版。 8.2 基本的代码生成技术 本节讨论代码生成的基本方法，在下一节，我们将针对单个的语言结构进行代码生成。 8.2.1 作为合成属性的中间代码或目标代码 中间代码生成(或没有中间代码的直接目标代码生成 )能被看作是一个属性计算，这类似于 第6章中研究的许多属性问题，实际上假如生成代码被看作一个字符串属性 (每条指令用换行符 分隔)，这个代码就成了一个合成属性并能用属性文法定义，并且能在分析期间直接生成或者 通过语法树的后序遍历生成。 为了看清楚三地址码或 P -代码怎样被作为合成属性定义，考虑下边的文法，它代表了 C表 达式的一个子集。 e x p→i d = e x p | a e x p a e x p→a e x p + factor | f a c t o r f a c t o r→( exp ) | n u m | i d 这个文法仅包含了两个操作，赋值 (=)和加法(+) 。记号i d代表简单标识符，记号n u m代表了 表示整数的简单数字序列。这两个记号被假设成有一个预先计算过的 s t rv a l属性，它可以是字 符串或词(例如“4 2”是n u m，“x t e m p”是i d)。 1) P -代码 我们首先考虑P -代码的情况，由于不需要产生临时变量名，属性文法会简单些， 然而，嵌套赋值的存在是一个复杂因素。在这种情况下，我们希望保留被存的值作为赋值表达 式的结果值，然而标准的P -代码指令s t o是有害的，因为所赋的值会丢掉( P -代码在这里显示出 了它p a s c a l源，在 p a s c a l源代码中不存在嵌套的赋值语句 )。我们通过引入一个无害的存储 (nondestructive store)指令s t n来解决这个问题，s t n和s t o一样，都假设栈顶有一个值且下面 有一地址。s t n将值存入那个地址，但在丢弃那个地址时栈顶上仍保留了那个值。表 8 - 1是使 用这个新的指令后 P -代码属性的属性文法。在那幅图中，已经用属性名 p c o d e表示P -代码串， 并已把两个不同的符号用于串的连接： + +表示所连的串之间不能在同一行， | |表示连接一个串 用空格相隔。 我们将跟踪某个例子的p c o d e属性计算留给读者并写出来，例如：表达式 ( x = x + 3 ) + 4有如 下的p c o d e属性： lda x lod x 3 1 2 编译原理及实践 下载 这个例子中的赋值有如下的语义：x = e将e的值存入x，该赋值的结果值是e
China-pub.com 第8章代码生成 313 下载 1de 3 adi atn adi 表81P代码合成字符串属性的属性文法 文法规则 语义规则 ep→id=ep, exp,pcode "lda"id.strval +exp.pcode +"stn exp-aexp exp.pcode aexp.pcode aexp,aexp,+factor aexp:pcode=aexp:pcode ++factor.pcode++"adi gexn-factor aexn ncode factor ncode factor一(ep) factorpcode=exp.pcode factor→nu 2)三地址码前面那个简单表达式的三地址码属性文法在表8-2中给出。在那张表中，我 们称代码属性为tacode。同表8-l,也用+表示其间插有换行符的串连接，表示其间有空格的 串连接。与P代码不同，三地码要求为表达式的中间结果生成临时变量名，这就要求属性文法 在每个节点中都包括一个新名字属性。这个属性也是合成的，如果没有为一个内部节点分配 个新产生的临时名，就用newtemp()产生 个临时名字系列t1、t2、t3,,(每次调用 newtemp()就返回一个新的)。在这个简单例子中，仅对应于+的节点需临时名，赋值操作使用 右边的表达式的名字。 表82三地址码作为合成串属性的属性文法 文法规则 语义规则 ep→id=ep exD.Hame=exD.月ane exp tacode exp..tacode +id.strval ="lexp.name ep一aep exp.name aexp.name aep,→ae明，+facto aexp,to code+factor.tacod +aexp namel"="aexp.nam "+"actor.name aep一factor aexp.name factor.name aexp.tacode factor.tacode factor一（ep) factor namte exp.nante factor.tacode exptacode factornum factor-id factor.tacode 表8-2的产生式exp一aexp和aep一factor中，将名字属性即1 acodek属性从子节点提到父节点， 在操作符内部节点中，新名字属性应在联合的acode代码之前生成。在叶产生式factor-一num利
ldc 3 adi s t n ldc 4 a d i 表8-1 P-代码合成字符串属性的属性文法 文 法 规 则 语 义 规 则 e x p1 → i d = e x p2 e x p1 .p c o d e = "lda" || i d. s t rv a l ++ e x p2 .p c o d e ++ " s t n " e x p → a e x p e x p.p c o d e = a e x p.p c o d e a e x p1 → a e x p2 + f a c t o r a e x p1 .p c o d e = a e x p2 .p c o d e ++ f a c t o r.p c o d e + + " a d i " a e x p → f a c t o r a e x p.p c o d e = f a c t o r.p c o d e f a c t o r → ( e x p ) f a c t o r.p c o d e = e x p.p c o d e f a c t o r → n u m f a c t o r.p c o d e = " l d c "| |n u m.s t rv a l f a c t o r → i d f a c t o r.p c o d e = " l o d "| |i d.s t rv a l 2) 三地址码 前面那个简单表达式的三地址码属性文法在表 8 - 2中给出。在那张表中，我 们称代码属性为t a c o d e。同表8 - 1，也用+ +表示其间插有换行符的串连接， | |表示其间有空格的 串连接。与P -代码不同，三地码要求为表达式的中间结果生成临时变量名，这就要求属性文法 在每个节点中都包括一个新名字属性。这个属性也是合成的，如果没有为一个内部节点分配一 个新产生的临时名，就用 n e w t e m p( ) 产生一个临时名字系列 t 1、t 2、t 3, . . . ( 每次调用 n e w t e mp( )就返回一个新的)。在这个简单例子中，仅对应于 +的节点需临时名，赋值操作使用 右边的表达式的名字。 表8-2 三地址码作为合成串属性的属性文法 文 法 规 则 语 义 规 则 e x p1 → i d = e x p2 e x p1 .n a m e = e x p2 .n a m e e x p1 .t a c o d e = e x p2 .t a c o d e ++ i d.s t rv a l || " = "| |e x p2 .n a m e e x p → a e x p e x p.n a m e = a e x p.n a m e e x p.t a c o d e = a e x p.t a c o d e a e x p1 → a e x p2 + f a c t o r a e x p1 .n a m e = n e w t e m p( ) a e x p1 .t a c o d e = a e x p2 .t a c o d e ++ f a c t o r.t a c o d e ++ a e x p1 .n a m e|| " = "|| a e x p2 .n a m e || " + "| |f a c t o r.n a m e a e x p → f a c t o r a e x p.n a m e = f a c t o r.n a m e a e x p.t a c o d e = f a c t o r.t a c o d e f a c t o r → ( e x p ) f a c t o r.n a m e = e x p.n a m e f a c t o r.t a c o d e = e x p.t a c o d e f a c t o r → n u m f a c t o r.n a m e = n u m. s t rv a l f a c t o r.tacode = " " f a c t o r → i d f a c t o r.n a m e = i d.s t rv a l f a c t o r.t a c o d e = " " 表8 - 2的产生式e x p→a e x p和a e x p→f a c t o r中，将名字属性即t a c o d e属性从子节点提到父节点， 在操作符内部节点中，新名字属性应在联合的 t a c o d e代码之前生成。在叶产生式f a c t o r→n u m和 第 8章 代 码 生 成 3 1 3 下载
314 翁译原理及实践 China-pub.Com 下载 factor-一id中记号的串值记作factor.name。与P.代码不同，在叶产生式的节点上没有生成三地 址码（用"表示空串） 再次，我们让读者按表8-2所给出的等式写出表达式(x=x+3)+4的每一步的tacode,这个 表达式的tacode属性如下： t1=x+3 x=1 t2=t1+4 (这里假设mew1em以)用后序调用并且产生从t1开始的临时名)。注意x=x+3是怎样用临时名产 生两个三地址指令的。这是属性值总是为每一个子表达式产生一个临时名的结果，它包括了赋 值号的右边部分。 将代码生成看成一个合成字符串属性计算，对于清楚地显示语法树各部分代码系列的关系 以及比较不同的代码生成方法是很有用的，但它作为真实的代码生成技术是不实际的，这有 几个原因：首先，串连接的使用造成了过度的串拷贝因而浪费了内存（除非连接符做得非常复 杂)，其次，通常希望产生几片代码作为代码产生的收益并且将这几片代码写入一个文件或将 它们插入一个数据结构（如四元式数组），这就需要语义动作，而语义动作又不与属性的标准后 序合成有牵连。最后，即使将代码看作是纯合成是有用的，但通常的代码生成很大程度上依 赖于继承属性，这将使得属性文法大大复杂化。由于这个原因，我们就不必麻烦再去写出实 现前面例子中的属性文法的代码了（即使是伪码）。相反地，在下一节中，我们将转向更直接的 代码生成技术。 8.2.2实际的代码生成 标准的代码生成或者涉及语法树后序遍历的修改，这棵语法树是由前面例子的属性文法所 包含的，或者如没有显式生成的语法树，则在分析中涉及了相等效的动作。基本算法由下面的 递归过程描述（用于二叉树，但容易将其推广到节点子树多于2的情况）： procedure genCode (T:treenode ) begin if T is not nil then generate code to prepare for code of left child of T, genCode (left child ofT). generate code to prepare for code of right child of T. genCode (right child ofT). generate code to implement the action ofT. end 注意，这个递归遍历过程不仅有一个后序部分（产生实现T动作的代码），而且还有一个前序和 一个中序部分（为T的左右子树产生准备代码）。通常，T表示的每一个动作需要前序和中序准 备代码的稍微不同的一个版本。 为了详细地看清在一个特殊的例子中怎样构造产生代码的过程，考虑我们在这一节已用过 的简单算术表达式的语法，这个语法的抽象语法树的C语言定义如下所示： Kind】NodeKind
f a c t o r→i d 中记号的串值记作f a c t o r. n a m e。与P -代码不同，在叶产生式的节点上没有生成三地 址码(用" "表示空串)。 再次，我们让读者按表8 - 2所给出的等式写出表达式 ( x = x + 3 ) + 4的每一步的t a c o d e，这个 表达式的t a c o d e属性如下： t1 = x+3 x = t1 t2 = t1+4 (这里假设n e w t e m p( )用后序调用并且产生从t 1开始的临时名)。注意x = x + 3是怎样用临时名产 生两个三地址指令的。这是属性值总是为每一个子表达式产生一个临时名的结果，它包括了赋 值号的右边部分。 将代码生成看成一个合成字符串属性计算，对于清楚地显示语法树各部分代码系列的关系 以及比较不同的代码生成方法是很有用的，但它作为真实的代码生成技术是不实际的，这有 几个原因：首先，串连接的使用造成了过度的串拷贝因而浪费了内存 (除非连接符做得非常复 杂)，其次，通常希望产生几片代码作为代码产生的收益并且将这几片代码写入一个文件或将 它们插入一个数据结构(如四元式数组)，这就需要语义动作，而语义动作又不与属性的标准后 序合成有牵连。最后，即使将代码看作是纯合成是有用的，但通常的代码生成很大程度上依 赖于继承属性，这将使得属性文法大大复杂化。由于这个原因，我们就不必麻烦再去写出实 现前面例子中的属性文法的代码了 (即使是伪码)。相反地，在下一节中，我们将转向更直接的 代码生成技术。 8.2.2 实际的代码生成 标准的代码生成或者涉及语法树后序遍历的修改，这棵语法树是由前面例子的属性文法所 包含的，或者如没有显式生成的语法树，则在分析中涉及了相等效的动作。基本算法由下面的 递归过程描述(用于二叉树，但容易将其推广到节点子树多于 2的情况)： p ro c e d u re genCode ( T: t reenode ) ; b e g i n if T is not nil t h e n generate code to pre p a re for code of left child of T; genCode (left child of T ) ; generate code to pre p a re for code of right child of T; genCode (right child of T ) ; generate code to implement the action of T; e n d; 注意，这个递归遍历过程不仅有一个后序部分 (产生实现T 动作的代码)，而且还有一个前序和 一个中序部分(为T 的左右子树产生准备代码 )。通常，T 表示的每一个动作需要前序和中序准 备代码的稍微不同的一个版本。 为了详细地看清在一个特殊的例子中怎样构造产生代码的过程，考虑我们在这一节已用过 的简单算术表达式的语法，这个语法的抽象语法树的 C语言定义如下所示： typedef enum { Plus, Assign } Optype; typedef enum { OpKind, ConstKind, IdKind } NodeKind; 3 1 4 编译原理及实践 下载