语法制导翻译和中间代码生成new.pptVIP

第八章 语法制导翻译和中间代码生成,【课前思考】 回顾第一章介绍的编译过程，理解语义分析在编译过程中的位置和作用。 “属性文法”的概念及应用。 “语法制导翻译”的概念及应用。 什么是中间代码（中间表示），为什么要中间代码？,【学习目标】,明确语义分析在编译过程所处的阶段和作用。 掌握属性文法的基本概念。 使用属性文法和语法制导翻译方法描述具体的语义分析和产生中间代码。 主要是要让同学们了解： )语义的描述方式； )语义的处理方法。,【本章重点】,1.几种典型的中间代码（语言）的形式; 2.语义的描述方法 着重介绍一种形式化的语义描述方法属性文法; 3.语义的处理方法 着重介绍语法制导的翻译法包括它的两种具体形式：语法制导的定义和翻译方案 。,编译程序的任务是把源程序翻译成目标程序，这个目标程序必须和源程序的语义等同，也就是说，尽管它们的语法结构完全不同，但它们所表达的结果应完全相同。 通常，在词法分析程序和语法分析程序对源程序的语法结构进行分析之后，要么由语法分析程序直接调用相应的语义子程序进行语义处理，要么首先生成语法树或该结构的某种表示，再进行语义处理。,8.0 概述,第八章 语法制导翻译和中间代码生成,第一，审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。有时把这个工作称为静态语义分析或静态审查。 第二，如果静态语义正确，语义处理则要执行真正的翻译，即，或者将源程序翻译成程序的一种中间表示形式（中间代码），或者将源程序翻译成目标代码。 本章引入属性文法和语法制导翻译方法的基本思想，介绍几种典型的中间代码形式，最后讨论一些语法成分的翻译工作。,编译中的语义处理是指两个功能：,8.1 属性文法(attribute grammar),属性文法(也称属性翻译文法)是Knuth在1968年首先提出的。 它是在上下文无关文法的基础上，为每个文法符号(终结符或非终结符)配备若干相关的“特性”（称为属性）。 这些属性代表与文法符号相关信息，例如它的类型、值、代码序列、符号表内容等等。 属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。,为文法的每个产生式配备的一组属性的计算规则，称为语义规则，称为语义规则。,所谓属性，其涉及的概念比较广泛，常用以描述事物或人的特征、性质，品质等等。比如，谈到一个物体，可以用“颜色“描述它，谈起某人，可以使用“有幽默感“来形容他。对编译程序使用的语法树的结点，可以用“类型“、“值“或“存储位置“来描述它。,一个属性文法包含一个上下文无关文法和一系列语义规则，这些语义规则附在文法的每个产生式上。,所谓语法制导的翻译指的是在语法分析过程中，完成这些语义规则描述的动作，从而实现语义处理。,8.1.1 属性文法定义,定义1： 形式上讲，属性文法是一个三元组 :A=(G，V，F)， 其中： G:是一个上下文无关文法； V:有穷的属性集,每个属性与文法的一个终结符或非终结符相联,这些属性代表与文法符号相关信息； F:关于属性的属性断言或一组属性的计算规则(称为语义规则) 。 断言或语义规则与一个产生式相联,只引用该产生式左端或右端的终结符或非终结符相联的属性。,定义2：,一个属性文法是一个三元组：A=(G,V,F ),其中 G -基础文法（一个上下文无关文法） V -每个文法符号有一组属性 F -每个文法产生式A有一组形式为b:=f(c1,c2,ck)的语义规则，其中f 是函数，b和c1,c2,ck是该产生式文法符号的属性。,属性文法中的属性分成两类：继承属性和综合属性。,简单地说，综合属性用“自下而上“传递信息，而继承属性用于“自上而下“传递信息。,综合属性（synthesized attribute）：如果b是A的属性，c1 , c2 , , ck是产生式右部文法符号的属性或A的其它属性，则称b是文法符号A的综合属性。 继承属性(inherited attribute)：如果b是产生式右部某个文法符号X的属性，并且c1,c2,ck是A或产生式右部文法符号的属性，则称b是文法符号X的继承属性。,每个文法产生式A有一组形式为b:=f(c1,c2,ck)的语义规则，其中f 是函数，b和c1,c2,ck是该产生式文法符号的属性,属性文法的主要思想是：,1.对每个文法符号引入相关的属性符号； 2.对于每个产生式设置一组计算属性值的属性规则（语义规则），其形式为：b：= f(c1, c2, , ck ) 即：属性变量：= 这里 f是一个函数，且对于产生式A ， (1) b或者是A的一个综合属性并且c1,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是产生式右边文法符号的属性； (2) b或者是产生式右边某个文法符号的一个继承属性并且c1,c2，ck是A或产生式右边任何文法符号的属性。 在两种情况下，我们都说属性b依赖于属性c1,c2，ck。,继承属性的求值规则： 产生式左部非终结符号的继承属性值取（来自于）前面产生式右部该符号已有的继承属性值； 产生式右部符号的继承属性值用该产生式左部符号的继承属性或出现在该符号左部的符号的属性值进行计算。,体现自顶向下，自左向右的求值特性,体现自底向上，自右向左的求值特性,综合属性的求值规则： 产生式右部非终结符号的综合属性值取（来自于）其下面产生式左部同名非终结符号的综合属性值； 产生式左部非终结符号的综合属性值用该产生式左部符号的继承属性或某个右部符号的属性进行计算；,例8.1 有文法G为： ET1 + T2|T1 or T2 Tnum|true|false 对输入串3+4的类型检查的属性文法如图8.1。,ET1+T2 T1.tint AND T2.tint ET1orT2 T1.tbool AND 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的产生式相联的语义规则指明：两个T的属性必须相同。 图8.2的（b）是图8.2(a)语法树结点带有语义信息的表示。,图8.2 静态语义审查,8.1.2 属性的确定,写属性文法，首先应确定对于每个文法符号都有哪些属性，然后给每个属性起个名字，接着确定每个属性的类别。 要特别强调的是： （1）终结符只有综合属性，它们的值由词法分析器提供； （2）非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值要在计算（整个处理）开始时指定。,正确确定综合属性和继承属性是非常重要的，究竟哪些属性确定为综合属性，哪些属性确定为继承属性，并没有固定的模式。,例8.2 简单算术表达式求值的语义描述。,产生式 语义规则 LE print(E.val) E E1 + T E. 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的属性是空的或是虚的。,例 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.type将L.in(继承属性)的属性值置为该说明语句指定的类型。属性L.in将被沿着语法树传递到下边的结点使用，与L产生式相联的规则里使用了它。 这个例子里，继承属性L.in在说明中为各个标识符提供类型信息。,图8.4是句子int id1,id2的语法树，使用表示属性的传递情况。在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。与L产生式相联的语义规则中有一个过程调用addtype，过程addtype的功能是把每个标识符的类型信息登录在符号表的相关项中。,图 8.4 属性信息传递情况,8.1.3 属性计算规则的确定,一般说来， 对产生式右部符号的继承属性和产生式左部符号的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性，这有助于在产生式范围内“封装”属性的依赖性。 然而，对产生式左部符号的继承属性和产生式右部符号的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计算器的参数提供。,属性文法看作是允许为每个终结符和非终结符配备一些属性的文法。它既能描述程序设计语言的语法，又为语义处理提供了方便。,属性文法里的属性有不同的类型，可以象变量一样地被赋值。赋值规则附加于语法规则之上。赋值与语法同时进行，赋值过程就是语义处理过程。 在推导或者归约的时候，诸属性的值被计算并通过赋值规则层层传递。有的从语法规则左边向右边传，有的从右边向左边传。语法推导树最后完成时，就得到开始符号的属性值。也就是整个源程序的语义。,中间代码，也称中间语言，是复杂性介于源程序语言和机器语言的一种表示形式。 为什么有的编译程序直接生成目标代码，有的编译程序采用中间代码。 一般，快速编译程序直接生成目标代码，没有将中间代码翻译成目标代码的额外开销。 但是为了使编译程序结构在逻辑上更为简单明确，常采用中间代码。 这样可以将与机器相关的某些实现细节置于代码生成阶段仔细处理，并且可以在中间代码一级进行优化工作使得代码优化比较容易实现。,8.2 中间代码（语言）,中间代码（语言）是一种特殊结构的语言，编译程序所使用的中间代码有多种形式。按其结构分常见的有逆波兰式（后缀式）、三地址代码（三元式、四元式）和树形表示（抽象语法树）、DAG表示。 8.2.1 逆波兰式（后缀式） 逆波兰式是最简单的一种中间代码表示形式，早在编译程序出现之前，它主要用于表示算术表达式，是波兰逻辑学家卢卡西维兹(J.Lukasiewicz)于1929年发明的。后来人们为了纪念他 ，就把这种后缀表示取名为逆波兰式。 逆波兰式最早是用于表示表达式的,后来计算机科学家把它应用于表示程序语言的各种语法成分。,（一）特点,首先我们考察算术表达式（中缀式）的计值顺序. 例8.4 中缀式的计值顺序见图8.5。,中缀式计值三个特点： （1）运算对象分别放在运算符（双目运算符）的两边； （2）计值顺序是根据运算符的优先级别及结合性确定，使用括号可以改变计值顺序； （3）运算符的排列顺序不等价于计值顺序。,（1）不考虑运算符的优先关系，又不使用括号； （2）运算符的排列顺序就是计值顺序； （3）运算对象放在运算符的前面。 这种表示称为逆波兰式，也称做后缀式。,中缀式虽然是人们习惯的表示，但对于计算机来说，处理起来很不方便，如果我们采用一种表示方法：,如上例：a b ( c d ( e f ) ) 其逆波兰式为：a b c d e f 这种后缀表示法虽然不符合人们的习惯，但它极易被计算机来处理。由于后缀式表示上的简洁和计值的方便，特别适用于解释执行的程序设计语言的中间表示，也方便具有堆栈体系的计算机的目标代码生成。,(二)定义,逆波兰式（后缀式）的一般形式为： 若 是一个K元运算符（ K 1） ，它对其运算对象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表示变量或常数 。 对于给定的中缀式首先找出最后被计算的运算符，并把此运算符作为上述式中的，使用上述规则转换之； 对中缀式的剩余部分重复上述过程，直至中缀式的每个量均被处理到为止。,把一般表达式翻译为后缀式是很容易的。,表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(+)numprint(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的后缀表示为“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 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 := &y，x := y 和 x := y,三地址代码有四元式、三元式、间接三元式等形式,三地址代码可看成中间代码的一种抽象形式。 编译程序中，三地址代码语句的具体实现可以用记录表示，记录中包含表示运算符和操作数的域。 三地址代码通常有三种表示方法：四元式、三元式、间接三元式。,四元式结构形式: (OP，ARG1，ARG2，RESULT),算符,左运算对象,右运算对象,运算结果,三元式结构形式: 编号 (OP，ARG1，ARG2) 间接三元式：由间接三元式序列和间接码表组成。,例8.6 有中缀式a:b*cb*c，求其等价的四元式和三元式。,四元式 三元式 算符 左对象 右对象 结果量 编号 算符 左对象 右对象 op arg1 arg2 result op arg1 arg2 minus c T1 (1) minus c b T1 T2 (2) b (1) minus c T3 (3) minus c b T3 T4 (4) b (3) T2 T4 T5 (5) (4) (2) T5 a (6) assign a,图8.6 四元式、三元式结构,8.2.3 图形表示,抽象语法树是一种图形化的中间表示，它的每一个叶结点都表示诸如常量或变量这样的运算对象，而它的内部结点则表示运算符；它不同于前述的语法树，它展示了一个操作过程并同时描述了源程序的自然层次结构； DAG（有向无环图）以更紧凑的方式给出了同样的信息（即对于相同的语法成分只给出一次），在图中其结点的含义同抽象语法树。,例：表达式a := (b + cd ) + cd的两种图形表示见图8.8。,抽象语法树是分析树的浓缩表示：算符和关键字是作为内部结点出现的。 语法制导翻译可以基于分析树，也可以基于抽象语法树 抽象语法树的例子：,抽象语法树,构造抽象语法树的语法制导定义,图8.10 抽象语法树的语法制导定义例子,例8.8 a+5*b的抽象语法树的构造,E.nptr,T.nptr,E.nptr,T.nptr,F.nptr,id,T.nptr,+,*,F.nptr,F.nptr,id,num,指向符号表中a的入口,指向符号表中b的入口,图8.11(a) a+5*b的抽象语法树,图8.11(b) a+5*b的抽象语法树,T.nptr,图8.11(c) a+5*b的抽象语法树,E.nptr,T.nptr,F.nptr,图8.11(d) a+5*b的抽象语法树,T.nptr,图8.11(e) a+5*b的抽象语法树,指向符号表中b的入口,图8.11(f) a+5*b的抽象语法树,图8.11(g) a+5*b的抽象语法树,图8.11(h) a+5*b的抽象语法树,图8.11(i) a+5*b的抽象语法树,8.3 语法制导翻译,编译程序的整个任务就是把源程序翻译为目标程序。 实际上可以把每个编译阶段都看作是完成一定翻译任务的处理过程： 词法分析阶段把字符流翻译为单词流，语法分析阶段把单词流翻译为语法树，语义分析和代码生成阶段把语法树翻译为汇编代码或者机器代码等等。 定义（语法制导翻译）：,为文法中每个产生式配备一组语义规则，并且在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译的办法称作语法制导翻译。,例8.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.code = 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|+ ) (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 基于属性文法的处理方法,处理方法： 1）,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 do 从ci结点到b结点构造一条有向边；,注:在构造依赖图之前,要为每一个过程调用的语义规则引入一个虚综合属性，即在依赖图中构造一个结点。这样，若属性b依赖于属性c，则从c的结点有一条有向边连接到b的结点。,例8.10：有属性文法见表8.2，构造int id1, id2, id3的分析树依赖图。,表8.2 说明语句的属性文法,表8.2 说明语句的属性文法,图 8.12(a) int id1, id2, id3的注释分析树,先构造int id1, id2, id3的语法树见图8.12 (a)所示。,再构造int id1, id2, id3的分析树的依赖图(结点用数字表示)见图8.12b。 D TL L.in := T.type,addtype (id.entry, L.in ),图 8.12(b) int id1, id2, id3的依赖图,8.3.3 语义规则的计算次序,1）拓扑排序,从依赖图的拓扑排序中我们可以得到计算语义规则的次序，用这个顺序来计算语义规则就得到了输入串的翻译。,拓扑排序：结点的一种排序，使得有向边只会从该次序中先出现的结点指向后出现的结点。,例：图8.12 (b)的拓扑排序为：1，2，3，4，5，6，7，8，9，10 。,一个依赖图的任何拓扑排序都给出了语法树中结点的语义规则计算的有效顺序。,2）属性的计算过程,属性计算有树遍历和一遍扫描两种方法。 树遍历：构造输入的语法树见图8.12 (a)，,2）属性的计算过程,构造带有属性分析树见图8.13。,属性计算有树遍历和一遍扫描两种方法。 树遍历：构造输入的语法树见图8.12(a)，,用深度优先遍历该分析树。,还可以采用一遍扫描的处理方法来计算属性值。 一遍扫描的处理方法不同于树遍历的方法，它不需要构造实际语法树，而是在语法分析的同时计算属性值。,如果需要的话，可以进行多次遍历，直至计算出所有属性。,3） 树遍历的属性计算方法,现在我们来考虑如何通过树遍历的方法计算属性的值。 通过树遍历计算属性值的方法有多种。这些方法都假设语法树已经建立起了，并且树中已带有开始符号的继承属性和终结符的综合属性。 然后以某种次序遍历语法树，直至计算出所有属性。 最常用的遍历方法是深度优先遍历的方法。如果需要的话，可使用多次遍历（或称遍）。,8.3.4 S-属性文法和自下而上翻译,S-属性文法：仅仅使用综合属性的属性文法。,在语法树中，一个结点的综合属性的值由其子结点的属性值确定。而叶结点的（终结点）的综合属性值由词法分析得到。 因此，通常使用自底向上的方法在每个结点处执行语义规则计算综合属性的值。,S-属性文法的翻译器通常可借助于LR分析器实现。,综合属性可以在分析输入串的同时自底向上的来计算。 分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右部符号的属性值来计算。,例8.12 简单台式计算器的属性文法。,8+5*2 n的注释分析树见图8.15。,图8.15 8+5*2 n的注释分析树,2）考察S属性的自下而上计算过程： 将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) 语法制导定义改成栈操作代码示意图,例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-属性文法是下列属性文法，如果对于每一个产生式A X1X2 Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj（1 jn）的一个继承属性(inherited attribute)，且这个继承属性仅依赖于： (1)产生式Xj在左边符号X1X2 Xj-1的属性; (2)A的继承属性。,即继承属性的求值规则： 产生式左部非终结符号的继承属性值取前面产生式右部该符号已有的继承属性值； 产生式右部符号的继承属性值用该产生式左部符号的继承属性或出现在该符号左边的符号的属性值进行计算。,体现自顶向下，自左向右的求值特性,S-属性文法是L-属性文法的一种。 L-属性文法允许一次遍历就计算出所有属性值。,L-属性文法的输入文法要求是LL(1)文法，可用自顶向下分析构造分析器，在分析过程中可进行属性求值。,例8.14 A BC的属性求值顺序:,A的继承属性（若A为开始符号则有指定值，否则由前面产生式右部符号的继承属性求得） B的继承属性（由A的继承属性求得） B的综合属性（由后面产生式中左部符号为B的综合属性求得） C的继承属性（由A的继承属性和/或B的属性求得） C的综合属性（由后面产生式左部符号为C的综合属性求得） A的综合属性（由A的继承属性和/或B及C的属性求得）, 翻译模式（翻译方案，Translation schemes ）,目前流行的语义处理方法有两种： 语法制导的定义和翻译模式。,语法制导的定义： 构造属性文法时，不指明翻译时语义规则的计算次序，这样的属性文法称为语法制导的定义。 其语义规则的计算次序要通过拓扑排序等方法来确定。 在这里，属性文法可以看作是关于语言翻译的高级规范说明，其中隐去实现细节，使用户从明确说明翻译顺序的工作中解脱出来。,翻译模式：,下面我们来讨论翻译模式。,如果在构造属性文法时把语义规则用花括号 括起来，插入到产生式右部的合适位置上，用以指明语义规则的计算次序，这样的属性文法称为翻译模式（或称为翻译方案）。 这是语法分析与语义动作交错进行的表示方法，以此来表示语义动作在语法分析过程中的执行时刻。这样就可把某些实现细节表示出来。,例8.15 把带加号和减号的中缀表达式翻译成相应的后缀表达式的属性文法，其中addop表示或。 EE addop T print（addop.lexeme） | T Tnum print（num.val）,如果采用LR分析方法，则其属性计算很容易实现，比如在对串235的分析的同时执行语义动作输出235。语法分析树中加上虚线联结的语义结点，形成一个可说明语义动作的树。见图8.18。,对于LL（1）这种自顶向下分析方法的分析过程，从概念上来说可以看成是深度优先建立语法树的过程。因此，我们可以在自顶向下语法分析的同时实现L-属性文法的计算。要注意的是，上例是一个含左递归的文法，如果采用LL（1）分析必须改写文法如下：,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）之间。,当只需要综合属性时，情况最为简单。在这种情况下，我们可以这样来建立翻译模式：为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。,设计翻译模式时，我们必须注意某些限制以保证当某个动作引用一个属性时它必须是有定义的。,例如，假设有下面的产生式和语义规则： 产生式 语义规则 TT1*F T.val T1.valF.val 我们建立产生式和语义动作： TT1*FT.valT1.valF.val,如果既有综合属性又有继承属性，在建立翻译模式时就必须特别小心。,后面我们将看到满足这三个条件的翻译模式是如何在一般的自上而下和自下而上分析器中实现的。,产生式右部的符号的继承属性必须在这个符号以前的动作中计算出来。 一个动作不能引用这个动作右边的符号的综合属性。 产生式左部非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的末尾。,8.3.6 L-属性文法在自下而上分析中的实现,下面我们讨论然后实现自下而上计算继承属性。办法有两种：从翻译模式中去掉嵌入在产生式中间的动作和用综合属性代替继承属性。 从翻译模式中去掉嵌入在产生式中间的动作 在8.3.4节中的自下而上的翻译方法中，要求把所有的语义动作都放在产生式的末尾，而在上节的自顶向下翻译方法中，我们需要在产生式右部的不同地方嵌入语义动作。下面我们介绍一种转换方法，它可以使所有嵌入的动作都出现在产生式的末尾，这样就可以自下而上处理继承属性。 转换方法：在基础文法中加入新的产生式，这种产生式的形式为M，其中M为新引入的一个标记非终结符。我们把嵌入在产生式中的每个语义动作用不同的标记非终结符M代替，并把这个动作放在产生式M的末尾。,例8.18 有下面翻译模式： ETR RT print（）R|T print（）R| Tnum print（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的语法树,这样根据输出串与归约的关系可以求得翻译方案如下： 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),处理完该句型后输出是什么？,则对于句型T+(T*(F+T)*i),处理完该句型后输出是： 424513034125,解：求得句型T+(T*(F+T)*i)的语法树见图8.25。,按最左归约的方式找当前句型的句柄，每当对句柄进行归约时同步执行相应的语义规则，就能得到翻译结果（即输出）。,8.4 简单赋值语句的翻译,在8.2.2的四元式表示中，使用变量名字本身表示运算对象arg1和arg2，用Ti表示RESULT。 在实际实现中，它们或者是一个指针，指向符号表的某一登录项，或者是一个临时变量的整数码。 在对赋值语句翻译为四元式的描述中，我们将表明怎样查找这样的符号表登录项。 首先对id表示的单词定义一属性，用做语义变量，用Lookup（）表示审查是否出现在符号表中，如在，则返回一指向该登录项的指针，否则返回nil。 语义过程emit表示输出四元式到输出文件上。 语义过程newtemp表示生成一个临时变量，每调用一次，生成一新的临时变量，并返回该变量在符号表中的地址。语义变量E.place，表示存放E值的变量名在符号表的登录项或一整数码（若此变量是一个临时变量）。,例8.22 图8.27列出了翻译赋值语句到三地址代码的语义描述。这里的语义工作包括对变量进行“先定义后使用“的检查。,实际上，在一个表达式中可能会出现各种不同类型的变量或常数，而不是像图8.24中的id假定为都是同一类型 也就是说，编译程序还应执行这样的语义动作：对表达式中的运算对象应进行类型检查，如不能接受不同类型的运算对象的混合运算，则应指出错误；如能接受混合运算，则应进行类型转换的语义处理。 例8.23 图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.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=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和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。 那么布尔表达式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 then 1 else 0，它翻译成的四元式序列为： （1） if ab 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.place or E2.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 id2 E.place=newtemp； emit（if id1.place relop id2.Place goto nextstat+3）； emit（E.place =0 ）； emit（goto nextstat+2）； emit（E.place =1） Etrue 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）中，其中