第6讲--属性文法课件

《第6讲--属性文法课件》由会员分享，可在线阅读，更多相关《第6讲--属性文法课件（62页珍藏版）》请在金锄头文库上搜索。

1、第六讲 属性文法和语法制导翻译,属性文法 基于属性文法的处理 属性的计算 S属性文法的自下而上计算 L属性文法的自上而下计算,2,1. 属性文法,属性文法是在上下文无关文法的基础上为每个文法符号（终结符或非终结符）配备若干个相关的“值”（称为属性）。这些属性代表与文法符号相关的信息，例如它的类型、值、代码序列、符号表内容等等。属性和变量一样，可以进行计算和传递。 属性一般分为两类： 综合属性：用于“自下而上”传递信息， 继承属性：用于“自上而下”传递信息。 属性加工的过程即是语义处理的过程，对于文法的每一个产生式都配备了一组属性的计算规则，称为语义规则。,3,属性的类型,综合属性： 在语法树中

2、，一个结点的综合属性的值由其子结点的属性值确定。通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。仅仅使用综合属性的属性文法称S-属性文法。 继承属性： 在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。可用继承属性来表示程序语言结构中的上下文依赖关系。,4,注意： （1）终结符只有综合属性，由词法分析器提供； （2）非终结符既可以有综合属性也可以有继承属性。文法开始符号的所有继承属性作为属性计算前的初始值。,出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。一般地，属性计算规则中只能使用相应产生式的文法符号的属性，这有利于

3、产生式范围内“封装”属性的依赖性。 出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或由属性计算器的参数提供。,5,在一个属性文法中，对应于每个产生式A都有一套与之相关联的语义规则，每条语义规则的形式为： b:=f(c1,c2,ck) 其中f是一个函数，并且满足下面两种情况之一： （1）b是A的一个综合属性并且c1,c2,ck是产生式右边文法符号的属性； （2）b是产生式右边某个文法符号的一个继承属性并且c1,c2,ck是A或产生式右边任何文法符号的属性。 对这两种情况都称为属性b依赖于属性c1,c2, , ck。,6

4、,语义规则,描述属性计算、静态语义检查、符号表操作、代码生成等。语义规则可能产生副作用（如产生代码），也可能不是变元的严格函数（即函数中还有其它没有列出的自变量如变量地址等），比如说某个规则可能给出可用的下一个数据单元的地址。这样的语义规则通常写成过程调用或过程段。,7,下表是一个台式计算器程序的属性文法。该计算器读入一个算术表达式，计算并打印它的值，每个输入行以n作为结束。 在这些语义规则中，一个整数综合属性val把每个非终结符E,T,F联系起来。记号digit具有综合属性lexval，其值由词法分析器提供。,8,句子3*5+4n的带注释的语法树,这是个带综合属性文法的例子，下面再来看一个继

5、承属性的例子。,9,变量声明语句中，通过继承属性把类型信息传递给每个标识符。,问题：给出句子real a,b,c 的带注释的语法树？,10,11,2. 基于属性文法的处理方法,对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树，并在语法树的各结点处按语义规则进行计算。 输入串语法树依赖图按次序计算语义规则 这种由源程序的语法结构所驱动的处理办法就是语法制导翻译。 语义规则的计算可能产生代码、在符号表中存放信息、给出错误信息或执行任何其它动作。,对输入串的翻译=根据语义规则进行计算得出结果,12,依赖图,语法树中结点属性之间的相互依赖关系用依赖图描述 为每一个包含过程调用的语义规则

6、引入一个虚综合属性b，这样把每一个语义规则都写成 b:= f(c1,c2, ck) 的形式。 依赖图是一个有向图，为每一个属性设置一个结点：如果属性b依赖属性c，则从属性c的结点有一条有向边连到属性b的结点。,13,依赖图的画法,例：属性 A.a:=f( X.x, Y.y ) 对应于产生式 AXY 的语义规则。 在依赖图中有三个相关结点： A.a,X.x,Y.y。 由于A.a依赖于X.x， Y.y，所以有两条有向边从X.x到A.a，从Y.y连到A.a. 如果与产生式AXY对应的语义规则还有： X.i:=g(A.a,Y.y) 图中再增加两条有向边：从A.a连到X.i，从Y.y连到X.i,因为X.

7、i依赖于A.a和Y.y.,14,例依赖图,当下面的产生式应用于语法树时，我们就像下图所示的那样把有向边加到依赖图中。 产生式 语义规则 EE1+E2 E.val:=E1.val+E2.val,15,例依赖图,因为产生式DTL的语义规则L.in=T.type ,从代表T.type的结点4有一条边连到代表L.in的结点5； 因为产生式LL1,id有语义规则L1.in=L.in,可知L1.in依赖于L.in,所以有两条向下的边分别进入结点7 和9。,每一个与L产生式有关的语义规则addtype(id.entry,L.in)都产生一个虚属性，结点6、8和10都是为这些虚属性构造的。,16,良定义文法和

8、属性的计算次序,定义：属性之间不存在循环依赖关系的属性文法。 一个有向非循环图的拓扑序是图中结点的任何顺序m1,m2, mk,使得边必须是从序列中前面的结点指向后面的结点。也就是说，如果mimj是mi到mj的一条边，那么在序列中mi必须出现在mj之前。 一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序。 属性文法说明的翻译是很精确的：基础文法用于构造输入符号串的语法分析树，在此基础之上可以建立依赖图。按照图的某一种拓扑排序，就可以根据语义规则进行翻译。,17,树遍历的属性计算方法,以某种次序遍历语法树，直至计算出所有的属性。最常用的遍历方法是深度优先，从左到右的遍历方法。

9、这种方法最简单，适应面最广。（算法略） 缺点： 必须在语法树建立之后才能使用 效率不高,对每个非终结符号： 多次重复计算所有能够计算的继承属性 最后计算所有能够计算的综合属性,18,一遍扫描的处理方法,在语法分析的同时计算属性值，因而无需构造实际的语法树。 语法制导翻译法就是为文法中每个产生式配上一组语义规则，并且，在语法分析的同时执行这些语义规则。,计算语义规则，完成有关语义分析和代码生成动作的时机： 自上而下分析中一个产生式匹配输入串成功时； 自下而上分析中一个产生式被用于进行归约时。,19,抽象语法树,在语法分析期间完成翻译工作可大幅提高编译的时空效率，但也存在一些问题： 适合于语法分析

10、的文法可能并不反映语言成分的自然层次结构； 特定的语法分析方法也可能限制了语法分析树的节点考察顺序 因此，现代编译器通用的做法是：通过语法分析构造语法树，再对语法树进行遍历完成属性的计算。也就是使用中间表示(Intermediate Representation)把翻译从语法分析中分离出来。 这样做可以使编译器更好地模块化，也方便了移植和优化。,20,为每个运算分量或运算符号都建立一个结点来为子表达式建立子树。运算符号结点的各子结点分别是表示该运算符号的各个运算分量的子表达式组成的子树的根。,抽象语法树中的每一个结点可以由包含几个域的记录来实现。 在一个运算符号对应的结点中,一个域标识运算符号

11、,其它域包含指向运算分量的结点的指针。 通常，运算符号叫做这个结点的标号。进行翻译时，抽象语法树中的结点可能会用附加域来存放结点的属性值(或指向属性的指针）。,表达式3*5+4 的抽象语法树,抽象语法树(AST)：语法分析树的压缩形式。 叶子结点：终结符的综合属性、文法开始符号的继承属性,以下以表达式为例，说明如何构造AST。,21,综合属性nptr表示函数调用返回的指针。,22,a+5*b的语法树的构造,23,a+5*b的语法树的构造,24,a+5*b的语法树的构造,25,a+5*b的语法树的构造,26,a+5*b的语法树的构造,27,a+5*b的语法树的构造,28,a+5*b的语法树的构造

12、,29,a+5*b的语法树的构造,30,a+5*b的语法树的构造,31,3. S-属性文法的自下而上计算,S-属性文法：只含有综合属性的属性文法。 在自底向上的分析法如LR分析法中，我们使用一个栈来存放已经分析过的子树的信息，现在可以在分析栈中使用一个附加的域来存放综合属性值。,如果一个属性文法是S-属性文法，那么在计算每个语义规则时，分析栈中栈顶处正好就是计算语义规则时需要用到的其它属性值。,32,假设图中的栈是由一对数组state和val来实现的。每一个state元素都是一个指向LR(1)分析表的指针（或索引）。（注意，文法符号隐含在state中而不需要存储在栈中）。然而，如果像前面LR分

13、析时的那样把文法符号存入栈中时，那么当第i个state对应的符号为A时，vali中就存放语法树中与结点A对应的属性值。 设当前栈顶由指针top指示。我们假设综合属性是刚好在每次归约前计算的。假设语义规则A.a:=f(X.x,Y.y,Z.z)是对应于产生式AXYZ的。在把XYZ归约成A以前，属性Z.z的值放在valtop中，Y.y的值放在valtop-1中，X.x的值放在valtop-2中。如果一个符号没有综合属性，那么数组val中相应的元素就不定义。归约后，top值减2，A的状态存放在statetop中（也就是X的位置）综合属性A.a的值存放在valtop中。,State val X X.x

14、Y Y.y Z栈顶Z.z ,val X.x Y.y 栈顶Z.z ,简化为,33,边分析边翻译的方式能否用于继承属性？ 属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制 分析树的结点是自左向右生成 如果属性信息是自左向右流动，那么就有可能在分析的同时完成属性计算,34,4. L-属性文法和自顶向下翻译,L-属性文法：如果对于每个产生式AX1X2Xn的每个语义规则中，每个属性或者是综合属性，或者是Xj(1=j=n)的一个继承属性且这个继承属性仅依赖于： （1）产生式Xj的左边符号X1,X2,Xj-1的属性 （2）A的继承属性。 L-属性文法也就是“左属性”文法，计算每一个继承属性时不能

15、引用右边符号的属性(继承属性和综合属性)。由此定义可知，S属性文法一定是L属性文法。,35,翻译模式,属性文法可以看成是关于语言翻译的高级规范说明，其中隐去实现细节，使用户从明确说明翻译顺序的工作中解脱出来。下面我们讨论一种适合语法制导翻译的另一种描述形式，称为翻译模式。翻译模式给出了使用语义规则进行计算的次序，这样就可以把某些实现细节表示出来。在翻译模式中，和文法符号相关的属性和语义规则（这里我们也称语义动作），用花括号 括起来，插入到产生式右部的合适位置上。这样翻译模式给出了使用语义规则进行计算的顺序。,36,对继承属性出现位置的限制,为了计算出继承属性，翻译模式必须满足三个条件： （1）

16、产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。 （2）一个动作不能引用这个动作右边符号的综合属性。 （3）产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来后才能计算。计算这种属性的动作通常可放在产生式右端的末尾。,37,不满足条件的例子,SA1A2 A1.in := 1; A2.in := 2; A a print(A.in) 应该改为： S A1.in := 1; A1 A2.in := 2; A2 A a print(A.in) 通常写成： S A1.in := 1; A1 A2.in := 2; A2 A a print(A.in) ,38,自顶向下翻译,在第四讲我们知道，为了构造不带回溯的自顶向下语法分析，必须消除文法中的左递归。现在我们把前面消除左递归的方法加以扩充,当消除一个翻译模式的基本语法的左递归时同时考虑属性。这种方法适合带综合属性的翻译模式。这样许多文法可以使用自顶向下分析来实现。,39,消除左递归,推广转换左递