第八章语法制导翻译和中间代码生成

第八章 语法制导翻译和中间代码生成课前索引【课前思考】回顾第一章介绍的编译过程，理解语义分析在编译过程中的位置和作用什么是中间表示（中间代码），为什么要中间表示？语法制导翻译”是什么含义？高级语言语句的结构和低级语言结构的不同。【学习目标】明确语义分析在编译过程所处的阶段和作用。掌握属性文法的基本概念。使用属性文法和语法制导翻译方法描述具体的语义分析和产生中间代码。【学习指南】紧接在词法分析和语法分析之后，编译程序要做的工作就是进行静态语义检查和翻译。 静态语义检查通常包括：类型检查，控制流检查，一致性检查，相关名字检查及名字的作用 域分析等等。虽然源程序可以直接翻译为目标语言代码，但是许多编译程序都采用了独立于机器的，复杂性介于源语言和机器语言之间的中间语言。其好处便于进行与目标机无关的 代码优化，也使得编译的前后端接口清晰，编译程序结构在逻辑上更简明【难重点】翻译时源语句到目标语句结构上的变换。语法制导翻译实现的方法。 Yacc和语法制导翻译.【知识结构】语法制号翻译和中问代码生成A语叟处理工員一一静悲语女检查_源稈序劉中闾代码的翻译隔性立法和语法制导翻译一_雇性立法定女 丄”静霑语义描述举例中间代码的走式佰语句的（四无式）翻译一布尔表达式的翻译一控制语句的初译 简单说明语甸的嘲译Yag和语袪制导翻译编译程序的任务是把源程序翻译成目标程序，这个目标程序必须和源程序的语义等 同，也就是说 ,尽管它们的语法结构完全不同， 但它们所表达的结果应完全相同 .通常， 在词 法分析程序和语法分析程序对源程序的语法结构进行分析之后,要么由语法分析程序直接调用相应的语义子程序进行语义处理，要么首先生成语法树或该结构的某种表示，再进行 语义处理 .编译中的语义处理是指两个功能：第一，审查每个语法结构的静态语义，即验证语法 结构合法的程序是否真正有意义。有时把这个工作称为静态语义分析或静态审查。第二， 如果静态语义正确， 语义处理则要执行真正的翻译， 即 ,或者将源程序翻译成程序的一种中 间表示形式（中间代码） ，或者将源程序翻译成目标代码。本章引入属性文法和语法制导翻译方法的基本思想，介绍几种典型的中间代码形式， 最后讨论一些语法成分的翻译工作。静态语义分析 通常包括： 类型检查。验证程序中执行的每个操作是否遵守语言的类型系统的过程。, 编译程序必须报告不符合类型系统的信息 . 控制流检查 .控制流语句必须使控制转移到合法的地方.例如，在 C 语言中 break 语句使控制跳离包括该语句的最小while 、for 或 switch 语句。如果不存在包括它的这样的语句，则就报错。 一致性检查。在很多场合要求对象只能被定义一次。例如 Pascal 语言规定同一标 识符在一个分程序中只能被说明一次,同一 case 语句的标号不能相同， 枚举类型的元素不能重复出现等等。 相关名字检查 .有时， 同一名字必须出现两次或多次 . 例如 ,Ada 语言程序中， 循环或 程序块可以有一个名字，出现在这些结构的开头和结尾，编译程序必须检查这两个地方用 的名字是相同的。 名字的作用域分析所谓 中间代码 ,也称中间语言 ,是复杂性介于源程序语言和机器语言的一种表示形式。 为什么有的编译程序直接生成目标代码,有的编译程序采用中间代码 .一般 ,快速编译程序直接生成目标代码 ,没有将中间代码翻译成目标代码的额外开销。但是为了使编译程序结构在逻辑上更为简单明确 ,常采用中间代码， 这样可以将与机器相关的某些实现细节置于代码生 成阶段仔细处理， 并且可以在中间代码一级进行优化工作使得代码优化比较容易实现。 文 档为个人收集整理，来源于网络8。 1 属性文法语义形式化是个专门的研究课题，目前有各种各样的方法和记号不断推出，例如操作 语义学、公理语义学和指称语义学。语义形式化 （语义建模）有几种模型 文法模型 - 属性文法 命令式或操作式模型 - - - 操作语义学 应用式模型 - 指称语义学 公理式模型 公理语义学 规格说明模型 - 代数数据类型 属性文法将在我们的讲义中介绍 .操作语义描述一段程序的含义是通过执行该段程序 所改变的计算机（无论是真实计算机还是虚拟计算机）状态来反映。计算机里所有的寄存 器的值和存储单元的值作为计算机的状态。For （expr1 ； expr2；expr3） 的操作语义表示： exprl;Loop： if expr2=0 goto outxpr3;goto loopout:.O 公理语义概念是随着程序正确性的证明而发展的。当正确性证明能构造时表明程序执行它的规格说明所描述的计算.在一个证明中， 每一个语句之前之后都有一个逻辑表达式对程序的变量进行约束，以此说明这个语句的含义一般的记号是P S Q o指称语义的基本概念是给每一段程序实体定义一个数学意义上的对象，和一个从实体 实例向数学意义对象的映射的函数。规格说明模型通过描述实现一个程序的各种函数间的关系来说明语义。如表明一个实现服从任何两个函数间的这种关系，则可以声明这个实现是此规格说明的正确实现。本文为互联网收集，请勿用作商业用途不论哪种方法 ,其本身的符号系统比较繁杂 ,其描述文本不易读，目前编译程序尚不便借助这些形式系统自动完成语义处理任务现在很多编译程序采用语法制导翻译方法。这仍不是一种形式系统，但它是比较接近形式化的。这种方法使用属性文法为工具来说明程序设 计语言的语义。一个属性文法包含一个上下文无关文法和一系列语义规则，这些语义规则 附在文法的每个产生式上，在语法分析过程中，完成这些语义规则描述的动作，从而实现 语义处理 .首先简单介绍属性文法。所谓属性，其涉及的概念比较广泛，常用以描述事物或人的特征、性质，品质等等。比如，谈到一个物体，可以用 ”颜色”描述它，谈起某人，可以使用 ”有幽默感”来形容他。对 编译程序使用的语法树的结点，可以用 ”类型、 ”值或”存储位置 来描述它 .属性文法（也称属性翻译文法 ）是 Knuth 在 1968 年首先提出的 .它是在上下文无关文法的基 础上，为每个文法符号 （终结符或非终结符）配备若干相关的值”（称为属性） .这些属性代表与文法符号相关信息 ，例如它的类型、值、代码序列、符号表内容等等.属性与变量一样 ，可以进行计算和传递属性加工的过程即是语义处理的过程。对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。形式上讲，一个属性文法是一个三元组,A =（ G,V , F），一个上下文无关文法 G; 个属性的有穷集 V和关于属性的断言或谓词的有穷集Fo每个断言与文法的某产生式相联 .如果对 G 中的某一输入串而言 （句子）， A 中的所有断言对 该输入串的语法树结点的属性全为真，则该串也是A语言中的句子。编译程序的静态语义审查工作就是验证关于所编译的程序的断言是否全部为真 .比如，有文法 G 为：ET 1 + T2|T1 or T2Ttnum|true | false（因为T在同一个产生式里出现了两次，使用上角标将它们区分开。） 对输入串 3+4 的语法树如图 81（A）图 8 1 静态语义审查(a)(b)属性文法记号中常使用 N .T的形式表示与非终结符N相联的属性t。比如可把对上面表达式的类型检查的属性文法写成图& 2的形式。与每个非终结符T相联的有属性t，t要么是int,要么是bool。与非终结符E的产生式相联的断言指明：两个T的属性必须相同。图8. 1的(b)是图8.1(a)语法树结点带有语义信息的表示图& 2类型检查的属性文法Et 1+T2 T 1.t= int ANDT2.t= intET 1orT2 T 1.t= bool ATD T 2 t= boolTt num T。t ：= int Tt true T.t ： = bool Tt falseT。 t ：= bool属性文法中的属性分成两类：继承属性和综合属性，简单地说，综合属性用”自上而上传递信息，而继承属性用于自上而下传递信息。在一个属性文法中，对应于每个产生式Aa都有一套与之相关联的语义规则，每条规则的形式为b := f (c 1,C2 ,C k)这里，f是一个函数，而且或者(1) b是A的一个综合属性并且 C1, C2,ck是产生式右边文法符号的属性：或者(2) b是产生式右边某个文法符号的一个继承属性并且C1,c2, -ck是A或产生式右边 任何文法符号的属性。在两种情况下，我们都说属性b依赖于属性C1, C2,C我们不对属性文法进行理论上的研究而仅仅将它做为工具描述语义分析。在编译的许 多实际应用中，属性和断言以多种形式出现，也就是说，与每个文法符号相联的可以是各种属 性、断言、以及语义规则，或者某种程序设计语言的程序段等等。一般说来，对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提 供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性，这有助于在 产生式范围内封装”属性的依赖性。然而，出现在产生式左边的继承属性和出现在产生式 右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计算器的参数提供。语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码生成等 等.语义规则可能产生副作用(如产生代码)，也可能不是变元的严格函数(如某个规则给出可用的下一个数据单元的地址)。这样的语义规则通常写成过程调用或过程段。下面再给出一些例子。f8-1-1。swf在该描述中，每个非终结符都有一个属性：一个整数值的称作val的属性。按照语义规则对每个产生式来说，它的左部E, T，F的属性值的计算来自它右部的非终结符，这种属性称作综合属性单词digit仅有综合属性，它的值是由词法分析程序提供的。和产生式LE相联的语义规则是一个过程，打印由E产生的表达式的值。我们可以理解为L的属性是空的或是虚的。例8.2中的文法定义了一种说明语句，该说明语句的形式是由关键字int或real开头，后面是一个标识符表，每个标识符由逗号隔开。非终结符T有一个综合属性type,它的值由关键字决定（int或real）。与产生式TL相联的语义规则 L.in : = T.type将L.in的属 性值置为该说明语句指定的类型。属性L.in将被沿着语法树传递到下边的结点使用，与L产生式相联的规则里使用了它。描述说明语句中各种变量的类型信息的语义规则，这个例子里，继承属性在说明 中为各个标识符提供类型信息。产生式语义规则(1) D TL L。 in ：= T.type(2)int To Type ：= integer(3)real T.Type ：= real(4) LL 1, id L1.in ： = L o inaddtype (id。 entry, L.in ) (5) Lt idaddtype(id.entry , L。 in) 图8.3是句子intid1, id2的语法树，使用表示属性的传递情况在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。与L产生式相联的语义规则中有一个过程调用addtype,过程addtype的功能是把每个标识符的类型信息登录在符号表的相关项中。图8。3属性信息传递情况属性文法看作是允许为每个终结符和非终结符配备一些属性的文法。它既能描述程序 设计语言的语法，又为语义处理提供了方便属性文法里的属性有不同的类型，可以象变量一样地被赋值。赋值规则附加于语法规则之上。赋值与语法同时进行，赋值过程就是语义处理过程。在推导语法树的时候，诸属性的值被计算并通过赋值规则层层传递。有的从语法 规则左边向右边传，有的从右边向左边传。语法推导树最后完成时，就得到开始符号的属性 值也就是整个程序的语义个人收集整理勿做商业用途& 2语法制导翻译编译程序的整个任务就是把源程序翻译为目标程序。实际上每个编译阶段都可以看成 是完成一定的翻译任务：词法分析阶段把字符流翻译为单词流，语法分析阶段把单词流翻 译为语法树，目标代码生成阶段把语法树翻译为汇编语言等等。在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序(或语义规则描述的语义动作)进行翻译的办法称作语法制导翻译假如我们要把中缀算术表达式翻译为后缀波兰表示形式(后缀波兰表示形式参见8。3.1),给出如下语义描述：iT + E 1 E 。 code=T.code | | E1。 code|+ iT E 。 code=T。 code Tf F * T 1 T.code=F。 code | |T1.code |* Tt F T 。 code =F。code Ff (E) F。code = E.code Ft a F.code = a 其中使用E。code, T.code和F.code分别表示相应的后缀式，” |表示后缀式的连接。如果对于输入串a+a*a采用最左分析，其形成的推导过程为：E T+EF+E a+Ea+T a+T* 厂-a+F*L-a+a*La+a*a(a ,) a是输入句子和句型，B是翻译的输出形式，则有：(E, E.code)(T+E , T。 code | E。code | |+) T (F+E, F。code | |E。code|+)一(a+E, a| | E.code|+) r (a+T, a | T。 code | |+)(a+F*, a | |F.code|T.code|+)* *一 (a+a , a|a| | T。code | | +)(a+a*F, a| | a | F.code | | *+)*= (a+a a, a| | a | |a | | +)去掉a | |a | |a | | +中的连结符，得到中缀表 达式a+a*a的后缀式 aaa+个人收集整理，勿做商业用途假定我们现在要分析的语法成分是简单算术表达式，所完成的语义处理不是将它翻译成中间代码或是目标代码，而是计算表达式的值。采用的描述系统是上节的例8.1。假如语法分析方法是自下而上的.在用某一产生式进行归约的同时就执行相应的语义动作，在分析出一个句子时，这个句子的”值也就同时产生了，例如输入串是2+3* 5,其语法树如图8。4(a),在第一步归约用到了产生式(6)，执行的语义动作是置F. val的值为单词digit值，我们把语法树中每个结点的语义值括在该结点处。那么第一步归约并完成语义动作后的情形 在图& 4 (b)中指出。继续进行分析，第七次归约后的情形在图8。4(c)中指出。归约至E时，它的值17也计算出来了。图8。4语法制导方法计算表达式L1EL1EL1EZNE1 TE1卜TE1 4-TTZN(2)(15)密 T】* FT T】* F1 1 111 1F F 51 123FF 5(e)这里再给出一种翻译模式，也是把中缀形式的算术表达式映射到后缀波兰表示：i T + E E=TE+ i T E=T F * T T=FT * F T =F i (E) F = E i a F = a 句子a+a*a的一个推导过程：E一 T+EF+E一 a+E .： a+T a+F*T a+a*T a+a F 1 a+a*a伴随着句子a+a*a的这个推导过程，按照上述翻译模式所进行的一步步翻译：* *E一 TE+ FE+ aE+ aT+ aFT + aaT + - aaF + aaa +语法制导翻译的具体实现途径不困难。假定有一个LR语法分析器，现在把它的分析栈扩充，使得每个文法符号都跟有语义值，即把栈的结构看成图8.5所示那样。图8.5扩充的分析栈Smy,ValySm 1x,Valx。S0一#状态栈语义值符号栈图8。 6 LR分析表状态ACTION (动作)GOTO (转换)d+*()#ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108r6s119r1s7r1r110r3r3r3r311r5r5r5r5同时把LR分析器的能力扩大，使它不仅执行语法分析任务，且能在用某个产生式进行 归约的同时调用相应的语义子程序，完成在例8.1的属性文法中描述的语义动作每步工作后的语义值保存在扩充的分析栈里语义值”栏中。采用的LR分析表见图& 6,其中使用d代替digit。分析和计值2+3衣5的过程列在图8.7中。图& 7 2+3*5的分析和计值过程步骤归约动作状态栈语义栈（值栈）符号栈留余输入串10一#2+3*5#205-#2+3*5#3r603-2#F+3*5#4r402一 2# T+3 * 5 #5r201-2#E+3 * 5#60162# E+3* 5 #701652-# E+3* 5 #8r601632 3# E+F*5 #9r40169-2 3# E+T* 5#10016972 3#E+T 5 #110169752-3-# E+T -5#12r601697(10)-2-2 5#E+T -F#13r30169-2- (15)# E+T#14t101(17)#E#15接受按照上述实现办法，若把语义子程序改为产生某种中间代码的动作，那么则可在语法 分析的制导下，随着分析的进展逐步生成中间代码8.3中间代码的形式编译程序所使用的中间代码有多种形式。常见的有逆波兰记号、三元式、四元式和树 形表示。下面分别将它们做一介绍8.3。1逆波兰记号逆波兰记号是最简单的一种中间代码表示形式，早在编译程序出现之前，它就用于表 示算术表达式，是波兰逻辑学家卢卡西维奇发明的。这种表示法将运算对象写在前面，把运算符号写在后面，比如把a+b写成ab+,把a*b写成ab*，用这种表示法表示的表达式也称做后缀式。图& 8给出了程序设计语言中的简单表达式和赋值语句相应的逆波兰表示形式：图8.8逆波兰表示程序设计语言中的表示逆波兰表示a+bab+a+b * cabc* +(a+b) *cab+c*a； =b * c+b * dabc* bd*+:=后缀表示法表示表达式， 其最大的优点是易于计算机处理表达式.常用的算法是使用一个栈，自左至右扫描算术表达式（后缀表示），每扫描到运算对象，就把它推进栈；扫描 到运算符，若该运算符是二目的，则对栈顶部的两个运算对象实施该运算，并将运算结果 代替这两个运算对象而进栈；若是一目运算符，则对栈顶元素执行该运算，并以运算结果 代替该元素进栈，最后的结果留在栈顶。例如BCD*+ （它的中缀表示为一 B+C * D，使用表示一目减）的计值过程为：1。B进栈；2. 对栈顶元素施行一目减运算，并将结果代替栈顶，即- B置于栈顶；3. C进栈；4。D进栈；5. 栈顶两元素相乘，两元素退栈，相乘结果置栈顶；6。栈顶两元素相加，两元素退栈，相加结果进栈，现在栈顶存放的是整个表达式的值。由于后缀式表示上的简洁和计值的方便，特别适用于解释执行的程序设计语言的中间表示，也方便具有堆栈体系的计算机的目标代码生成。逆波兰表示很容易扩充到表达式以外的范围。在图& 8中已见到了赋值语句的后缀表示的例子。只要遵守运算对象后直接紧跟它们的运算符的规则即可.比如把转语句GOTO L写为L jump ”运算对象L为语句标号，运算符jump表示转到某个标号。 再比如条件语句 if E then S1 else S2可表示为：ES1S2Y，把if then else看成三目运算符，用Y来表示。又如 数组元素 A 下标表达式 1, 下标表达式 n可表示为 下标表达式nA subs，运算符Subs表示求数组的下标。当然，这些扩充的后缀表示的计值远比后缀表达式的计值复杂得多，要注意对新添加的运算符的含义正确处理。以图& 8中的赋值语句为例，当计算到：=时，执行的是将表达式B*C+B * D的值送到变量a,所以,而在执行完赋值后，栈中并不产生结果值， 这与算术的 二目运算符是不一样的，另外，因为需要的是a的地址，而不是a的值，这也必须注意到。本文为互联网收集，请勿用作商业用途832三元式和树形表示另一类中间代码形式是三元式。把表达式及各种语句表示成一组三元式.每个三元式由三个部分组成，分别是：算符op,第一运算对象 ARG1和第二运算对象 ARG2。运算对象可能是源程序中的变量，也可能是某个三元式的结果，用三元式的编号表示。例如a： =b衣c+b衣d的表示为：宀 b, c)(2) ( * , b, d)(3) (+ (1 ),(2)(4) (: =(2), a)与后缀式不同，三元式中含有对中间计算结果的显式引用，比如三元式(1)表示的是b* c的结果。三元式(3)中的(1 )和(2)分别表示第一个三元式和第二个三元式的结果.对于一目算符 op,只需选用一个运算对象，不妨规定只用ARG1.至于多目算符，可用若干个相继的三元式表示。树形表示是三元式表示的翻版.上述三元式可表示成下面的树表示：L cb d表达式的树形表示很容易实现：简单变量或常数的树就是该变量或常数自身，如果表达式&和e2的树分别为Ti和T2,那么ei+e2, ei*e2, ei的树分别为：+/ * -/ /G1 + 匸九Ci + Cr1二目运算对应二叉子树，多目运算对应多叉子树，不过，为了便于安排存储空间，一棵多叉子树可以通过引进新结而表示成一棵二叉子树。& 3.3四元式四元式是一种比较普遍采用的中间代码形式。四元式的四个组成成分是：算符op,第一和第二运算对象 ARG1和ARG 及运算结果 RESULT。运算对象和运算结果有时指用户自己定义的变量，有时指编译程序引进的临时变量。例如a： =b*c+b * d的四兀式表示如下：(1) ( * ,b,c, t1)(*,b,d,t2)(3) (+ ,t1, t2, t3)(：=,t3, , a)四元式和三元式的主要不同在于，四元式对中间结果的引用必须通过给定的名字，而 三元式是通过产生中间结果的三元式编号。也就是说，四元式之间的联系是通过临时变量 实现的。也许读者已经发现，四元式表示很类似于三地址指令，确实，有时把这类中间表示称 为”三地址代码”因为这种表示可看作一种虚拟三地址机的通用汇编码，即这种虚拟机的每条指令包含操作符和三个地址，两个是为运算对象的，一个是为结果的。这种表示对于 代码优化和目标代码生成都较有利.有时 ,为了更直观， 也把四元式的形式写成简单赋值形式或更易理解的形式。比如把上述四元式序列写成：1)tl :=b*c2)t2 :=b * d3)t3 :=t1+t24)a :=t3把( jump， L )写成 goto L把(jrop , B, C, L)写成 if B rop C goto L本书中 ,为了叙述的方便，两种形式将同时使用。如何用四元式表示各种语句， 以及翻译各种语句的语义描述， 将在后面各节陆续讨论 为了复习与巩固一下前面所学习的几种中间代码的形式,下面举一个例子，分别用几种中间代码的形式来表示例：A + B *( C D ) + E / ( C D ) ANA四元式：1)(-CD T1 )2)(*BT1T2)3)(+AT2T3)4)(CDT4)5)(AT4NT5)6)(/ET5T6)7)(+T3T6T7)三元式：( 1)(CD)( 2)(*B(1)(3)(+A2)( 4)(CD)( 5)(A (4)N(6)( / E (5 ) ( 7)( +( 3)( 6)间接三元式 ：间接三元式序列( 1)( C D)( 2)( * B ( 1) )(3) ( + A (2)(4) ( 1) N)( 5)( / E ( 4) ( 6)( +( 3)( 5)间接码表( 1)(2)( 3)(1)( 4)(5)( 6)间接码表表面了执行间接三元式的顺序8.4 简单赋值语句的(四元式)翻译在 8。3。3的四元式中，使用变量名字本身表示运算对象ARG1 和 ARG2 ，用 ti 表示RESULT 。在实际实现中，它们或者是一个指针,指向符号表的某一登录项 ,或者是一个临时变量的整数码 .在对赋值语句翻译为四元式的描述中，我们将表明怎样查找这样的符号表登录项。首先对id表示的单词定义一属性 id . name,用做语义变量，用 Lookup (id . name) 表示审查id . name是否出现在符号表中，如在，则返回一指向该登录项的指针，否则返回nil.语义过程emit表示输出四元式到输出文件上。语义过程newtemp表示生成一个临时变量，每调用一次，生成一新的临时变量。语义变量E. place，表示存放E值的变量名在符号表的登录项或一整数码(若此变量是一个临时变量 )图 8。 9 列出了翻译赋值语句到四元 式的语义描述。这里的语义工作包括对变量进行 先定义后使用 ”的检查。图 8。 9 赋值语句的四元式翻译(1) S tid : =E p： =lookup ( id . name);if p 丰 nilthenEmit (p： =E place) else error(2) E tE1+E2 Eplace： =newtemp；Emit (Eplace ： = 1E.place 2+pElace) (3) EtE 1E2 EplaceE： =newtemp；Emit (E. place ： = E. place *2Eplace)(4) E tE1 E . placeE ： =newtemp；Emit(E. place： = uminu1s. pElace )(5) E t( E1)E. place： =E1. place(6) Et id p:=look up( id. name)；if p 工 nil then E . placeE： =p else error实际上 ,在一个表达式中可能会出现各种不同类型的变量或常数,而不是像图8.9 中的id 假定为都是同一类型。也就是说,编译程序还应执行这样的语义动作：对表达式中的运 算对象应进行类型检查 ,如不能接受不同类型的运算对象的混合运算,则应指出错误； 如能接受混合运算, 则应进行类型转换的语义处理。 假如, 图 8.9 中的表达式可以有混合运算 ,id 可以是实型量也可以是整型量,并且约定 ,当两个不同类型的量进行运算时,必须首先将整型量转换为实型量。为进行类型转换的语义处理，增加语义变量，用E. type表示E的类型信息，E. type的值或为int或为real,此外，为区别整型加(乘)和实型加(乘)，把+ (*) 分别写作+i(*i)和+r严r)。用一目算符itr表示将整型运算对象转换成实型.这样,图 8.9中的第( 3)条产生式及其有关语义描述如图8。 10。图 8。 10 类型转换的语义处理产生式语义动作EtE 1E2 E . place： =newtemp；if E1. type = int AND E 2. type = int then begin emit( E.place, ： =, E1. place, i, E2. place)；E. type： =intendelse if E1. type = real AND E 2. type= real then begin emit （E. place, ： = 1E place,*, E2. place）;E. type : =realendelse if E1. type = int/* and E 2. type=real * / thenbegin t： =newtemp；emit（t， ,： =,， , it，r E,1. place）； emit（E. place，,： =,， t, ,r,，*E2. place）；E. type： =realendelse /*E1 type = real and E2. type = int * / begin t： =newtemp；emit（t,：, =, ; , it2r.,pl,aEce）； emit（ E. place， ,： =, ,1E. place, *, r,， t）;E. type： =realend；图8.9中的例子里，与非终结符E相联的语义值有 E. place，还有E. type。语义 值的设计是与语义处理的描述相关的.大家回顾一下 PL/0 编译程序中对赋值语句的语义处理,其中对赋值语句左部的标识符，检查它的种类（kind ）,若不是变量名，则指出错误，若是变量名， 才生成赋值运算的代码。 对右部表达式中作为运算对象的标识符,检查其是否变量名或常量名，是，生成相应代码，不是（即是过程名 ），则指出错误 .这一点若用语义规 则描述的话，还应增加一语义值，与非终结符相联,比如用 E. kind 表示。赋值语句中会含有复杂数据类型，如数组元素、记录（结构）的引用。这种情况的翻 译工作要复杂些，我们将在后面给予专门讨论。8。 5 布尔表达式的翻译程序设计语言中的布尔表达式有两个作用。 一是计算逻辑值， 更多的情况是二 ,用做改 变控制流语句中的条件表达式，如在if then， if-then-else ，或是 while do 语句中那样 .布尔表达式是由布尔算符and， or 和 not 施于布尔变量或关系表达式而成.即布尔表达式的形式为Ei rop E2,其中Ei和E2都是算术表达式，rop是关系符，如=v ,= ,=,舞等。 有的语言， 如 PL/1 ，允许更通用的表达式 ,其中，布尔算符，算术算符和关系算符可以施于 任何类型的表达式，并不区别布尔值和算术值，只不过在需要时执行强制变换。为简单起 见，我们只考虑如下文法生成的布尔表达式 .iE and E | E or E| not E|id rop id|true|false并且按通常习惯，约定布尔算符的优先顺序 (从高到低)为not、and、or,并且and和or服从左结合。8。 5。 1 布尔表达式的翻译方法 通常，计算布尔表达式的值有两种办法 ,第一种办法，如同计算算术表达式一样，步步 计算出各部分的真假值，最后计算出整个表达式的值。例如，用数值1表示true,用0表示false。那么布尔表达式 1 or (not 0 and 0) or 0的计算过程是：1 or(not 0 and 0)or 0=1 or(1 and 0) or 0=1 or 0 or 0=1 or 0=1另一种计算方法是采取某种优化措施，只计算部分表达式，例如要计算A or B ，若计算出 A 的值为 1，那么 B 的值就无需再计算了，因为不管 B 的值为何结果， A or B 的值都 为 1 。 个人收集整理，勿做商业用途上述两种方法对于不包含布尔函数调用的表达式是没有什么差别的。但是，假若一个 布尔式中会有布尔函数调用，并且这种函数调用引起副作用(如有对全局量的赋值 )时，这两种方法未必等价。采用哪种方法取决于程序设计语言的语义，有些语言规定，函数过程 调用应不影响这个调用处环境的计值，或者说，函数过程的工作不许产生副作用，在这种 规定下 ,可以任选其中一种。若按第一种办法计算布尔表达式。 布尔表达式 a or b and not c 翻译成的四元式序列为：(1) ti : =not c(2) t2 : =b and t1(3) t3 : =a or t2对于像av b这样的关系表达式，可看成等价的条件语句if a v b then 1else 0,它翻译成的四元式序列为：( 1) if av b goto ( 4)(2) t : =0( 3)goto (5 )( 4)t: =1(5) 其中用临时变量t存放布尔表达式av b的值，(5)为后续的四元式序号。图 8.11 给出了按第一种办法计算布尔表达式的值， 将布尔表达式翻译成四元式的描述 , 在该描述中使用了过程 newtemp和emit，其含义同前，过程 nextstat给出在输出序列中下 一四元式序号 ,emit 过程每被调用一次， nextstat 增加 1。 文档为个人收集整理，来源于网络 图 8。 11 用数值表示布尔值的翻译方案E 1 or E2 E. place : =newtemp ;emit(E . place : = E. place or2.Eplace)EE 1 and E2 E. place : =newtemp ;emit(E . place ： = E. place and. place)i not E1 E. place : =newtemp :;emit (E. place : = not1. Eplace)i (E1) E. place : =E1. placei id 1 relop id 2 E. place : =newtemp;emit ( if 1. i0lace relop id 2. place goto nextstat+3); emit (E. place ： = 0 );emit( goto nextstat+2emit (E. place ： = ) 1zi true E. place : =newtemp ;emit (E. place ： = ) 1i falseE . place : =newtemp; emit(E . place ： = )控制语句中布尔表达式的翻译现在讨论出现在if then ； if then else和while do等语句中的布尔表达式E的翻译。这三种语句的语法为：St if E then S 1|if E then S1 else S2 I while E do S 1这些语句的代码结构示意分别在图& 12 (a) (b) (c)中，其中使用。和。两个出口分别用于表示E为真和假时控制流向的转移。分别叫真出口和假出口。图8.12控制语句的代码结构biginE的代码工彳的代码口jiunp outjuirp beg in呼的代码1ffllt:(c) awhile E do S1代砚结构(b) if E then 51else SE 代码结构在控制语句中，布尔表达式E作为控制流转移的条件，仅把其翻译成一串条件转和无条件转的四元式代码。比如将布尔表达式E=a rop b翻译成四元式代码：if a rop b goto E . true 禾口goto E. false这里使用E. true和E. false分别表示布尔表达式E的”真”假”出口转移目标。下面将多处使用它们。对于E为E1 or E2的形式，若E1是真，则可知道 E为真即E1的真出口和E的真出口 一样。如果E1是假，那么必须计算 E2, E1的假出口应是E2代码的第一个四元式标号，这 时E2的真出口和假出口分别与E的真出口和假出口一样。类似的考虑适于E为E1 and E2的情形.E为not E1的翻译更容易，只需调换E1的真假出口即可得到 E的真假出口 .例如布尔表达式 a f翻译为如下四元式序列：(1) if a v b goto E. true(2) goto (3)(3) if c v d goto (5)(4) goto E. false(5) is e f goto E . true2)是不需要的。这种问题可留(6) goto E . false这样生成的四元式显然不是最优的，如四元式(待代码优化阶段解决在例8。3中，我们使用 E. true和E. false分别表示整个表达式 av b or cv d andef的真、假出口，而 E. true和E. false的值并不能在产生四元式的同时就知道。为了 看清这一点，我们把该表达式放在条件语句中考虑，如语句if a v b or c v d and e f then S1 else S 的四元式序列为(1) ifavbgoto (7)/*( 7)是整个布尔表达式的真出口*/(2) goto (3)(3) ifcv dgoto(5)(4) goto (p+1) 1*( p+1)是整个布尔表达式的假出口*/(5) if e f goto (7)(6) goto (p+1)(7) (关于S1的四元式)实际上，上述四元式(1)和(5), (4)和(6)的转移地址并不能在产生这些四元式的同时 得知。例如(1)和(5)的转移地址为(7),它是在整个布尔表达式的四元式序列生成之后 才回填的地址。为了记录需回填地址的四元式，常采用一种拉链”的办法。把需回填E. true 的四元式拉成一链，把需回填E. false的四元式拉成一链，分别称做真链和假链。用一个例子说明拉链是如何方式，若有四元式序列：(10)gotoE.true(20)gotoE.true(30)gotoE.true则把需回填E. true的四兀式（10）,（20）和（30）链成(10) goto(0)(20)goto(10)(30)goto(20)把地址（30）称作链首,0为链尾标志，即地址（10）为链尾。如何描述回填，我们不再介绍，有兴趣的同学可阅读参考书。8。 6 控制语句的翻译8.6.1 条件转移考虑 if then,if then else 和 while do 语句，在图 8。 12 中已给出了它们的代码结构。这 里我们使用下面文法 GS 定义这些语句 :GS(1) St if E then S(2) | if E then S else S(3) |while E do S(4) |beg in L end(5) |A( 6) LtL； S I S其中各非终结符号的意义是：s-语句L- 语句串A-赋值句E 布尔表达式回想在上一节 ,讨论控制语句中的布尔表达式的翻译时,使用 Etrue 和 Efalse 分别指出尚待回填”真、”假”出口的四元式串， 如对于条件语句if E then S1 else S2,在扫描到then 时才能知道E的”真”出口，而E的”假出口只有处理了 S1之后，到达else时才明确即是说， 必须将E. false的值传下去，以便到达相应的else时才进行回填。另外，E为真时，S1语句执行完时意味着整个if then else语句也已执行完毕，因此应在S1之后产生一无条件转指 令，将控制离开整个if then else语句.但在完成S2的翻译之前，该无条件转的转移目标无 法知道对于语句嵌套的情况，如下面的语句：if E1 then if E then S1 else S2 else S3,在翻译完S2之后,S1后的无条件转移目标仍无法确定，因为它不仅要跨越 S2还应跨越S3。看出，转移目标的确定和语句所处的环境密切相关 因此仿照处理布尔表达式的办法，让非终结符S (和L)含有一项语义值 S. CHAIN (和L. CHAIN )。也是一条链，它把所有那些四元 式串在一起，这些四元式期待在翻译完S( L)之后回填转移目标。真正的回填工作将在处理 S 的外层环境的某一适当时候完成 按照上述文法产生式相应的语义动作，加上前述关于赋值句和布尔表达式的翻译法， 语句while (A v B) do if (Cv D) then X : =Y+Z将被翻译成如下的一串四元式：100 if AvB goto 102101 goto 107102 if Cv D goto 104103 goto 100104 T: =Y+Z105 X : =T106 goto 100107 个人收集整理，勿做商业用途8。 6。 2 开关语句开关语句( case 语句或 switch 语句 )是很多程序设计语言中都有的，方式不尽相同,甚至FORTRAN中的计算GOTO和赋值GOTO也可看做是一种开关语句.我们假定要讨论的开关语句的形式为：switch E ofcase Vi: Sicase V2： S2case Vn1: Sn1default: Snend这里的E是一个表达式，也称为选择子。开关语句是分情形选择机制，在E被计算之后，测试它的值符合哪种 case中的值，而执行和该值相关的语句 ，并做相应的转移如果E 的值不能与任何 Vi(i i w 1匹配，便执行default时的语句。直观上看，case语句翻译成如下的一连串条件转移语句。t : =E ；Li： if t 并goto L2;Si；goto next;L2：if t2?goto L3；S2goto next;Ln-i : if t 齐iVgoto Ln；Sn-1 ；goto next;Ln: Sn；next:& 6.3 for循环语句除了 while do语句外，很多程序设计语言具有下面形式的循环语句：for i : =EI step E2 until E3 do Si为了简单起见，假定 E2总是正的.在这种假定下，上述循环句的意义等价于：i : =EI ;goto OVER ;AGAIN : i : =i+E2;OVER : if i w E3 thenbegin Si; goto AGAIN end ;8.6.4 goto 语句多数程序语言中的转移是通过标号和goto语句实现的。带标号语句的形式是L : S;goto语句的形式是goto L 0当L : S;语句被处理之后，标号L是定义了 ”的。即在符号表中，将登记 L的项的”地址栏中登上语句S的第一个四元式的地址。如果goto L是一个向上转移的语句， 那么，当编译程序碰到这个语句时 丄必是已定义 了的。通过对L查找符号表获得它的定义地址 p,编译程序可立即产生出相应于这个 goto L 的四兀式如(j, , , P)O如果goto L是一个向下转移的语句，也就是说，标号L尚未定义，那么，若L是第一一次出现，则把它填进符号表中并标志上未定义”。由于L尚未定义对goto L只能产生一个不完全的四元式(goto -),它的转移目标须待 L定义时再回填进去。在这种情况下，必 须把所有那些以L为转移目标的四元式的地址全都记录下来，以便一旦L定义时就可对这些四元式进行回填我们将采用如图8.13所示的拉链办法，把所有以L为转移目标的四元式串在一起。链的首地址放在符号表中L的地址栏中.建链的方法是：若 goto L中的标号L尚未在符号表中出现，则把L填入表中，置 L的”定义否标志为未”，把nextstat填进L的地址栏中作为新链首，然后产生四元式(goto 0)，其中0为链尾标志若L已在符号表中出现(但”定义否”标志为”未”)，则