资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,武汉理工大学计算机科学系陈天煌,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,是该产生式文法符号的属性。,属性文法中的属性分成两类:继承属性和综合属性。,简单地说,综合属性用,自下而上,传递信息,而继承属性用于,自上而下,传递信息。,综合属性(,synthesized attribute,):,如果,b,是,A,的属性,,c,1,c,2,c,k,是产生式右部文法符号的属性或,A,的其它属性,则称,b,是,文法符号,A,的综合属性。,继承属性,(inherited attribute),:,如果,b,是产生式右部某个文法符号,X,的属性,并且,c,1,c,2,c,k,是,A,或产生式右部文法符号的属性,则称,b,是文法符号,X,的继承属性。,每个文法产生式,A,有一组形式为,b,:=,f,(,c,1,c,2,c,k,),的语义规则,其中,f,是函数,,b,和,c,1,c,2,c,k,是该产生式文法符号的属性,属性文法的主要思想是:,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,属性的确定,写属性文法,首先应确定对于每个文法符号都有哪些属性,然后给每个属性起个名字,接着确定每个属性的类别。,要特别强调的是:,(,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,产生式相联的规则里使用了它。,这个例子里,继承属性,L.in,在说明中为各个标识符提供类型信息。,图,8.4,是句子,int,id,1,id,2,的语法树,使用,表示属性的传递情况。在语法树中,一个结点的继承属性由此结点的父结点和,/,或兄弟结点的某些属性确定。与,L,产生式相联的语义规则中有一个过程调用,addtype,,,过程,addtype,的功能是把每个标识符的类型信息登录在符号表的相关项中。,图,8.4,属性信息传递情况,D,T,L,L,int,id,1,,,Id,2,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.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(c,1,,,c,2,,,,,c,k,)do,for i:=1 to k do,从,c,i,结点到,b,结点构造一条有向边;,注,:,在构造依赖图之前,要为每一个过程调用的语义规则引入一个虚综合属性,即在依赖图中构造一个结点。这样,,若属性,b,依赖于属性,c,,,则从,c,的结点有一条有向边连接到,b,的结点,。,例,8.10,:有属性文法见表,8.2,,构造,int,id,1,id,2,id,3,的分析树依赖图。,产 生 式,语,义,规,则,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,id,1,id,2,id,3,的,注释分析树,产 生 式,语,义,规,则,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,id,1,id,2,id,3,的语法树见图,8.12(a),所示。,再构造,int,id,1,id,2,id,3,的分析树的依赖图,(,结点用数字表示,),见图,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,id,1,id,2,id,3,的依赖图,8.3.3,语义规则的计算次序,1,)拓扑排序,从依赖图的拓扑排序中我们可以得到计算语义规则的次序,用这个顺序来计算语义规则就得到了输入串的翻译。,拓扑排序:结点的一种排序,使得有向边只会从该次序中先出现的结点指向后出现的结点。,例:图,8.12(b),的拓扑排序为:,1,,,2,,,3,,,4,,,5,,,6,,,7,,,8,,,9,,,10,。,一个依赖图的任何拓扑排序都给出了语法树中结点的语义规则计算的有效顺序。,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,)树遍历的属性计算方法,现在我们来考虑如何通过树遍历的方法计算属性的值。,通过树遍历计算属性值的方法有多种。这些方法都假设语法树已经建立起了,并且树中已带有开始符号的继承属性和终结符的综合属性。,然后以某种次序遍历语法树,直至计算出所有属性。,最常用的遍历方法是深度优先遍历的方法。如果需要的话,可使用多次遍历(或称遍)。,8.3.4,S-,属性文法和自下而上翻译,S-,属性文法:仅仅使用综合属性的属性文法。,1,)综合属性的求值规则:,产生式右部非终结符号的综合属性值取其下面产生式左部同名非终结符号的综合属性值;,产生式左部非终结符号的综合属性值用该产生式左部符号的继承属性或某个右部符号的属性进行计算;,体现自底向上,自,左向右,的求值特性,在语法树中,一个结点的综合属性的值由其子结点的属性值确定。而叶结点的(终结点)的综合属性值由词法分析得到。,因此,通常使用自底向上的方法在每个结点处执行语义规则计算综合属性的值。,S-,属性文法的翻译器通常可借助于,LR,分析器实现。,综合属性可以在分析输入串的同时自底向上的来计算。,分析器可以保存与栈中文法符号有关的综合属性值,每当进行归约时,新的属性值就由栈中正在归约的产生式右部符号的属性值来计算。,例,8.12,简单台式计算器的属性文法。,F.va,l,:=,digit,.lexval,F,digit,F.val,:=,E.val,F,(,E,),T.val,:=,F.val,T,F,T.val,:=,T,1,.,val,*,F.val,T,T,1,*,F,E,.,val,:=,T.val,E,T,E,.,val,:=,E,1,.,val,+,T.val,E,E,1,+,T,print,(,E,.,val,),L,E,n,语,义,规,则,产,生,式,表,8.4,简单台式计算器的属性文法,8+5*2 n,的注释分析树见图,8.15,。,图,8.15 8+5*2 n,的注释分析树,digit.,lexval,=2,L,E,.,val,=18,n,T,.,val,=10,E,.,val,=8,T,.,val,=8,F,.,val,=8,digit.,lexval,=8,T,.,val,=5,+,*,F,.,val,=5,F,.,val,=2,digit.,lexval,=5,2,),考察,S,属性的自下而上计算过程:,将,LR,分析器符号栈中增加一个域来保存综合属性值。,.,.,X,.,x,X,Y,.,y,Y,Z,.,z,Z,.,.,栈,state,val,top,若产生式,A,XYZ,的语义规则是,A,.,a,:=,f,(,X,.,x,Y,.,y,Z,.,z,),那么归约后有:,.,.,A,.,a,A,.,.,top,图,8.16 LR,分析器符号栈属性域示意图,例,8.13,把台式计算器的语法制导定义改成栈操作代码如图,8.17,。,F.va,l,:=,digit,.lexval,F,digit,F.val,:=,E.val,F,(,E,),T.val,:=,F.val,T,F,T.val,:=,T,1,.,val,*,F.val,T,T,1,*,F,E,.,val,:=,T.val,E,T,E,.,val,:=,E,1,.,val,+,T.val,E,E,1,+,T,print,(,E,.,val,),L,E,n,代 码 段,产,生,式,.,.,X,.,x,X,Y,.,y,Y,Z,.,z,Z,.,.,栈,state,val,top,n,图,8.17(a),语法制导定义改成栈操作代码,示意图,例,8.13,把台式计算器的语法制导定义改成栈操作代码如图,8.17,。,F.va,l,:=,digit,.lexval,F,digit,F.val,:=,E.val,F,(,E,),T.val,:=,F.val,T,F,T.val,:=,T,1,.,val,*,F.val,T,T,1,*,F,E,.,val,:=,T.val,E,T,E,.,val,:=,E,1,.,val,+,T.val,E,E,1,+,T,print,(,val,top,1,),L,E,n,代 码 段,产,生,式,.,.,X,.,x,X,Y,.,y,Y,Z,.,z,Z,.,.,栈,state,val,top,n,图,8.17(b),语法制导定义改成栈操作代码,示意图,例,8.13,把台式计算器的语法制导定义改成栈操作代码如图,8.17,。,F.va,l,:=,digit,.lexval,F,digit,F.val,:=,E.val,F,(,E,),T.val,:=,F.val,T,F,T.v
展开阅读全文