单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章,语法制导翻译及中间代码生成,5.1,引言,词法分析,与,语法分析,仅仅是编译程序的一小部分。,在早期的一些编译程序中，是在语法分析的基础上根据源程序中各语法成份的语义，直接产生机器语言或汇编语言形式的,目标代码,。,现在的编译系统一般都将经过语法分析的源程序先翻译为某种形式的,中间语言代码,，然后再将其翻译为目标代码。,优点,：,使编译程序各组成部分,功能更单一,;,使得编译程序的,逻辑结构更为清晰,，从而,使编译程序更,易于编写与调整,;同时,为代码优化和程序的,可移植性,提供了条件,5.1,引言(续),本章要讨论的,中间代码生成,，是指把单词符号串形式的源程序转换为另一种等价的便于代码优化处理和目标代码生成表示。,目前常见的中间语言有,逆波兰表示,、,三元式,、,四元式,等等。,遗憾的是,，中间代码生成与语言的语义密切相关，而,语义的形式化描述,是一个非常困难的;,存在一种称为,语法制导翻译,的模式，这种模式实际上是对前后文无关文法的一种扩充。,方法,:,对文法中的每个产生式都附加一个语义动作或语义子程序,在语法分析过程中，每当需要使用一个产生式进行,推导,或,归约,，语法分析程序除执行相应的语法分析动作外，还要执行相应的语义动作或调用相应的语义子程序。,5.1,引言(续),这种模式既把,语法分析,与,语义处理,分开，又令其,平行地进行,，让其在同一遍扫描中同时完成语法分析和语义处理两项工作。,由此可见，抽象文法符号的具体语义信息，是,在,与语法分析同步的语义处理过程中获取和加工的,。,文法符号,X,的语义信息我们称之为,语义属性,或简称为,属性,（,Attributes,）。,我们用形如,X.ATTR,的记号来表示文法符号,X,的相关,语义属性,。,如果一个文法符号,X,在一产生式中多次出现，为了在语义上能够对其进行区分，可添加不同的上标。,文法符号及其语义属性,例如,文法,GE,:,产生式语义子程序,EE,(1),+TE.Val=E,(1),.val+T.val;,ETE.Val=T.Val;,TdigitT.Val=digit;,为了能在语法分析过程中平行地进行语义处理，可在语法分析栈旁边并行地设置一个,语义信息栈,语法分析栈,语义分析栈,T,T.Val,+,+,E,#,本章内容简介,本章，我们首先介绍一种适用于定义语义的一种特殊文法,属性文法,，并进一步介绍适用于语义翻译的文法,属性翻译文法,的相关知识。,在第三小节中我们将介绍几种常见的,中间语言,;,在第四小节中引入程序设计语言中常见语法结构的,语法制导翻译,技术。,5.2,属性文法,与,属性翻译文法,语法制导翻译方法,的实质，就是根据文法中每个产生式所蕴含的语义，为其配备一个（或多个）处理语句或子程序，对所要完成的功能进行描述。,语义子程序的,编写质量决定了语义翻译的准确性和有效性,。所以,产生式相应语义子程序的正确性是能够进行正确语义翻译的先决条件。,产生式的语义,是由组成该产生式的,文法符号的语义,所决定的。,我们可将这些语义以“,属性,”的形式附加到各个文法符号上，再根据产生式所蕴含的语义，给出每个文法符号的属性的,求值规则,，从而形成一种附带有,语义属性,的前后文无关文法，即,属性文法,。,5.2.1,语义属性与属性文法,定义 5.1,一,文法符号的,语义性质,称为该文法符号的,语义属性,（,Attributes,），简称为,属性,。我们用,A(X),表示,X,的所有属性的集合。每个属性表示,X,的一个特定性质，并可任意指定其取值范围。我们用,X.a,表示,A(X),中的属性,a,。,属性,可表征诸如数、符号串、类型、存储空间和其它需表征的实体。,终结符,至少有一种,属性,，即,词文,。当然，它还可能具有其它属性，例如无符号数,123,，单词“,123,”就是它的词文，而其数值以及它的类型（整型）是它的其它两个属性。,终结符的属性是其,内在性质,.,非终结符,的,属性,是从其它符号的,属性,经计算而得的，即由其它符号的,属性,定义的。,属性依赖关系,各个文法符号的,属性,之间，可能存在某种,依赖关系,，这种,依赖关系,可用属性规则（,语义规则,）定义。,定义 5.2,设,p:X,0,X,1,X,2,X,n,是文法,G,的一个产生式，则与,p,相关联的,属性规则集,R(p),=,X,i,.a,=f(,X,k1,.a,k1,X,km,.a,km,)|,X,i,.a,A(X,i,),定义了该产生式所涉及的文法符号之属性的,求值规则,，它表示：,X,i,的,a,属性是由的,X,k1,的,a,k1,属性，的,X,km,的,a,km,属性计算而得的。,综合属性,与,继承属性,定义,5.3,对每个产生式,p:X,0,X,1,X,2,X,n,，设属性定义性出现的集合为,AF(p),=,X,i,.a,|,X,i,.a,=f(,X,k1,.a,k1,X,km,.a,km,)R(p),0k,j,n,若,X,i,是产生式左部的非终结符(即,i=0,),则称属性,X,i,.a,是,综合属性,(,Synthesized Attributes,);若,X,i,出现在产生式的右部(即1in),则称,X,i,.a,是,继承属性,（,Inherited Attributes,）。,加注语法树,在语法树中,将每个结点均视为由若干个域组成的,结构,则可将其中的一些域用来存放相应文法符号诸属性之值，并可用,属性,来为这些域命名。通常我们将每个结点都标注相应属性值的语法树称为,加注语法树,（,Annotated Syntax Tree,）或,装饰树,（,Decor,a,ted Syntax Tree,书中有错!,）。,由,定义5.3,可知：在,加注语法树,中，一个文法符号,X,在相应结点的,综合属性,之值，由其子结点的属性和（或）X的其它属性，通过相关属性规则经计算而得，故,综合属性,的求值在语法树中是按,自下而上,的方式进行的；,X,的,继承属性,之值则由,X,的父结点和(或)其它兄弟结点来定义,故,继承属性,的求值将按,自上而下,的方式进行。,属性文法的定义,定义5.4,属性文法,AG,是一个四元组：,AG=(G,A,R,B),其中,G,是已简化的,CFG,;,A,=,XV,A(X),是属性的有限集合;,R,=,pP,R(p),是属性定义规则的有限集;,B,=,pP,B(p),是条件的有限集合，,B(p),用于描述使规则,R(p),有效的条件；,且同时满足：,（,1,）对,G,中任意两个不同的文法符号,X,和,Y,而言，属性集合,A(X),和,A(Y),不相交,A(X)A(Y)=,（,2,）在,G,的任意一个语法树中，对文法符号,X,的每一次出现，可用于计算,X,的每个属性之值的规则至多有一条。,属性文法(续),由,定义5.4,可知，,属性文法,实际上就是对前后文无关文法的一种拓广。,另外，每个产生式中的任一文法符号的,属性计算规则只能是唯一,的，且任一文法符号的,综合属性集,与,继承属性集,不相交,，即,AS(X)AI(X)=,其中：,AS(X),=,X.a,|,p:,X,P,X.a,AF(p),AI(X),=,X.a,|q:,YX,P,X.a,AF(q),例5.1,简单赋值语句文法的属性文法,属性文法中的一些限制,在属性文法中，由于每个非终结符号的属性都由若干文法符号的属性通过相应的属性规则来定义，所以，就不能排除某文法符号的属性由其自身定义的可能性。为避免这种情况的发生，我们需对属性文法作一定的限制。,定义5.5,对于,L(G),中每个句子所对应的语法树,T,，若其每个结点标记符号的所有属性之值均可有效地计算，则称相应属性文法,AG,是,良定义,的。此外，若所有条件,B(p),均取,true,值，则称,L(G),中的这个句子是,正确赋予属性的,（或称,T,是,可加注的,）。,从定义,5.5,可以看出，在良定义属性文法的任何语法树中，不会出现属性依赖于自身的现象。,属性依赖关系,定义5.6,对于每个产生式,p:X,0,X,1,X,2,X,n,P,直接属性依赖关系由下式给出：,DDP(p)=,(X,i,.a,X,j,.b),|,X,j,.b,=f(,X,i,.a,)R(p),若序偶,(X,i,.a,X,j,.b),DDP(p),，则称属性,X,j,.b,依赖于属性,X,i,.a,，记作,X,i,.aX,j,.b,。,显然，若有,X,i,.aX,j,.b,，则对,X,j,.b,的计值，应在求出,X,i,.a,的值之后进行。但若,X,i,.a,又直接或间接地依赖于,X,j,.b,则称属性,X,i,.a,和,X,j,.b,是,循环依赖,的。含有属性循环依赖的属性文法,AG,，其中的一些属性之值将不能得到有效的计算。,依赖关系图,定义5.7,设,T,是,L(G),中一个句子相应的加注语法树，并设在构造,T,时使用过产生式,p,:,X,0,X,1,X,2,X,n,，对于,T,中由,X,0,X,1,X,2,X,n,所标记的每个结点，若有,(X,i,.a,X,j,.b),DDP(p),则在树中引一条从到的有向边，由此而得到的树称之为该句子的属性化语法树。,所有这样的有向边构成的集合,DT(T),，,称为树,T,上的依赖关系。根据,DT,(,T),所构造的关系图称为,依赖关系图,（或简称为,依赖图,）。,例如，对于,例5.1,所给文法下的一个句子,x:=y+z,，相应属性化语法树的依赖关系如,P191,图,5-3,所示。,属性文法的良定义性判别,有了属性化的语法树及其依赖关系图，我们就可根据图中是否有回路来确定一属性文法是否是良定义的。,定理5.1,一个,属性文法,是,良定义,的，,当且仅当,对于它的每棵语法树,T,，相应的依赖关系图是一个,无回路有向图,（,directed acyclic graph,）。,从P191图5-3可以看出，该语法树相应的依赖关系,DT(T),未出现回路，通过对其文法的验证，可知该,属性文法,是,良定义,的。,为便于设计编译程序，实际工作中我们只处理良定义的属性文法。至于有关良定义文法的判定算法，读者可参阅文献,18,。,5.2.2,属性翻译文法,由于属性文法的抽象性和属性定义的任意性，当我们把它用于进行语义翻译时，就会发现仅有属性文法是不够的，,须在属性文法的基础上做进一步的工作,。,首先，我们应对文法的属性依赖关系作出限制，不允许出现属性的直接或间接的循环定义，即,要求属性文法是良定义的,。,其次，我们还应将属性规则改造为计算属性值的语义程序，,即将静态的规则改写为可动态执行的语义动作,。经过这样的改造后，我们就可得到一种新的文法,属性翻译文法,。,翻译文法的定义,定义5.8,在文法产生式右部适当的位置上插入,语义动作,而得的新文法称为,翻译文法,或,增广文法,(,Augmented Grammar,),。在一,翻译文法,中，若每个产生式右部中的全部,语义动作,均出现在所有文法符号的右边，则称这样的,翻译文法,为,波兰翻译文法,。,为了区分文法符号与语义动作，在本书中我们用一对花括号,及,将插入的语义动作括起来（语义动作采用C语言格式书写）。而且，我们还把语义动作视为翻译文法中的一个“,符号,”，称为,动作符号,。插入语义动作后，翻译文法产生式的一般形式为：A(,statement,;),*,V,*,翻译文法（续）,翻译文法的作用是，在进行语法分析时，无论是用产生式进行推导还是进行归约，只要遇到其中带有语义动作的花括号，就要求编译系统,自动执行花括号内指定的语义动作,，在执行完该动作之后才继续进行下一步的语法分析。,例：,Expr,Term Expr,Expr,+,Term,WriteCode(“+”);,Expr,|,TermFactor Term,Term,*,Factor,WriteCode(“*”);,Term,|,Factoroperand,Writ