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

1、第八章 语法制导翻译和中间代码生成课前索引【课前思考】 回顾第一章介绍的编译过程，理解语义分析在编译过程中的位置和作用。什么是中间表示（中间代码），为什么要中间表示？ "语法制导翻译 "是什么含义？ 高级语言语句的结构和低级语言结构的不同。【学习目标】明确语义分析在编译过程所处的阶段和作用。掌握属性文法的基本概念。使用属性文法和语法制导翻译方法描述具体的语义分析和产生中间代码。【学习指南】紧接在词法分析和语法分析之后， 编译程序要做的工作就是进行静态语义检查和翻译。静态语义检查通常包括：类型检查，控制流检查，一致性检查，相关名字检查及名字的作 用域分析等等。虽然源程序可以直

2、接翻译为目标语言代码，但是许多编译程序都采用了独 立于机器的，复杂性介于源语言和机器语言之间的中间语言。其好处便于进行与目标机无 关的代码优化，也使得编译的前后端接口清晰，编译程序结构在逻辑上更简明。【难重点】 翻译时源语句到目标语句结构上的变换。语法制导翻译实现的方法。 Yacc 和语法制导翻译。【知识结构】编译程序的任务是把源程序翻译成目标程序，这个目标程序必须和源程序的语义等 同，也就是说，尽管它们的语法结构完全不同，但它们所表达的结果应完全相同。通常， 在词法分析程序和语法分析程序对源程序的语法结构进行分析之后，要么由语法分析程序 直接调用相应的语义子程序进行语义处理，要么首先生成语法

3、树或该结构的某种表示，再 进行语义处理。编译中的语义处理是指两个功能：第一，审查每个语法结构的静态语义，即验证语法 结构合法的程序是否真正有意义。有时把这个工作称为静态语义分析或静态审查。第二， 如果静态语义正确，语义处理则要执行真正的翻译，即，或者将源程序翻译成程序的一种 中间表示形式（中间代码） ，或者将源程序翻译成目标代码。本章引入属性文法和语法制导翻译方法的基本思想，介绍几种典型的中间代码形式， 最后讨论一些语法成分的翻译工作。静态语义分析 通常包括： 类型检查。验证程序中执行的每个操作是否遵守语言的类型系统的过程.，编译程序必须报告不符合类型系统的信息。 控制流检查。控制流语句必须使

4、控制转移到合法的地方。例如，在 C 语言中 break 语句使控制跳离包括该语句的最小 while 、 for 或 switch 语句。如果不存在包括它的这样的 语句，则就报错。 一致性检查。在很多场合要求对象只能被定义一次。例如Pascal 语言规定同一标识符在一个分程序中只能被说明一次，同一case语句的标号不能相同，枚举类型的元素不能重复出现等等。 相关名字检查。有时，同一名字必须出现两次或多次。例如， Ada 语言程序中， 循环或程序块可以有一个名字，出现在这些结构的开头和结尾，编译程序必须检查这两个 地方用的名字是相同的。 名字的作用域分析所谓 中间代码 ，也称中间语言， 是复杂性介

5、于源程序语言和机器语言的一种表示形式。 为什么有的编译程序直接生成目标代码，有的编译程序采用中间代码。一般，快速编译程 序直接生成目标代码，没有将中间代码翻译成目标代码的额外开销。但是为了使编译程序 结构在逻辑上更为简单明确，常采用中间代码，这样可以将与机器相关的某些实现细节置 于代码生成阶段仔细处理，并且可以在中间代码一级进行优化工作使得代码优化比较容易 实现。8.1 属性文法语义形式化是个专门的研究课题，目前有各种各样的方法和记号不断推出，例如操作 语义学、公理语义学和指称语义学。语义形式化 （语义建模 ）有几种模型 文法模型 属性文法 命令式或操作式模型 操作语义学 应用式模型 指称语义

6、学 公理式模型 公理语义学 规格说明模型 代数数据类型属性文法将在我们的讲义中介绍。操作语义描述一段程序的含义是通过执行该段程序 所改变的计算机（无论是真实计算机还是虚拟计算机）状态来反映。计算机里所有的寄存 器的值和存储单元的值作为计算机的状态。For （expr1;expr2;expr3） 的操作语义表示： expr1;Loop:if expr2=0 goto out xpr3;goto loopout:. 公理语义概念是随着程序正确性的证明而发展的。当正确性证明能构造时表明程序执 行它的规格说明所描述的计算。在一个证明中，每一个语句之前之后都有一个逻辑表达式 对程序的变量进行约束 ,以此

7、说明这个语句的含义。一般的记号是P S Q 。指称语义的基本概念是给每一段程序实体定义一个数学意义上的对象，和一个从实体 实例向数学意义对象的映射的函数。规格说明模型通过描述实现一个程序的各种函数间的关系来说明语义。如表明一个实 现服从任何两个函数间的这种关系，则可以声明这个实现是此规格说明的正确实现。不论哪种方法，其本身的符号系统比较繁杂，其描述文本不易读，目前编译程序尚不 便借助这些形式系统自动完成语义处理任务。现在很多编译程序采用语法制导翻译方法。 这仍不是一种形式系统，但它是比较接近形式化的。这种方法使用属性文法为工具来说明 程序设计语言的语义。一个属性文法包含一个上下文无关文法和一系

8、列语义规则，这些语 义规则附在文法的每个产生式上，在语法分析过程中，完成这些语义规则描述的动作，从 而实现语义处理。首先简单介绍属性文法。 所谓属性，其涉及的概念比较广泛，常用以描述事物或人的特征、性质，品质等等。 比如，谈到一个物体，可以用 "颜色 "描述它，谈起某人，可以使用 "有幽默感 "来形容他。 对编译程序使用的语法树的结点，可以用 "类型 "、"值"或"存储位置 "来描述它。属性文法 （也称属性翻译文法 ）是 Knuth 在 1968 年首先提出的。 它是在上下文无关文法的基 础上，

9、为每个文法符号 （终结符或非终结符 ）配备若干相关的 " 值"（称为属性） 。这些属性代 表与文法符号相关信息，例如它的类型、值、代码序列、符号表内容等等。属性与变量一 样，可以进行计算和传递。属性加工的过程即是语义处理的过程。对于文法的每个产生式 都配备了一组属性的计算规则，称为语义规则。形式上讲，一个属性文法是一个三元组， A（ G，V，F），一个上下文无关文法 G；一个属性的有穷集 V 和关于属性的断言或谓 词的有穷集 F。每个断言与文法的某产生式相联。 如果对 G 中的某一输入串而言 （句子） A 中的所有断言对该输入串的语法树结点的属性全为真，则该串也是 A 语言

10、中的句子。编 译程序的静态语义审查工作就是验证关于所编译的程序的断言是否全部为真。比如，有文法 G 为：ET1 + T2|T1 or T2Tnum|true|false（因为 T 在同一个产生式里出现了两次，使用上角标将它们区分开。） 对输入串 3+4 的语法树如图 81（A ）图 8 1 静态语义审查属性文法记号中常使用 NT 的形式表示与非终结符 N 相联的属性 t。比如可把对上面 表达式的类型检查的属性文法写成图82的形式。与每个非终结符 T 相联的有属性 t，t要么是 int，要么是 bool。与非终结符 E的产生式相联的断言指明：两个 T 的属性必须相 同。图 81 的（ b）是图

11、8.1（a）语法树结点带有语义信息的表示。图 82 类型检查的属性文法1 2 12ET1+T 2 T 1.t int AND T2.tint1 2 12ET1orT 2 T 1.tbool ATD T 2.t boolT numT.t intT trueT.t boolT falseT.t bool属性文法中的属性分成两类： 继承属性和综合属性， 简单地说， 综合属性用 "自上而上 " 传递信息，而继承属性用于 "自上而下 "传递信息。在一个属性文法中，对应于每个产生式Aa 都有一套与之相关联的语义规则，每条规则的形式为b := f （c 1,c2, c

12、k）这里， f 是一个函数，而且或者（1）b是 A的一个综合属性并且 c1,c2, ck是产生式右边文法符号的属性：或者（2）b是产生式右边某个文法符号的一个继承属性并且c1,c2, ck是A 或产生式右边任何文法符号的属性。在两种情况下，我们都说属性 b 依赖于属性 c1,c2, ck。我们不对属性文法进行理论上的研究而仅仅将它做为工具描述语义分析。在编译的许 多实际应用中，属性和断言以多种形式出现，也就是说，与每个文法符号相联的可以是各 种属性、断言、以及语义规则，或者某种程序设计语言的程序段等等。一般说来，对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提 供一个计算规则。

13、属性计算规则中只能使用相应产生式中的文法符号的属性，这有助于在 产生式范围内 "封装 "属性的依赖性。然而，出现在产生式左边的继承属性和出现在产生式 右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规 则计算或者由属性计算器的参数提供。语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码生成等 等。语义规则可能产生副作用 （如产生代码） ，也可能不是变元的严格函数 （如某个规则给 出可用的下一个数据单元的地址） 。这样的语义规则通常写成过程调用或过程段。 下面再给 出一些例子。f8-1-1.swf 在该描述中，每个非终结符都有一个

14、属性：一个整数值的称作 val 的属性。按照语义 规则对每个产生式来说，它的左部 E，T，F 的属性值的计算来自它右部的非终结符，这种 属性称作综合属性。 单词 digit 仅有综合属性， 它的值是由词法分析程序提供的。和产生式 LE相联的语义规则是一个过程，打印由 E产生的表达式的值。我们可以理解为 L 的属 性是空的或是虚的。例 8.2 中的文法定义了一种说明语句，该说明语句的形式是由关键字 int 或 real 开头， 后面是一个标识符表，每个标识符由逗号隔开。非终结符 T 有一个综合属性 type，它的值 由关键字决定 （int 或 real）。与产生式 DTL 相联的语义规则 L.i

15、n T.type 将 L.in 的属 性值置为该说明语句指定的类型。属性 L.in 将被沿着语法树传递到下边的结点使用，与 L 产生式相联的规则里使用了它。例 8.2描述说明语句中各种变量的类型信息的语义规则，这个例子里，继承属性在说明 中为各个标识符提供类型信息。产生式语义规则（1）DTLL.in T.type（2）Tint T.Type integer（3）Treal T.Type real（4）LL1，id L 1.in L.inaddtype（ id.entry ， L.in ） （5）Lidaddtype （ id.entry ， L.in ）图 8.3 是句子 intid 1,id

16、2 的语法树，使用 表示属性的传递情况。在语法树中，一个结 点的继承属性由此结点的父结点和 /或兄弟结点的某些属性确定。 与 L 产生式相联的语义规 则中有一个过程调用 addtype，过程 addtype 的功能是把每个标识符的类型信息登录在符号 表的相关项中。图 8.3 属性信息传递情况属性文法看作是允许为每个终结符和非终结符配备一些属性的文法。它既能描述程序 设计语言的语法， 又为语义处理提供了方便 .属性文法里的属性有不同的类型， 可以象变量 一样地被赋值。赋值规则附加于语法规则之上。赋值与语法同时进行，赋值过程就是语义 处理过程。在推导语法树的时候，诸属性的值被计算并通过赋值规则层层

17、传递。有的从语 法规则左边向右边传，有的从右边向左边传。语法推导树最后完成时，就得到开始符号的 属性值。也就是整个程序的语义。立身以立学为先，立学以读书为本8.2 语法制导翻译编译程序的整个任务就是把源程序翻译为目标程序。实际上每个编译阶段都可以看成 是完成一定的翻译任务：词法分析阶段把字符流翻译为单词流，语法分析阶段把单词流翻 译为语法树，目标代码生成阶段把语法树翻译为汇编语言等等。在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序(或 语义规则描述的语义动作)进行翻译的办法称作语法制导翻译。假如我们要把中缀算术表达式翻译为后缀波兰表示形式(后缀波兰表示形式参见 8.3.

18、1)，给出如下语义描述：11E T + E 1 E.code=T.code| E 1.code|+ E T E.code=T.code 11TF * T 1 T.code=F.code|T 1.code| * T F T.code =F.code F (E ) F.code = E.code F a F.code = a 其中使用 E.code，T.code 和 F.code 分别表示相应的后缀式， "|" 表示后缀式的连接。如 果对于输入串 a+a*a 采用最左分析，其形成的推导过程为：E T+E F+E a+E a+T a+T* F a+F*F a+a*F a+a*a(

19、 ， ), 是输入句子和句型， 是翻译的输出形式，则有：(E,E.code) (T+E, T.code|E.code|+) T (F+E, F.code|E.code|+)(a+E, a|E.code|+)(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*+假定我们现在要分析的语法成分是简单算术表达式，所完成的语义处理不是将它翻译 成中间代码或是目

20、标代码， 而是计算表达式的值。 采用的描述系统是上节的例 8.1。假如语 法分析方法是自下而上的。在用某一产生式进行归约的同时就执行相应的语义动作，在分 析出一个句子时，这个句子的 "值"也就同时产生了，例如输入串是2+3*5 ，其语法树如图8.4( a)，在第一步归约用到了产生式( 6)，执行的语义动作是置 F val 的值为单词 digit 值，我们把语法树中每个结点的语义值括在该结点处。那么第一步归约并完成语义动作后 的情形在图 8.4( b)中指出。继续进行分析，第七次归约后的情形在图8.4(c)中指出。归约至 E时，它的值 17 也计算出来了。图 8.4 语法制导

21、方法计算表达式这里再给出一种翻译模式，也是把中缀形式的算术表达式映射到后缀波兰表示：E T + E E=TE+ E T E=T T F * T T=FT * T F T =F F（E） F = E F a F = a 句子 a+a*a 的一个推导过程：ET+EF+Ea+Ea+Ta+F*Ta+a*Ta+a*Fa+a*a伴随着句子 a+a*a 的这个推导过程 ,按照上述翻译模式所进行的一步步翻译：ETE+FE+aE+aT+aFT*+aaT*+aaF*+aaa*+语法制导翻译的具体实现途径不困难。假定有一个 LR 语法分析器，现在把它的分析栈扩充，使得每个文法符号都跟有语义值，即把栈的结构看成图8.

22、5 所示那样。图 8.5 扩充的分析栈Smy,ValySm-1x,Valx.S0-#状态栈语义值符号栈图 8.6 LR 分析表状态ACTION （动作）GOTO （转换）d+()#ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108r6s119r1s7r1r110r3r3r3r311r5r5r5r5同时把 LR 分析器的能力扩大， 使它不仅执行语法分析任务， 且能在用某个产生式进行 归约的同时调用相应的语义子程序，完成在例8.1 的属性文法中描述的语义动作。每步工作后的语义值保存在扩充的分析栈里 "语义

23、值 "栏中。采用的 LR 分析表见图 8.6，其中使用d 代替 digit 。分析和计值 2+3*5 的过程列在图 8.7 中。 图 8.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#6016-2-#E+3*5#70165-2-#E+3*5#8r60163-2-3#E+F*5#9r40169-2-3#E+T*5#1001697-2-3-#E+T·5#11016975-2-3-#E+T·5#12r601697

24、（10）-2-2-5#E+T·F#13r30169-2-（15）#E+T#14t101（17）#E#15接受按照上述实现办法，若把语义子程序改为产生某种中间代码的动作，那么则可在语法 分析的制导下，随着分析的进展逐步生成中间代码。8.3 中间代码的形式编译程序所使用的中间代码有多种形式。常见的有逆波兰记号、三元式、四元式和树 形表示。下面分别将它们做一介绍。8.3.1 逆波兰记号 逆波兰记号是最简单的一种中间代码表示形式，早在编译程序出现之前，它就用于表 示算术表达式，是波兰逻辑学家卢卡西维奇发明的。这种表示法将运算对象写在前面， 把运算符号写在后面， 比如把 a+b写成 ab+，把

25、 a*b 写成 ab*，用这种表示法表示的表达式也称做后缀式。图 8.8 给出了程序设计语言中的简单表达式和赋值语句相应的逆波兰表示形式：图 8.8 逆波兰表示程序设计语言中的表示逆波兰表示a+bab+a+b*cabc*+(a+b)*cab+c*a;=b*c+b*dabc*bd*+:=后缀表示法表示表达式，其最大的优点是易于计算机处理表达式。常用的算法是使用 一个栈，自左至右扫描算术表达式（后缀表示），每扫描到运算对象，就把它推进栈；扫 描到运算符，若该运算符是二目的，则对栈顶部的两个运算对象实施该运算，并将运算结 果代替这两个运算对象而进栈；若是一目运算符，则对栈顶元素执行该运算，并以运算结

26、 果代替该元素进栈，最后的结果留在栈顶。例如 BCD*+ （它的中缀表示为 B+C*D ，使用 表示一目减）的计值过程为：1. B 进栈；2. 对栈顶元素施行一目减运算，并将结果代替栈顶，即 B 置于栈顶；3. C 进栈；4. D 进栈；5. 栈顶两元素相乘，两元素退栈，相乘结果置栈顶；6. 栈顶两元素相加， 两元素退栈， 相加结果进栈， 现在栈顶存放的是整个表达式的值。由于后缀式表示上的简洁和计值的方便，特别适用于解释执行的程序设计语言的中间 表示，也方便具有堆栈体系的计算机的目标代码生成。逆波兰表示很容易扩充到表达式以外的范围。在图 8.8 中已见到了赋值语句的后缀表 示的例子。只要遵守运

27、算对象后直接紧跟它们的运算符的规则即可。比如把转语句 GOTO L 写为 "L jump" ，运算对象 L 为语句标号，运算符 jump 表示转到某个标号。再比如条件语 句 if E then S1 else S2 可表示为： ES1S2￥，把 if then else 看成三目运算符，用￥来表示。又 如数组元素 A 下标表达式 1， 下标表达式 n可表示为下标表达式 1下标 表达式 2 下标表达式 nA subs，运算符 Subs 表示求数组的下标。当然，这些扩充的后缀表示的计值远比后缀表达式的计值复杂得多，要注意对新添加 的运算符的含义正确处理。以图 8.8 中的赋值语

28、句为例，当计算到 =时，执行的是将表达 式 B*C+B*D 的值送到变量 a，所以，而在执行完赋值后，栈中并不产生结果值，这与算术的二目运算符是不一样的，另外，因为需要的是a的地址，而不是 a 的值，这也必须注意到。8.3.2 三元式和树形表示 另一类中间代码形式是三元式。把表达式及各种语句表示成一组三元式。每个三元式 由三个部分组成，分别是：算符 op，第一运算对象 ARG1 和第二运算对象 ARG2 。运算对 象可能是源程序中的变量，也可能是某个三元式的结果，用三元式的编号表示。例如a=b*c+b*d 的表示为：（1）（ * ， b，c）（2）（ * ， b，d）（3）（ + （1）， （

29、2）（4）（ （ 2）， a）与后缀式不同，三元式中含有对中间计算结果的显式引用，比如三元式（1）表示的是 b*c 的结果。三元式（ 3）中的（ 1）和（ 2）分别表示第一个三元式和第二个三元式的结 果。对于一目算符 op，只需选用一个运算对象，不妨规定只用ARG1 。至于多目算符，可用若干个相继的三元式表示。树形表示是三元式表示的翻版。上述三元式可表示成下面的树表示：表达式的树形表示很容易实现：简单变量或常数的树就是该变量或常数自身，如果表达式 e1和 e2的树分别为 T1和 T2，那么 e1+e2，e1*e2，e1的树分别为：二目运算对应二叉子树，多目运算对应多叉子树，不过，为了便于安排存

30、储空间，一 棵多叉子树可以通过引进新结而表示成一棵二叉子树。8.3.3 四元式四元式是一种比较普遍采用的中间代码形式。四元式的四个组成成分是：算符op，第一和第二运算对象自己定义的变量，ARG1 和 ARG 及运算结果 有时指编译程序引进的临时变量。RESULT 。运算对象和运算结果有时指用户 例如 a =b*c+b*d 的四元式表示如下（1）（*，b，c，t1)（2）（*，b，d，t2)（3）（+，t1，t2，t3)（4）（=，t3，a）四元式和三元式的主要不同在于，四元式对中间结果的引用必须通过给定的名字，而 三元式是通过产生中间结果的三元式编号。也就是说，四元式之间的联系是通过临时变量

31、实现的。也许读者已经发现，四元式表示很类似于三地址指令，确实，有时把这类中间表示称 为" 三地址代码 "，因为这种表示可看作一种虚拟三地址机的通用汇编码，即这种虚拟机的 每条 "指令"包含操作符和三个地址，两个是为运算对象的，一个是为结果的。这种表示对 于代码优化和目标代码生成都较有利。有时，为了更直观，也把四元式的形式写成简单赋值形式或更易理解的形式。比如把上述四元式序列写成：（1）t1=b*c（2）t2=b*d（3）t3=t1+t2（4）a=t3把（ jump， L ）写成 goto L 把（ jrop， B，C，L）写成 if B rop C go

32、to L 本书中，为了叙述的方便，两种形式将同时使用。 如何用四元式表示各种语句， 以及翻译各种语句的语义描述， 将在后面各节陆续讨论。 为了复习与巩固一下前面所学习的几种中间代码的形式，下面举一个例子，分别用几 种中间代码的形式来表示例 : A + B * （ C - D ） + E / （ C - D ） N 四元式：1）（-CD T1 )2）（*BT1T2)3）（+AT2T3)4）（CDT4)5）（T4NT5)6）（/ET5T6)7）（+T3T6T7)三元式：1）（CD）2）（*B（1）3）（+A（2）4）（CD）5）（4）N）6）（/E（5）7）（+（3）（6）间接三元式：间接三元式序

33、列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 表示的单词定义一属性 idname

34、，用做语义变量， 用 Lookup（ idname） 表示审查 idname 是否出现在符号表中， 如在，则返回一指向该登录项的指针，否则返回 nil 。语义过程 emit 表示输出四元式到输出文件上。 语义过程 newtemp 表示生成一个临时变 量，每调用一次，生成一新的临时变量。语义变量E place，表示存放 E 值的变量名在符号表的登录项或一整数码（若此变量是一个临时变量）图 8.9 列出了翻译赋值语句到四元 式的语义描述。这里的语义工作包括对变量进行 " 先定义后使用 "的检查。图 8.9 赋值语句的四元式翻译（1） S id =E p =lookup （ id

35、 name）；if p nil thenEmit ( p =E place) else error(2) EE1+E2 E place=newtemp；2+pElace) Emit(Eplace =1E.place 12(3) EE1*E 2 E placeE=newtemp ；Emit(Eplace =1Eplace *2Eplace) (4) E1E1 E placeE=newtemp ；Emit(Eplace =uminu1spElace ) (5) E1(E1) E place1=E1 place(6) E id p:=lookup( id name) ；if p nil thenE

36、placeE =p else error实际上，在一个表达式中可能会出现各种不同类型的变量或常数，而不是像图 8.9 中 的 id 假定为都是同一类型。也就是说，编译程序还应执行这样的语义动作：对表达式中的 运算对象应进行类型检查，如不能接受不同类型的运算对象的混合运算，则应指出错误； 如能接受混合运算，则应进行类型转换的语义处理。假如，图 8.9 中的表达式可以有混合 运算， id 可以是实型量也可以是整型量，并且约定，当两个不同类型的量进行运算时，必 须首先将整型量转换为实型量。为进行类型转换的语义处理，增加语义变量，用 E type 表示 E 的类型信息， E type的值或为 int

37、或为 real，此外，为区别整型加（乘）和实型加 （乘），把+（* ）分别写作 +i（ * i）和+r（* r）。用一目算符 itr 表示将整型运算对象转换成实 型。这样，图 8.9 中的第（ 3）条产生式及其有关语义描述如图8.10。图 8.10 类型转换的语义处理产生式 语义动作12EE *EE place =newtemp ；if E 1 type int AND E 2 type int then1 i 2begin emit （ E.place， =， E place，*, E place）；E type =intend12else if E type real AND E type

38、 real then begin emit （E place, = ,1Eplace, r*,2Eplace）;E type =realend12else if E type int/* and E type=real */ then begin t =newtemp；emit（ t， =， it，r E1place）；emit（ Eplace，=，t，r*，E2place）；Etype =realend12else /*E ·type real and E type int*/begin t =newtemp；emit（ t， =； it，r E2place）；emit（ Epla

39、ce，=，E1 place， r*）,t；Etype =realend；图 8.9 中的例子里，与非终结符 E 相联的语义值有 Eplace，还有 E type。语义 值的设计是与语义处理的描述相关的。 大家回顾一下 PL/0 编译程序中对赋值语句的语义处 理，其中对赋值语句左部的标识符，检查它的种类（ kind ），若不是变量名，则指出错误， 若是变量名，才生成赋值运算的代码。对右部表达式中作为运算对象的标识符，检查其是 否变量名或常量名，是，生成相应代码，不是（即是过程名），则指出错误。这一点若用 语义规则描述的话，还应增加一语义值，与非终结符相联，比如用E kind 表示。赋值语句中会含

40、有复杂数据类型，如数组元素、记录（结构）的引用。这种情况的翻 译工作要复杂些，我们将在后面给予专门讨论。8.5 布尔表达式的翻译程序设计语言中的布尔表达式有两个作用。一是计算逻辑值，更多的情况是二，用做 改变控制流语句中的条件表达式，如在if-then ， if-then-else ，或是 while-do 语句中那样。布尔表达式是由布尔算符 and， or 和 not 施于布尔变量或关系表达式而成。即布尔表 达式的形式为 E1 rop E 2，其中 E1 和 E2 都是算术表达式， rop 是关系符，如<， ， 等等。有的语言，如 PL/1，允许更通用的表达式，其中，布尔算符，算术算符

41、和关 系算符可以施于任何类型的表达式，并不区别布尔值和算术值，只不过在需要时执行强制 变换。为简单起见，我们只考虑如下文法生成的布尔表达式。E E 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

42、 0 and 0） or 0 的计算过程是：1 or（ not 0 and 0） or 01 or（1 and 0）or 0 1 or 0 or 0 1 or 01另一种计算方法是采取某种优化措施，只计算部分表达式，例如要计算A or B ，若计算出 A 的值为 1，那么 B 的值就无需再计算了，因为不管 B 的值为何结果， A or B 的值都 为 1。上述两种方法对于不包含布尔函数调用的表达式是没有什么差别的。但是，假若一个 布尔式中会有布尔函数调用，并且这种函数调用引起副作用（如有对全局量的赋值）时， 这两种方法未必等价。采用哪种方法取决于程序设计语言的语义，有些语言规定，函数过 程调用

43、应不影响这个调用处环境的计值，或者说，函数过程的工作不许产生副作用，在这 种规定下，可以任选其中一种。若按第一种办法计算布尔表达式。 布尔表达式 a or b and not c 翻译成的四元式序列为：（ 1） t1 =not c（ 2） t2 =b and t1（ 3） t3 =a or t2对于像 a<b 这样的关系表达式，可看成等价的条件语句if a< b then 1else 0，它翻译成的四元式序列为：（ 1） if a<b goto （ 4）（ 2） t=0（ 3） goto （ 5）（ 4） t=1（ 5） 其中用临时变量 t 存放布尔表达式 a< b的值

44、， （5）为后续的四元式序号。图 8.11 给出了按第一种办法计算布尔表达式的值， 将布尔表达式翻译成四元式的描述， 在该描述中使用了过程 newtemp 和 emit ，其含义同前，过程 nextstat 给出在输出序列中下 一四元式序号， emit 过程每被调用一次， nextstat 增加 1。图 8.11 用数值表示布尔值的翻译方案12EE1 or E2 E place=newtemp ； emit （ E place =E1 place or 2Eplace）12EE1 and E2 E place =newtemp ； emit （ E place =E1 place and2Ep

45、lace） Enot E 1 E place =newtemp ：； emit （ E place =not1Eplace） E（E1）1 E place=E placeE id 1 relop id 2E place =newtemp；emit （ if 1idplace relop id 2nextstat+3）；emit （ E place =）0；emit （ goto nextsta）t+；2 emit （ E place =）1EtrueE place=newtemp ； emit （ E place =）1 Efalse E place =newtemp； emit （ E pl

46、ace =）08.5.2 控制语句中布尔表达式的翻译现在讨论出现在 if then ； if then else 和 while do 等语句中的布尔表达式 E 的翻译。 这三种语句的语法为：1 1 2 1Sif E then S 1|if E then S1 else S2|while E do S1 这些语句的代码结构示意分别在图8.12（a）（ b）（c）中，其中使用 .和。两个出口分别用于表示 E 为真和假时控制流向的转移。分别叫真出口和假出口。图 8.12 控制语句的代码结构在控制语句中 , 布尔表达式 E 作为控制流转移的条件，仅把其翻译成一串条件转和无条件转的四元式代码。比如将布

47、尔表达式 E=a rop b 翻译成四元式代码：if a rop b goto E true 和goto E false这里，使用 Etrue和 Efalse 分别表示布尔表达式 E的"真""假"出口转移目标。下面 将多处使用它们。对于 E为 E1 or E2的形式，若 E1是真，则可知道 E为真即 E1的真出口和 E 的真出口 一样。如果 E1 是假，那么必须计算 E2，E1的假出口应是 E2代码的第一个四元式标号，这 时 E2 的真出口和假出口分别与 E 的真出口和假出口一样。类似的考虑适于 E 为 E1 and E2 的情形。 E 为 not E1

48、 的翻译更容易，只需调换 E1 的 真假出口即可得到 E 的真假出口。例如布尔表达式 a<b or c<d and e>f 翻译为如下四元式序列：例 8.31）if a<b goto E true2）goto （3）3）if c< d goto （5）4）goto E false5）is e>f goto E true6）goto E false这样生成的四元式显然不是最优的，如四元式（2）是不需要的。这种问题可留待代码优化阶段解决。在例 8.3 中，我们使用 Etrue 和 Efalse 分别表示整个表达式 a< b or c<d and e

49、>f 的真、假出口，而 Etrue和 Efalse 的值并不能在产生四元式的同时就知道。为了看 清这一点，我们把该表达式放在条件语句中考虑，如语句 if a<b or c<d and e>f then S1 else S2的四元式序列为（1）if a< b goto（7）/* （7）是整个布尔表达式的真出口*/（2）goto （ 3）（3）if c< d goto（5）（4）goto （p+1） /* （p+1）是整个布尔表达式的假出口 */（5）if e> f goto（7）（6）goto （ p+1）（ 7） （关于 S1 的四元式）实际上，上述四

50、元式（1）和（ 5），（ 4）和（ 6）的转移地址并不能在产生这些四元式的同时得知。例如（ 1）和（5）的转移地址为（ 7），它是在整个布尔表达式的四元式序列生成之后才回填的地址。为了记录需回填地址的四元式，常采用一种" 拉链 "的办法。把需回填 Etrue 的四元式拉成一链，把需回填 Efalse 的四元式拉成一链，分别称做 "真 "链和 "假"链。用一个例子说明拉链是如何方式，若有四元式序列：10） gotoEtrue20） gotoEtrue30） gotoEtrue则把需回填 Etrue 的四元式（ 10），（ 20）和（ 3

51、0） 链成（ 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）S if E then S（2）| if E then S else S（3）| while E do S（4）| begin L end（5）|A（6）LL； S（7

52、）|S其中各非终结符号的意义是：S-语句L- 语句串A- 赋值句E-布尔表达式回想在上一节，讨论控制语句中的布尔表达式的翻译时，使用E true 和 E false 分别指出尚待回填 "真、"假"出口的四元式串，如对于条件语句 if E then S1 else S2，在扫描到 then 时才能知道 E 的"真"出口，而 E 的"假"出口只有处理了 S1 之后，到达 else时才明确。 即是说，必须将 E false的值传下去，以便到达相应的 else时才进行回填。另外， E 为真 时， S1语句执行完时意味着整个 if t

53、hen else语句也已执行完毕，因此应在 S1之后产生一 无条件转指令， 将控制离开整个 if then else 语句。 但在完成 S2 的翻译之前， 该无条件转的 转移目标无法知道。 对于语句嵌套的情况， 如下面的语句： if E1 then if E then S1 else S2 else S3，在翻译完 S2之后， S1后的无条件转移目标仍无法确定， 因为它不仅要跨越 S2 还应跨 越 S3。看出，转移目标的确定和语句所处的环境密切相关。因此仿照处理布尔表达式的办 法，让非终结符 S（和 L）含有一项语义值 SCHAIN （和 L CHAIN ）。也是一条链，它 把所有那些四元式串在一起，这些四元式期待在翻译完S（ L）之后回填转移目标。真正的回填工作将在处理 S 的外层环境的某一适当时候完成。按照上述文法产生式相应的语义动作，加上前述关于赋值句和布尔表达式的翻译法， 语句while （A<B） do if （C<D） then X =Y+Z将被翻译成如下的一串四元式：100if A < B goto 10