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 编译原理及实践 下载