第08章 语法制导翻译及中间代码生成

1、第第8章语法制导翻译和中间章语法制导翻译和中间代码生成代码生成编译原理编译原理华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理2本章研究语义分析和中间代码生成基本原理和方法，主要介绍本章研究语义分析和中间代码生成基本原理和方法，主要介绍属性文法和属性文法和3种中间代码形式及其特点，重点讨论了计算机高级语言种中间代码形式及其特点，重点讨论了计算机高级语言主要成分，在语法分析过程的制导下，如何进行语义分析和中间代码主要成分，在语法分析过程的制导下，如何进行语义分析和中间代码生成的各种相应的技术。生成的各种相应的技术。 内容摘要内容摘要华中科技大学计算机学院华中科技大学计算机学院编译原理

2、编译原理38.1属性文法属性文法 8.2语法制导翻译概论语法制导翻译概论 8.3中间代码形式中间代码形式 8.4简单赋值语句翻译简单赋值语句翻译 8.5布尔表达式翻译布尔表达式翻译8.6控制结构翻译控制结构翻译8.7说明语句翻译说明语句翻译8.8数组和结构翻译数组和结构翻译 重点讲解重点讲解小结华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理4目录在语言形式化研究领域，基于形式语言和自动机理论，可以较好在语言形式化研究领域，基于形式语言和自动机理论，可以较好地解决计算机高级语言语法的形式化描述。关于语言语义形式化问题，地解决计算机高级语言语法的形式化描述。关于语言语义形式化问题，已

3、经推出了诸如操作语义学、公理语义学和指称语义学等理论。但是，已经推出了诸如操作语义学、公理语义学和指称语义学等理论。但是，目前这些理论与实际应用尚有较大距离。目前这些理论与实际应用尚有较大距离。现实的编译程序通常采用一种在语法制导下的语义分析和代码生现实的编译程序通常采用一种在语法制导下的语义分析和代码生成方法。所谓成方法。所谓“语法制导语法制导”是指伴随着语法分析过程，在语法分析每是指伴随着语法分析过程，在语法分析每步推导或归约时刻，增加相应的语义分析和代码生成处理之含义。这步推导或归约时刻，增加相应的语义分析和代码生成处理之含义。这种方法，可以采用一种非形式化、但接近形式化的种方法，可以采

4、用一种非形式化、但接近形式化的“属性文法属性文法”，作，作为语言语义的描述工具。为语言语义的描述工具。8.1 属性文法属性文法华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理5例例8.1 设文法设文法GE定义如下，试解释其语义。定义如下，试解释其语义。 GE： EN( (1) ) + N( (2) ) EN( (1) ) or N( (2) ) Nn Nt Nf 考察输入串考察输入串n+t，因为存在如下推导过程，所以输入串，因为存在如下推导过程，所以输入串n+t是文是文法法GE的一个句子。的一个句子。 最后一步归约时，可以发现其语义错误！最后一步归约时，可以发现其语义错误！华中科技

5、大学计算机学院华中科技大学计算机学院编译原理编译原理6如果将数据值和数据类型两类语义称为文法符的属性，并分别命名如果将数据值和数据类型两类语义称为文法符的属性，并分别命名为为 value和和type属性，任意文法符属性，任意文法符X的数据值和数据类型两类语义分别记的数据值和数据类型两类语义分别记为为 X.value和和X.type ，则每个规则的语义要求就可以描述成形式化的断，则每个规则的语义要求就可以描述成形式化的断言或谓词形式如下，并称为语义规则。其中，言或谓词形式如下，并称为语义规则。其中，int和和bool分别表示整数型分别表示整数型和逻辑型，和逻辑型，(a)表示词法分析提供的表示词法

6、分析提供的a之数据值。之数据值。 华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理7定义定义8.1 一个一个属性文法属性文法A定义为一个三元组（定义为一个三元组（G，V，F），记为），记为A（G，V，F）。其中，）。其中，G为文法，为文法，V为文法为文法符号属性集符号属性集，F为规则的有关为规则的有关属性的断言或谓词集也称为属性的断言或谓词集也称为语义规则集语义规则集。文法符文法符(对应于自然语言的语法成分对应于自然语言的语法成分)的语义可以通过引入属性来进行的语义可以通过引入属性来进行描述，称为描述，称为文法符的属性文法符的属性。如：。如：“数据类型数据类型”、“数据值数据值”和

7、和“存储地址存储地址”等等属性来描述。等等属性来描述。每个规则的语义可以使用有关属性的断言或谓词形式加以描述。即为每个规则的语义可以使用有关属性的断言或谓词形式加以描述。即为文法的每个规则配备计算属性的计算规则，称为语义规则。文法的每个规则配备计算属性的计算规则，称为语义规则。在文法基础上扩充属性和属性的断言，就是所谓的在文法基础上扩充属性和属性的断言，就是所谓的“属性文法属性文法”近似近似描述语言语义的基本思路。描述语言语义的基本思路。 华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理8属性可以分为两类：继承属性和综合属性。属性可以分为两类：继承属性和综合属性。继承属性继承属性是

8、指其属性值是指其属性值是自顶向下传递所得的属性。是自顶向下传递所得的属性。综合属性综合属性是指其属性值是自底向上传递所是指其属性值是自底向上传递所得的属性。得的属性。对每个产生式对每个产生式A ，都有一套与之相关联的语义规则，其形式为：，都有一套与之相关联的语义规则，其形式为：b=f(c1,c2 , , ck),其中其中b,c1,c2 , , ck是该产生式文法符号的属性。是该产生式文法符号的属性。（1）如果）如果b是是A的一个属性，的一个属性，c1,c2 , , ck是该产生式右部文法符号是该产生式右部文法符号的属性。则称的属性。则称b是是A的的综合属性综合属性。（2）如果）如果b是产生式右

9、部某个文法符号是产生式右部某个文法符号X的属性，的属性， c1,c2 , , ck是是A或产生式右部任何文法符号的属性。则称或产生式右部任何文法符号的属性。则称b是是X的的继承属性继承属性。注：（注：（1）非终结符既）非终结符既可以有综合属性，也可以有继承属性。但文法可以有综合属性，也可以有继承属性。但文法开始符号没有继承属性。开始符号没有继承属性。 （2）终结符只有综合属性，它们是由词法程序提供的终结符只有综合属性，它们是由词法程序提供的。华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理9例例8.1文法文法GE语义规则，实际上，是在假定归约分析前提下设语义规则，实际上，是在假定归

10、约分析前提下设计的。涉及到的计的。涉及到的value，和，和type属性都是综合属性。输入串属性都是综合属性。输入串n+t的属性的属性值传递过程如下图所示。值传递过程如下图所示。 华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理10例例8.2 设说明语句文法设说明语句文法GD定义如下，其中定义如下，其中int、real 和和id是是3个终结个终结符。试设计描述数据类型的语义规则。符。试设计描述数据类型的语义规则。 GD： DTL Tint Treal LL1，id Lid 在文法在文法GD中，中，int、real和和id为为3个终结符号，个终结符号，int和和real分分别是整型和

11、实型的数据类型名称，别是整型和实型的数据类型名称，id表示运算对象。实际上，表示运算对象。实际上，文法文法GD描述的说明语句一般形式为描述的说明语句一般形式为 real id1,id2,idn 或或 int id1,id2,idn。 华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理11设计两个属性设计两个属性type和和in，均表示数据类型的语义，均表示数据类型的语义，enter(id,)是将符号是将符号id及其相关信息登记到符号表中的语义处理子程序。文法及其相关信息登记到符号表中的语义处理子程序。文法GD 数据类型的语义规则设计如下。数据类型的语义规则设计如下。 华中科技大学计算

12、机学院华中科技大学计算机学院编译原理编译原理12规则和的语义规则中规则和的语义规则中integer 和和real表示数据类型整型和实型表示数据类型整型和实型的内部名称。属性的内部名称。属性type是综合属性，属性是综合属性，属性in是继承属性。输入串是继承属性。输入串int a,b的属性值传递过程如下图所示，其中天蓝色和粉红色分别表示属性的属性值传递过程如下图所示，其中天蓝色和粉红色分别表示属性type和和in的传递线路。的传递线路。 华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理13目录逻辑上的语义分析阶段和中间代码生成阶段，其相互的内在联系逻辑上的语义分析阶段和中间代码生成阶

13、段，其相互的内在联系紧密，通常是合并为一遍完成。紧密，通常是合并为一遍完成。语法制导翻译方法语法制导翻译方法是指伴随着语法分析过程，在语法分析每步推是指伴随着语法分析过程，在语法分析每步推导或归约时刻，增加相应的语义分析和代码生成处理，从而完成源语导或归约时刻，增加相应的语义分析和代码生成处理，从而完成源语言到中间语言言到中间语言(或目标语言或目标语言)一种翻译方法。一种翻译方法。由于语法制导翻译依赖于语法分析过程，所以语法分析采用的是由于语法制导翻译依赖于语法分析过程，所以语法分析采用的是推导类分析法还是归约类分析法，将导致语义规则的属性值传递方向推导类分析法还是归约类分析法，将导致语义规则

14、的属性值传递方向不同，相应语法制导翻译技术上有所差异。从而形成了不同，相应语法制导翻译技术上有所差异。从而形成了自顶向下语法自顶向下语法制导翻译制导翻译和和自底向上语法制导翻译自底向上语法制导翻译的两类语法制导翻译方法。的两类语法制导翻译方法。 8.2 语法制导翻译概论语法制导翻译概论华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理14一个一般性的属性文法的翻译器可能是很难建立，但对于一个一般性的属性文法的翻译器可能是很难建立，但对于L-属性文属性文法的翻译器却很好建立。法的翻译器却很好建立。S-属性文法属性文法：只含有综合属性的属性文法。：只含有综合属性的属性文法。L-属性文法属

15、性文法：如果对每个产生式：如果对每个产生式 AX1X2Xn,其其 每个语义规则中每个语义规则中的每个属性或者为综合属性，或者是的每个属性或者为综合属性，或者是Xj(1 j n)的一个继承属性且这个的一个继承属性且这个继承属性仅依赖于：继承属性仅依赖于：（1）产生式）产生式Xj在左边的在左边的X1X2Xj-1（2）A的继承属性的继承属性S-属性文法是属性文法是L-属性文法的一个特例。属性文法的一个特例。华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理15例例8.3 将中綴表达式翻译成后缀表达式的属性文法将中綴表达式翻译成后缀表达式的属性文法 EEaddop T print(addop

16、Lexeme) Tnum print(num.val)对表达式对表达式2+3-5，如果采用，如果采用LR分析法，在规约时执行语义动作即可完成。分析法，在规约时执行语义动作即可完成。8.2.1L-属性文法在自上而下分析法中的实现属性文法在自上而下分析法中的实现 EE - TE + T5 Print(5) Print(-)T3 Print(3)2 Print(2) Print(+)华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理例例8.4 将将8.3的改写成的改写成LL（1）文法后，中綴表达式翻译成后缀表达式的）文法后，中綴表达式翻译成后缀表达式的属性文法属性文法 ETR R addo

17、p T print(addop.Lexeme) R | Tnum print(num.val)这种将语义动作嵌入规则右部文法符号之间的形式称为这种将语义动作嵌入规则右部文法符号之间的形式称为翻译模式翻译模式对表达式对表达式2+3-5，E =TR=2print(2)R =2print(2)+Tprint(+)R = 2print(2)+3print(3) print(+)R = 2print(2)+3print(3) print(+)-Tprint(-)R = 2print(2)+3print(3) print(+)- 5print(5) print(-)R = 2print(2)+3print

18、(3) print(+)- 5print(5) print(-)华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理17自底向上语法制导翻译自底向上语法制导翻译的实现总体框架是基于自底向上语法分析程的实现总体框架是基于自底向上语法分析程序总体框架基础上，增加一个与语法分析栈同步的语义栈，存放与分序总体框架基础上，增加一个与语法分析栈同步的语义栈，存放与分析栈中文法符对应属性值，依据每个语法规则的语义规则、语义信息析栈中文法符对应属性值，依据每个语法规则的语义规则、语义信息处理和代码生成处理，编写成独立的语义处理子程序，待语法规则用于处理和代码生成处理，编写成独立的语义处理子程序，待语法

19、规则用于归约时刻调用。自底向上语法制导翻译程序总体框架如下图归约时刻调用。自底向上语法制导翻译程序总体框架如下图8.1所示。所示。 8.2.2自下而上分析法的实现自下而上分析法的实现 华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理18例例8.5设文法设文法GE定义如下，仅仅文法考虑数据值定义如下，仅仅文法考虑数据值value属性，试设计属属性，试设计属性文法，并基于特殊二义性文法的性文法，并基于特殊二义性文法的LR分析法，给出输入串分析法，给出输入串7+8*5的语法制导翻译过程。的语法制导翻译过程。 GE： EE1 + E2 EE1 * E2 E(E1) Ed ) 设计属性文法如

20、下，其中设计属性文法如下，其中(a)表示词法分析提供的表示词法分析提供的a之数据值。之数据值。 华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理19）文法）文法GE的的LR分析表分析表M如下。如下。 ）输入串）输入串7+8*5的的语法制导翻译过程演示语法制导翻译过程演示，其中符，其中符号号“”表示空属性值。表示空属性值。 目录华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理20目录通常表达式是将运算符置于运算对象之间，其形如：通常表达式是将运算符置于运算对象之间，其形如： ab。此。此外，还可以运算符置于运算对象之前或者之后描述表达式。如，外，还可以运算符置于运算对象之

21、前或者之后描述表达式。如，ab、ab等。依据运算符置于运算对象之前、之间和之后不同位置，等。依据运算符置于运算对象之前、之间和之后不同位置，形成了描述表达式的形成了描述表达式的3种方式。它们描述的表达式分别称为种方式。它们描述的表达式分别称为前缀表达前缀表达式式、中缀表达式中缀表达式和和后缀表达式后缀表达式。前缀表达式和后缀表达式，亦分别称。前缀表达式和后缀表达式，亦分别称为为波兰式波兰式和和逆波兰式逆波兰式。 8.3.1逆波兰式逆波兰式 中间代码生成阶段任务是将源程序转换成中间代码形式，其目的中间代码生成阶段任务是将源程序转换成中间代码形式，其目的就是便于代码的优化。中间语言是便于优化程序处

22、理和目标代码生成就是便于代码的优化。中间语言是便于优化程序处理和目标代码生成的、逻辑上独立于硬件的、介于高级语言和机器语言之间的接近机器的、逻辑上独立于硬件的、介于高级语言和机器语言之间的接近机器端的一种语言形态。常见的中间语言形式有逆波兰式、三元组式和四端的一种语言形态。常见的中间语言形式有逆波兰式、三元组式和四元组式。元组式。 8.3 中间代码形式中间代码形式华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理21目录逆波兰式具有如下特点：逆波兰式具有如下特点： ）与中缀表达式相比，逆波兰式运算对象的前后相对顺序不变；）与中缀表达式相比，逆波兰式运算对象的前后相对顺序不变； ）逆波

23、兰式中运算符从左至右出现的顺序就是运算符的实际运算）逆波兰式中运算符从左至右出现的顺序就是运算符的实际运算次序；次序； ）逆波兰式不必约定运算符的计算优先级别，也不需要使用括号）逆波兰式不必约定运算符的计算优先级别，也不需要使用括号来强制提高运算符计算优先级别。来强制提高运算符计算优先级别。 华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理22逆波兰式的计算逆波兰式的计算很容易算法实现。很容易算法实现。采用一个运算对象栈，从左至右扫描逆波兰式，每扫描到一个单采用一个运算对象栈，从左至右扫描逆波兰式，每扫描到一个单词，按下列情况分别处理，直到逆波兰式扫描完毕。词，按下列情况分别处理，

24、直到逆波兰式扫描完毕。情况情况 如果遇到运算对象，则入栈；如果遇到运算对象，则入栈；情况情况 如果遇到运算符，则在运算对象栈顶部，取出（即出栈）如果遇到运算符，则在运算对象栈顶部，取出（即出栈）与运算符目数相同个数的运算对象，进行运算符约定的计算，之后将与运算符目数相同个数的运算对象，进行运算符约定的计算，之后将计算结果再入栈。计算结果再入栈。 华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理23四元组式四元组式是常用的一种中间代码形式，它是将表达式描述成仅是常用的一种中间代码形式，它是将表达式描述成仅含单个运算符的四元组的序列。四元组是有运算符含单个运算符的四元组的序列。四元组是

25、有运算符op、运算对象、运算对象arg1和和arg2以及运算结果以及运算结果result四个分量构成的向量，形式如下所示。四个分量构成的向量，形式如下所示。 8.3.2 四元组式四元组式 华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理24例如，表达式例如，表达式a*b/(b+d)+d的四元组式如下，其中的四元组式如下，其中 ti 是中间计算是中间计算结果变量，由编译程序内部自动产生，表达式的值为结果变量，由编译程序内部自动产生，表达式的值为t4。 （*，a，b，t1）（+，b，d，t2）（/，t1，t2，t3）（+，t3，d，t4）t1:a*bt2:b+dt3:t1/t2t4:t

26、3+d为了更直观起见，四元组为了更直观起见，四元组(op，arg1，arg2，result)也可以写成也可以写成类似于简单赋值语句的形式类似于简单赋值语句的形式result:arg1 op arg2。如上述表达式。如上述表达式a*b/(b+d)+d的四元组式可以写成如下赋值语句的形式。的四元组式可以写成如下赋值语句的形式。华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理25四元组式可以扩充描述其它语言成分。比如，赋值语句和四元组式可以扩充描述其它语言成分。比如，赋值语句和转转移语句的移语句的四元组式如下。四元组式如下。（jump是0目的无条件转移运算符；jrop是一类2目的条件转移

27、运算符，rop表示诸如、和关系运算。） x:a(:，a，x)或者或者x:a四元组四元组语句语句(jrop，B，C，L)或者或者if B rop C goto Lgoto Lif B rop C goto L(jump，L)或者或者goto L其它语言成分的其它语言成分的四元组式四元组式华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理26三元组式三元组式类似于四元组式，也是将它是将表达式描述成仅含单类似于四元组式，也是将它是将表达式描述成仅含单个运算符的三元组的序列。三元组是有运算符个运算符的三元组的序列。三元组是有运算符op、运算对象、运算对象arg1和和arg2三个分量构成的向量

28、，运算结果用三元组自身整体隐式地表示，三个分量构成的向量，运算结果用三元组自身整体隐式地表示，并给每个三元组赋予唯一编号，以便三元组引用时书写简洁。具体并给每个三元组赋予唯一编号，以便三元组引用时书写简洁。具体形式如下所示。形式如下所示。 8.3.3 三元组式三元组式 华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理27例如，表达式例如，表达式a*b/(b+d)+d的三元组式如下，表达式的值为三元组。的三元组式如下，表达式的值为三元组。 （*， a ，b ）（+，b ，d ）（/， ，），）（+， ，d ）三元组式也可以转换成树形结构表示。方法三元组式也可以转换成树形结构表示。方法

29、是一个三元组是一个三元组(op，arg1，arg2)构造成一个以构造成一个以op为为根结点、根结点、arg1和和arg2分别为儿子结点的子树。如分别为儿子结点的子树。如果果arg1或或arg2是三元组编号，则儿子结点即为对是三元组编号，则儿子结点即为对应编号的三元组的子树根。应编号的三元组的子树根。例如，表达式例如，表达式a*b/(b+d)+d的四元组式的树形的四元组式的树形结构表示如下。结构表示如下。 华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理28目录简单赋值语句一般格式为简单赋值语句一般格式为id:e，其中，其中e为仅含有加法、乘法、为仅含有加法、乘法、取相反数运算和括号

30、，令其文法规则是取相反数运算和括号，令其文法规则是Sid:E, EE+EE*E(E)id。以此为例，说明在自底向上语法制导下对简单赋值语句进。以此为例，说明在自底向上语法制导下对简单赋值语句进行语义分析和四元组翻译方法。行语义分析和四元组翻译方法。假设假设name、place和和type分别表示单词自身、存储地址和数据类分别表示单词自身、存储地址和数据类型的属性。型的属性。lookup(idname)是查找是查找idname是否在符号表中的子程序，是否在符号表中的子程序，如果在，其返回值为如果在，其返回值为idname在符号表中地址，否则返回值为在符号表中地址，否则返回值为nil空空值。这里，

31、假定编译程序已将源程序中说明语句定义的单词及其属值。这里，假定编译程序已将源程序中说明语句定义的单词及其属性值翻译存放在符号表中。性值翻译存放在符号表中。newtemp是分配一个临时变量的子程序，返回值为临时变量的是分配一个临时变量的子程序，返回值为临时变量的地址。地址。emit()四元组输出子程序，其每次输出文件指针四元组输出子程序，其每次输出文件指针nextstat自动加自动加1，指向文件尾。指向文件尾。error是错误处理程序。是错误处理程序。8.4 简单赋值语句翻译简单赋值语句翻译华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理29在仅进行变量在仅进行变量“先定义后使用先定

32、义后使用”语义检查，并翻译成四元组式语义检查，并翻译成四元组式的假设之下，其语义规则及翻译处理设计如下，其中的假设之下，其语义规则及翻译处理设计如下，其中uminus是取相反是取相反数的单目运算符内部表示。数的单目运算符内部表示。 目录华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理30目录8.5.1 一般布尔表达式翻译一般布尔表达式翻译 对于一般关系表达式对于一般关系表达式id1 rop id2，可以理解成等价的选择计算，可以理解成等价的选择计算if id1 rop id2 then t:1 else t:0，其中，其中 t是编译内部生成的临时变量。是编译内部生成的临时变量。即其

33、翻译如下在四元组序列，这个序列称为关系表达式即其翻译如下在四元组序列，这个序列称为关系表达式id1 rop id2翻译翻译的目标代码结构如图的目标代码结构如图8.2所示。所示。 8.5 布尔表达式翻译布尔表达式翻译华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理31所谓所谓“目标代码结构目标代码结构”是指将源语言语法成分翻译成中间语言是指将源语言语法成分翻译成中间语言或目标语言的、等价的代码序列一般格式。或目标语言的、等价的代码序列一般格式。例如，表示例如，表示ax and xb对应目标代码对应目标代码(即四元组序列即四元组序列)如下，其中如下，其中t1、t2和和t3为临时变量。为

34、临时变量。and华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理32假设一般布尔表达式文法规则是假设一般布尔表达式文法规则是 EE or EE and Enot E(E)id rop idtruefalse。在自底向上语法制导下，一般布尔表达式的。在自底向上语法制导下，一般布尔表达式的翻译处理设计示例如下。这里，不含相关语义规则处理。翻译处理设计示例如下。这里，不含相关语义规则处理。 华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理33逻辑逻辑“或或”和和“与与”运算的特性是指对于逻辑运算的特性是指对于逻辑“或或”表达式只表达式只要有一个运算对象为真，则表达式为真；对于

35、逻辑要有一个运算对象为真，则表达式为真；对于逻辑“与与” 表达式只表达式只要有一个运算对象为假，则表达式为假。这样，如果逻辑要有一个运算对象为假，则表达式为假。这样，如果逻辑“或或”表达表达式式A or B的计算的计算A为真，则实际上可以不再计算为真，则实际上可以不再计算B，且表达式为真。逻，且表达式为真。逻辑辑“与与”表达式表达式A and B的情况类似。的情况类似。基于这种思路采用的翻译方法，在下面控制语句中的布尔表达基于这种思路采用的翻译方法，在下面控制语句中的布尔表达式翻译中详细讨论。式翻译中详细讨论。 8.5.2 控制语句中布尔表达式翻译控制语句中布尔表达式翻译华中科技大学计算机学院

36、华中科技大学计算机学院编译原理编译原理34基本的控制语句是基本的控制语句是if语句和语句和while语句，使用下列文法定义，目标语句，使用下列文法定义，目标代码结构如图代码结构如图8.3所示。非终结符所示。非终结符S和和E含义分别是语句和布尔表达式。含义分别是语句和布尔表达式。GS： Sif E then S1 Sif E then S1 else S2 Swhile E do S1 注意：注意： E代码中代码中生成转移四元组时刻，其转移地址无法确定，需要生成转移四元组时刻，其转移地址无法确定，需要等待翻译生成后续四元组后才获得转移地址，进行等待翻译生成后续四元组后才获得转移地址，进行“回填回

37、填”的。的。华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理35(jrop ，id1 ， id2 ，Etrue)(jump ，Efalse)或：或：if id1 rop id2 goto Etruegoto Efalse对于对于E为基本布尔表达式为基本布尔表达式id1 rop id2 ，其目标代码结构设计如图，其目标代码结构设计如图8.4所所示。其中示。其中E.true和和E.false分别表示分别表示id1 rop id2归约到归约到E时，需要回填地址的时，需要回填地址的真值和假值转移四元组编号真值和假值转移四元组编号( (地址地址) )。具体回填地址由布尔表达式。具体回填地址由

38、布尔表达式E所在的所在的控制语句中控制语句中S1 和和S2翻译后确定的。翻译后确定的。E.true和和E.false称为布尔表达式称为布尔表达式E的真出的真出口口和和假出口假出口。 例如，语句例如，语句if ab then x:1 else x:-1的翻译成四元组序列如下。的翻译成四元组序列如下。华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理36对于布尔表达式对于布尔表达式E为为E1 or E2 和和E1 and E2，其目标代码结构设计，其目标代码结构设计如图如图8.5所示。所示。 从图从图8.5 E1 or E2 和和E1 and E2代码结构可以看出，多个四元组需要代码结构

39、可以看出，多个四元组需要回填转移地址。问题是回填转移地址。问题是 E1 or E2( (或或E1 and E2) ) 归约到归约到E时，一个时，一个E.true ( (或或E.false) )如何如何记录多个需要回填转移地址的四元组？记录多个需要回填转移地址的四元组？ 可采用可采用“拉拉链链回填回填”技术解决。技术解决。注意：对于注意：对于E1 or E2，属性，属性E1.true和和E2.true存放的回填地址是存放的回填地址是同一同一个四元组序号个四元组序号；对于；对于E1 and E2，属性，属性E1.false和和E2.false存放的回填地址存放的回填地址是是同一个四元组序号同一个四

40、元组序号。华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理37将回填地址的四元组作为结点，利用其第四分量作为指针域，存储将回填地址的四元组作为结点，利用其第四分量作为指针域，存储在语义栈中在语义栈中E的属性的属性E.true和和E.false作为头指针，分别将回填相同地址四作为头指针，分别将回填相同地址四元组，链接成一个回填真出口和一个回填假出口的单链表。在遇到回填元组，链接成一个回填真出口和一个回填假出口的单链表。在遇到回填真出口或假出口地址时，依据真出口或假出口单链表，可以找到并回填真出口或假出口地址时，依据真出口或假出口单链表，可以找到并回填所有的需要回填地址的四元组。这种方

41、法简称为所有的需要回填地址的四元组。这种方法简称为“拉链拉链回填回填”技术。技术。 例如，对于下列语句，在例如，对于下列语句，在LR分析制导下，在分析制导下，在cb or bd or ca or ad归约到归约到E时，分析器以及翻译生成四元组的状态如下屏所示。时，分析器以及翻译生成四元组的状态如下屏所示。 if cb or bd or ca or ad then x: 1 else x:-1“拉链拉链回填回填”技术技术华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理38华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理39控制语句中的布尔表达式翻译控制语句中的布尔表达式翻

42、译参见参见课程内容课程内容8.5.2 ，其中，其中使用到子程序和属性等含义如下。使用到子程序和属性等含义如下。merge(p,q)是将是将p和和q为头指针的两个单链表合并成一个单链表的为头指针的两个单链表合并成一个单链表的子程序，其返回值为合并后单链表的头指针；子程序，其返回值为合并后单链表的头指针；backpath(p,t)是把是把p为头指针的单链表中的所有四元组第四分量为头指针的单链表中的所有四元组第四分量回填地址回填地址t的子程序；的子程序；属性属性E.codebegin表示归约到表示归约到E的表达式对应生成的第一个四元组的表达式对应生成的第一个四元组式之序号式之序号(即地址即地址)；n

43、ull表示空属性值，则在控制控制语句中的布尔表达式翻译设计表示空属性值，则在控制控制语句中的布尔表达式翻译设计示例如下。这里，不含相关语义规则处理。示例如下。这里，不含相关语义规则处理。 目录华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理40华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理41目录8.6.1 条件转移语句条件转移语句 仅以仅以if语句和语句和while语句之基本控制语句为例，说明控制语句的翻语句之基本控制语句为例，说明控制语句的翻译基本技术。译基本技术。if语句和语句和while语句使用下列文法语句使用下列文法GS定义。其中，非终结符定义。其中，非终结

44、符S、L、A和和E的含义分别是语句、语句串、赋值语句和布尔表达式。的含义分别是语句、语句串、赋值语句和布尔表达式。 GS： Sif E then S Sif E then S else S Swhile E do S Sbegin L end SA LL；S LS 8.6 控制结构翻译控制结构翻译华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理42前面已经完成了构成基本控制语句的核心部分，即赋值语句和前面已经完成了构成基本控制语句的核心部分，即赋值语句和布尔表达式的翻译技术的讨论。现在仅仅需要解决转移四元组地址回布尔表达式的翻译技术的讨论。现在仅仅需要解决转移四元组地址回填的问题。

45、填的问题。 回填地址的四元组可分为三类（可参见图回填地址的四元组可分为三类（可参见图8.3）：第一类是布尔表）：第一类是布尔表达式达式E产生的转移四元组，第二类是产生的转移四元组，第二类是if语句中语句中S1 和和S2对应四元组序列之间对应四元组序列之间一个转移四元组，第三类是一个转移四元组，第三类是while语句中末尾的一个转移四元组。语句中末尾的一个转移四元组。 华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理43由于由于if语句和语句和while语句可以嵌套使用，第二类和第三类必然出现语句可以嵌套使用，第二类和第三类必然出现多个转移四元组依次连续转移而最终转移到相同的四元组的

46、情况。多个转移四元组依次连续转移而最终转移到相同的四元组的情况。例如，语句例如，语句if ab then if cd then x:0 else x:1 else x:2的代的代码结构如下，其中四元组码结构如下，其中四元组(105)和和(107)就是这种情况的示例就是这种情况的示例。 华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理44这样连续转移的四元组序列会随着嵌套层数增加而增长。显然，这样连续转移的四元组序列会随着嵌套层数增加而增长。显然，这将导致目标代码的运行效率降低。通常生成四元组时，对这样连续这将导致目标代码的运行效率降低。通常生成四元组时，对这样连续转移的四元组序列，

47、同样采用第一类中使用的转移的四元组序列，同样采用第一类中使用的“拉链拉链回填回填”技术，技术，使得序列中的每个转移四元组直接转移到目标地址。使得序列中的每个转移四元组直接转移到目标地址。 为了及时回填地址，文法为了及时回填地址，文法GS等价转换为等价转换为GS。 GS： SCS1 STPS2 SWdS3 Sbegin L end SA LLSS1 LS2 Cif E then TPCS else WdWE do Wwhile LSL； 华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理45华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理46L ；SWd SW E doC

48、Swhile A B if E thenX:=Y+ZC DCodebegin:100E.true : 100E.false: 101100 if AB goto -101 gotoChain : 101 Codebegin:100102102 if CD goto -103 goto104107 106 goto 100E.true: 102E.false: 103100Chain :103104 T:=Y+Z 105 X:=Tchain: 0chain:103Chain:101while (AB) do if (CD) then X:=Y+ZChain:101Ls107华中科技大学计算机学院

49、华中科技大学计算机学院编译原理编译原理478.6.2 开关语句开关语句华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理48目录8.6.3 for循环语句循环语句华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理49简单说明语句是指基本数据类型的变量说明语句。它用于定义简单说明语句是指基本数据类型的变量说明语句。它用于定义了源程序中引用的标识符是什么数据类型的变量，其数据类型说明了源程序中引用的标识符是什么数据类型的变量，其数据类型说明了变量对应存储单元的大小和数据格式等属性，作为编译存储分配了变量对应存储单元的大小和数据格式等属性，作为编译存储分配和语义分析依据。和语义分

50、析依据。简单说明语句翻译主要任务是将其定义的标识符及其相关属性简单说明语句翻译主要任务是将其定义的标识符及其相关属性登记在符号表中以备后用。在符号表中至少含有标识符自身和数据登记在符号表中以备后用。在符号表中至少含有标识符自身和数据类型。类型。目录8.7 说明语句翻译说明语句翻译华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理50 ATT为数据类型属性为数据类型属性 enter(name, A)是将标识符是将标识符name和数据类型和数据类型A登记到符号表中的登记到符号表中的子程序子程序下面是简单说明语句文法及其主要语义处理。下面是简单说明语句文法及其主要语义处理。注意：注意：AT

51、T属于综合属性，属于综合属性，enter()出现实参出现实参int和和real为为ATT的属性值。的属性值。 目录华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理51目录如果一个数组是静态数组，则其下标上下界如果一个数组是静态数组，则其下标上下界lk hk(1kn)和数组和数组元素类型大小元素类型大小L均为常量。自然地，其界差均为常量。自然地，其界差dkhklk+1(1kn)必为必为常数，即界差在编译阶段是可以计算出来的。这样，静态数组的寻址常数，即界差在编译阶段是可以计算出来的。这样，静态数组的寻址公式可以分解为常量部分公式可以分解为常量部分(CONSPART)与非常量部分与非常

52、量部分(VARPART)之和。之和。即即 +(i1-l1)d2d3dn+(i2-l2)d3d4dn +.+(in-1-ln-1)dn+(in-ln) ) L =CONSPARTVARPART 其中，其中，CONSPART C C (l1d2d3d4dnl2d3d4dnl n1dnl n)L VARPART (i1d2d3d4dni2d3d4dnin1dnin)L 8.8 数组和结构翻译数组和结构翻译华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理52数组内情向量子表可以设计如下。其中，仍然存储上下界数组内情向量子表可以设计如下。其中，仍然存储上下界lkhk(1kn)目的在于语义检查，事实上仅仅是辅助代码与上下目的在于语义检查，事实上仅仅是辅助代码与上下界是无关的。界是无关的。 l1h1d1l2h2d2l nh nd nnCelementype华中科技大学计算机学院华中科技大学计算机学院编译原理编译原理53数组元素数组元素 Ai1，i2，in 引用翻译的目标结构是计算下标表达引用翻译的目标结构是计算下标表达式四元组序列、计算式四元组序列、计算VARPART四元组序列四元组序列(令结果存储