第8章 语法制导翻译和中间代码生成.ppt

1、第八章 语法制导翻译和中间代码生成,【课前思考】 回顾第一章介绍的编译过程，理解语义分析在编译过程中的位置和作用。 “属性文法”的概念及应用。 “语法制导翻译”的概念及应用。 什么是中间代码（中间表示），为什么要中间代码？,【学习目标】,明确语义分析在编译过程所处的阶段和作用。 掌握属性文法的基本概念。 使用属性文法和语法制导翻译方法描述具体的语义分析和产生中间代码。 主要是要让同学们了解： )语义的描述方式； )语义的处理方法。,【本章重点】,1.几种典型的中间代码（语言）的形式; 2.语义的描述方法 着重介绍一种形式化的语义描述方法属性文法; 3.语义的处理方法 着重介绍语法制导的翻译法包

2、括它的两种具体形式：语法制导的定义和翻译方案 。,词法分析、语法分析 程序在书写上是正确的、在语法上是正确的，不能保证含义（语义）上的正确性,8.0 概述,第八章 语法制导翻译和中间代码生成,第一，审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。有时把这个工作称为静态语义分析或静态审查。 第二，如果静态语义正确，语义处理则要执行真正的翻译，即，或者将源程序翻译成程序的一种中间表示形式（中间代码），或者将源程序翻译成目标代码。,编译中的语义处理是指两个功能：,静态语义分析通常包括： 类型检查。 控制流检查。 一致性检查。 相关名字检查。 名字的作用域分析,语义分析的输入是语法

3、分析的输出（分析树），输出是中间代码，但同时它还完成了很多语义处理工作。,语义分析的主流技术 语法制导翻译技术,8.1 属性文法(attribute grammar),属性文法(也称属性翻译文法)是Knuth在1968年首先提出的。 它是在上下文无关文法的基础上，为每个文法符号(终结符或非终结符)配备若干相关的“特性”（称为属性）。 这些属性代表与文法符号相关信息，例如它的类型、值、代码序列、符号表内容等等。 属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。,对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。,所谓属性，其涉及的概念比较广泛，常用以描述事物或人

4、的特征、性质，品质等等。 对编译程序使用的语法树的结点，可以用类型、值或存储位置来描述它。,一个属性文法包含一个上下文无关文法和一系列语义规则，这些语义规则附在文法的每个产生式上。,所谓语法制导的翻译指的是在语法分析过程中，完成这些语义规则描述的动作，从而实现语义处理。,8.1.1 属性文法定义,定义1： 形式上讲，属性文法是一个三元组 :A=(G，V，F)， 其中： G:是一个上下文无关文法； V:有穷的属性集,每个属性与文法的一个终结符或非终结符相连,这些属性代表与文法符号相关信息； F:关于属性的属性断言或一组属性的计算规则(称为语义规则) 。 断言或语义规则与一个产生式相联,只引用该产

5、生式左端或右端的终结符或非终结符相联的属性。,定义2：,一个属性文法是一个三元组：A=(G,V,F ),其中 G -基础文法（一个上下文无关文法） V -每个文法符号有一组属性 F -每个文法产生式A有一组形式为b:=f(c1,c2,ck)的语义规则，其中f 是函数，b和c1,c2,ck是该产生式文法符号的属性。,属性的类型（从分析过程中属性值的计算方法来分类）：,1、综合属性（Synthesized Attributes）：属性值是分析树中该结点的子结点的属性值的函数,2、继承属性（Inherited Attributes）：属性值是分析树中该结点的父结点和/或兄弟结点的属性值的函数,对于产

6、生式 AX1 X2 Xn,A,X1,X2,Xn,计算 A 的综合属性, S ( A ) : = f ( I ( X1 ) , , I ( Xn ) ),计算 Xj 的继承属性, T ( Xj ) : = f ( I ( A ) , ., I ( Xn ) ),综合属性用于“自下而上”传递信息，继承属性用于“自上而下”传递信息,属性文法的主要思想是：,1.对每个文法符号引入相关的属性符号； 2.对于每个产生式写出计算属性值的属性规则（语义规则），其形式为：b：= f(c1, c2, , ck ) 即：属性变量：= 这里 f是一个函数，且对于产生式A ， (1) b或者是A的一个综合属性并且c1,

7、c2,，ck是产生式右边文法符号的属性； (2) b或者是产生式右边某个文法符号的一个继承属性并且c1,c2,，ck是A或产生式右边任何文法符号的属性。 在两种情况下，我们都说属性b依赖于属性c1,c2,，ck。,即：属性规则中的左部b能写那些属性变量是有规定的，只能为下述两种变量： 产生式左部符号的综合属性变量； 产生式右部符号的继承属性变量。,2.对于每个产生式写出计算属性值的属性规则（语义规则）， 其形式为： b：= f(c1, c2, , ck ) 即属性变量：= 这里 f是一个函数，且对于产生式A ， (1) b或者是A的一个综合属性并且c1,c2，ck是产生式右边文法符号的属性；

8、(2) b或者是产生式右边某个文法符号的一个继承属性并且c1,c2，ck是A或产生式右边任何文法符号的属性。 在两种情况下，我们都说属性b依赖于属性c1,c2，ck。,继承属性的求值规则： 产生式左部非终结符号的继承属性值取前面产生式右部该符号已有的继承属性值； 产生式右部符号的继承属性值用该产生式左部符号的继承属性或出现在该符号左部的符号的属性值进行计算。,体现自顶向下，自左向右的求值特性,体现自底向上，自右向左的求值特性,综合属性的求值规则： 产生式右部非终结符号的综合属性值取其下面产生式左部同名非终结符号的综合属性值； 产生式左部非终结符号的综合属性值用该产生式左部符号的继承属性或某个右

9、部符号的属性进行计算；,例8.1 有文法G为： ET1 + T2|T1 or T2 Tnum|true|false 对输入串3+4的类型检查的属性文法如图8.1。,ET1+T2 T1.tintANDT2.tint ET1orT2 T1.tboolAND T2.tbool Tnum T.tint Ttrue T.tbool Tfalse T.tbool,图8.1 类型检查的属性文法,属性文法记号中常使用N.t的形式表示与非终结符N相联的属性t。比如可把对上面表达式的类型检查的属性文法写成图8.1的形式。与每个非终结符T相联的有属性t，t要么是int，要么是bool。与非终结符E的产生式相联的语义

10、规则指明：两个T的属性必须相同。 图8.2的（b）是图8.2(a)语法树结点带有语义信息的表示。,图8.2 静态语义审查,8.1.2 属性的确定,写属性文法，首先应确定对于每个文法符号都有哪些属性，然后给每个属性起个名字，接着确定每个属性的类别。,正确确定综合属性和继承属性是非常重要的，究竟哪些属性确定为综合属性，哪些属性确定为继承属性，并没有固定的模式。,非终结符（开始符号除外）既可有综合属性也可有继承属性,文法开始符号没有继承属性,终结符号只有综合属性，一般由词法分析器提供,例8.2 简单算术表达式求值的语义描述。,产生式 语义规则 LE print(E.val) E E1 + T E.

11、val E1. val+ T. val ET E. val T. val T T1 * F T. val T1. val * F. val TF T . val F. val F（E） F . val E. val Fdigit F . val digit.lexval,在该描述中，大多数非终结符都有一个属性：一个整数值的称作val的属性。 按照语义规则对每个产生式来说，它的左部E，T，F的属性值的计算来自它右部的非终结符，这种属性称作综合属性。 单词digit仅有综合属性，它的值是由词法分析程序提供的。 和产生式LE相联的语义规则是一个过程，打印由E产生的表达式的值。我们可以理解为L的属性是

12、空的或是虚的。,例 8.3描述说明语句中各种变量的类型信息的语义规则。,产生式 语义规则 （1）DTL L.inT.type （2）Tint T.Typeinteger （3）Treal T.Typereal （4）LL1，id L1.inL.in; addtype（id.entry，L.in） （5）Lid addtype（id.entry，L.in）,例8.3中的文法定义了一种说明语句，该说明语句的形式是由关键字int或real开头，后面是一个标识符表，每个标识符用逗号隔开。 非终结符T有一个综合属性type，它的值由关键字决定（int或real）。与产生式DTL相联的语义规则L.inT.

13、type将L.in的属性值置为该说明语句指定的类型。属性L.in将被沿着语法树传递到下边的结点使用，与L产生式相联的规则里使用了它。 这个例子里，继承属性在说明中为各个标识符提供类型信息。,图8.4是句子int id1,id2的语法树，使用表示属性的传递情况。在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。与L产生式相联的语义规则中有一个过程调用addtype，过程addtype的功能是把每个标识符的类型信息登录在符号表的相关项中。,图 8.4 属性信息传递情况,产生式 语义规则 （1）DTL L.inT.type （2）Tint T.Typeinteger （3）

14、Treal T.Typereal （4）LL1，id L1.inL.in; addtype（id.entry，L.in） （5）Lid addtype（id.entry，L.in）,8.1.3 属性计算规则的确定,一般说来， 对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性，这有助于在产生式范围内“封装”属性的依赖性。 然而，对出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计算器的参数提供。,属性文法看作是允许为每个终结符和非

15、终结符配备一些属性的文法。它既能描述程序设计语言的语法，又为语义处理提供了方便。,属性文法里的属性有不同的类型，可以象变量一样地被赋值。赋值规则附加于语法规则之上。赋值与语法同时进行，赋值过程就是语义处理过程。 在推导建立语法树的时候，诸属性的值被计算并通过赋值规则层层传递。有的从语法规则左边向右边传，有的从右边向左边传。语法推导树最后完成时，就得到开始符号的属性值。也就是整个程序的语义。,8.2 中间代码（语言）,中间代码（语言）是一种特殊结构的语言，编译程序所使用的中间代码有多种形式。按其结构分常见的有逆波兰式（后缀式）、三地址代码（三元式、四元式）和树形表示（抽象语法树）、DAG表示。

16、8.2.1 逆波兰式（后缀式） 逆波兰式是最简单的一种中间代码表示形式，早在编译程序出现之前，它主要用于表示算术表达式，是波兰逻辑学家卢卡西维兹(J.Lukasiewicz)于1929年发明的。后来人们为了纪念他 ，就把这种后缀表示取名为逆波兰式。 逆波兰式最早是用于表示表达式的,后来计算机科学家把它应用于表示程序语言的各种语法成分。,（一）特点,首先我们考察算术表达式（中缀式）的计值顺序. 例8.4 中缀式的计值顺序见图8.5。,中缀式计值三个特点： （1）运算对象分别放在运算符（双目运算符）的两边； （2）计值顺序是根据运算符的优先级别及结合性确定，使用括号可以改变计值顺序； （3）运算符

17、的排列顺序不等价于计值顺序。,（1）不考虑运算符的优先关系，又不使用括号； （2）运算符的排列顺序就是计值顺序； （3）运算对象放在运算符的前面。 这种表示称为逆波兰式，也称做后缀式。 如上例：a b ( c d ( e f ) ) 其逆波兰式为：a b c d e f 这种后缀表示法虽然不符合人们的习惯，但它极易被计算机来处理。由于后缀式表示上的简洁和计值的方便，特别适用于具有堆栈体系的计算机的目标代码生成。,中缀式虽然是人们习惯的表示，但对于计算机来说，处理起来很不方便，如果我们采用一种表示方法：,(二)定义,逆波兰式（后缀式）的一般形式为： 若 是一个K元运算符（ K 1） ，它对其运算

18、对象e1,e2, ,ek作用的结果被表示为： e1 e2 ek ,表达式E的后缀表示的递归定义： （1）如果E是变量或常数，那么E的后缀表示是E本身； （2）如果E是形如E1 op E2的表达式，其中op是任意的二元运算符，那么E的后缀表示是E1| E2| op ,其中；E1和E2分别是E1和 E2的后缀表示，| 称为连接 （并置）运算符； （3）如果E是形如（E1），那么E的后缀表示就是E1的后缀表示。,（三）转换（中缀式 后缀式）,转换算法： 转换规则：设E为给定的中缀式，我们用表示E的后缀式，则有： | ； ； a,其中a表示变量或常数 。 对于给定的中缀式首先找出最后被计算的运算符，并

19、把此运算符作为上述式中的，使用上述规则转换之； 对中缀式的剩余部分重复上述过程，直至中缀式的每个量均被处理到为止。,把一般表达式翻译为后缀式是很容易的。,表8.1给出了把表达式翻译为后缀式的语义规则描述，其中E.code表示E后缀形式，op表示任意二元操作符，“|”表示后缀形式的连接。,解：E T R numprint (8)R numprint(8)+Tprint(+)R1 numprint(8)+numprint(5)print(+) R1 numprint(8)+numprint(5)print(+)Tprint() R1 numprint(8)+numprint(5)print(+)n

20、umprint(2) print() R1 numprint(8)+numprint(5)print(+)numprint(2) print() 输出：print(8)print(5)print(+)print(2)print() 即： 8 5 + 2 ,例8.5 有下面翻译模式： ETR RT print（）R1|T print（）R1| Tnum print（num.val） 把中缀表达式8+5 2翻译成后缀表达式。,后缀式很容易扩充到表达式以外的范围。只要遵守运算对象后直接紧跟它们的运算符的规则即可。 赋值语句的后缀表示：如有ab + c， 则有 a b c + 转向语句GOTO L的后

21、缀表示为“L jump”， 运算对象L为语句标号，运算符jump表示转到某个标号。,数组元素A下标表达式1，下标表达式n的后缀表示可表示为： 下标表达式1下标表达式2 下标表达式nA subs，运算符Subs表示求数组的下标。 当然，这些扩充的后缀表示的计值远比后缀表达式的计值复杂得多，要注意对扩展的运算符的含义正确处理。,条件语句if E then S1 else S2的后缀表示可表示为： E S1 S2 ￥， 把if-then-else看成三目运算符，用￥来表示。,8.2.2 三地址代码,一般形式：x := y op z 如表达式x + y z 翻译成的三地址代码序列是 t1 := y z

22、 t2 := x + t1 常用的三地址表示: 赋值语句 x := y op z， x := op y， x := y 无条件转移 goto L 条件转移 if x relop y goto L 过程调用 param x 和call p , n 过程返回 return y 索引赋值 x := yi和 xi := y 地址和指针赋值 x := a5:=a4; addtype(id1，entry，a5); a7:=a5; addtype(id2，entry，a7); a9:=a7; addtype(id3，entry，a9); 通过这些语义规则的计算将把类型值integer填入到每个标识符对应的符

23、号表项中去,也就是说，在拓扑排序中，在一个结点上，语义规则b:=f(c1,c2,ck)中属性c1,c2,ck 在计算b之时是可用的。既属性b依赖于属性c1,c2,ck 。,2）属性的计算过程,属性计算有树遍历和一遍扫描两种方法。 树遍历：构造输入的语法树见图8.12 (a)，,2）属性的计算过程,构造带有属性分析树见图8.13。,属性计算有树遍历和一遍扫描两种方法。 树遍历：构造输入的语法树见图8.12(a)，,用深度优先遍历该分析树。,还可以采用一遍扫描的处理方法来计算属性值。 一遍扫描的处理方法不同于树遍历的方法，它不需要构造实际语法树，而是在语法分析的同时计算属性值。,如果需要的话，可以

24、进行多次遍历，直至计算出所有属性。,3） 树遍历的属性计算方法,现在我们来考虑如何通过树遍历的方法计算属性的值。 通过树遍历计算属性值的方法有多种。这些方法都假设语法树已经建立起了，并且树中已带有开始符号的继承属性和终结符的综合属性。 然后以某种次序遍历语法树，直至计算出所有属性。 最常用的遍历方法是深度优先遍历的方法。如果需要的话，可使用多次遍历（或称遍）。,下面算法可对任何无循环的属性文法进行计算。,While 还有未被计算的属性 do VisitNode(S) /* S是开始符号 */ procedure VisitNode(NNode); begin if N是一个非终结符 then

25、/* 假设它的产生式为 N X1Xm */ for i:=1 to m do if XiVN then / * 即Xi是非终结符*/ begin 计算Xi的所有能够计算的继承属性; VisitNode(Xi) End; 计算N的所有能够计算的综合属性; end,例8.11 考虑表8.3所给的属性的文法G。,表8.3语义规则中有较复杂的依赖关系,其中S有继承属性a，综合属性b；X有继承属性c、综合属性d；Y有继承属性e、综合属性f；Z有继承属性h、综合属性g。,假设文法开始符号的继承属性S.a的初始值为0，则输入串xyz的语法树如图8.14（a）所示。,8.3.4 S-属性文法和自下而上翻译,S

26、-属性文法：仅仅使用综合属性的属性文法。,在语法树中，一个结点的综合属性的值由其子结点的属性值确定。而叶结点的（终结点）的综合属性值由词法分析得到。 因此，通常使用自底向上的方法在每个结点处执行语义规则计算综合属性的值。,S-属性文法的翻译器通常可借助于LR分析器实现。,综合属性可以在分析输入串的同时自底向上的来计算。 分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右部符号的属性值来计算。,例8.12 简单台式计算器的属性文法。,8+5*2 n的注释分析树见图8.15。,图8.15 8+5*2 n的注释分析树,2）考察S属性的自下而上计算过程：

27、 将LR分析器符号栈中增加一个域来保存综合属性值。,若产生式A XYZ的语义规则是A.a := f (X.x, Y.y, Z.z),那么归约后有：,例8.13 把台式计算器的语法制导定义改成栈操作代码如图8.17。,图8.17(a) 语法制导定义改成栈操作代码示意图,例8.13 把台式计算器的语法制导定义改成栈操作代码如图8.17。,图8.17(b) 语法制导定义改成栈操作代码示意图,例8.13 把台式计算器的语法制导定义改成栈操作代码如图8.17。,图8.17(c) 语法制导定义改成栈操作代码示意图,例8.13 把台式计算器的语法制导定义改成栈操作代码如图8.17。,图8.17(d) 语法制

28、导定义改成栈操作代码示意图,例8.13 把台式计算器的语法制导定义改成栈操作代码如图8.17。,图8.17(e) 语法制导定义改成栈操作代码示意图,例8.13 把台式计算器的语法制导定义改成栈操作代码如图8.17。,图8.17(f) 语法制导定义改成栈操作代码示意图,例8.13 把台式计算器的语法制导定义改成栈操作代码如图8.17。,图8.17(g) 语法制导定义改成栈操作代码示意图,例8.13 把台式计算器的语法制导定义改成栈操作代码如图8.17。,图8.17(h) 语法制导定义改成栈操作代码示意图,8.3.5 L-属性文法在自上而下分析中的实现, L-属性文法 定义： L-属

29、性文法是下列属性文法，如果对于每一个产生式A X1X2 Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj（1 jn）的一个继承属性(inherited attribute)，且这个继承属性仅依赖于： (1)产生式Xj在左边符号X1X2 Xj-1的属性; (2)A的继承属性。,即继承属性的求值规则： 产生式左部非终结符号的继承属性值取前面产生式右部该符号已有的继承属性值； 产生式右部符号的继承属性值用该产生式左部符号的继承属性或出现在该符号左边的符号的属性值进行计算。,体现自顶向下，自左向右的求值特性,S-属性文法是L-属性文法的一种。 L-属性文法允许一次遍历就计算出所有属性值。,L

30、-属性文法的输入文法要求是LL(1)文法，可用自顶向下分析构造分析器，在分析过程中可进行属性求值。,例8.14 A BC的属性求值顺序:,A的继承属性（若A为开始符号则有指定值，否则由前面产生式右部符号的继承属性求得） B的继承属性（由A的继承属性求得） B的综合属性（由后面产生式中左部符号为B的综合属性求得） C的继承属性（由A的继承属性和/或B的属性求得） C的综合属性（由后面产生式左部符号为C的综合属性求得） A的综合属性（由A的继承属性和/或B及C的属性求得）, 翻译模式（翻译方案，Translation schemes ）,目前流行的语义处理方法有两种： 语法制导的定义

31、和翻译模式。,语法制导的定义： 构造属性文法时，不指明翻译时语义规则的计算次序，这样的属性文法称为语法制导的定义。 其语义规则的计算次序要通过拓扑排序等方法来确定。 在这里，属性文法可以看作是关于语言翻译的高级规范说明，其中隐去实现细节，使用户从明确说明翻译顺序的工作中解脱出来。,翻译模式：,下面我们来讨论翻译模式。,如果在构造属性文法时把语义规则用花括号 括起来，插入到产生式右部的合适位置上，用以指明语义规则的计算次序，这样的属性文法称为翻译模式（或称为翻译方案）。 这是语法分析与语义动作交错进行的表示方法，以此来表示语义动作在语法分析过程中的执行时刻。这样就可把某些实现细节表示出来。,例8

32、.15 把带加号和减号的中缀表达式翻译成相应的后缀表达式的属性文法，其中addop表示或。 EE addop T print（addop.lexeme） | T Tnum print（num.val）,如果采用LR分析方法，则其属性计算很容易实现，比如在对串235的分析的同时执行语义动作输出235。语法分析树中加上虚线联结的语义结点，形成一个可说明语义动作的树。见图8.18。,对于LL（1）这种自顶向下分析方法的分析过程，从概念上来说可以看成是深度优先建立语法树的过程。因此，我们可以在自顶向下语法分析的同时实现L-属性文法的计算。要注意的是，上例是一个含左递归的文法，如果采用LL（1）分析必须

33、改写文法如下：,ETR Raddop T R1 | Tnum,这时对串235分析的语法树见图8.19， 而将后缀式 2 35输出的动作在语法树中应该出现的位置见图8.20所示。,例8.16： 下面是一个简单的翻译模式例子，它把带加号和减号的中缀表达式翻译成相应的后缀表达式。 ETR Raddop T print（addop.lexeme） R1 | Tnum print（num.val）,此例给出了可使用LL（1）分析方法的语义描述，不同的是，语义动作不是附在产生式右部的末尾，而是嵌入在产生式右部某些符号（如T和R）之间。,当只需要综合属性时，情况最为简单。在这种情况下，我们可以这样来建立翻译

34、模式：为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。,设计翻译模式时，我们必须注意某些限制以保证当某个动作引用一个属性时它必须是有定义的。,例如，假设有下面的产生式和语义规则： 产生式 语义规则 TT1*F T.val T1.valF.val5 我们建立产生式和语义动作： TT1*FT.valT1.valF.val,如果既有综合属性又有继承属性，在建立翻译模式时就必须特别小心。,后面我们将看到满足这三个条件的翻译模式是如何在一般的自上而下和自下而上分析器中实现的。,产生式右部的符号的继承属性必须在这个符号以前的动作中计算出来。 一个动作不能引用这个动作右边的符

35、号的综合属性。 产生式左部非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的末尾。,在第五章我们知道，为了构造不带回溯的自顶向下语法分析，必须消除文法中的左递归。现在我们把前面讨论过的消除左递归的算法加以扩充，当消除一个翻译模式的基本文法的左递归时同时考虑属性。这种方法适合带综合属性的翻译模式。这样，许多属性文法可以使用自顶向下分析来实现。下面将通过一个例子来介绍。,下面，我们讨论L-属性文法在自顶向下分析中的实现。为了便于说明动作的顺序和属性计算的顺序，我们用翻译模式进行描述。,一般转换左递归翻译模式的方法简述如下: 假定翻译模式为：

36、AA1YA.ag(A1.a，Y.y) AX A.af(X.x),其中，每个文法符号都有一个综合属性，用小写字母表示，g和f是任意函数。消除左递归，文法转换成： AXR RYR|,再考虑语义动作，则翻译模式为： AX R.if(X.x) R A.aR.s RY R1.ig(R.i，Y.y) R1 R.sR1.s R R.sR.i,例8.17 对图8.21消除左递归。,EE1+T E.valE1.val +T.val EE1T E.valE1.val T.val ET E.valT.val T(E) T.valE.val Tnum T.valnum.val 图8.21 带左递归的文法的翻译模式,对

37、图8.21消除左递归，构造新的翻译模式如图8.22所示。,ET R.iT.val R E.valR.s R T R1.iR.iT.val R1 R.sR1.s R T R1.iR.iT.val R1 R.sR1.s R R.sR1.s T（E）T.valE.val Tnum T.valnum.val 图8.22 消除左递归后的翻译模式,EE1+T E.valE1.val +T.val EE1T E.valE1.val T.val ET E.valT.val T(E) T.valE.val Tnum T.valnum.val 图8.21 带左递归的文法的翻译模式,在图8.22中的翻译模式中，每个

38、数都是由T产生的，并且T.val的值就是由属性num.val给出的数的词法值。子表达式95中的数字9是由最左边的T生成的，但是减号和5是由根的右子结点R生成的。继承属性R.i从T.val得到值9。计算95并把结果4传递到中间的R结点，这是通过产生式中嵌入的下面动作实现： R1.iR.iT.val 新的翻译模式产生的表达式952的带注释的语法树如图8.23所示。图中箭头指明了对表达式计算的顺序。,图8.23计算表达式952,8.3.6 L-属性文法在自下而上分析中的实现,下面我们讨论然后实现自下而上计算继承属性。办法有两种：从翻译模式中去掉嵌入在产生式中间的动作和用综合属性代替继承属性。 8.3

39、.6.1 从翻译模式中去掉嵌入在产生式中间的动作 在8.3.4节中的自下而上的翻译方法中，要求把所有的语义动作都放在产生式的末尾，而在上节的自顶向下翻译方法中，我们需要在产生式右部的不同地方嵌入语义动作。下面我们介绍一种转换方法，它可以使所有嵌入的动作都出现在产生式的末尾，这样就可以自下而上处理继承属性。 转换方法：在基础文法中加入新的产生式，这种产生式的形式为M，其中M为新引入的一个标记非终结符。我们把嵌入在产生式中的每个语义动作用不同的标记非终结符M代替，并把这个动作放在产生式M的末尾。,例8.18 有下面翻译模式： ETR RT print（）R|T print（）R| Tnum pri

40、nt（numval）,使用标记非终结符号M和N转换为 ETR RTMR|TNR| Tnumprint（numval） Mprint（） N print（）,两个翻译模式中的文法接受相同的语言。通过画出带有表示动作的附加结点的分析树，我们可以看到动作的执行程序也是一样的。在经过转换的翻译模式中，动作都在产生式右端的末尾，因此，可以在自下而上分析过程中产生式右部被归约时执行相应的动作。,例8.19 给定文法: SbTc Sa TR RR/S RS 为该文法设计翻译方案，使句型bR/bTc/bSc/ac经该翻译方案翻译后,输出串：0342031320,图8.24 句型bR/bTc/bSc/ac的语法

41、树,这样根据输出串与归约的关系可以求得翻译方案如下： SbTc print“0” Sa print“1” TR print“2” RR/S print“3” RS print“4”,解：求得该句型的语法树见图8.24。,按最左归约的方式找当前句型的句柄，每当对句柄进行归约时同步执行相应的语义规则，就能得到输出串：0342031320。,例8.20 给定文法及相应的翻译方案： EE+T print(“5”) ET print(“4”) TT*F print(“3”) TF print(“2”) F( E ) print(“1”) Fi print(“0”) 对于句型T+(T*(F+T)*i),处

42、理完该句型后输出是什么？,则对于句型T+(T*(F+T)*i),处理完该句型后输出是： 424513034124,解：求得句型T+(T*(F+T)*i)的语法树见图8.25。,按最左归约的方式找当前句型的句柄，每当对句柄进行归约时同步执行相应的语义规则，就能得到翻译结果（即输出）。, 用综合属性代替继承属性,为了用综合属性代替继承属性，改变基础文法是一种可能的办法。,因为标识符由L产生而类型符不在L的子树中，我们不能仅仅使用综合属性就把类型与标识符联系起来。事实上，如果非终结符L从第一个产生式中它右边的T中继承了类型。则我们得到的属性文法就不是L属性的，因此，基于这个属性文法的翻

43、译工作不能在语法分析的同时进行。,例8.21 一个PASCAL语言的说明语句形式是由一个标识符序列后跟类型组成，如m, n : integer ，其文法为： DL：T Tinteger|char LL，id| id,一个解决的方法是重新构造文法，借以实现用综合属性代替继承属性。比如一个等价的文法如下： Did L L，id L |：T Tinteger|char,这样，使类型作为标识符表（identifiers list）的最后一个元素，类型可以通过综合属性L.type进行传递，当通过L产生每个标识符时，它的类型就可以填入到符号表中。,变换后的属性文法如下： Did L addtype(id.

44、entry,L.type) L，id L1 L.typeL1.type，addtype (id.entry,L.type) |：T L.typeT.type Tinteger T.typeint |char T.typech,8.4 简单赋值语句的翻译,在8.2.2的四元式表示中，使用变量名字本身表示运算对象arg1和arg2，用Ti表示RESULT。 在实际实现中，它们或者是一个指针，指向符号表的某一登录项，或者是一个临时变量的整数码。 在对赋值语句翻译为四元式的描述中，我们将表明怎样查找这样的符号表登录项。 首先对id表示的单词定义一属性，用做语义变量，用Lookup（id.

45、name）表示审查是否出现在符号表中，如在，则返回一指向该登录项的指针，否则返回nil。 语义过程emit表示输出四元式到输出文件上。 语义过程newtemp表示生成一个临时变量，每调用一次，生成一新的临时变量。语义变量E.place，表示存放E值的变量名在符号表的登录项或一整数码（若此变量是一个临时变量）。,例8.22 图8.27列出了翻译赋值语句到三地址代码的语义描述。这里的语义工作包括对变量进行先定义后使用的检查。,图8.27中的例子里，与非终结符E相联的语义值有E.place，还有E.type。语义值的设计是与语义处理的描述相关的。 对赋值语句的语义处理，需要对赋值语句左

46、部的标识符，检查它的种类（kind），若不是变量名，则指出错误，若是变量名，才生成赋值运算的代码。 对右部表达式中作为运算对象的标识符，检查其是否变量名或常量名，是，生成相应代码，不是（即是过程名），则指出错误。 这一点若用语义规则描述的话，还应增加一语义值，与非终结符相联，比如用E.kind表示。,实际上，在一个表达式中可能会出现各种不同类型的变量或常数，而不是像图8.24中的id假定为都是同一类型 也就是说，编译程序还应执行这样的语义动作：对表达式中的运算对象应进行类型检查，如不能接受不同类型的运算对象的混合运算，则应指出错误；如能接受混合运算，则应进行类型转换的语义处理。 例8.23 图

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

48、.typeint then begin emit（E.place，=，E1.place，*i, E2.place）； E.type=int end else if E1.typereal AND E2.typereal then begin emit (E.place,=,E1.place,*r,E2.place); E.type=real end else if E1.typeint /* and E2.type=real*/then begin t=newtemp； emit（t，=，itr，E1.place）； emit（E.place，=，t，*r，E2.place）； E.type=

49、real end else /*E1.typereal and E2.typeint*/ begin t=newtemp； emit（t，=,itr，E2.place）； emit（E.place，=，E1.place，* r,t）； E.type=real end； ,赋值语句中会含有复杂数据类型，如数组元素、记录（结构）的引用。这种情况的翻译工作要复杂些。,8.5 布尔表达式的翻译,程序设计语言中的布尔表达式有两个作用： 一是计算逻辑值; 二是在控制流语句中用作条件表达式。,如在if-then，if-then-else，或是while-do语句中那样。 布尔表达式是由布尔算符and，or和

50、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.1 布尔表达式的翻译方法,通常，计算布尔表达式的值有两种办法，第一种办法，如同计算算术表达式一样，步步计算出各部分的真假值，最后计算出整个表达式的值。,例8.24 用数值1表示true，用0表示false。 那么布尔表达

51、式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）t1=not c （2）t2=b and t1 （3）t3=a or t2,对于像ab这样的关系表达式，可看成等价的条件语句if ab th

52、en 1 else 0，它翻译成的四元式序列为： （1）ifab goto （4） （2）t=0 （3）goto （5） （4）t=1 （5） 其中用临时变量t存放布尔表达式ab的值，(5)为后续的四元式序号。 图8.29给出了按第一种办法计算布尔表达式的值，将布尔表达式翻译成四元式的描述，在该描述中使用了过程newtemp和emit，其含义同前，过程nextstat给出在输出序列中下一四元式序号，emit过程每被调用一次，nextstat增加1。,图8.29用数值表示布尔值的翻译方案,EE1 or E2 E.place=newtemp； emit（E.place = E1.placeor E

53、2.place） EE1 and E2 E.place =newtemp； emit（E.place = E1.place and E2.place） Enot E1 E.place =newtemp：； emit（E.place =not E1.place） E（E1） E.place=E1.place Eid1 relop id2E.place=newtemp； emit（if id1.place relop id2.Place goto nextstat+3）； emit（E.place =0 ）； emit（goto nextstat+2）； emit（E.place =1） Etru

54、e E.place=newtemp； emit（E.place =1） Efalse E.place=newtemp； emit（E.place =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.30（a）（b）（c）中，其中使用.和。两个出口分别用于表示E为真和假时控制流向的转移。分别叫真出口和假出口。,图8.30 控制语句的代码结构,

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

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

57、为了看清这一点，我们把该表达式放在条件语句中考虑，如语句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的四元式） （p）goto（q） （p+1）（关于S2的四元式） （q）,实际上，上述四元式（1）和（5），（4）和（6）的转移地址并不能在产生这些四元式的同时得知。例如（1）和（5）的转移地

58、址为（7），它是在整个布尔表达式的四元式序列生成之后才回填的地址。为了记录需回填地址的四元式，常采用一种拉链的办法。把需回填E.true的四元式拉成一链，把需回填E.false的四元式拉成一链，分别称做真链和假链。用一个例子说明拉链是如何方式，若有四元式序列：,（0） （10）gotoE.true （20）gotoE.true （30）gotoE.true,回填为,这里把地址（30）称作链首，0为链尾标志，即地址（10）为链尾。,8.6 控制语句的翻译8.6.1条件转移,考虑if then，if then else和while do语句，在图8.27中已给出了它们的代码结构。这里给出其文法GS定义：,其中各非终结符号的意义是： S语句 L语句串 A赋值句 E布尔表达式,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,即是说，必须将E