单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,6,章 属性文法和语法制导翻译,一、基本概念,1.,编译系统的两类翻译：,非语法制导的翻译,语法制导的翻译：以语法分析为主导的语义处理在源程序的语法分析中嵌入语义处理即，利用源程序的文法框架生成中间代码或目标代码Tips,：语义学：,semantics,lexeme,lexicon,semantic,例,（,1,）递归子程序法的代码生成,（,2,）利用优先矩阵的语法分析直接生成目标代码,（,3,）利用逆波兰算法进行语法、语义分析,（,1,）,语法分析语义分析,：,直接生成目标代码,优点：编译相对简单，时间效率高,缺点：空间代价较高,（,2,）语法分析中间代码优化目标代码,二、两种编译流程,从本章开始，我们介绍有关语义分析及翻译的问题其处理的方法主要是属性文法和语法制导翻译方法本章中，我们将首先介绍属性文法的基本概念，然后介绍基于属性文法的处理方法，讨论如何自上而下分析和自下而上分析中实现属性计算本章重点掌握,:,6.1,属性文法,6.2,基于属性文法的处理方法,6.3,S,属性文法的自下而上计算,6.4,L,属,性文法和自顶向下翻译,。
6.1,属性文法,属性文法是在上下文无关文法的基础上为每个文法符号（终结符或非终结符）配备若干个相关的“值”（称为,属性,）这些属性代表与文法符号相关的信息，例如它的类型、值、代码序列,、符号表内容等等属性和变量一样，可以进行计算和传递属性一般分为两类：,综合属性,和,继承属性,简单的说，综合属性用于“自下而上”传递信息，而继承属性用于“自上而下”传递信息属性加工的过程即是语义处理的过程，对于文法的每一个产生式都配备了一组属性的计算规则，则称为语义规则在一个属性文法中，对应于每个产生式,A,都有一套与之相关联的语义规则，每条语义规则的形式为：,b:=f(c1,c2,ck),这里,f,是一个函数，而且或者 （,1,）,b,是,A,的一个综合属性并且,c1,c2,ck,是产生式右边文法符号的属性；或者 （,2,）,b,是产生式右边某个文法符号的一个继承属性并且,c1,c2,ck,是,A,或产生式右边任何文法符号的属性 在这两种情况下，我们都说属性,b,依赖于属性,c1,c2,ck.,要特别强掉的是：（,1,）终结符只有综合属性，它由词法分析器提供；（,2,）非终结符既可以有综合属性也可以有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。
一般来讲，对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则，属性计算规则中只能使用相应产生式的文法符号的属性，这有利于产生式范围内“封装”属性的依赖性然而，出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算,由属性计算器的参数提供,语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码生成等语义规则可能产生副作用（如产生代码），也可能不是变元的严格函数（如某个规则给出可用的下一个数据单元的地址）这样的语义规则通常写成过程调用，或过程段综合属性,：,在语法树中，一个结点的综合属性的值由其子结点的属性值确定因此，通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值仅仅使用综合属性的属性文法,称,S,属性文法继承属性,：,在语法树中，一个结点的继承属性由此结点的父结点和,/,或兄弟结点的某些属性确定用继承属性来表示程序语言结构中的上下文依赖关系很方便6.2,基于属性文法的处理方法,从概念上讲，基于属性文法的处理过程通常是这样的：对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树，并在语法树的各结点处按语义规则进行计算。
输入串,语法树依赖图语义规则计算次序,这种由源程序的语法结构所驱动的处理办法就是,语法制导翻译法,语义规则的计算可能产生代码、在符号表中存放信息、给出错误信息或执行任何其它动作对输入串的翻译也就是根据语义规则进行计算得出结果6.2.1,依赖图,如果在一棵语法树中一个结点的属性,b,依赖于属性,c,，,那么这个结点处计算,b,的属性规则必须在确定,c,的语义规则之后使用在一颗语法树中的结点的继承属性和综合属性之间的相互依赖关系可以用称作依赖图的一个有向图来描述在为一棵语法树构造依赖图以前，我们为每一个包含过程调用的语义规则引入一个虚综合属性,b,，,这样把每一个语义规则都写成,b:=f(c,1,c,2,c,k,),的形式依赖图中为每一个属性设置一个结点，如果属性,b,依赖属性,c,，,则从属性,c,的结点有一条有向边连到属性,b,的结点这里要掌握,依赖图,的画法例如，属性,A.a:=f(X.x,Y.y),对应于产生式,A,XY,的语义规则,这条语义规则确定了依赖于属性,X.x,和,Y.y,的综合属性,A.a,如果在语法树中应用这个产生式，那么在依赖图中会有三个结点,A.a,X.x,和,Y.y,。
由于,A.a,依赖,X.x,，,所以有一条有向边,从,X.x,到,A.a.,由于,A.a,也依赖于,Y.y,，,所以还有一条有向边从,Y.y,连到,A.a.,如果与产生式,AXY,对应的语义规则还有：,X.i:=g(A.a,Y.y),那么，图中还应有两条有向边，一条从,A.a,连到,X.i,，,另一条从,Y.y,连到,X.i,因为,X.i,依赖于,A.a,和,Y.y.,例,6.3,当下面的产生式应用于语法树时，我们就像图,6.4,所示的那样把有向边加到依赖图中产生式 语义规则,E,E1+E2,E.val,:=E1.val+E2.val,例,6.4,下页的图是书中图,6.2,（,P139,）,带注释语法树的依赖图依赖图中的结点由数字来标识，这些数字将在讨论属性的计算次序时用到从代表,T.type,的结点,4,有一条边连到代表,L.in,的结点,5,，因为根据产生式,D,TL,的语义规则,L1.in=L.in,可知,L1.in,依赖于,L.in,所以有两条向下的边分别进入结点,7,和,9,每一个于,L,产生式有关的语义规则,addtype(id.entry,L.in,),都产生一个虚属性，结点,6,、,8,和,10,都为这些虚属性构造的。
如果一属性文法不存在属性之间的循环依赖关系，那么该文法为,良定义的,为了设计编译程序，我们只处理良定义的属性文法属性的计算次序,一个有向非循环图的拓扑序是图中结点的任何顺序,m1,m2,mk,使得边必须是从序列中前面的结点指向后面的结点也就是说，如果,mi,mj,是,mi,到,mj,的一条边，那么在序列,中,mi,必须出现在,mj,之前一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序这就是说，在拓扑排序中，在一个结点上，语义规则,b:=f,（,c1,c2,ck),中的属性,c1,c2ck,在计算,b,以前都是可用的6.2.2,树遍历的属性计算方法,通过树遍历计算属性值得方法很多种这些方法都假设语法树已经建立起了，并且树中已带有开始符号的继承属性和终结符的综合属性然后以某种次序遍历语法树，直至计算出所有的属性最常用的遍历方法是深度优先，从左到右的遍历方法6.2.3,一,遍扫描的处理方法,与树遍历的属性计算方法不同，一遍扫描的方法是在语法分析的同时计算属性值如果按这种一遍扫描的编译程序模型来理解语法制导翻译方法的话，所谓语法制导翻译法，直观上说是为文法中每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则,.,在自上而下的语义分析中,若一个产生式匹配输入串成功,或者在自下而上分析中,当一个产生式被用于进行归约时,此产生式相应的语义规则就被计算,完成有关语义分析和代码生成的工作,.,6.2.4,抽象语法树,建立表达式的抽象语法树,我们通过为每个运算分量或运算符号都建立一个结点来为子表达式建立子树,.,运算符号结点的各子结点分别是表示该运算符号的各个运算分量的子表达式组成的子树的根,.,抽象语法树中的每一个结点可以由包含几个域的记录来实现的,.,在一个运算符号对应的结点中,一个域标识运算符号，其它域包含指向运算分量的结点的指针。
运算符号通常叫做这个结点的标号当我们进行翻译时，抽象语法树中的结点可能会用附加域来存放结点的属性值,(,或指向属性的指针）6.3 S,属,性文法的自下而上计算,这一节我们考虑这样一类属性文法：,S,属性文法，它只含有综合属性下面我们讨论分析栈中的综合属性在自底向上的分析法中我们使用一个栈来存放已经分析过的子树的信息现在我们可以在分析栈中使用一个附域来存放综合属性值图,6.9,表示的是一个带有一个属性值空间的分析栈的例子State,val,X X.x,Y Y.y,Z Z.z,图,6.9,top,我们假设图中的栈是由一对数组,state,和,val,来实现的每一个,state,元素都是一个指向,LR(1),分析表的指针（或索引）注意，文法符号隐含在,state,中而不需要存储在栈中）然而，如果像第五章中的那样把文法符号存入栈中时，那么当第,i,个,state,对应的符号为,A,时，,vali,中就存放语法树中与结点,A,对应的属性值,设当栈顶由指针,top,指示我们假设综合属性是刚好在每次归约前计算的假设语义规则,A.a:=f(X.x,Y.y,Z.z),是对应于产生,式,A,XYZ,的在把,XYZ,归约成,A,以前，属性,Z.z,的值放在,valtop,中，,Y.y,的值放在,valtop-1,中，,X.x,的值放在,valtop-2,中。
如果一个符号没有综合属性，那么数组,val,中相应的元素就不定义归约,后，,top,值减,2,，,A,的状态存放在,statetop,中（也就是,X,的位置）综合属性,A.a,的值存放在,valtop,中6.4 L,属,性文法和自顶向下翻译,一个属性文法称为,L,属性文法,：如果对于每个产生式,AX1X2,Xn,其每个语义规则中的每个属性或者是综合属性，或者是,Xj(1=j=n),的一个继承属性且这个继承属性仅依赖于：,（,1,）,产生式,Xj,的左边符号,X1,X2,Xj-1,的属性,（,2,）,A,的继承属性6.4.1,翻译模式,属性文法可以看成是关于语言翻译的高级规范说明，其中隐去实现细节，使用户从明确说明翻译顺序的工作中解脱出来下面我们讨论一种适合语法制导翻译的另一种描述形式，称为,翻译模式,翻译模式给出了使用语义规则进行计算的次序，这样就可以把某些实现细节表示出来在翻译模式中，和文法符号相关的属性和语义规则（这里我们也称语义动作），用花括号,括起来，插入到产生式右部的合适位置上这样翻译模式给出了使用语义规则进行计算的顺序如果既有综合属性又有继承属性，在建立翻译模式时就必须特别小心：,（,1,）产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。
2,）一个动作不能引用这个动作右边符号的综合属性3,）产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来后才能计算计算这种属性的动作通常可放在产生式右端的末尾6.4.2,自顶向下翻译,在第四章我们知道，为了构造不带回溯的自顶向下语法分析，必须消除文法中的左递归现在我们把前面消除左递归的方法加以扩充,当消除一个翻译模式的基本语法的左递归时同时考虑属性这种方法适合带综合属性的翻译模式这样许多文法可以使用自顶向下分析来实现对于自顶向下的分析，我们假设动作是在处于相同位置上的符号被展开（匹配成功）时执行的一个符号的继承属性必须由出现这个符号之前的动作来计算，产生式左边非终结符的综合属性必须在它的所依赖的所有属性都计算出来之后才能被计算下面我们把转换左递规翻译模式的方法推广到一般，以便进行自顶向下分析：,。