《语法制导翻译和中间代码生成new.ppt》由会员分享，可在线阅读，更多相关《语法制导翻译和中间代码生成new.ppt（131页珍藏版）》请在金锄头文库上搜索。
1、第八章语法制导翻译和中间代码生成【课前思考】回顾第一章介绍的编译过程，理解语义分析在编译过程中的位置和作用。“属性文法”的概念及应用。“语法制导翻译”的概念及应用。什么是中间代码（中间表示），为什么要中间代码？【学习目标】明确语义分析在编译过程所处的阶段和作用。掌握属性文法的基本概念。使用属性文法和语法制导翻译方法描述具体的语义分析和产生中间代码。主要是要让同学们了解：)语义的描述方式；)语义的处理方法。【本章重点】1.1.几种典型的中间代码（语言）的形式; ;2.2.语义的描述方法 着重介绍一种形式化的语义描述方法属性文法; ;3.3.语义的处理方法 着重介绍语法制导的翻译法包括它的两种具体
2、形式：语法制导的定义和翻译方案 。编译程序的任务是把源程序翻译成目标程序，这个目标程序必须和源程序的语义等同，也就是说，尽管它们的语法结构完全不同，但它们所表达的结果应完全相同。通常，在词法分析程序和语法分析程序对源程序的语法结构进行分析之后，要么由语法分析程序直接调用相应的语义子程序进行语义处理，要么首先生成语法树或该结构的某种表示，再进行语义处理。8.0概述第八章语法制导翻译和中间代码生成第一，审查每个语法结构的静态语义，即验证第一，审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。有时把这个语法结构合法的程序是否真正有意义。有时把这个工作称为静态语义分析或静态审查。工作
3、称为静态语义分析或静态审查。第二，如果静态语义正确，语义处理则要执行第二，如果静态语义正确，语义处理则要执行真正的翻译，即，或者将源程序翻译成程序的一种真正的翻译，即，或者将源程序翻译成程序的一种中间表示形式（中间代码），或者将源程序翻译成中间表示形式（中间代码），或者将源程序翻译成目标代码。目标代码。本章引入属性文法和语法制导翻译方法的基本本章引入属性文法和语法制导翻译方法的基本思想，介绍几种典型的中间代码形式，最后讨论一思想，介绍几种典型的中间代码形式，最后讨论一些语法成分的翻译工作。些语法成分的翻译工作。编译中的语义处理是指两个功能：编译中的语义处理是指两个功能：8.1属性文法(attr
4、ibutegrammar)属性文法( (也称属性翻译文法) )是KnuthKnuth在19681968年首先提出的。它是在上下文无关文法的基础上，为每个文法符号( (终结符或非终结符) )配备若干相关的“特性”（称为属性）。这些属性代表与文法符号相关信息，例如它的类型、值、代码序列、符号表内容等等。属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。为文法的每个产生式配备的一组属性的计算规则，为文法的每个产生式配备的一组属性的计算规则，称为语义规则，称为称为语义规则，称为语义规则语义规则。 所谓属性，其涉及的概念比较广泛，常用以描所谓属性，其涉及的概念比较广泛，常用以描述事物
5、或人的特征、性质，品质等等。比如，谈到述事物或人的特征、性质，品质等等。比如，谈到一个物体，可以用一个物体，可以用 颜色颜色 描述它，谈起某人，可以描述它，谈起某人，可以使用使用 有幽默感有幽默感 来形容他。对编译程序使用的语法来形容他。对编译程序使用的语法树的结点，可以用树的结点，可以用 类型类型 、 值值 或或 存储位置存储位置 来描来描述它。述它。 一个属性文法包含一个上下文无关文法和一系列一个属性文法包含一个上下文无关文法和一系列语义规则，这些语义规则附在文法的每个产生式上。语义规则，这些语义规则附在文法的每个产生式上。所谓所谓语法制导的翻译语法制导的翻译指的是在语法分析过程中，指的是
6、在语法分析过程中，完成这些语义规则描述的动作，从而实现语义处理。完成这些语义规则描述的动作，从而实现语义处理。8.1.1属性文法定义定义1：形式上讲，属性文法是一个三元组 :A=(G，V，F)，其中：G:是一个上下文无关文法；V:有穷的属性集,每个属性与文法的一个终结符或非终结符相联,这些属性代表与文法符号相关信息；F:关于属性的属性断言或一组属性的计算规则(称为语义规则)。断言或语义规则与一个产生式相联,只引用该产生式左端或右端的终结符或非终结符相联的属性。定义2 2：一个属性文法是一个三元组：A=(G,V,F ),A=(G,V,F ),其中uG -G -基础文法（一个上下文无关文法）uV
7、-V -每个文法符号有一组属性uF -F -每个文法产生式A A有一组形式为b b:=:=f f( (c c1 1, ,c c2 2, , ,c ck k) )的语义规则，其中f f 是函数，b b和c c1 1, ,c c2 2, , ,c ck k是该产生式文法符号的属性。 属性文法中的属性分成两类：继承属性和综合属属性文法中的属性分成两类：继承属性和综合属性。性。简单地说，综合属性用简单地说，综合属性用 自下而上自下而上 传递信息，而传递信息，而继承属性用于继承属性用于 自上而下自上而下 传递信息。传递信息。 u综合属性（综合属性（synthesized attribute）：）：如果如
8、果b是是A的的属性，属性，c1 , c2 , , ck是产生式右部文法符号的属性是产生式右部文法符号的属性或或A的其它属性，则称的其它属性，则称b是是文法符号文法符号A的综合属性。的综合属性。u继承属性继承属性(inherited attribute)：如果如果b是产生式是产生式右部某个文法符号右部某个文法符号X的属性，并且的属性，并且c1,c2,ck是是A或或产生式右部文法符号的属性，则称产生式右部文法符号的属性，则称b是文法符号是文法符号X的的继承属性。继承属性。每个文法产生式每个文法产生式A有一组形式为有一组形式为b:=f(c1,c2,ck)的语义规的语义规则，其中则，其中f 是函数，是
9、函数，b和和c1,c2,ck是该产生式文法符号的属性是该产生式文法符号的属性属性文法的主要思想是：属性文法的主要思想是：1.对每个文法符号引入相关的属性符号；对每个文法符号引入相关的属性符号；2.对于每个产生式设置一组计算属性值的属性规则（语对于每个产生式设置一组计算属性值的属性规则（语义规则），其形式为：义规则），其形式为：b：= f(c1, c2, , ck ) 即：属性变量：即：属性变量：=这里这里 f是一个函数，且对于产生式是一个函数，且对于产生式A ，(1) b或者是或者是A的一个综合属性并且的一个综合属性并且c1,c2,，ck是产生式是产生式右边文法符号的属性；右边文法符号的属性；
10、(2) b或者是产生式右边某个文法符号的一个继承属性并或者是产生式右边某个文法符号的一个继承属性并且且c1,c2,，ck是是A或产生式右边任何文法符号的属性。或产生式右边任何文法符号的属性。 在两种情况下，我们都说属性在两种情况下，我们都说属性b依赖于属性依赖于属性c1,c2,，ck。即：属性规则中的左部即：属性规则中的左部b能写那些属性变量是有规定的，能写那些属性变量是有规定的，只能为下述两种变量：只能为下述两种变量：产生式左部符号的综合属性变量；产生式左部符号的综合属性变量；产生式右部符号的继承属性变量。产生式右部符号的继承属性变量。2.对于每个产生式设置一组计算属性值的属性规则（语义规则
11、）对于每个产生式设置一组计算属性值的属性规则（语义规则），其形式为：，其形式为： b：= f(c1, c2, , ck ) 即属性变量：即属性变量：=，这里，这里 f是一个函数，且对于产生式是一个函数，且对于产生式A A ，(1) 1) b b或或者者是是A A的的一一个个综综合合属属性性并并且且c c1 1,c,c2 2，c ck k是是产产生生式式右右边边文文法符号的属性；法符号的属性；(2) (2) b b或或者者是是产产生生式式右右边边某某个个文文法法符符号号的的一一个个继继承承属属性性并并且且c c1 1,c,c2 2，c ck k是是A A或产生式右边任何文法符号的属性。或产生式右
12、边任何文法符号的属性。在两种情况下，我们都说属性在两种情况下，我们都说属性b b依赖于属性依赖于属性c c1 1,c,c2 2，c ck k。 继承属性的求值规则：继承属性的求值规则：产生式左部非终结符号的继承属性值产生式左部非终结符号的继承属性值取取（来自于）（来自于）前面前面产生式右部该符号已有的继承属性值；产生式右部该符号已有的继承属性值；产生式右部符号的继承属性值产生式右部符号的继承属性值用用该产生式左部符号的继该产生式左部符号的继承属性或出现在该符号左部的符号的属性值进行计算。承属性或出现在该符号左部的符号的属性值进行计算。体现自顶向下，自体现自顶向下，自左向右的求值特性左向右的求值
13、特性体现自底向上，自体现自底向上，自右向左的求值特性右向左的求值特性综合属性的求值规则：综合属性的求值规则：产生式右部非终结符号的综合属性值产生式右部非终结符号的综合属性值取（来自于）取（来自于）其下其下面产生式左部同名非终结符号的综合属性值；面产生式左部同名非终结符号的综合属性值；产生式左部非终结符号的综合属性值产生式左部非终结符号的综合属性值用用该产生式左部符该产生式左部符号的继承属性或某个右部符号的属性进行计算；号的继承属性或某个右部符号的属性进行计算；例8.1 8.1 有文法G G为：ETET1 1 + T + T2 2|T|T1 1 or Tor T2 2Tnum|true|fals
14、e Tnum|true|false 对输入串3+43+4的类型检查的属性文法如图8.18.1。 ET1+T2T1.tintANDT2.tintET1orT2T1.tboolANDT2.tboolTnumT.t intTtrueT.t boolTfalseT.t bool图8.1类型检查的属性文法 属性文法记号中常使用属性文法记号中常使用N.tN.t的形式表示与非终结符的形式表示与非终结符N N相联的相联的属性属性t t。比如可把对上面表达式的类型检查的属性文法写成图比如可把对上面表达式的类型检查的属性文法写成图8.18.1的形式。与每个非终结符的形式。与每个非终结符T T相联的有属性相联的有属
15、性t t，t t要么是要么是intint，要么是要么是boolbool。与非终结符与非终结符E E的产生式相联的语义规则指明：两的产生式相联的语义规则指明：两个个T T的属性必须相同。的属性必须相同。图图8.28.2的（的（b b）是图是图8.2(a)8.2(a)语法树结点带有语义信息的表示。语法树结点带有语义信息的表示。 图图8.2 静态语义审查静态语义审查 ETT+34（a）ETT+34（b）T2. .t=intT1. .t=intT1. .t= T2. .t 8.1.2属性的确定写属性文法，首先应确定对于每个文法符号都有哪些属性，然后给每个属性起个名字，接着确定每个属性的类别。要特别强调
16、的是：（1）终结符只有综合属性，它们的值由词法分析器提供；（2）非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值要在计算（整个处理）开始时指定。 正确确定综合属性和继承属性是非常重要的，究竟哪些属正确确定综合属性和继承属性是非常重要的，究竟哪些属性确定为综合属性，哪些属性确定为继承属性，并没有固定的性确定为综合属性，哪些属性确定为继承属性，并没有固定的模式。模式。例8.2 8.2 简单算术表达式求值的语义描述。产生式语义规则LEprint(E.val)EE1+TE.val E1.val+T.valETE.val T.valTT1*FT.val T1.val
17、*F.valTFT.val F.valF（E）F.val E.valFdigitF.val digit.lexval在该描述中，大多数非终结符都有一个属性：一个整数值的称作在该描述中，大多数非终结符都有一个属性：一个整数值的称作valval的的属性。属性。按照语义规则对每个产生式来说，它的左部按照语义规则对每个产生式来说，它的左部E E，T T，F F的属性值的计算来的属性值的计算来自它右部的非终结符，这种属性称作综合属性。自它右部的非终结符，这种属性称作综合属性。单词单词digitdigit仅有综合属性，它的值是由词法分析程序提供的。仅有综合属性，它的值是由词法分析程序提供的。和产生式和产生
18、式LELE相联的语义规则是一个过程，打印由相联的语义规则是一个过程，打印由E E产生的表达式的值。产生的表达式的值。我们可以理解为我们可以理解为L L的属性是空的或是虚的。的属性是空的或是虚的。例 8.38.3描述说明语句中各种变量的类型信息的语义规则。产生式语义规则（1）DTLL.in T.type（2）TintT.Type integer（3）TrealT.Type real（4）LL1，idL1.in L.in;addtype（id.entry，L.in）（5）Lidaddtype（id.entry，L.in）例例8.38.3中的文法定义了一种说明语句，该说明语句的形式是由关键字中的文法
19、定义了一种说明语句，该说明语句的形式是由关键字intint或或realreal开头，后面是一个标识符表，每个标识符用逗号隔开。开头，后面是一个标识符表，每个标识符用逗号隔开。非终结符非终结符T T有一个综合属性有一个综合属性typetype，它的值由关键字决定（它的值由关键字决定（intint或或realreal）。）。与产生式与产生式DTLDTL相联的语义规则相联的语义规则L.inL.inT.typeT.type将将L.in(L.in(继承属性继承属性) )的属性值的属性值置为该说明语句指定的类型。属性置为该说明语句指定的类型。属性L.inL.in将被沿着语法树传递到下边的结点将被沿着语法树
20、传递到下边的结点使用，与使用，与L L产生式相联的规则里使用了它。产生式相联的规则里使用了它。 这个例子里，继承属性这个例子里，继承属性L.in在说明中为各个标识符提供类型信息。在说明中为各个标识符提供类型信息。 图8.48.4是句子intint id id1 1,id,id2 2的语法树，使用表示属性的传递情况。在语法树中，一个结点的继承属性由此结点的父结点和/ /或兄弟结点的某些属性确定。与L L产生式相联的语义规则中有一个过程调用addtypeaddtype，过程addtypeaddtype的功能是把每个标识符的类型信息登录在符号表的相关项中。 图图 8.4 属性信息传递情况属性信息传递
21、情况 D T L Lintid1，Id28.1.3属性计算规则的确定一般说来，对产生式右部符号的继承属性和产生式左部符号的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性，这有助于在产生式范围内“封装”属性的依赖性。然而，对产生式左部符号的继承属性和产生式右部符号的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计算器的参数提供。属性文法看作是允许为每个终结符和非终结符配备一些属性的文法。它既能描述程序设计语言的语法，又为语义处理提供了方便。属性文法里的属性有不同的类型，可以象变量一样地被属性文法里的属性有不同的类型，可
22、以象变量一样地被赋值。赋值规则附加于语法规则之上。赋值与语法同时进行，赋值。赋值规则附加于语法规则之上。赋值与语法同时进行，赋值过程就是语义处理过程。赋值过程就是语义处理过程。在推导或者归约的时候，诸属性的值被计算并通过赋值在推导或者归约的时候，诸属性的值被计算并通过赋值规则层层传递。有的从语法规则左边向右边传，有的从右边规则层层传递。有的从语法规则左边向右边传，有的从右边向左边传。语法推导树最后完成时，就得到开始符号的属性向左边传。语法推导树最后完成时，就得到开始符号的属性值。也就是整个源程序的语义。值。也就是整个源程序的语义。 中间代码，也称中间语言，是复杂性介于源程序中间代码，也称中间语
23、言，是复杂性介于源程序语言和机器语言的一种表示形式。语言和机器语言的一种表示形式。为什么有的编译程序直接生成目标代码，有的编为什么有的编译程序直接生成目标代码，有的编译程序采用中间代码。译程序采用中间代码。一般，快速编译程序直接生成目标代码，没有将一般，快速编译程序直接生成目标代码，没有将中间代码翻译成目标代码的额外开销。中间代码翻译成目标代码的额外开销。但是为了使编译程序结构在逻辑上更为简单明确，但是为了使编译程序结构在逻辑上更为简单明确，常采用中间代码。常采用中间代码。这样可以将与机器相关的某些实现细节置于代码这样可以将与机器相关的某些实现细节置于代码生成阶段仔细处理，并且可以在中间代码一
24、级进行优生成阶段仔细处理，并且可以在中间代码一级进行优化工作使得代码优化比较容易实现。化工作使得代码优化比较容易实现。 8.2中间代码（语言）中间代码（语言）是一种特殊结构的语言，编译程序所使用的中间代码有多种形式。按其结构分常见的有逆波兰式（后缀式）、三地址代码（三元式、四元式）和树形表示（抽象语法树）、DAG表示。8.2.1逆波兰式（后缀式）逆波兰式是最简单的一种中间代码表示形式，早在编译程序出现之前，它主要用于表示算术表达式，是波兰逻辑学家卢卡西维兹(J.Lukasiewicz)于1929年发明的。后来人们为了纪念他，就把这种后缀表示取名为逆波兰式。逆波兰式最早是用于表示表达式的,后来计
25、算机科学家把它应用于表示程序语言的各种语法成分。（一）特点首先我们考察算术表达式（中缀式）的计值顺序.例8.4中缀式的计值顺序见图8.5。 中缀式计值三个特点：中缀式计值三个特点：（1）运算对象分别放在运算符（双目运算符）的两边；）运算对象分别放在运算符（双目运算符）的两边；（2）计值顺序是根据运算符的优先级别及结合性确定，）计值顺序是根据运算符的优先级别及结合性确定，使用括号可以改变计值顺序；使用括号可以改变计值顺序；（3）运算符的排列顺序不等价于计值顺序。）运算符的排列顺序不等价于计值顺序。图图8.5 中缀式的计值顺序例中缀式的计值顺序例a + b * ( c + d * ( e f )
26、)a + b * ( c + d * ( e f ) )（1）不考虑运算符的优先关系，又不使用括号；（2）运算符的排列顺序就是计值顺序；（3）运算对象放在运算符的前面。这种表示称为逆波兰式，也称做后缀式。中缀式虽然是人们习惯的表示，但对于计算机来说，处中缀式虽然是人们习惯的表示，但对于计算机来说，处理起来很不方便，如果我们采用一种表示方法：理起来很不方便，如果我们采用一种表示方法：如上例：如上例：a b ( c d ( e f ) )其逆波兰式为：其逆波兰式为：a b c d e f 这种后缀表示法虽然不符合人们的习惯，但它极易被计算机这种后缀表示法虽然不符合人们的习惯，但它极易被计算机来处理
27、。由于后缀式表示上的简洁和计值的方便，特别适用来处理。由于后缀式表示上的简洁和计值的方便，特别适用于解释执行的程序设计语言的中间表示，也方便具有堆栈体于解释执行的程序设计语言的中间表示，也方便具有堆栈体系的计算机的目标代码生成。系的计算机的目标代码生成。 (二)定义逆波兰式（后缀式）的一般形式为：若是一个K元运算符（K1），它对其运算对象e1,e2,ek作用的结果被表示为：e1e2ek 表达式表达式E E的后缀表示的递归定义：的后缀表示的递归定义：（1 1）如果）如果E E是变量或常数，那么是变量或常数，那么E E的后缀表示是的后缀表示是E E本身；本身；（2 2）如果）如果E E是形如是形如
28、E E1 1 op Eop E2 2的表达式，其中的表达式，其中opop是任意的二元运算是任意的二元运算符，那么符，那么E E的后缀表示是的后缀表示是E E1 1 | E| E2 2 | op ,| op ,其中；其中；E E1 1 和和E E2 2 分别是分别是E E1 1和和 E E2 2的后缀表示，的后缀表示，| | 称为称为连接连接 （并置）运算符；（并置）运算符；（3 3）如果）如果E E是形如（是形如（E E1 1），），那么那么E E的后缀表示就是的后缀表示就是E E1 1的后缀表示。的后缀表示。（三）转换（中缀式 后缀式）转换算法： 转换规则：设E E为给定的中缀式，我们用表示
29、E E的后缀式，则有： E E | ； ； a, a,其中a a表示变量或常数。 对于给定的中缀式首先找出最后被计算的运算符，并把此运算符作为上述式中的 ，使用上述规则转换之； 对中缀式的剩余部分重复上述过程，直至中缀式的每个量均被处理到为止。把一般表达式翻译为后缀式是很容易的。表表8.1 把表达式翻译为后缀式的语义规则描述把表达式翻译为后缀式的语义规则描述 产产 生生 式式 语语 义义 规规 则则EE1 op E2 E.code =E1.code |E2.code | opE（E1） E.code =E1.codeEid E. .code=id 表表8.1给出了把表达式翻译为后缀式的语义规则
30、描述，给出了把表达式翻译为后缀式的语义规则描述，其中其中E.code表示表示E后缀形式，后缀形式，op表示任意二元操作符，表示任意二元操作符，“|”表示后缀形式的连接。表示后缀形式的连接。 解：ETRnumprint(8)Rnumprint(8)+Tprint(+)R1numprint(8)+numprint(5)print(+)R1numprint(8)+numprint(5)print(+) Tprint( )R1numprint(8)+numprint(5)print(+) numprint(2)print( )R1numprint(8)+numprint(5)print(+) nump
31、rint(2)print( )输出：print(8)print(5)print(+)print(2)print( )即：85+2 例例8.5 有下面翻译模式：有下面翻译模式：ETRRT print（）R1|T print（）R1| Tnum print（num.val）把中缀表达式把中缀表达式8+5 2翻译成后缀表达式。翻译成后缀表达式。后缀式很容易扩充到表达式以外的范围。只要遵守运算对象后直接紧跟它们的运算符的规则即可。赋值语句的后缀表示：如有aab + cb + c，则有 a b c + a b c + 转向语句GOTO LGOTO L的后缀表示为“L jumpL jump”，运算对象L
32、L为语句标号，运算符jumpjump表示转到某个标号。数组元素数组元素AA下标表达式下标表达式1 1，下标表达下标表达式式n n 的后缀表示可表示为：的后缀表示可表示为：下标表达式下标表达式1 1下标表达式下标表达式2 2 下标下标表达式表达式n nA subsA subs，运算符运算符SubsSubs表示求数组的下标。表示求数组的下标。 当然，这些扩充的后缀表示的计值远比后缀表达当然，这些扩充的后缀表示的计值远比后缀表达式的计值复杂得多，要注意对扩展的运算符的含义正式的计值复杂得多，要注意对扩展的运算符的含义正确处理。确处理。条件语句条件语句if E then Sif E then S1 1
33、 else S else S2 2的后缀表示可表的后缀表示可表示为：示为： E SE S1 1 S S2 2 ￥，把把if-then-elseif-then-else看成三目运算符，用￥来表示。看成三目运算符，用￥来表示。8.2.2三地址代码一般形式：x x := := y op zy op z如表达式x x + + y y z z 翻译成的三地址代码序列是 t t1 1 := := y y z z t t2 2 := := x x + + t t1 1 常用的三地址表示: :赋值语句 x x := := y op zy op z， x x := := op yop y， x x := :=
34、y y无条件转移 gotogoto L L条件转移 if if x x reloprelop y y gotogoto L L过程调用 paramparam x x 和call p , call p , n n过程返回 returnreturn y y索引赋值 x x := := y y i i 和 x x i i := := y y地址和指针赋值 x x := & := &y y，x x := := y y和 x x := := y y三地址代码有四元式、三元式、间接三元式等形式三地址代码可看成中间代码的一种抽象形式。编译程序中，三地址代码语句的具体实现可以用记录表示，记录中包含表示运算符和
35、操作数的域。三地址代码通常有三种表示方法：四元式、三元式、间接三元式。 四元式结构形式:(OP，ARG1，ARG2，RESULT)算符算符左运算对象左运算对象右运算对象右运算对象运算结果运算结果三元式结构形式三元式结构形式: 编号编号 (OP，ARG1，ARG2)间接三元式：间接三元式：由间接三元式序列和间接码表组成。由间接三元式序列和间接码表组成。例8.6有中缀式a:b*cb*c，求其等价的四元式和三元式。 四元式 三元式 算符 左对象 右对象 结果量 编号 算符 左对象 右对象 op arg1 arg2 result op arg1 arg2op arg1 arg2 result op a
36、rg1 arg2 minus c T1 (1) minus c minus c T1 (1) minus c b T1 T2 (2) b T1 T2 (2) b (1) b (1) minus c T3 (3) minus c minus c T3 (3) minus c b T3 T4 (4) b T3 T4 (4) b (3) b (3) T2 T4 T5 (5) T2 T4 T5 (5) (4) (2) (4) (2) T5 a (6) assign a T5 a (6) assign a 图图8.6 四元式、三元式四元式、三元式结构结构8.2.3 8.2.3 图形表示抽象语法树是一种图
37、形化的中间表示，它的每一个叶结点都表示诸如常量或变量这样的运算对象，而它的内部结点则表示运算符；它不同于前述的语法树，它展示了一个操作过程并同时描述了源程序的自然层次结构；DAG（有向无环图）以更紧凑的方式给出了同样的信息（即对于相同的语法成分只给出一次），在图中其结点的含义同抽象语法树。assigna+ bcdcd minus(a)抽象语法树抽象语法树assigna+ bcd minus(b)DAG(b)DAG 图图8.8 a := (8.8 a := ( b + cb + c d ) + cd ) + c d d的图形表的图形表示示例：表达式例：表达式a := (a := ( b + cb
38、 + c d ) + cd ) + c d d的的两种图形两种图形表示见图表示见图8.88.8。抽象语法树是分析树的浓缩表示：算符和关键字是作为内部结点出现的。语法制导翻译可以基于分析树，也可以基于抽象语法树抽象语法树的例子：if-then-elseBS1S2+*258图图8.9 抽象语法树的例子抽象语法树的例子 抽象语法树抽象语法树构造抽象语法树的语法制导定义 F.nptr:=mkleaf (num,num.val) F num F.nptr:=mkleaf (id,id.entry) F id F.nptr:=E.nptr F (E) T.nptr:=F.nptr T F T.nptr:=
39、mknode(* *,T1.nptr, F.nptr) T T1* *F E.nptr:=T.nptr E T E.nptr:=mknode(+,E1.nptr, T.nptr) E E1+T 语义规则产 生 式图图8.10 抽象语法树的语法制导定义例子抽象语法树的语法制导定义例子例8.8a+5* *b的抽象语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5* *+ +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口图8.11(a)a+5*b的抽象语法树E.nptrT.np
40、trE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5* *+ +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口图8.11(b)a+5*b的抽象语法树T.nptrE.nptrT.nptrE.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5* *+ +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口图8.11(c)a+5*b的抽象语法树E.nptrT.nptrF.nptrE.nptrT.nptridT.nptr+*F.nptrF.nptr
41、idnumididnum 5* *+ +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口图8.11(d)a+5*b的抽象语法树T.nptrE.nptrT.nptrE.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5* *+ +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口图8.11(e)a+5*b的抽象语法树指向符号表中指向符号表中b的入口的入口E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5* *+ +指向符
42、号表中指向符号表中a的入口的入口图8.11(f)a+5*b的抽象语法树E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5* *+ +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口图8.11(g)a+5*b的抽象语法树E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5* *+ +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口图8.11(h)a+5*b的抽象语法树E.nptrT
43、.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5* *+ +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口图8.11(i)a+5*b的抽象语法树8.3 8.3 语法制导翻译编译程序的整个任务就是把源程序翻译为目标程序。实际上可以把每个编译阶段都看作是完成一定翻译任务的处理过程：词法分析阶段把字符流翻译为单词流，语法分析阶段把单词流翻译为语法树，语义分析和代码生成阶段把语法树翻译为汇编代码或者机器代码等等。定义（语法制导翻译）：为文法中每个产生式配备一组语义规则，并且在语法分为文法中每个产生式配备
44、一组语义规则，并且在语法分析过程中，随着分析的步步进展，根据每个产生式所对应析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译的的语义子程序（或语义规则描述的语义动作）进行翻译的办法称作语法制导翻译。办法称作语法制导翻译。 例8.98.9：把中缀算术表达式翻译为后缀表示形式，给出如下语义描述： ET + E1 E.code=T.code| E1.code|+ ET E.code=T.code TF * T1 T.code=F.code|T1.code| * TF T.code =F.code F（E） F.code = E.code Fa F.c
45、ode = a 其中使用其中使用E.code，T.code和和F.code分别表示其相应的后缀式，分别表示其相应的后缀式，|表示后缀式的连接。如果对于输入串表示后缀式的连接。如果对于输入串a+b*c采用最左分采用最左分析，其形成的推导过程为：析，其形成的推导过程为： E T+E F+E a+E a+T a+T* F a+F*F a+b*F a+b*c 把语义规则计算带入推导过程中，用(，)表示拓广的句型,其中是句型，是翻译的输出形式，则有：(E , E.code) (T+E, T.code|E.code|+ ) (F+E, F.code|E.code|+ ) (a+E, a|E.code|+
46、) (a+T, a|T.code|+ ) (a+FT, a|F.code|T.code|+ ) (a+bT, a|b|T.code|+ ) (a+bF, a|b|F.code|+ ) (a+b*c, a|b|c| |+ ) 去掉去掉a|b|c| | +中的连结符，得到中缀表达式中的连结符，得到中缀表达式a+bc的的后缀式后缀式a b c + 。 E T+E F+E a+E a+T a+T* F a+F*F a+b*F a+b*c 8.3.1 8.3.1 基于属性文法的处理方法处理方法：1 1）多遍扫描多遍扫描依赖图依赖图树遍历树遍历2）一遍扫描）一遍扫描基于属性文法的处理过程基于属性文法的处理
47、过程(理论上理论上):输入串输入串语法树语法树 依赖图依赖图 计算语义规则顺序计算语义规则顺序语法分析树遍历语法分析树遍历执行语义规则执行语义规则语义规则的计算可能产生代码，在符号表中存取信息，语义规则的计算可能产生代码，在符号表中存取信息，给出执行动作或出错信息。对输入串的翻译也就是根据语给出执行动作或出错信息。对输入串的翻译也就是根据语义规则进行计算的结果。义规则进行计算的结果。然而，在具体实现时并不是一定要严格按照上述顺序然而，在具体实现时并不是一定要严格按照上述顺序不可，有时也可采用一遍扫描实现属性文法的语义规则的不可，有时也可采用一遍扫描实现属性文法的语义规则的计算。即在语法分析的同
48、时完成语义规则的计算，无须明计算。即在语法分析的同时完成语义规则的计算，无须明显地去构造语法树和依赖图。但就普遍性而言，我们仍然显地去构造语法树和依赖图。但就普遍性而言，我们仍然需要了解依赖图。需要了解依赖图。8.3.2 8.3.2 属性依赖图依赖图是一个有向图，用于描述分析树中的属性和属性之间的相互依赖关系。依赖图构造算法：for 语法树中每一结点语法树中每一结点n do for 结点n的文法符号的每一个属性a do 为a在依赖图中建立一个结点；for 语法树中每一个结点n do for 结点n所用产生式对应的每一个语义规则 b:=f(c1，c2，ck) do for i:=1 to k d
49、o 从ci i结点到b结点构造一条有向边；注注:在构造依赖图之前在构造依赖图之前,要为每一个过程调用的语义规则引入一要为每一个过程调用的语义规则引入一个虚综合属性，即在依赖图中构造一个结点。这样，个虚综合属性，即在依赖图中构造一个结点。这样，若属性若属性b依赖于属性依赖于属性c，则从则从c的结点有一条有向边连接到的结点有一条有向边连接到b的结点的结点。例8.10：有属性文法见表8.2，构造intid1,id2,id3的分析树依赖图。产 生 式语义规则 D TLL.in:=T.typeTintT. type:=integerTrealT. type:=realLL1,idL1.in:=L.in;
50、addtype(id.entry,L.in)Lidaddtype(id.entry,L.in)表8.2说明语句的属性文法表8.2说明语句的属性文法图图 8.12(a) int id1, id2, id3的的注释分析树注释分析树产 生 式语义规则 D TLL.in:=T.typeTintT. type:=integerTrealT. type:=realLL1,idL1.in:=L.in;addtype(id.entry,L.in)Lidaddtype(id.entry,L.in) 先构造先构造int id1, id2, id3的语法树见图的语法树见图8.12 (a)所示。所示。 再构造inti
51、d1,id2,id3的分析树的依赖图(结点用数字表示)见图8.12b。D TLL.in:=T.typeD intT,id3LLLid2id1,1 entry102 entry3 entryin 98in 76in 54 typeaddtype (id.entry, L.in )图图 8.12(b) int id1, id2, id3的依赖的依赖图图8.3.3语义规则的计算次序1）拓扑排序）拓扑排序 从依赖图的拓扑排序中我们可以得到计算语义规则的次序从依赖图的拓扑排序中我们可以得到计算语义规则的次序，用这个顺序来计算语义规则就得到了输入串的翻译。，用这个顺序来计算语义规则就得到了输入串的翻译。拓
52、扑排序：结点的一种排序，使得有向边只会从该次序中拓扑排序：结点的一种排序，使得有向边只会从该次序中先出现的结点指向后出现的结点。先出现的结点指向后出现的结点。 例：图例：图8.12 (b)的拓扑排序为：的拓扑排序为：1，2，3，4，5，6，7，8，9，10 。一个依赖图的任何拓扑排序都给出了语法树中结点的语义规则计算的有效顺序。2）属性的计算过程图图8.12 (a) int id1, id2, id3的语法树的语法树 DintT,id3LLLid2id1, 属性计算有树遍历和一遍扫描两种方法。属性计算有树遍历和一遍扫描两种方法。 树遍历：构造输入的语法树见图树遍历：构造输入的语法树见图8.12
53、 (a)，2）属性的计算过程DintT.type = integer,id3L.in = integerL.in = integerL.in = integerid2id1,图图 8.13int id1, id2, id3的注释分析树的注释分析树构造带有属性分析树见图构造带有属性分析树见图8.13。属性计算有树遍历和一遍扫描两种方法。属性计算有树遍历和一遍扫描两种方法。树遍历：构造输入的语法树见图树遍历：构造输入的语法树见图8.12(a)，用深度优先遍历该分析树。还可以采用一遍扫描的处理方法来计算属性值。还可以采用一遍扫描的处理方法来计算属性值。 一遍扫描的处理方法不同于树遍历的方法，它一遍扫
54、描的处理方法不同于树遍历的方法，它不需要构造实际语法树，而是在语法分析的同时计不需要构造实际语法树，而是在语法分析的同时计算属性值。算属性值。如果需要的话，可以进行多次遍历，直至计算如果需要的话，可以进行多次遍历，直至计算出所有属性。出所有属性。3）树遍历的属性计算方法现在我们来考虑如何通过树遍历的方法计算属性的值。通过树遍历计算属性值的方法有多种。这些方法都假设语法树已经建立起了，并且树中已带有开始符号的继承属性和终结符的综合属性。然后以某种次序遍历语法树，直至计算出所有属性。最常用的遍历方法是深度优先遍历的方法。如果需要的话，可使用多次遍历（或称遍）。8.3.4S-属性文法和自下而上翻译S
55、-属性文法：仅仅使用综合属性的属性文法。属性文法：仅仅使用综合属性的属性文法。 1）综合属性的求值规则：产生式右部非终结符号的综合属性值取其下面产生式左部同名非终结符号的综合属性值；产生式左部非终结符号的综合属性值用该产生式左部符号的继承属性或某个右部符号的属性进行计算；体现自底向上，自体现自底向上，自左向右左向右的求值特性的求值特性在语法树中，一个结点的综合属性的值由其子结点的属在语法树中，一个结点的综合属性的值由其子结点的属性值确定。而叶结点的（终结点）的综合属性值由词法分性值确定。而叶结点的（终结点）的综合属性值由词法分析得到。析得到。因此，通常使用自底向上的方法在每个结点处执行语义因此
56、，通常使用自底向上的方法在每个结点处执行语义规则计算综合属性的值。规则计算综合属性的值。 S-属性文法的翻译器通常可借助于属性文法的翻译器通常可借助于LR分析器实现。分析器实现。综合属性可以在分析输入串的同时自底向上的来综合属性可以在分析输入串的同时自底向上的来计算。计算。分析器可以保存与栈中文法符号有关的综合属性分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约值，每当进行归约时，新的属性值就由栈中正在归约的产生式右部符号的属性值来计算。的产生式右部符号的属性值来计算。例8.12简单台式计算器的属性文法。 F.val:=digit.lexval F di
57、git F.val:=E.val F(E) T.val:=F.val T F T.val:=T1.val* *F.val T T1* *F E.val:=T.val E T E.val:=E1.val+T.val E E1+T print(E.val) L E n 语义规则 产生式 表表8.4 简单台式计算器的属性文法简单台式计算器的属性文法 8+5*2n的注释分析树见图8.15。图图8.15 8+5*2 n的注释分析树的注释分析树digit.lexval = 2LE.val = 18nT.val = 10E.val = 8T.val = 8F.val = 8digit.lexval = 8T
58、.val = 5+*F.val = 5F.val = 2digit.lexval = 52）考察S S属性的自下而上计算过程：将LRLR分析器符号栈中增加一个域来保存综合属性值。.X.xXY.yYZ.zZ.栈栈 state valtop若产生式若产生式A XYZ的语义规则是的语义规则是A.a := f (X.x, Y.y, Z.z)那么归约后有：那么归约后有：.A.aA.top图图 8.16 LR分析器符号栈属性域示意图分析器符号栈属性域示意图例8.13把台式计算器的语法制导定义改成栈操作代码如图8.17。F.val:=digit.lexval F digit F.val:=E.val F(E
59、) T.val:=F.val T F T.val:=T1.val* *F.val T T1* *F E.val:=T.val E T E.val :=E1.val+T.val E E1+T print(E.val) L E n 代 码 段产生式 .X.xXY.yYZ.zZ.栈栈 state valtopn图图8.17(a) 语法制导定义改成栈操作代码语法制导定义改成栈操作代码示意图示意图例8.13把台式计算器的语法制导定义改成栈操作代码如图8.17。F.val:=digit.lexval F digit F.val:=E.val F(E) T.val:=F.val T F T.val:=T1.
60、val* *F.val T T1* *F E.val:=T.val E T E.val :=E1.val+T.val E E1+T print (valtop 1) L E n 代 码 段产生式 .X.xXY.yYZ.zZ.栈栈 state valtopn图图8.17(b) 语法制导定义改成栈操作代码语法制导定义改成栈操作代码示意图示意图例8.13把台式计算器的语法制导定义改成栈操作代码如图8.17。F.val:=digit.lexval F digit F.val:=E.val F(E) T.val:=F.val T F T.val:=T1.val* *F.val T T1* *F E.va
61、l:=T.val E T valtop 2:=valtop 2+valtop E E1+T print (valtop 1) L E n 代 码 段产生式 .X.xXY.yYZ.zZ.栈栈 state valtopE1+T图图8.17(c) 语法制导定义改成栈操作代码语法制导定义改成栈操作代码示意图示意图例8.13把台式计算器的语法制导定义改成栈操作代码如图8.17。F.val:=digit.lexval F digit F.val:=E.val F(E) T.val:=F.val T F T.val:=T1.val* *F.val T T1* *F E T valtop 2:=valtop
62、2+valtop E E1+T print (valtop 1) L E n 代 码 段产生式 .X.xXY.yYZ.zZ.栈栈 state valtopT图图8.17(d) 语法制导定义改成栈操作代码语法制导定义改成栈操作代码示意图示意图例8.13把台式计算器的语法制导定义改成栈操作代码如图8.17。F.val:=digit.lexval F digit F.val:=E.val F(E) T.val:=F.val T F valtop 2:=valtop 2 valtop T T1* *F E T valtop 2:=valtop 2+valtop E E1+T print (valtop
63、 1) L E n 代 码 段产生式 .X.xXY.yYZ.zZ.栈栈 state valtopT1*F图图8.17(e) 语法制导定义改成栈操作代码语法制导定义改成栈操作代码示意图示意图例8.13把台式计算器的语法制导定义改成栈操作代码如图8.17。F.val:=digit.lexval F digit F.val:=E.val F(E) T F valtop 2:=valtop 2 valtop T T1* *F E T valtop 2:=valtop 2+valtop E E1+T print (valtop 1) L E n 代 码 段产生式 .X.xXY.yYZ.zZ.栈栈 sta
64、te valtopF图图8.17(f) 语法制导定义改成栈操作代码语法制导定义改成栈操作代码示意图示意图例8.13把台式计算器的语法制导定义改成栈操作代码如图8.17。F.val:=digit.lexval F digit val top 2 :=val top 1 F(E) T F valtop 2:=valtop 2 valtop T T1* *F E T valtop 2:=valtop 2+valtop E E1+T print (valtop 1) L E n 代 码 段产生式 .X.xXY.yYZ.zZ.栈栈 state valtop)E(图图8.17(g) 语法制导定义改成栈操作
65、代码语法制导定义改成栈操作代码示意图示意图例8.13把台式计算器的语法制导定义改成栈操作代码如图8.17。 F digit val top 2 :=val top 1 F(E) T F valtop 2:=valtop 2 valtop T T1* *F E T valtop 2:=valtop 2+valtop E E1+T print (valtop 1) L E n 代 码 段产生式 .X.xXY.yYZ.zZ.栈栈 state valtopdigit图图8.17(h) 语法制导定义改成栈操作代码语法制导定义改成栈操作代码示意图示意图8.3.5L-属性文法在自上而下分析中的实现 8.3.
66、5.1L-属性文法 定义：L-属性文法是下列属性文法，如果对于每一个产生式AX1X2Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj（1 jn）的一个继承属性(inheritedattribute)，且这个继承属性仅依赖于：(1)产生式Xj在左边符号X1X2Xj-1的属性;(2)A的继承属性。即继承属性的求值规则：即继承属性的求值规则：产生式左部非终结符号的继承属性值取前面产生式右部产生式左部非终结符号的继承属性值取前面产生式右部该符号已有的继承属性值；该符号已有的继承属性值；产生式右部符号的继承属性值用该产生式左部符号的继产生式右部符号的继承属性值用该产生式左部符号的继承属性或出现
67、在该符号左边的符号的属性值进行计算。承属性或出现在该符号左边的符号的属性值进行计算。体现自顶向下，自体现自顶向下，自左向右的求值特性左向右的求值特性S-属性文法是属性文法是L-属性文法的一种。属性文法的一种。L-属性文法允许一次遍历就计算出所有属性值。属性文法允许一次遍历就计算出所有属性值。L-属性文法的输入文法要求是LL(1)文法，可用自顶向下分析构造分析器，在分析过程中可进行属性求值。例8.14 ABC的属性求值顺序:A的继承属性（若A为开始符号则有指定值，否则由前面产生式右部符号的继承属性求得）B的继承属性（由A的继承属性求得）B的综合属性（由后面产生式中左部符号为B的综合属性求得）C的
68、继承属性（由A的继承属性和/或B的属性求得）C的综合属性（由后面产生式左部符号为C的综合属性求得）A的综合属性（由A的继承属性和/或B及C的属性求得）8.3.5.2翻译模式（翻译方案，Translationschemes ）目前流行的语义处理方法有两种：语法制导的定义和翻译模式。语法制导的定义：语法制导的定义： 构造属性文法时，不指明翻译时语义规则的计算构造属性文法时，不指明翻译时语义规则的计算次序，这样的属性文法称为语法制导的定义。次序，这样的属性文法称为语法制导的定义。 其语义规则的计算次序要通过拓扑排序等方法来其语义规则的计算次序要通过拓扑排序等方法来确定。确定。 在这里，属性文法可以看
69、作是关于语言翻译的高在这里，属性文法可以看作是关于语言翻译的高级规范说明，其中隐去实现细节，使用户从明确说明级规范说明，其中隐去实现细节，使用户从明确说明翻译顺序的工作中解脱出来。翻译顺序的工作中解脱出来。翻译模式：下面我们来讨论翻译模式。下面我们来讨论翻译模式。如果在构造属性文法时把语义规则用花括号如果在构造属性文法时把语义规则用花括号 括起来，括起来，插入到产生式右部的合适位置上，插入到产生式右部的合适位置上，用以指用以指明语义规则的计算次序，这样的属性文法称为翻译明语义规则的计算次序，这样的属性文法称为翻译模式（或称为翻译方案）。模式（或称为翻译方案）。这是语法分析与语义动作交错进行的表
70、示方法，这是语法分析与语义动作交错进行的表示方法，以此来表示语义动作在语法分析过程中的执行时刻。以此来表示语义动作在语法分析过程中的执行时刻。这样就可把某些实现细节表示出来。这样就可把某些实现细节表示出来。例8.15把带加号和减号的中缀表达式翻译成相应的后缀表达式的属性文法，其中addop表示或。EEaddopTprint（addop.lexeme）|TTnumprint（num.val）图图8.18 2 23 35 5的说明语义动作的语法分析树（的说明语义动作的语法分析树（1）TET3print(2)print(5)print()2ETprint(+)E5print(3) 如果采用如果采用L
71、R分析方法，则其属性计算很容易实现，比如分析方法，则其属性计算很容易实现，比如在对串在对串235的分析的同时执行语义动作输出的分析的同时执行语义动作输出235。语。语法分析树中加上虚线联结的语义结点，形成一个可说明语义法分析树中加上虚线联结的语义结点，形成一个可说明语义动作的树。见图动作的树。见图8.18。 对于LL（1）这种自顶向下分析方法的分析过程，从概念上来说可以看成是深度优先建立语法树的过程。因此，我们可以在自顶向下语法分析的同时实现L-属性文法的计算。要注意的是，上例是一个含左递归的文法，如果采用LL（1）分析必须改写文法如下：ETRRaddop T R1 |Tnum 这时对串这时对
72、串235分析分析的语法树见图的语法树见图8.19，而将而将后缀式后缀式 2 35输输出的动作在语法树中应该出出的动作在语法树中应该出现的位置见图现的位置见图8.20所示。所示。 图图8.192 23 35 5语法树语法树RTETTRR235RTETTRR23print(5)print()print(2)print(3)print()5图图8.20 2 23 35 5的说明语义动作的语法分析树（的说明语义动作的语法分析树（2）图图8.192 23 35 5语法树语法树RTETTRR235例8.16：下面是一个简单的翻译模式例子，它把带加号和减号的中缀表达式翻译成相应的后缀表达式。ETRRaddo
73、pTprint（addop.lexeme）R1|Tnumprint（num.val） 此例给出了可使用此例给出了可使用LL（1）分析方法的语义描分析方法的语义描述，不同的是，语义动作不是附在产生式右部的末述，不同的是，语义动作不是附在产生式右部的末尾，而是嵌入在产生式右部某些符号（如尾，而是嵌入在产生式右部某些符号（如T和和R）之之间。间。当只需要综合属性时，情况最为简单。在这种情况下，我们可以这样来建立翻译模式：为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。设计翻译模式时，我们必须注意某些限制以保证当某设计翻译模式时，我们必须注意某些限制以保证当某个动作引用
74、一个属性时它必须是有定义的。个动作引用一个属性时它必须是有定义的。例如，假设有下面的产生式和语义规则：例如，假设有下面的产生式和语义规则： 产生式产生式 语义规则语义规则 TT1*F T.val T1.valF.val我们建立产生式和语义动作：我们建立产生式和语义动作： TT1*FT.val T1.valF.val如果既有综合属性又有继承属性，在建立翻译模式时就必须特别小心。后面我们将看到满足这三个条件的翻译模式后面我们将看到满足这三个条件的翻译模式是如何在一般的自上而下和自下而上分析器中是如何在一般的自上而下和自下而上分析器中实现的。实现的。产生式右部的符号的继承属性必须在这个符产生式右部的
75、符号的继承属性必须在这个符号以前的动作中计算出来。号以前的动作中计算出来。一个动作不能引用这个动作右边的符号的综一个动作不能引用这个动作右边的符号的综合属性。合属性。产生式左部非终结符的综合属性只有在它所产生式左部非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的末尾。这种属性的动作通常可放在产生式右端的末尾。8.3.6L-属性文法在自下而上分析中的实现下面我们讨论然后实现自下而上计算继承属性。办法有两种：从翻译模式中去掉嵌入在产生式中间的动作和用综合属性代替继承属性。8.3.6.1从翻译模式中去
76、掉嵌入在产生式中间的动作在8.3.4节中的自下而上的翻译方法中，要求把所有的语义动作都放在产生式的末尾，而在上节的自顶向下翻译方法中，我们需要在产生式右部的不同地方嵌入语义动作。下面我们介绍一种转换方法，它可以使所有嵌入的动作都出现在产生式的末尾，这样就可以自下而上处理继承属性。转换方法：在基础文法中加入新的产生式，这种产生式的形式为M，其中M为新引入的一个标记非终结符。我们把嵌入在产生式中的每个语义动作用不同的标记非终结符M代替，并把这个动作放在产生式M的末尾。 例8.18有下面翻译模式：ETRETR R RT printT print（）R|R|T printT print（）R|R| T
77、num print Tnum print（numnumvalval） 使用标记非终结符号使用标记非终结符号M和和N转换为转换为 ETRETR R RTMR|TMR|TNR|TNR| Tnumprint Tnumprint（numnumvalval） Mprint Mprint（） N print N print（） 两个翻译模式中的文法接受相同的语言。通过画出带有两个翻译模式中的文法接受相同的语言。通过画出带有表示动作的附加结点的分析树，我们可以看到动作的执行程表示动作的附加结点的分析树，我们可以看到动作的执行程序也是一样的。在经过转换的翻译模式中，动作都在产生式序也是一样的。在经过转换的翻译
78、模式中，动作都在产生式右端的末尾，因此，可以在自下而上分析过程中产生式右部右端的末尾，因此，可以在自下而上分析过程中产生式右部被归约时执行相应的动作。被归约时执行相应的动作。 例8.19给定文法:SbTcSaTRRR/SRS为该文法设计翻译方案，使句型bR/bTc/bSc/ac经该翻译方案翻译后,输出串：0342031320S Sb bc cR RR RS S/ /S Sa aR RS SR RS SR Rb bc cT T/ / /T Tb bc cT T 图图8.24 8.24 句型句型bR/bTc/bSc/acbR/bTc/bSc/ac的语法树的语法树 这样根据输出串与归约的关系这样根据
79、输出串与归约的关系可以求得翻译方案如下：可以求得翻译方案如下： SbTc print“0” Sa print“1” TR print“2” RR/S print“3” RS print“4” 解：求得该句型的语法树见图解：求得该句型的语法树见图8.24。 按最左归约的方式找当前句型的按最左归约的方式找当前句型的句柄，每当对句柄进行归约时同步执句柄，每当对句柄进行归约时同步执行相应的语义规则，就能得到输出串：行相应的语义规则，就能得到输出串：0342031320。例8.20给定文法及相应的翻译方案：EE+Tprint(“5”)ETprint(“4”)TT*Fprint(“3”)TFprint(“
80、2”)F(E)print(“1”)Fiprint(“0”)对于句型T+(T*(F+T)*i),处理完该句型后输出是什么？图图8.25 8.25 句型句型T+(T*(F+T)*i)T+(T*(F+T)*i)的语法树的语法树E EE ET TF F( () )E ET Ti iT TT TF FF FT TF FT T( () )+ +* * *E EE ET T+ + 则对于句型则对于句型T+(T*(F+T)*i),处理完该句型后输出是：处理完该句型后输出是： 424513034125解：求得句型解：求得句型T+(T*(F+T)*i)的语法树见的语法树见图图8.25。 按最左归约的方式找当前句型
81、的句柄，按最左归约的方式找当前句型的句柄，每当对句柄进行归约时同步执行相应的语每当对句柄进行归约时同步执行相应的语义规则，就能得到翻译结果（即输出）。义规则，就能得到翻译结果（即输出）。8.4简单赋值语句的翻译在8.2.2的四元式表示中，使用变量名字本身表示运算对象arg1和arg2，用Ti表示RESULT。在实际实现中，它们或者是一个指针，指向符号表的某一登录项，或者是一个临时变量的整数码。在对赋值语句翻译为四元式的描述中，我们将表明怎样查找这样的符号表登录项。首先对id表示的单词定义一属性id.name，用做语义变量，用Lookup（id.name）表示审查id.name是否出现在符号表中
82、，如在，则返回一指向该登录项的指针，否则返回nil。语义过程emit表示输出四元式到输出文件上。语义过程newtemp表示生成一个临时变量，每调用一次，生成一新的临时变量，并返回该变量在符号表中的地址。语义变量E.place，表示存放E值的变量名在符号表的登录项或一整数码（若此变量是一个临时变量）。例8.22图8.27列出了翻译赋值语句到三地址代码的语义描述。这里的语义工作包括对变量进行先定义后使用的检查。(1) Sid=E p=lookup(1) Sid=E p=lookup（ id.nameid.name）；）； if pnilif pnilthenthen emitemit（p=E.pl
83、acep=E.place） elseelseerrorerror(2) EE(2) EE1 1+E+E2 2 E.place= E.place=newtempnewtemp； emitemit（E.place=EE.place=E1 1.place+E.place+E2 2.place.place） (3) EE(3) EE1 1*E*E2 2 E.placeE.place=newtempnewtemp； emitemit（E.placeE.place =E=E1 1.place.place*EE2 2.place.place） (4) E(4) EE E1 1 E.placeE.place=
84、newtempnewtemp； emitemit（E.place=uminusEE.place=uminusE1 1.place .place ） (5) E(5) E（E E1 1） E.place=EE.place=E1 1.place.place(6) Eid p=lookup(6) Eid p=lookup（id.nameid.name） ； ififpnil then E.place=p elsepnil then E.place=p elseerror error 图8.27赋值语句的三地址代码翻译实际上，在一个表达式中可能会出现各种不同类型的变量或常数，而不是像图8.24中的id
85、假定为都是同一类型也就是说，编译程序还应执行这样的语义动作：对表达式中的运算对象应进行类型检查，如不能接受不同类型的运算对象的混合运算，则应指出错误；如能接受混合运算，则应进行类型转换的语义处理。例8.23图8.27中的表达式可以有混合运算，id可以是实型量也可以是整型量，并且约定，当两个不同类型的量进行运算时，必须首先将整型量转换为实型量。为进行类型转换的语义处理，增加语义变量，用E.type表示E的类型信息，E.type的值或为int或为real。此外，为区别整型加（乘）和实型加（乘），把+（或*）分别写作+i（或*i）和+r（或*r）。用一目算符itr表示将整型运算对象转换成实型。这样，
86、图8.27中的第（3）条产生式及其有关语义描述如图8.28。图8.28类型转换的语义处理产生式产生式 语义动作语义动作EEEE1 1*E*E2 2 E.place=E.place=newtempnewtemp； if Eif E1 1. .typetypeintint AND E AND E2 2. .typetypeintint then then begin emit begin emit（E E. .placeplace，=，E E1 1. .placeplace，*i*i, E, E2 2. .placeplace）；）； E E. .type=type=intint end end
87、else if E else if E1 1. .typetypereal AND Ereal AND E2 2. .typetypereal thenreal then begin emit (E begin emit (E. .place,place,=,E,E1 1. .placeplace,*r,*r,E,E2 2. .place);place); E E. .type=realtype=real end end else if E else if E1 1. .typetypeintint /* and E/* and E2 2. .type=realtype=real* */ /t
88、henthen begin t= begin t=newtempnewtemp； emitemit（t t，=，itritr，E E1 1. .placeplace）；）； emitemit（E E. .placeplace，=，t t，*r*r，E E2 2. .placeplace）；）； E E. .type=realtype=real end end else else /*E/*E1 1. .typetypereal and Ereal and E2 2. .typetypeintint*/*/ begin t= begin t=newtempnewtemp； emitemit（t
89、t，=, ,itritr，E E2 2. .placeplace）；）； emitemit（E E. .placeplace，=，E E1 1. .placeplace，* r,r,t t）；）； E E. .type=realtype=real end end；赋值语句中会含有复杂数据类型，如数组元素、记录（结构）的引用。这种情况的翻译工作则要更复杂些。8.5布尔表达式的翻译程序设计语言中的布尔表达式有两个作用：一是计算逻辑值;二是在控制流语句中用作条件表达式。如在如在if-then，if-then-else，或是，或是while-do语句中那样。语句中那样。布尔表达式是由布尔算符布尔表达式
90、是由布尔算符and，or和和not施加于布尔变量或施加于布尔变量或关系表达式而成。关系表达式而成。布尔表达式的形式为布尔表达式的形式为E1 rop E2，其中，其中E1和和E2都是算术表都是算术表达式，达式，rop是关系符。是关系符。为简单起见，我们只考虑如下文法生成的布尔表达式。为简单起见，我们只考虑如下文法生成的布尔表达式。EE and E|E or E| not E|id rop id|true|false并且按通常习惯，约定布尔算符的优先顺序（从高到低）并且按通常习惯，约定布尔算符的优先顺序（从高到低）为为not 、and、or，并且，并且and和和or服从左结合。服从左结合。 8.5
91、.1布尔表达式的翻译方法通常，计算布尔表达式的值有两种办法:第一种办法，如同计算算术表达式一样，步步计算出各部分的真假值，最后计算出整个表达式的值。例例8.24 用数值用数值1表示表示true，用，用0表示表示false。那么布尔表达式那么布尔表达式1 or（not 0 and 0）or 0的计算过程是：的计算过程是：1 or（not 0 and 0）or 01 or（1 and 0）or 01 or 0 or 01 or 01 另一种计算方法是采取某种优化措施，只计算部分表达式，另一种计算方法是采取某种优化措施，只计算部分表达式，例如要计算例如要计算A or B，若计算出，若计算出A的值为的
92、值为1，那么，那么B的值就无需的值就无需再计算了，因为不管再计算了，因为不管B的值为何结果，的值为何结果，A or B的值都为的值都为1。若按第一种办法计算布尔表达式，布尔表达式若按第一种办法计算布尔表达式，布尔表达式a or b and not c 翻译成的四元式序列为：翻译成的四元式序列为：（1）t1 =not c（2）t2 =b and t1（3）t3 =a or t2对于像ab这样的关系表达式，可看成等价的条件语句ifabthen1else0，它翻译成的四元式序列为：（1）ifabgoto（4）（2）t =0（3）goto（5）（4）t =1（5）其中用临时变量t存放布尔表达式ab的值
93、，(5)为后续的四元式序号。图8.29给出了按第一种办法计算布尔表达式的值，将布尔表达式翻译成四元式的描述，在该描述中使用了过程newtemp和emit，其含义同前，过程nextstat给出在输出序列中下一四元式序号，emit过程每被调用一次，nextstat增加1。图8.29用数值表示布尔值的翻译方案EEEE1 1 or E or E2 2 E E. .placeplace= =newtempnewtemp； emitemit（E E. .place place = = E E1 1. .placeplaceoror E E2 2. .placeplace）EEEE1 1 and E and
94、 E2 2 E E. .placeplace = =newtempnewtemp； emitemit（E E. .place place = = E E1 1. .place place andand E E2 2. .placeplace）Enot EEnot E1 1 E E. .placeplace = =newtempnewtemp：；：； emitemit（E E. .place place = =notnot E E1 1. .placeplace）EE（E E1 1） E E. .placeplace=E=E1 1. .placeplaceEidEid1 1 reloprelop
95、 id id2 2EE. .placeplace= =newtempnewtemp； emitemit（ifif id id1 1. .place place reloprelop id id2 2. .Place Place gotogoto nextstat+3nextstat+3）；）； emitemit（E E. .place place = =0 0 ）；）； emitemit（gotogoto nextstat+2 nextstat+2）；）； emitemit（E E. .place place = =1 1）Etrue Etrue E E. .placeplace= =newt
96、empnewtemp； emitemit（E E. .place place = =1 1）Efalse Efalse EE. .placeplace= =newtempnewtemp； emitemit（E E. .place place = =0 0） 8.5.2控制语句中布尔表达式的翻译现在讨论出现在ifthen；ifthenelse和whiledo等语句中的布尔表达式E的翻译。这三种语句的语法为：SifEthenS1| ifEthenS1elseS2|whileEdoS1这些语句的代码结构示意分别在图8.30（a）（b）（c）中，其中使用.和。两个出口分别用于表示E为真和假时控制流向的
97、转移。分别叫真出口和假出口。图图8.30 控制语句的代码结构控制语句的代码结构真真 E的代码的代码 S1的代码的代码begin： E的代码的代码 S1的代码的代码 jump beginif E then S1代码结构代码结构 E的代码的代码 S1的代码的代码 jump out S2的代码的代码out：假假if E then S1 else S2代码结构代码结构while E do S1代码结构代码结构比如将布尔表达式E=aropb翻译成四元式代码：ifaropbgotoE.true和gotoE.false在控制语句中在控制语句中, 布尔表达式布尔表达式E作为控制流转移的条件，仅作为控制流转移的
98、条件，仅把其翻译成一串条件转和无条件转的四元式代码。翻译方案把其翻译成一串条件转和无条件转的四元式代码。翻译方案见见P185。这里，使用这里，使用E.true和和E.false分别表示布尔表达式分别表示布尔表达式E的的“真真“、假假出口转移目标。下面将多处使用它们。出口转移目标。下面将多处使用它们。对于对于E为为E1 or E2的形式，若的形式，若E1是真，则可知道是真，则可知道E为真即为真即E1的真出口和的真出口和E的真出口一样。如果的真出口一样。如果E1是假，那么必须计算是假，那么必须计算E2，E1的假出口应是的假出口应是E2代码的第一个四元式标号，这时代码的第一个四元式标号，这时E2的的
99、真出口和假出口分别与真出口和假出口分别与E的真出口和假出口一样。的真出口和假出口一样。 类似的考虑适于类似的考虑适于E为为E1 and E2 的情形。的情形。例8.25布尔表达式aborcf翻译为如下四元式序列：（1）ifabgotoE.true（2）goto（3）（3）ifcdgoto（5）（4）gotoE.false（5）isefgotoE.true（6）gotoE.false这里，我们使用这里，我们使用E.true和和E.false分别表示整个表达式分别表示整个表达式ab or cd and ef的真、假出口，而的真、假出口，而E.true和和E.false的值并不能的值并不能在产生四元
100、式的同时就知道。在产生四元式的同时就知道。 这样生成的四元式显然不是最优的，如四元式（这样生成的四元式显然不是最优的，如四元式（2）是不）是不需要的。这种问题可留待代码优化阶段解决。需要的。这种问题可留待代码优化阶段解决。为了看清这一点，我们把该表达式放在条件语句中考虑，如语句ifaborcdandefthenS1elseS2的四元式序列为：（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的四元式
101、） （p）goto（q）（p+1）（关于S2的四元式） （q）实际上，上述四元式（1）和（5），（4）和（6）的转移地址并不能在产生这些四元式的同时得知。例如（1）和（5）的转移地址为（7），它是在整个布尔表达式的四元式序列生成之后才回填的地址。为了记录需回填地址的四元式，常采用一种拉链的办法。把需回填E.true的四元式拉成一链，把需回填E.false的四元式拉成一链，分别称做真链和假链。用一个例子说明拉链是如何方式，若有四元式序列：（0） （10）gotoE.true （20）gotoE.true （30）gotoE.true 回填为回填为这里把地址（这里把地址（30）称作链首，）称作链首
102、，0为链尾标志，即地址（为链尾标志，即地址（10）为）为链尾。链尾。 （0） （10）goto（0） （20）goto（10） （30）goto（20） 8.6控制结构的翻译8.6.1条件转移见P1868.6.2开关语句开关语句（case语句或switch语句）是很多程序设计语言中都有的，方式不尽相同，甚至FORTRAN中的计算GOTO和赋值GOTO也可看做是一种开关语句。我们假定要讨论的开关语句的形式为：switchEofcaseV1：S1caseV2：S2 caseVn-1：Sn-1default：Snend这里的E是一个表达式，也称为选择子。开关语句是分情形选择机制，在E被计算之后，测试
103、它的值符合哪种case中的值，而执行和该值相关的语句，并做相应的转移。如果E的值不能与任何Vi（1in-1）匹配，便执行default时的语句。直观上看，case语句翻译成如下的一连串条件转移语句。t =E；L1：iftV1gotoL2；S1；gotonext；L2：iftV2gotoL3；S2；gotonext； Ln-1：iftVn-1gotoLn；Sn-1；gotonext；Ln：Sn；next：8.6.3for循环语句除了whiledo语句外，很多程序设计语言具有下面形式的循环语句：fori =E1stepE2untilE3doS1为了简单起见，假定E2总是正的。在这种假定下，上述循环
104、句的意义等价于： i =E1； goto OVER；AGAIN： i =i+E2； OVER： if iE3 then begin S1； goto AGAIN end； i =E1； OVER： if iE3 then begin S1； i =i+E2； goto OVER end； 或：或：属性文法的定义见书属性文法的定义见书P1918.6.4goto语句多数程序语言中的转移是通过标号和goto语句实现的。带标号语句的形式是L S；goto语句的形式是gotoL。当L S；语句被处理之后，标号L是定义了的。即在符号表中，将登记L的项的地址栏中登上语句S的第一个四元式的地址。如果gotoL
105、是一个向上转移的语句，那么，当编译程序碰到这个语句时，L必是已定义了的。通过对L查找符号表获得它的定义地址p，编译程序可立即产生出相应于这个gotoL的四元式如（j，p）。如果gotoL是一个向下转移的语句，也就是说，标号L尚未定义，那么，若L是第一次出现，则把它填进符号表中并标志上未定义。由于L尚未定义，对gotoL只能产生一个不完全的四元式（goto，），它的转移目标须待L定义时再回填进去。在这种情况下，必须把所有那些以L为转移目标的四元式的地址全都记录下来，以便一旦L定义时就可对这些四元式进行回填。 我们将采用如图8.28所示的拉链办法，把所有以L为转移目标的四元式串在一起。链的首地址放
106、在符号表中L的地址栏中。建链的方法是：若gotoL中的标号L尚未在符号表中出现，则把L填入表中，置L的定义否标志为未，把nextstat填进L的地址栏中作为新链首，然后，产生四元式（goto0），其中0为链尾标志。若L已在符号表中出现（但定义否标志为未），则把它的地址栏中的编号（记为q）取出，把nextstat填进该栏作新链首，然后，产生四元式（gotoq）。图图8.31 未定义标号的引用链未定义标号的引用链 名字名字类型类型定义否定义否 地址地址L标号标号未未r(r)(goto q)(q)(goto p)(p)(goto 0)符号表符号表四元式四元式一旦标号L定义时，我们将根据这条链回填那些
107、待填转移目标的四元式。一般而言，假定用下面的产生式来定义标号语句：SlabelSlabeli：那么，当用labeli：进行归约时，应做如下的语义动作：若i所指的标识符（假定为L）不在符号表中，则把它填入，置类型为标号，定义否为已，地址为nextstat。若L已在符号表中但类型不为标号或定义否为已，则报告出错。若L已在符号表中，则把标志未改为已，然后，把地址栏中的链首（记为q）取出，同时把nextstat填在其中，最后，执行回填。翻译goto语句时，还有两点必须注意，第二：可能有些转移标号是非法的，第二：可能有些转移标号是非法的，如下例：如下例：（1）for i =1 to 10 do（2） b
108、egin goto L；（3） for j =1 to 20 do（4） begin goto L； （n） L： endfor jendfori处理到第（处理到第（n）行后，第（行后，第（4）行）行的的goto目标得以解决。而第（目标得以解决。而第（2）行）行的的goto L是非法的，但只有当循环关是非法的，但只有当循环关闭时才能确定。闭时才能确定。 还要注意的问题是转移出分程序或过程外的还要注意的问题是转移出分程序或过程外的goto语句，语句，编译程序需要很多额外的编码，比如要恢复和保留一些运行编译程序需要很多额外的编码，比如要恢复和保留一些运行环境等，这在后面环境等，这在后面(第第10章
109、章)介绍了运行环境时，可能会理解介绍了运行环境时，可能会理解更深些。更深些。 第一：是相同名字的标号可以在不第一：是相同名字的标号可以在不同名字作用域中定义。如：同名字作用域中定义。如：（1）begin（2） L：begin（3） goto L；（4） （5） L：（6） end（7）end 当在行（当在行（3）处理）处理goto语句时，不知语句时，不知道道L的作用域到底是哪个，（因为的作用域到底是哪个，（因为还没见到语句（还没见到语句（5），因此一定），因此一定要延迟解决这个标号的使用。要延迟解决这个标号的使用。8.7简单说明语句的翻译程序设计语言中的说明语句旨在定义各种形式的有名实体，如常
110、量、变量、数组、记录(结构)、过程、子程序等等，说明语句的种类也多，对象说明、变量说明、类型说明、过程说明等等。编译程序把说明语句中定义的名字和性质登记在符号表中，用以检查名字的引用和说明是否一致。许多说明语句的翻译并不生成相应的目标代码。过程说明和动态数组的说明有相应的代码。程序设计语言中最简单的说明句的语法描述为：Dintegernamelist|realnamelistnamelisenamelist，id|id即使用关键字integer和real定义一串名字的性质。对这种说明句的翻译是指在符号表中登录该名和性质。用上述文法来制导翻译(自下而上)存在着这样一个问题，我们只能在把所有的名字
111、都归约成namelist后才能把它们的性质登记进符号表。这意味着namelist必须用一个队列(或栈)来保存所有这些名字。 但我们可以把上述的文法改写成：DD1,id|integerid|realid这样,就能把所说明的性质及时地告诉每个名字id，或者说，每当读进一个标识符时，就可以把它的性质登记在符号表中，不用把它们集中起来最后再成批登记了。现在来定义这些产生式所对应的语义动作，给非终结符D一个语义变量D.ATT，用以记录说明句所引入的名字的性质(int还是real)，使用过程enter(id,A)把名字id和性质A登录在名表中。(1)Dintegeridenter(id，int);D.AT
112、T =int(2)Drealidenter(id，real);D.ATT =real(3)DD1，identer(id，D1.ATT);D.ATT =D1.ATT8.8含数组元素的赋值语句的翻译在程序设计语言中，数组是用来存储有规律或同类型数据的数据结构，数组中的每一个元素在计算机内占有相同大小的存储空间，又称为存储宽度。如果在编译时刻就已知道一个数组的大小，则称该数组为静态数组，否则称为动态数组。我们现在只讨论静态数组元素的引用如何翻译。数组的一般定义为al1：u1，l2：u2，lk：uk，ln：un(1kn)其中a是数组名，lk称为数组下界，uk称为数组上界，变量k是数组的维数。一维数组a
113、l1：u1：若数组元素存放在一片连续的单元里，元素的宽度为，则数组元素ai(l1iu1)的地址定义为：数组起始地址+该元素在数组中的线性序号1b1+(i-l1)，其中b1是存放数组a的第一个元素的相对地址，称为数组a的起始地址。考虑存储宽度则有：数组起始地址+元素在数组中的线性序号1b1+(i-l1)*整理后有：b1-l1*+i*令Cb1-l1*，则有：C+i*二维数组al1：u1，l2：u2：必须事先约定存储顺序。常见的有按行存放和按列存放两种。如有一个2行3列的二维数组a1：2，1：3，则有：按行存放顺序为：a1，1，a1，2，a1，3，a2，1，a2，2，a2，3按列存放顺序为：a1，1
114、，a2，1，a1，2，a2，2，a1，3，a2，3存放顺序不一样则数组元素存储地址的计算就不一样，下面我们仅讨论按行存放方式的数组元素存储地址的计算。例：例：A是是1020的二维数组。的二维数组。按行存放：按行存放：A1, 1A1, 2第一行第一行. A1, 20A2, 1 第二行第二行A10, 20 第十行第十行. . . . . . . . . . . 按列存放：按列存放：A1, 1A2, 1第一列第一列. A20, 1A1, 2 第二列第二列A1, 20 第十列第十列. . . . . . . . . . . 例如：对于二维数组a1：2，1：3，数组元素ai，j的存储地址计算为：数组起始
115、地址+该元素在数组中的线性序号1b+(i-1)*3+(i-1)而数组元素a1，3存储地址的计算为：b+(1-1)*3+(3-1)b+2一般地二维数组al1：u1，l2：u2，数组元素ai，j的存储地址计算为：数组起始地址+元素在数组中的线性序号1b+(行数-1)*每行个数+列数-1)b+(i1-l1+1)-1)*(u2-l1+1)+(i2-l2+1)-1)b+(i1-l1)*n2+(i2-l2+1)-1)b-(l1*n2+l2)+(i1*n2)+i2C+(i1*n2)+i2其中：n2(u2-l1+1)考虑存储宽度则有：C+(i1*n2)+i2*其中：Cb-(l1*n2+l2)*，n2(u2-l
116、1+1) 数组信息数组信息(内情内情)向量：向量： 编译将数组的有关信息记录在一些单元中，称为编译将数组的有关信息记录在一些单元中，称为数组的数组的“信息信息(内情内情)向量向量”。l1 l2u2:typea（首地址）首地址）n C u1:多维数组typeal1：u1，l2：u2，lk：uk：多维数组al1：u1，l2：u2，lk：uk：其任一数组元素ai1，i2，ik的存储地址计算为：数组起始地址+元素在数组中的线性序号1b-(l1*n2+l2)*n3+l3)*nk+lk)+(i1*n2+i2)*n3+i3)*n4+)*nk+ikC+(i1*n2+i2)*n3+i3)*n4+)*nk+ik考
117、虑存储宽度则有：C+V其中：Cb-(l1*n2+l2)*n3+l3)*nk+lk)*，V(+(i1*n2+i2)*n3+i3)*n4+)*nk+ik)*nj(uj-lj-1+1)1jk分析一下C中的各项，在处理数组说明语句时就可以得到。因此C的值在编译时刻就能算出，并保存到数组a的相关符号表项里。这样到运行时刻求数组元素地址时，仅需要计算V的值，直接调用C的值，避免重复计算。实现数组元素的地址计算时，产生两组四元式序列。一组产生基本地址C，其值存放在临时单元T1中；另一组计算变元地址V的值，将其存放在另一个临时单元T中。用T1T表示数组元素的地址。这样，对应数组元素的引用和赋值就有两种不同的四
118、元式：变址取数：若有X:T1T，可用四元式表示为（，T1T，_，X）变址存数：若有T1T:X，可用四元式表示为（，X，_，T1T）例8.26设A为一个10x20的数组，即nl10，n220。对赋值语句x:Ai，j的四元式序列为：（*，i，20，t1）（，t1，j，t1）（-，A，21，t2）（，t2t1，_，t3）（:，t3，_，X） 要生成有关数组引用的代码，其主要问题是把的存储地址计算公式的计算与数组引用的文法联系起来。如果在图8.278.27的文法中idid出现的地方也允许下面产生式中的L L出现，则可把数组元素引用加入到赋值语句中。下标变量访问的产生式L L id id ElistEl
119、ist | id | idElistElist ElistElist, , E E | | E E为了便于语义处理，改成L L ElistElist | id | idElistElist ElistElist, , E E | id | id E E即把数组名字id与最左下标表达式E相联系，而不是在形成L时与Elist相联系。其目的是使我们在整个下标表达式串Elist的翻译过程中随时都能知道符号表中相应于数组名字id的全部信息。对于非终结符号Elist引进综合属性p，用来记录指向符号表中相应数组名字表项的指针。我们还利用Elist. ndim来记录Elist中的下标表达式的个数，即维数。函数
120、Indt（p，j）返回nj，即由array所指示的数组的第j维长度。最后，Elist.Place表示临时变量，用来临时存放由Elist中的下标表达式计算出来的值。描述L的左值（即地址）用两个属性L.place及L.offset。如果L仅为一个简单名字，L.place就为指向符号表中相应此名字表项的指针，而L.offset为null，表示这个左值是一个简单的名字而非数组引用。 S:=L.place := xL.offset := nullxE.place := t4L.place := t2L.offset := t3Elist.place := t1Elist.ndim := 2Elist.a
121、rray := A,Elist.place := yElist.ndim := 1Elist.array := AE.place := zL.place := zL.offset := nullE.place := yL.place := yL.offset := nullAzy图图8.29 x := A y, z 的注释分析树的注释分析树t1 := y t1 := y 20 20t1 := t1 + zt1 := t1 + zt2 :=A t2 :=A 84 84 t3 := 4 t3 := 4 t1 t1t4 := t2 t3 t4 := t2 t3 x := t4x := t4所有产生式
122、1.S L :=E2.E E+E3.E (E)4.E L5.L Elist 6.L id7.ElistElist,E8.ElistidE 若若L是一个简单的名是一个简单的名字，将生成一般的赋值；字，将生成一般的赋值；否则，若否则，若L为数组元素引为数组元素引用，则生成对用，则生成对L所指示地所指示地址的索引赋值：址的索引赋值： 1.S L :=E ifL.offset=nullthen/ L是简单变量 /emit(L.place,:=,E.place)elseemit(L.place,L.offset,:=, E.place)2.E E1 + E2E.place := newtemp;emit
123、 (E.place, :=, E1.place , +, E2.place) 3.E (E1 )E.place := E1.place 4.E Lif L.offset = null then / L是简单变量是简单变量 / E.place := L.place else begin E.place := newtemp; emit (E.place, :=, L.place, , L.offset, ) end 5.L Elist L.place:=newtemp; emit(L.place,:=,base(Elist.array), ,C);/*C=invariant (Elist.arr
124、ay)*/ L.offset:=newtemp; emit(L.offset,:=,Elist.place, ,w)6.L id L.place := id.place; L.offset := null 7.Elist Elist1, E t := newtemp; m := Elist1.ndim + 1; emit (t, :=, Elist1.place, , limit(Elist1.array, m) ); emit (t, :=, t, +, E.place); Elist.array := Elist1.array; Elist.place := t; Elist.ndim :
125、= m8.Elist id E Elist.place := E.place; Elist.ndim := 1; Elist.array := id.place 例8.27设A为一个10x20的数组，即nl10，n220，并设4。对赋值语句x：Ay，z翻译成如下三地址语句序列。解：对赋值语句x：Ay，z的带注释的语法分析树见图8.29。该赋值语句被翻译成如下三地址语句序列：t1：y*20t1：=t1zt2：A84t3：4*t1t4：t2t3x：t4其中每个变量，我们用它的名字来代替idplace。【本章小结】1.中间代码是复杂性介于源程序语言和机器语言的一种表式形式。编译程序中所使用的中间代码
126、有多种形式，常见的有逆波兰记号、三元式和四元式等等。2.源程序翻译成中间表示，要在保证源语言语句语义的条件下进行源语句到目标语句结构上的变换。学习了本章应能掌握一般语法成分，如赋值语句、条件语句、循环语句和简单说明语句等结构的翻译。3.语法制导翻译指的是编译实现的方法，分析过程和分析树用于制导语义分析和源程序的翻译，常用的办法是扩充惯用的文法，加上控制语义分析和翻译的信息，这样的文法称为属性文法。Yacc这类工具接受这种方式提供的语义分析和翻译信息，因而成为编译程序的生成器。实验2安排：时间：第11周周一下午14：0017：00地点：系实验中心题目：赋值语句的翻译程序设计要求：请同学们务必在实验开始前完成程序的编写工作，到实验室时主要是进行调试和验收，不参加验收则不能获得实验成绩。报告提交时间：第12周周二的下午14：00本章作业P202：1#，2#，5#
