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

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

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

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

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

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

6、义描述一段程序的含义是通过执行该段程序所改变的计算机（无论是真实计算机还是虚拟计算机）状态来反映。计算机里所有的寄存器的值和存储单元的值作为计算机的状态。For (expr1;expr2;expr3) 的操作语义表示： expr1;. Loop:if expr2=0 goto out xpr3;goto loopout:.公理语义概念是随着程序正确性的证明而发展的。当正确性证明能构造时表明程序执行它的规格说明所描述的计算。在一个证明中，每一个语句之前之后都有一个逻辑表达式对程序的变量进行约束,以此说明这个语句的含义。一般的记号是P S Q。指称语义的基本概念是给每一段程序实体定义一个数学意义上

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

8、。首先简单介绍属性文法。所谓属性，其涉及的概念比较广泛，常用以描述事物或人的特征、性质，品质等等。比如，谈到一个物体，可以用颜色描述它，谈起某人，可以使用有幽默感来形容他。对编译程序使用的语法树的结点，可以用类型、值或存储位置来描述它。属性文法(也称属性翻译文法)是Knuth在1968年首先提出的。它是在上下文无关文法的基础上，为每个文法符号(终结符或非终结符)配备若干相关的值（称为属性）。这些属性代表与文法符号相关信息，例如它的类型、值、代码序列、符号表内容等等。属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则

9、。形式上讲，一个属性文法是一个三元组，A（G，V，F），一个上下文无关文法G；一个属性的有穷集V和关于属性的断言或谓词的有穷集F。每个断言与文法的某产生式相联。如果对G中的某一输入串而言（句子），A中的所有断言对该输入串的语法树结点的属性全为真，则该串也是A语言中的句子。编译程序的静态语义审查工作就是验证关于所编译的程序的断言是否全部为真。 比如，有文法G为：ET1 + T2|T1 or T2Tnum|true|false（因为T在同一个产生式里出现了两次，使用上角标将它们区分开。）对输入串3+4的语法树如图81（A） 图81 静态语义审查属性文法记号中常使用NT的形式表示与非终结符N相联的属

10、性t。比如可把对上面表达式的类型检查的属性文法写成图82的形式。与每个非终结符T相联的有属性t，t要么是int，要么是bool。与非终结符E的产生式相联的断言指明：两个T的属性必须相同。图81的（b）是图8.1(a)语法树结点带有语义信息的表示。图82类型检查的属性文法ET1+T2 T1.tintANDT2.tintET1orT2 T1.tboolATD T2.tboolTnumT.tintTtrueT.tboolTfalseT.tbool属性文法中的属性分成两类：继承属性和综合属性，简单地说，综合属性用自上而上传递信息，而继承属性用于自上而下传递信息。在一个属性文法中，对应于每个产生式Aa都

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

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

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

14、in将被沿着语法树传递到下边的结点使用，与L产生式相联的规则里使用了它。例 8.2描述说明语句中各种变量的类型信息的语义规则，这个例子里，继承属性在说明中为各个标识符提供类型信息。产生式 语义规则（1）DTL L.inT.type（2）Tint T.Typeinteger（3）Treal T.Typereal（4）LL1，id L1.inL.inaddtype（id.entry，L.in）（5）Lid addtype（id.entry，L.in） 图8.3是句子intid1,id2的语法树，使用表示属性的传递情况。在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。与L

15、产生式相联的语义规则中有一个过程调用addtype，过程addtype的功能是把每个标识符的类型信息登录在符号表的相关项中。图 8.3 属性信息传递情况属性文法看作是允许为每个终结符和非终结符配备一些属性的文法。它既能描述程序设计语言的语法，又为语义处理提供了方便.属性文法里的属性有不同的类型，可以象变量一样地被赋值。赋值规则附加于语法规则之上。赋值与语法同时进行，赋值过程就是语义处理过程。在推导语法树的时候，诸属性的值被计算并通过赋值规则层层传递。有的从语法规则左边向右边传，有的从右边向左边传。语法推导树最后完成时，就得到开始符号的属性值。也就是整个程序的语义。8.2 语法制导翻译编译程序的

16、整个任务就是把源程序翻译为目标程序。实际上每个编译阶段都可以看成是完成一定的翻译任务：词法分析阶段把字符流翻译为单词流，语法分析阶段把单词流翻译为语法树，目标代码生成阶段把语法树翻译为汇编语言等等。在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译的办法称作语法制导翻译。假如我们要把中缀算术表达式翻译为后缀波兰表示形式（后缀波兰表示形式参见8.3.1），给出如下语义描述： ET + E1 E.code=T.code| E1.code|+ ET E.code=T.code TF * T1 T.code=F.code|T1.code| * T

17、F T.code =F.code F（E） F.code = E.code Fa F.code = a 其中使用E.code，T.code和F.code分别表示相应的后缀式，|表示后缀式的连接。如果对于输入串a+a*a采用最左分析，其形成的推导过程为： ET+EF+Ea+Ea+Ta+T* Fa+F*Fa+a*Fa+a*a(，),是输入句子和句型，是翻译的输出形式，则有：(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.c

18、ode|*+) (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），执行的语义动作是置Fval

19、的值为单词digit值，我们把语法树中每个结点的语义值括在该结点处。那么第一步归约并完成语义动作后的情形在图8.4（b）中指出。继续进行分析，第七次归约后的情形在图8.4（c）中指出。归约至E时，它的值17也计算出来了。图 8.4 语法制导方法计算表达式这里再给出一种翻译模式，也是把中缀形式的算术表达式映射到后缀波兰表示：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 的一个推导过程：E T+E F+E a+E a+T a+F*T a+a*T a+a*F a+a*a伴随着句子a+a*a的这个推

20、导过程,按照上述翻译模式所进行的一步步翻译：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+*()#ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108r6s119r1s7r1r110

21、r3r3r3r311r5r5r5r5同时把LR分析器的能力扩大，使它不仅执行语法分析任务，且能在用某个产生式进行归约的同时调用相应的语义子程序，完成在例8.1的属性文法中描述的语义动作。每步工作后的语义值保存在扩充的分析栈里语义值栏中。采用的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#

22、8r60163-2-3#E+F*5#9r40169-2-3#E+T*5#1001697-2-3-#E+T5#11-2-3-#E+T5#12r601697（10）-2-2-5#E+TF#13r30169-2-（15）#E+T#14t101（17）#E#15接受按照上述实现办法，若把语义子程序改为产生某种中间代码的动作，那么则可在语法分析的制导下，随着分析的进展逐步生成中间代码。8.3 中间代码的形式编译程序所使用的中间代码有多种形式。常见的有逆波兰记号、三元式、四元式和树形表示。下面分别将它们做一介绍。 8.3.1 逆波兰记号逆波兰记号是最简单的一种中间代码表示形式，早在编译程序出现之前，它就用

23、于表示算术表达式，是波兰逻辑学家卢卡西维奇发明的。这种表示法将运算对象写在前面，把运算符号写在后面，比如把a+b写成ab+，把a*b写成ab*，用这种表示法表示的表达式也称做后缀式。图8.8给出了程序设计语言中的简单表达式和赋值语句相应的逆波兰表示形式：图 8.8 逆波兰表示程序设计语言中的表示逆波兰表示a+ba+b*c(a+b)*ca;=b*c+b*d ab+abc*+ ab+c*abc*bd*+:=后缀表示法表示表达式，其最大的优点是易于计算机处理表达式。常用的算法是使用一个栈，自左至右扫描算术表达式（后缀表示），每扫描到运算对象，就把它推进栈；扫描到运算符，若该运算符是二目的，则对栈顶部

24、的两个运算对象实施该运算，并将运算结果代替这两个运算对象而进栈；若是一目运算符，则对栈顶元素执行该运算，并以运算结果代替该元素进栈，最后的结果留在栈顶。例如 BCD*+（它的中缀表示为B+C*D，使用表示一目减）的计值过程为：1. B进栈；2. 对栈顶元素施行一目减运算，并将结果代替栈顶，即B置于栈顶；3. C进栈； 4. D进栈；5. 栈顶两元素相乘，两元素退栈，相乘结果置栈顶；6. 栈顶两元素相加，两元素退栈，相加结果进栈，现在栈顶存放的是整个表达式的值。由于后缀式表示上的简洁和计值的方便，特别适用于解释执行的程序设计语言的中间表示，也方便具有堆栈体系的计算机的目标代码生成。逆波兰表示很容

25、易扩充到表达式以外的范围。在图8.8中已见到了赋值语句的后缀表示的例子。只要遵守运算对象后直接紧跟它们的运算符的规则即可。比如把转语句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中的赋值语句

26、为例，当计算到=时，执行的是将表达式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）， （2）（4）（ （2）， a）与后缀式不同，

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

28、四元式四元式是一种比较普遍采用的中间代码形式。四元式的四个组成成分是：算符op，第一和第二运算对象ARG1和ARG及运算结果RESULT。运算对象和运算结果有时指用户自己定义的变量，有时指编译程序引进的临时变量。例如a=b*c+b*d的四元式表示如下：（1）（*，b，c，t1）（2）（*，b，d，t2）（3）（+， t1， t2， t3）（4）（=，t3， ， a）四元式和三元式的主要不同在于，四元式对中间结果的引用必须通过给定的名字，而三元式是通过产生中间结果的三元式编号。也就是说，四元式之间的联系是通过临时变量实现的。也许读者已经发现，四元式表示很类似于三地址指令，确实，有时把这类中间表示

29、称为三地址代码，因为这种表示可看作一种虚拟三地址机的通用汇编码，即这种虚拟机的每条指令包含操作符和三个地址，两个是为运算对象的，一个是为结果的。这种表示对于代码优化和目标代码生成都较有利。有时，为了更直观，也把四元式的形式写成简单赋值形式或更易理解的形式。比如把上述四元式序列写成：（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 goto L本书中，为了叙述的方便，两种形式将同时使用。如何用四元式表示各种语句，以及翻译各种语句的语义描述，将在后面各节陆续讨论。为了复习与巩固一下前面所学习

30、的几种中间代码的形式，下面举一个例子，分别用几种中间代码的形式来表示例 : A + B * ( C - D ) + E / ( C - D ) N 四元式：（1）（ - CDT1）（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）间接三元式：间接三元式序列（1）（CD）（2）（*B（1）（3）（+A（2）（4）（1）N）（5）（/E（4）（6）（+（3）（5）间接码表（1）（2）（3）（1）

31、（4）（5）（6）间接码表表面了执行间接三元式的顺序8.4 简单赋值语句的（四元式）翻译在8.3.3的四元式中，使用变量名字本身表示运算对象ARG1和ARG2，用ti表示RESULT。在实际实现中，它们或者是一个指针，指向符号表的某一登录项，或者是一个临时变量的整数码。在对赋值语句翻译为四元式的描述中，我们将表明怎样查找这样的符号表登录项。首先对id表示的单词定义一属性idname，用做语义变量，用Lookup（idname）表示审查idname是否出现在符号表中，如在，则返回一指向该登录项的指针，否则返回nil。语义过程emit表示输出四元式到输出文件上。语义过程newtemp表示生成一个临

32、时变量，每调用一次，生成一新的临时变量。语义变量Eplace，表示存放E值的变量名在符号表的登录项或一整数码（若此变量是一个临时变量）图8.9列出了翻译赋值语句到四元式的语义描述。这里的语义工作包括对变量进行先定义后使用的检查。图 8.9 赋值语句的四元式翻译 (1) Sid=E p=lookup（ idname）； if pnilthen Emit（p=Eplace） elseerror(2) EE1+E2 Eplace=newtemp； Emit（Eplace=E1.place+E2place）(3) EE1*E2 EplaceE=newtemp； Emit（Eplace=E1place*

33、E2place）(4) EE1 EplaceE=newtemp； Emit（Eplace=uminusE1place ）(5) E（E1） Eplace=E1place(6) Eid p:=lookup（idname）；ifp nil thenEplaceE=pelseerror实际上，在一个表达式中可能会出现各种不同类型的变量或常数，而不是像图8.9中的id假定为都是同一类型。也就是说，编译程序还应执行这样的语义动作：对表达式中的运算对象应进行类型检查，如不能接受不同类型的运算对象的混合运算，则应指出错误；如能接受混合运算，则应进行类型转换的语义处理。假如，图8.9中的表达式可以有混合运算，

34、id可以是实型量也可以是整型量，并且约定，当两个不同类型的量进行运算时，必须首先将整型量转换为实型量。为进行类型转换的语义处理，增加语义变量，用Etype表示E的类型信息，Etype的值或为int或为real，此外，为区别整型加（乘）和实型加（乘），把+（*）分别写作+i（*i）和+r（*r）。用一目算符itr表示将整型运算对象转换成实型。这样，图8.9中的第（3）条产生式及其有关语义描述如图8.10。 图 8.10 类型转换的语义处理 产生式语义动作EE1*E2Eplace=newtemp；if E1typeint AND E2typeint thenbegin emit（E.place，=

35、，E1place，*i, E2place）；Etype=intendelse if E1typereal AND E2typereal thenbegin emit (Eplace,=,E1place,*r,E2place);Etype=realendelse if E1typeint/* and E2type=real*/thenbegin t=newtemp；emit（t，=，itr，E1place）；emit（Eplace，=，t，*r，E2place）；Etype=realendelse/*E1typereal and E2typeint*/begin t=newtemp；emit（t

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

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

38、和算术值，只不过在需要时执行强制变换。为简单起见，我们只考虑如下文法生成的布尔表达式。EE 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 01

39、or（1 and 0）or 01 or 0 or 01 or 01另一种计算方法是采取某种优化措施，只计算部分表达式，例如要计算A or B，若计算出A的值为1，那么B的值就无需再计算了，因为不管B的值为何结果，A or B的值都为1。上述两种方法对于不包含布尔函数调用的表达式是没有什么差别的。但是，假若一个布尔式中会有布尔函数调用，并且这种函数调用引起副作用（如有对全局量的赋值）时，这两种方法未必等价。采用哪种方法取决于程序设计语言的语义，有些语言规定，函数过程调用应不影响这个调用处环境的计值，或者说，函数过程的工作不许产生副作用，在这种规定下，可以任选其中一种。若按第一种办法计算布尔表达式

40、。布尔表达式a or b and not c翻译成的四元式序列为：（1）t1=not c（2）t2=b and t1（3）t3=a or t2对于像ab这样的关系表达式，可看成等价的条件语句if ab then 1else 0，它翻译成的四元式序列为：（1）ifab goto （4）（2）t=0（3）goto （5）（4）t=1（5）其中用临时变量t存放布尔表达式ab的值，(5)为后续的四元式序号。图8.11给出了按第一种办法计算布尔表达式的值，将布尔表达式翻译成四元式的描述，在该描述中使用了过程newtemp和emit，其含义同前，过程nextstat给出在输出序列中下一四元式序号，emit

41、过程每被调用一次，nextstat增加1。图8.11用数值表示布尔值的翻译方案 EE1 or E2Eplace=newtemp；emit（Eplace=E1placeorE2place）EE1 and E2Eplace =newtemp；emit（Eplace=E1place andE2place）Enot E1Eplace =newtemp：；emit（Eplace=notE1place）E（E1）Eplace=E1placeEid1 relop id2Eplace=newtemp；emit（ifid1place relop id2placegotonextstat+3）；emit（Epla

42、ce=0）；emit（gotonextstat+2）；emit（Eplace=1）EtrueEplace=newtemp；emit（Eplace=1）EfalseEplace=newtemp； emit（Eplace=0） 8.5.2 控制语句中布尔表达式的翻译现在讨论出现在if then；if then else和while do等语句中的布尔表达式E的翻译。这三种语句的语法为：Sif E then S1|if E then S1 else S2|while E do S1这些语句的代码结构示意分别在图8.12（a）（b）（c）中，其中使用.和。两个出口分别用于表示E为真和假时控制流向的转移

43、。分别叫真出口和假出口。图 8.12 控制语句的代码结构在控制语句中, 布尔表达式E作为控制流转移的条件，仅把其翻译成一串条件转和无条件转的四元式代码。比如将布尔表达式E=a rop b翻译成四元式代码：if a rop b goto Etrue和goto Efalse这里，使用Etrue和Efalse分别表示布尔表达式E的真假出口转移目标。下面将多处使用它们。对于E为E1 or E2的形式，若E1是真，则可知道E为真即E1的真出口和E的真出口一样。如果E1是假，那么必须计算E2，E1的假出口应是E2代码的第一个四元式标号，这时E2的真出口和假出口分别与E的真出口和假出口一样。 类似的考虑适于

44、E为E1 and E2 的情形。 E为not E1 的翻译更容易，只需调换E1 的真假出口即可得到E的真假出口。例如布尔表达式ab or cf翻译为如下四元式序列：例 8.3（1）if ab goto Etrue（2）goto （3）（3）if cdgoto （5）（4）goto Efalse（5）is ef goto Etrue（6）goto Efalse这样生成的四元式显然不是最优的，如四元式（2）是不需要的。这种问题可留待代码优化阶段解决。在例8.3中，我们使用Etrue和Efalse分别表示整个表达式ab or cd and ef的真、假出口，而Etrue和Efalse的值并不能在产生

45、四元式的同时就知道。为了看清这一点，我们把该表达式放在条件语句中考虑，如语句 if ab or cd and ef then S1 else S2的四元式序列为（1）ifabgoto（7） /*（7）是整个布尔表达式的真出口*/（2）goto（3）（3）ifcdgoto（5）（4）goto(p+1) /*（p+1）是整个布尔表达式的假出口*/（5）ifefgoto（7）（6）goto（p+1）（7） （关于S1的四元式）实际上，上述四元式（1）和（5），（4）和（6）的转移地址并不能在产生这些四元式的同时得知。例如（1）和（5）的转移地址为（7），它是在整个布尔表达式的四元式序列生成之后才回填

46、的地址。为了记录需回填地址的四元式，常采用一种拉链的办法。把需回填Etrue的四元式拉成一链，把需回填Efalse的四元式拉成一链，分别称做真链和假链。用一个例子说明拉链是如何方式，若有四元式序列：（10）gotoEtrue （20）gotoEtrue （30）gotoEtrue则把需回填Etrue的四元式（10），（20）和（30） 链成（10）goto（0） （20）goto（10） （30）goto（20）把地址（30）称作链首，0为链尾标志，即地址（10）为链尾。如何描述回填，我们不再介绍，有兴趣的同学可阅读参考书。8.6 控制语句的翻译8.6.1条件转移考虑if then，if th

47、en else和while do语句，在图8.12中已给出了它们的代码结构。这里我们使用下面文法GS定义这些语句：GS（1）Sif 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）|S其中各非终结符号的意义是：S-语句L-语句串A-赋值句E-布尔表达式回想在上一节，讨论控制语句中的布尔表达式的翻译时，使用Etrue和Efalse分别指出尚待回填真、假出口的四元式串，如对于条件语句if E then S1 else S2，在扫描到then时才能知道E的真出口，而E的假出口只有处理了S1之后，到

48、达else时才明确。即是说，必须将Efalse的值传下去，以便到达相应的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

49、（和L）含有一项语义值SCHAIN（和LCHAIN）。也是一条链，它把所有那些四元式串在一起，这些四元式期待在翻译完S（L）之后回填转移目标。真正的回填工作将在处理S的外层环境的某一适当时候完成。 按照上述文法产生式相应的语义动作，加上前述关于赋值句和布尔表达式的翻译法，语句while （AB） do if （CD） then X=Y+Z将被翻译成如下的一串四元式：100if AB goto 102101goto107102ifCD goto 104103goto 100104T=Y+Z105X=T106goto 1001078.6.2 开关语句开关语句（case语句或switch语句）是很多

50、程序设计语言中都有的，方式不尽相同，甚至FORTRAN中的计算GOTO和赋值GOTO也可看做是一种开关语句。我们假定要讨论的开关语句的形式为：switch E ofcase V1：S1case V2：S2case Vn-1：Sn-1default：Snend这里的E是一个表达式，也称为选择子。开关语句是分情形选择机制，在E被计算之后，测试它的值符合哪种case中的值，而执行和该值相关的语句，并做相应的转移。如果E的值不能与任何Vi（1in-1）匹配，便执行default时的语句。直观上看，case语句翻译成如下的一连串条件转移语句。t=E；L1：if tV1 goto L2； S1；goto next；L2：if tV2 goto L3；S2goto next；Ln-1：if tVn-1 goto Ln；Sn-1；goto ne