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

,武汉理工大学计算机科学系陈天煌,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Compile,第八章 语法制导翻译和中间代码生成,【,课前思考,】,回顾第一章介绍的编译过程，理解语义分析在编译过程中的位置和作用。,“属性文法”的概念及应用。,“语法制导翻译”的概念及应用。,什么是中间代码（中间表示），为什么要中间代码？,【,学习目标,】,明确语义分析在编译过程所处的阶段和作用。,掌握属性文法的基本概念。,使用属性文法和语法制导翻译方法描述具体的语义分析和产生中间代码。,主要是要让同学们了解：,),语义的描述方式；,),语义的处理方法。,【,本章重点,】,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,(,c,1,c,2,c,k,),的语义规则，其中,f,是函数，,b,和,c,1,c,2,c,k,是该产生式文法符号的属性。,属性的类型（从分析过程中属性值的计算方法来分类）：,1,、,综合属性,（,Synthesized Attributes,）,：,属性值是分析树中该结点的子结点的属性值的函数,2,、,继承属性,（,Inherited Attributes,）,：,属性值是分析树中该结点的父结点,和,/,或,兄弟结点的属性值的函数,对于产生式,A,X,1,X,2,X,n,A,X,1,X,2,X,n,计算,A,的综合属性,S(A):=f(I(X,1,),I(,X,n,),计算,X,j,的继承属性,T(,X,j,):=f(I(A),.,I(,X,n,),综合属性用于“自下而上”传递信息，继承属性用于“自上而下”传递信息,属性文法的主要思想是：,1.,对每个文法符号引入相关的属性符号；,2.,对于每个产生式写出计算属性值的属性规则（语义规则），其形式为：,b,：,=,f,(,c,1,c,2,c,k,),即：属性变量：,=,这里,f,是一个函数，且对于产生式,A,，,(1)b,或者是,A,的一个综合属性并且,c,1,c,2,，,c,k,是产生式右边文法符号的属性；,(2)b,或者是产生式右边某个文法符号的一个继承属性并且,c,1,c,2,，,c,k,是,A,或产生式右边任何文法符号的属性。,在两种情况下，我们都说属性,b,依赖于属性,c,1,c,2,，,c,k,。,即：属性规则中的左部,b,能写那些属性变量是有规定的，只能为下述两种变量：,产生式左部符号的综合属性变量；,产生式右部符号的继承属性变量。,2.,对于每个产生式写出计算属性值的属性规则（语义规则），,其形式为：,b,：,=,f,(,c,1,c,2,c,k,),即属性变量：,=,这里,f,是一个函数，且对于产生式,A,，,(,1)b,或者是,A,的一个综合属性并且,c,1,c,2,，,c,k,是产生式右边文法符号的属性；,(2)b,或者是产生式右边某个文法符号的一个继承属性并且,c,1,c,2,，,c,k,是,A,或产生式右边任何文法符号的属性。,在两种情况下，我们都说属性,b,依赖于属性,c,1,c,2,，,c,k,。,继承属性的求值规则：,产生式左部非终结符号的继承属性值取前面产生式右部该符号已有的继承属性值；,产生式右部符号的继承属性值用该产生式左部符号的继承属性或出现在该符号左部的符号的属性值进行计算。,体现自顶向下，自左向右的求值特性,体现自底向上，自右向左的求值特性,综合属性的求值规则：,产生式右部非终结符号的综合属性值取其下面产生式左部同名非终结符号的综合属性值；,产生式左部非终结符号的综合属性值用该产生式左部符号的继承属性或某个右部符号的属性进行计算；,例,8.1,有文法,G,为：,ET,1,+T,2,|T,1,or T,2,Tnum|true|false,对输入串,3+4,的,类型检查的属性文法,如图,8.1,。,ET,1,+T,2,T,1,.t,int,AND,T,2,.t,int,ET,1,orT,2,T,1,.t,bool,AND T,2,.t,bool,Tnum T.t,int,Ttrue T.t,bool,Tfalse T.t,bool,图,8.1,类型检查的属性文法,属性文法记号中常使用,N.t,的形式表示与非终结符,N,相联的属性,t,。比如可把对上面表达式的类型检查的属性文法写成图,8.1,的形式。与每个非终结符,T,相联的有属性,t,，,t,要么是,int,，要么是,bool,。与非终结符,E,的产生式相联的语义规则指明：两个,T,的属性必须相同。,图,8.2,的（,b,）是图,8.2(a),语法树结点带有语义信息的表示。,图,8.2,静态语义审查,E,T,T,+,3,4,（,a,）,E,T,T,+,3,4,（,b,）,T,2,.,t=int,T,1,.,t=int,T,1,.,t=T,2,.,t,8.1.2,属性的确定,写属性文法，首先应确定对于每个文法符号都有哪些属性，然后给每个属性起个名字，接着确定每个属性的类别。,正确确定综合属性和继承属性是非常重要的，究竟哪些属性确定为综合属性，哪些属性确定为继承属性，并没有固定的模式。,非终结符（开始符号除外）既可有综合属性也可有继承属性,文法开始符号没有继承属性,终结符号只有综合属性，一般由词法分析器提供,例,8.2,简单算术表达式求值的语义描述。,产生式 语义规则,LE print(E.val),E E,1,+T E.,val,E,1,.val+T.val,ET E.val,T.val,T T,1,*F T.val,T,1,.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.,in,T.,type,（,2,）,Tint,T.Type,integer,（,3,）,Treal,T.Type,real,（,4,）,LL,1,，,id L,1,.in,L.in;,addtype,（,id.entry,，,L.in,）,（,5,）,Lid,addtype,（,id.entry,，,L.in,）,例,8.3,中的文法定义了一种说明语句，该说明语句的形式是由关键字,int,或,real,开头，后面是一个标识符表，每个标识符用逗号隔开。,非终结符,T,有一个综合属性,type,，它的值由关键字决定（,int,或,real,）。与产生式,DTL,相联的语义规则,L.in,T.type,将,L.in,的属性值置为该说明语句指定的类型。属性,L.in,将被沿着语法树传递到下边的结点使用，与,L,产生式相联的规则里使用了它。,这个例子里，继承属性在说明中为各个标识符提供类型信息。,图,8.4,是句子,int id,1,id,2,的语法树，使用,表示属性的传递情况。在语法树中，一个结点的继承属性由此结点的父结点和,/,或兄弟结点的某些属性确定。与,L,产生式相联的语义规则中有一个过程调用,addtype,，过程,addtype,的功能是把每个标识符的类型信息登录在符号表的相关项中。,图,8.4,属性信息传递情况,D,T,L,L,int,id,1,，,Id,2,产生式 语义规则,（,1,）,DTL,L.,in,T.,type,（,2,）,Tint,T.Type,integer,（,3,）,Treal,T.Type,real,（,4,）,LL,1,，,id L,1,.in,L.in;,addtype,（,id.entry,，,L.in,）,（,5,）,Lid,addtype,（,id.entry,，,L.in,）,8.1.3,属性计算规则的确定,一般说来，,对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性，这有助于在产生式范围内,“,封装,”,属性的依赖性。,然而，对出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计算器的参数提供。,属性文法看作是允许为每个终结符和非终结符配备一些属性的文法。它既能描述程序设计语言的语法，又为语义处理提供了方便。,属性文法里的属性有不同的类型，可以象变量一样地被赋值。赋值规则附加于语法规则之上。赋值与语法同时进行，赋值过程就是语义处理过程。,在推导建立语法树的时候，诸属性的值被计算并通过赋值规则层层传递。有的从语法规则左边向右边传，有的从右边向左边传。语法推导树最后完成时，就得到开始符号的属性值。也就是整个程序的语义。,8.2,中间代码（语言）,中间代码（语言）是一种特殊结构的语言，编译程序所使用的中间代码有多种形式。按其结构分常见的有逆波兰式（后缀式）、三地址代码（三元式、四元式）和树形表示（抽象语法树）、,DAG,表示。,8.2.1,逆波兰式（后缀式）,逆波兰式是最简单的一种中间代码表示形式，早在编译程序出现之前，它主要用于表示算术表达式，是波兰逻辑学家卢卡西维兹,(J.Lukasiewicz),于,1929,年发明的。后来人们为了纪念他，就把这种后缀表示取名为逆波兰式。,逆波兰式最早是用于表示表达式的,后来计算机科学家把它应用于表示程序语言的各种语法成分。,（一）特点,首先我们考察算术表达式（中缀式）的计值顺序,.,例,8.4,中缀式的计值顺序见图,8.5,。,中缀式计值三个特点：,（,1,）运算对象分别放在运算符（双目运算符）的两边；,（,2,）计值顺序是根据运算符的优先级别及结合性确定，使用括号可以改变计值顺序；,（,3,）运算符的排列顺序不等价于计值顺序。,图,8.5,中缀式的计值顺序例,a+b*(c+d*(e,f),a+b*(c+d*(e,f),（,1,）不考虑运算符的优先关系，又不使用括号；,（,2,）运算符的排列顺序就是计值顺序；,（,3,）运算对象放在运算符的前面。,这种表示称为逆波兰式，也称做后缀式。,如上例：,a,b,(c,d,(e,f),其逆波兰式为：,a b c d e f,这种后缀表示法虽然不符合人们的习惯，,但它极易被计算机来处理,。由于后缀式表示上的简洁和计值的方便，特别适用于具有,堆栈,体系的计算机的目标代码生成。,中缀式虽然是人们习惯的表示，但对于计算机来说，处理起来很不方便，如果我们采用一种表示方法：,(,二,),定义,逆波兰式（,后缀,式）的一般形式为：,若,是一个,K,元运算符（,K 1,），它对其运算对象,e,1,e,2,e,k,作用的结果被表示为：,e,1,e,2,e,k,表达式,E,的后缀表示的递归定义：,（,1,）如果,E,是变量或常数，那么,E,的后缀表示是,E,本身；,（,2,）如果,E,是形如,E,1,op E,2,的表达式，其中,op,是任意的二元运算符，那么,E,的后缀表示是,E,1,|E,2,|op,其中；,E,1,和,E,2,分别是,E,1,和,E,2,的后缀表示，,|,称为,连接,（并置）运算符；,（,3,）如果,E,是形如（,E,1,），那么,E,的后缀表示就是,E,1,的后缀表示。,（三）转换（中缀式,后缀式）,转换算法：,转换规则：设,E,为给定的中缀式，我们用,表示,E,的后缀式，则有：,|,；,；,a,其中,a,表示,变量或常数 。,对于给定的中缀式首先找出最后被计算的运算符，并把此运算符作为上述式中的,，使用上述规则转换之；,对,中缀式的剩余部分重复上述过程，直至中缀式的每个量均被处理到为止。,把一般表达式翻译为后缀式是很容易的。,表,8.1,把表达式翻译为后缀式的语义规则描述,产 生 式 语 义 规 则,E,E,1,op E,2,E.code=E1.code|E2.code|op,E,（,E,1,）,E.code=E1.code,E,id E,.,code,=id,表,8.1,给出了把表达式翻译为后缀式的语义规则描述，其中,E.code,表示,E,后缀形式，,op,表示任意二元操作符，“,|”,表示后缀形式的连接。,解：,E,T R,num,print(8),R,num,print(8),+T,print(+),R,1,num,print(8),+num,print(5)print(+),R,1,num,print(8),+num,print(5)print(+),T,print(),R,1,num,print(8),+num,print(5)print(+),num,print(2),print(),R,1,num,print(8),+num,print(5)print(+),num,print(2),print(),输出：,print(8)print(5)print(+)print(2)print(),即：,8 5+2,例,8.5,有下面翻译模式：,ETR,R,T print,（）,R1|,T print,（）,R1|,Tnum print,（,num.val,）,把中缀表达式,8+5,2,翻译成后缀表达式。,后缀式,很容易扩充到表达式以外的范围。只要遵守运算对象后直接紧跟它们的运算符的规则即可。,赋值语句的后缀表示：如有,a,b+c,，,则有,a b c+,转向语句,GOTO L,的后缀表示为,“,L jump,”,，,运算对象,L,为语句标号，运算符,jump,表示转到某个标号。,数组元素,A,下标表达式,1,，,，,下标表达式,n,的后缀表示可表示为：,下标表达式,1,下标表达式,2,下标表达式,nA subs,，运算符,Subs,表示求数组的下标。,当然，这些扩充的后缀表示的计值远比后缀表达式的计值复杂得多，要注意对扩展的运算符的含义正确处理。,条件语句,if E then S,1,else S,2,的后缀表示可表示为：,E S,1,S,2,￥,，,把,if-then-else,看成三目运算符，用￥来表示。,8.2.2,三地址代码,一般形式：,x,:=,y op z,如表达式,x,+,y,z,翻译成的三地址代码序列是,t,1,:=,y,z,t,2,:=,x,+,t,1,常用的三地址表示,:,赋值语句,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,:=,y,i,和,x,i,:=,y,地址和指针赋值,x,:=&,y,，,x,:=,y,和,x,:=,y,三地址代码有,四元式、三元式、间接三元式等形式,三地址代码可看成中间代码的一种抽象形式。,编译程序中，三地址代码语句的具体实现可以用记录表示，记录中包含表示运算符和操作数的域。,三地址代码通常有三种表示方法：四元式、三元式、间接三元式。,四元式结构形式,:,(OP,，,ARG1,，,ARG2,，,RESULT),算符,左运算对象,右运算对象,运算结果,三元式结构形式,:,编号,(OP,，,ARG1,，,ARG2),间接三元式：,由间接三元式序列和间接码表组成。,例,8.6,有中缀式,a:,b*,c,b*,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.7,有中缀式,A+B*(C-D)+E/(C-D)N,，求其等价的几种不同的三地址代码序列的形式。,四元式：,（,1,）（,C,D,T1,）,（,2,）（*,B,T1,T2,）,（,3,）（,+,A,T2,T3,）,（,4,）（,C,D,T4,）,（,5,）（,T4,N,T5,）,（,6,）（,/,E,T5,T6,）,（,7,）（,+T3,T6,T7,）,三元式：,（,1,）（,C,D,）,（,2,）（*,B,（,1,）,（,3,）（,+,A,（,2,）,（,4,）（,C,D,）,（,5,）（,（,4,）,N,）,（,6,）（,/,E,（,5,）,（,7,）（,+,（,3,）（,6,）,间接三元式：间接三元式序列,（,1,）（,C,D,）,（,2,）（*,B,（,1,）,（,3,）（,+,A,（,2,）,（,4,）（,（,1,）,N,）,（,5,）（,/,E,（,4,）,（,6,）（,+,（,3,）（,5,）,间接码表,（,1,）,（,2,）,（,3,）,（,1,）,（,4,）,（,5,）,（,6,）,间接码表表示了执行三元式的顺序。,图,8.7,几种不同的三地址代码序列,8.2.3,图形表示,抽象语法树是一种图形化的中间表示，它的每一个叶结点都表示诸如常量或变量这样的运算对象，而它的内部结点则表示运算符；它不同于前述的语法树，它展示了一个操作过程并同时描述了源程序的自然层次结构；,DAG,（有向无环图）以更紧凑的方式给出了同样的信息（即对于相同的语法成分只给出一次），在图中其结点的含义同抽象语法树。,assign,a,+,+,b,c,d,c,d,minus,(a),抽象语法树,assign,a,+,+,b,c,d,minus,(b)DAG,图,8.8 a:=(,b+c,d)+c,d,的图形表示,例：表达式,a:=(,b+c,d)+c,d,的两种图形表示见图,8.8,。,抽象语法树是分析树的浓缩表示,：,算符和关键字是作为内部结点出现的。,语法制导翻译可以基于分析树，也可以基于抽象语法树,if-then-else,B,S,1,S,2,+,*,2,5,8,图,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,:=,mknode,(,*,T,1,.,nptr,F,.,nptr,),T,T,1,*,F,E,.,nptr,:=,T,.,nptr,E,T,E,.,nptr,:=,mknode,(+,E,1,.,nptr,T,.,nptr,),E,E,1,+,T,语,义,规,则,产 生 式,图,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,id,id,num 5,*,+,指向符号表中,a,的入口,指向符号表中,b,的入口,图,8.11(a)a+5*b,的抽象语法树,E,.,nptr,T,.,nptr,E,.,nptr,T,.,nptr,F,.,nptr,id,T,.,nptr,+,*,F,.,nptr,F,.,nptr,id,num,id,id,num 5,*,+,指向符号表中,a,的入口,指向符号表中,b,的入口,图,8.11(b)a+5*b,的抽象语法树,T,.,nptr,E,.,nptr,T,.,nptr,E,.,nptr,F,.,nptr,id,T,.,nptr,+,*,F,.,nptr,F,.,nptr,id,num,id,id,num 5,*,+,指向符号表中,a,的入口,指向符号表中,b,的入口,图,8.11(c)a+5*b,的抽象语法树,E,.,nptr,T,.,nptr,F,.,nptr,E,.,nptr,T,.,nptr,id,T,.,nptr,+,*,F,.,nptr,F,.,nptr,id,num,id,id,num 5,*,+,指向符号表中,a,的入口,指向符号表中,b,的入口,图,8.11(d)a+5*b,的抽象语法树,T,.,nptr,E,.,nptr,T,.,nptr,E,.,nptr,F,.,nptr,id,T,.,nptr,+,*,F,.,nptr,F,.,nptr,id,num,id,id,num 5,*,+,指向符号表中,a,的入口,指向符号表中,b,的入口,图,8.11(e)a+5*b,的抽象语法树,指向符号表中,b,的入口,E,.,nptr,T,.,nptr,E,.,nptr,T,.,nptr,F,.,nptr,id,T,.,nptr,+,*,F,.,nptr,F,.,nptr,id,num,id,id,num 5,*,+,指向符号表中,a,的入口,图,8.11(f)a+5*b,的抽象语法树,E,.,nptr,T,.,nptr,E,.,nptr,T,.,nptr,F,.,nptr,id,T,.,nptr,+,*,F,.,nptr,F,.,nptr,id,num,id,id,num 5,*,+,指向符号表中,a,的入口,指向符号表中,b,的入口,图,8.11(g)a+5*b,的抽象语法树,E,.,nptr,T,.,nptr,E,.,nptr,T,.,nptr,F,.,nptr,id,T,.,nptr,+,*,F,.,nptr,F,.,nptr,id,num,id,id,num 5,*,+,指向符号表中,a,的入口,指向符号表中,b,的入口,图,8.11(h)a+5*b,的抽象语法树,E,.,nptr,T,.,nptr,E,.,nptr,T,.,nptr,F,.,nptr,id,T,.,nptr,+,*,F,.,nptr,F,.,nptr,id,num,id,id,num 5,*,+,指向符号表中,a,的入口,指向符号表中,b,的入口,图,8.11(i)a+5*b,的抽象语法树,8.3,语法制导翻译,编译程序的整个任务就是把源程序翻译为目标程序。,实际上可以把每个编译阶段都看作是完成一定翻译任务的处理过程：,词法分析阶段把字符流翻译为单词流，语法分析阶段把单词流翻译为语法树，语义分析和代码生成阶段把语法树翻译为汇编代码或者机器代码等等。,在语法分析过程中，随着分析的步步进展，每当进行推导或归约时，同步的去执行每个产生式所附带的语义规则描述的语义动作（或语义子程序），这样进行翻译的办法称作语法制导翻译。,语法制导翻译：,例,8.9,：把中缀算术表达式翻译为后缀表示形式，给出如下语义描述：,ET+E,1,E.code=T.code|E,1,.code|+,ET E.code=T.code,TF*T,1,T.code=F.code|T,1,.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+F,T,a|F.code|T.code|,|+,),(a+b,T,a|b|T.code|,|+,),(a+b,F,a|b|F.code|,|+,),(a+b*c,a|b|c|,|+,),去掉,a|b|c|,|+,中的连结符，得到中缀表达式,a+b,c,的后缀式,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,的分析树依赖图。,产 生 式,语,义,规,则,D,TL,L,.,in,:=,T,.,type,T,int,T,.,type,:=,integer,T,real,T,.,type,:=,real,L,L,1,id,L,1,.in,:=,L,.,in,;,addtype,(id.,entry,L,.,in,),L,id,addtype,(id.,entry,L,.,in,),表,8.2,说明语句的属性文法,表,8.2,说明语句的属性文法,图,8.12(a),int id1,id2,id3,的,注释分析树,产 生 式,语,义,规,则,D,TL,L,.,in,:=,T,.,type,T,int,T,.,type,:=,integer,T,real,T,.,type,:=,real,L,L,1,id,L,1,.in,:=,L,.,in,;,addtype,(id.,entry,L,.,in,),L,id,addtype,(id.,entry,L,.,in,),先构造,int id1,id2,id3,的语法树见图,8.12(a),所示。,再构造,int id1,id2,id3,的分析树的依赖图,(,结点用数字表示,),见图,8.12b,。,D,TL,L,.,in,:=,T,.,type,D,int,T,id,3,L,L,L,id,2,id,1,1,entry,10,2,entry,3,entry,in,9,8,in,7,6,in,5,4,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,。,一个依赖图的任何拓扑排序都给出了语法树中结点的语义规则计算的有效顺序。,根据例,8.10,的拓扑排序我们可得到下列语义规则计算顺序（其中,a,n,代表图中与序号,n,的结点有关的属性,),：,a,4,:=,integer,;,a,5,:=a,4,;,addtype(id,1,，,entry,，,a,5,);,a,7,:=a,5,;,addtype(id,2,，,entry,，,a,7,);,a,9,:=a,7,;,addtype(id,3,，,entry,，,a,9,);,通过这些语义规则的计算将把类型值,integer,填入到每个标识符对应的符号表项中去,也就是说，在拓扑排序中，在一个结点上，语义规则,b,:=,f,(,c,1,c,2,ck,),中属性,c,1,c,2,ck,在计算,b,之时是可用的。既,属性,b,依赖于属性,c,1,c,2,ck,。,2,）属性的计算过程,图,8.12(a)int id1,id2,id3,的语法树,D,int,T,id,3,L,L,L,id,2,id,1,属性计算有树遍历和一遍扫描两种方法。,树遍历：构造输入的语法树见图,8.12(a),，,2,）属性的计算过程,D,int,T,.,type,=,integer,id,3,L,.,in,=,integer,L,.,in,=,integer,L,.,in,=,integer,id,2,id,1,图,8.13,int id1,id2,id3,的注释分析树,构造带有属性分析树见图,8.13,。,属性计算有树遍历和一遍扫描两种方法。,树遍历：构造输入的语法树见图,8.12(a),，,用,深度优先遍历,该分析树。,还可以采用一遍扫描的处理方法来计算属性值。,一遍扫描的处理方法不同于树遍历的方法，它不需要构造实际语法树，而是在语法分析的同时计算属性值。,如果需要的话，可以进行多次遍历，直至计算出所有属性。,3,）树遍历的属性计算方法,现在我们来考虑如何通过树遍历的方法计算属性的值。,通过树遍历计算属性值的方法有多种。这些方法都假设语法树已经建立起了，并且树中已带有开始符号的继承属性和终结符的综合属性。,然后以某种次序遍历语法树，直至计算出所有属性。,最常用的遍历方法是深度优先遍历的方法。如果需要的话，可使用多次遍历（或称遍）。,下面算法可对任何无循环的属性文法进行计算。,While,还有未被计算的属性,do,VisitNode(S)/*S,是开始符号*,/,procedure VisitNode(NNode);,begin,if N,是一个非终结符,then,/*,假设它的产生式为,N X,1,Xm*/,for i:=1 to m do,if XiV,N,then,/*,即,Xi,是非终结符*,/,begin,计算,Xi,的所有能够计算的继承属性,;,VisitNode(Xi),End;,计算,N,的所有能够计算的综合属性,;,end,例,8.11,考虑表,8.3,所给的属性的文法,G,。,表,8.3,语义规则中有较复杂的依赖关系,产生式 语义规则,S,XYZ,Z.h=S.a,X.c=Z.g,S.b=X.d-2,Y.e=S.b,Xx X.d=2*X.c,Yy Y.f=Y.e*3,Zz Z,.,g,=Z,.,h+1,其中,S,有继承属性,a,，综合属性,b,；,X,有继承属性,c,、综合属性,d,；,Y,有继承属性,e,、综合属性,f,；,Z,有继承属性,h,、综合属性,g,。,假设文法开始符号的继承属性,S.a,的初始值为,0,，则输入串,xyz,的语法树如图,8.14,（,a,）所示。,S,.,a=0,X,Y,Z,x,y,z,(a),S,.,a=0,Z,.,h=0,g=1,X,Y,x,y,z,(b),Z,.,h=0,.,g=1,X,.,c=1,.,d=2,Y,x,y,z,(c),S,.,a=0,b=0,Z,.,h=0,.,g=1,X,.,c=1,.,d=2,Y,.,e=0,.,f=0,x,y,z,(d),S,.,a=0,b=0,图,8.14,对文法,G,的属性计算步骤,（,a,）初始状态；（,b,）对,VisitNode(S),的第一次调用后；,（,c,）对,VisitNode(S),第二次调用后；（,d,）最终状态,8.3.4,S-,属性文法和自下而上翻译,S-,属性文法：仅仅使用综合属性的属性文法。,1,）综合属性的求值规则：,产生式右部非终结符号的综合属性值取其下面产生式左部同名非终结符号的综合属性值；,产生式左部非终结符号的综合属性值用该产生式左部符号的继承属性或某个右部符号的属性进行计算；,体现自底向上，自,左向右,的求值特性,在语法树中，一个结点的综合属性的值由其子结点的属性值确定。而叶结点的（终结点）的综合属性值由词法分析得到。,因此，通常使用自底向上的方法在每个结点处执行语义规则计算综合属性的值。,S-,属性文法的翻译器通常可借助于,LR,分析器实现。,综合属性可以在分析输入串的同时自底向上的来计算。,分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右部符号的属性值来计算。,例,8.12,简单台式计算器的属性文法。,F.va,l:=digit,.lexval,F,digit,F.val,:=,E.val,F,(,E,),T.