《属性文法》PPT课件.ppt

《《属性文法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《属性文法》PPT课件.ppt（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的带注释的语法树,这是个带综合属性文法的例子，下面再来看一个继承属性的例子。,9,变量声明语句中，通过继承属性

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

6、=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.i依赖于A.a和Y.y.,14,例依赖图,当下面的产生式应用于语法树时，我们就像下图

7、所示的那样把有向边加到依赖图中。产生式 语义规则 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的语法树的构造,29,a+5*b的语法树的构造,30,a+5*b的语法树的构造,31,3.S-属性文法的自下而上计算,S-属性文法：只含有综合

12、属性的属性文法。在自底向上的分析法如LR分析法中，我们使用一个栈来存放已经分析过的子树的信息，现在可以在分析栈中使用一个附加的域来存放综合属性值。,如果一个属性文法是S-属性文法，那么在计算每个语义规则时，分析栈中栈顶处正好就是计算语义规则时需要用到的其它属性值。,32,假设图中的栈是由一对数组state和val来实现的。每一个state元素都是一个指向LR(1)分析表的指针（或索引）。（注意，文法符号隐含在state中而不需要存储在栈中）。然而，如果像前面LR分析时的那样把文法符号存入栈中时，那么当第i个state对应的符号为A时，vali中就存放语法树中与结点A对应的属性值。设当前栈顶由指

13、针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.xY Y.yZ栈顶Z.z,val X.x Y.y栈顶Z.z,简化为,33,边分析边翻译的方式能否用于继承属性？属性的计算次序一定受分析方法

14、所限定的分析树结点建立次序的限制分析树的结点是自左向右生成如果属性信息是自左向右流动，那么就有可能在分析的同时完成属性计算,34,4.L-属性文法和自顶向下翻译,L-属性文法：如果对于每个产生式AX1X2Xn的每个语义规则中，每个属性或者是综合属性，或者是Xj(1=j=n)的一个继承属性且这个继承属性仅依赖于：（1）产生式Xj的左边符号X1,X2,Xj-1的属性（2）A的继承属性。L-属性文法也就是“左属性”文法，计算每一个继承属性时不能引用右边符号的属性(继承属性和综合属性)。由此定义可知，S属性文法一定是L属性文法。,35,翻译模式,属性文法可以看成是关于语言翻译的高级规范说明，其中隐去实

15、现细节，使用户从明确说明翻译顺序的工作中解脱出来。下面我们讨论一种适合语法制导翻译的另一种描述形式，称为翻译模式。翻译模式给出了使用语义规则进行计算的次序，这样就可以把某些实现细节表示出来。在翻译模式中，和文法符号相关的属性和语义规则（这里我们也称语义动作），用花括号 括起来，插入到产生式右部的合适位置上。这样翻译模式给出了使用语义规则进行计算的顺序。,36,对继承属性出现位置的限制,为了计算出继承属性，翻译模式必须满足三个条件：（1）产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。（2）一个动作不能引用这个动作右边符号的综合属性。（3）产生式左边非终结符的综合属性只有在它所引用

16、的所有属性都计算出来后才能计算。计算这种属性的动作通常可放在产生式右端的末尾。,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,自顶向下翻译,在第四讲我们知道，为了构造不带回溯的自顶向下语法分析，必须消除文法中的左递归。现在我们把前面消除左递归的方法加以扩充,当消除一个翻译模式的基本语法的左递归时同时考虑属性。这种方法适合带综合属性的翻译模式。这样许多

17、文法可以使用自顶向下分析来实现。,39,消除左递归,推广转换左递规翻译模式的方法，以便进行自顶向下分析：假设我们有下面的翻译模式：AA1Y A.a:=g(A1.a,Y.y)AX A.a:=f(X.x)其每个文法符号都有一个综合属性，用小写字母表示，g和f是任意函数。利用第四章消除左递归的算法，可将其转换成下面文法：AXR R YR|,40,翻译模式变为：AX R.i:=f(X.x)R A.a:=R.s RY R1.i:=g(R.i,Y.y)R1 R.s:=R1.s R R.s:=R.i 经过转换的翻译模式，使用了R的继承属性i和综合属性s.考虑产生算术表达式的文法，它的翻译模式如何?,考虑语义

18、动作,41,求值翻译模式：使用属性val来保存计算结果 ET R.i:=T.val R E.val:=R.s R+T R1.i:=R.i+T.val R1 R.s:=R1.s R R.s:=R.i T(E)T.val:=E.val Tnum T.val:=num.val,42,构造语法树的翻译模式：使用属性p来保存语法子树的根结点指针 ET R.i:=T.p R E.p:=R.s R+T R1.i:=mknod(+,R.i,T.p)R1 R.s:=R1.s R R.s:=R.i T(E)T.p:=E.p Tnum T.p:=mkleaf(num,num.val),43,递归下降翻译器的构造,思

19、想：对递归下降的语法分析器进行扩展（在适当的位置加入语义子程序），使之能够实现翻译模式。方法：为每个非终结符A构造一个函数，A的继承属性对应该函数的形式参数，其返回值为A的综合属性。函数体内，对出现在A的产生式右部的每个文法符号的每个属性都设置一个局部变量。控制流程依然由递归下降分析方法确定。,44,在每个产生式对应的程序代码中，按照从左到右的次序，对于终结符、非终结符及其语义动作分别作以下工作：对于带有综合属性x的终结符X，把x的值存入为X.x设置的变量中。然后产生一个匹配X的调用，并继续输入。对于每个非终结符B，产生一个右部带有函数调用的赋值语句 c=B(b1,b2,.,bn)，其中b1,

20、b2,.,bn是为B的继承属性设置的变量，c是为B的综合属性设置的变量。对于语义动作，把动作的代码抄进语法分析器中，并把对属性的引用改为对相应变量的引用。思考：实现上述算术表达式文法的翻译模式，产生语法树。,45,预测翻译器的设计：示例把预测分析器的构造方法推广到翻译方案的实现产生式R+TR|的分析过程procedure R;beginif lookahead=+then beginmatch(+);T;Rendelse begin/什么也不做/endend,46,function R(i:syntax_tree_node):syntax_tree_node;var nptr,i1,s1,s:

21、syntax_tree_node;addoplexeme:char;begin if lookahead=+then begin/产生式 R+T R/addoplexeme=lexval;match(+);nptr=T;i1=mknode(addoplexme,i,nptr);s1=R(i1);s=s1endelse s=i;/产生式 R/return send;,R:i,sT:nptr+:addoplexeme,47,5.自下而上计算继承属性,自下而上地计算L-属性。可以基于所有LL(1)文法和许多LR(1)的L-属性文法。,从翻译模式中去掉嵌入在产生式中间的动作分析栈中的继承属性 复写规则

22、：能够预知属性值在栈中的存放位置模拟继承属性的计算 不能预知属性值在栈中的存放位置时，通过模拟非终结符、修改翻译模式归结为2中的情形用综合属性代替继承属性 改变基础文法以避免继承属性 详见参考书,48,习题一,下列文法由开始符号S产生一个二进制数，令综合属性val给出该数的值：SL.L|LL LB|BB 0|1 试设计求S.val的属性文法。其中，已知B的综合属性c，给出由B产生的二进位的结果值。,49,方法1:使用L.val、L.len属性,SL S.val=L.val SL1.L2 S.val=L1.val+L2.val/2L2.lenL BL.val=B.c,L.len=1L L1BL.

23、val=2*L1.val+B.c,L.len=L1.len+1B 0B.c=0B 1B.c=1,50,方法2：使用L.lval、L.w属性,SL S.val=L.lval SL1.L2 S.val=L1.lval+L2.lval/L2.wL BL.lval=B.c,L.w=2L L1BL.lval=2*L1.lval+B.c,L.w=2*L1.w B 0B.c=0B 1B.c=1,51,为下面文法写一个语法制导的定义，用S的综合属性val给出下面文法中S产生的二进制数的值。例如，输入101.101时，S.val=5.625。不得修改文法，但属性使用没有限制S L.R|LL L B|BR B R

24、|BB 0|1,习题二,52,S L.RS.val=L.val+R.valS LS.val=L.valL L1 BL.val=L1.val 2+B.valL BL.val=B.valR B R1R.val=R1.val/2+B.val/2R BR.val=B.val/2B 0B.val=0B 1B.val=1,53,给出把中缀表达式翻译成没有冗余括号的中缀表达式的语法制导定义。例如,因为和是左结合,(a(b+c)(d)可以重写成a(b+c)d先把表达式的括号都去掉，然后在必要的地方再加括号去掉表达式中的冗余括号，保留必要的括号,习题三,54,第一种方法S E print(E.code)E E1

25、+T if T.op=plus thenE.code=E1.code|“+”|“(”|T.code|“)”elseE.code=E1.code|“+”|T.code;E.op=plusE TE.code=T.code;E.op=T.op,55,T T1 Fif(F.op=plus)or(F.op=times)thenif T1.op=plus thenT.code=“(”|T1.code|“)”|“”|“(”|F.code|“)”elseT.code=T1.code|“”|“(”|F.code|“)”else if T1.op=plus thenT.code=“(”|T1.code|“)”|“

26、”|F.codeelseT.code=T1.code|“”|F.code;T.op=times,56,T FT.code=F.code;T.op=F.opF idF.code=id.lexeme;F.op=idF(E)F.code=E.code;F.op=E.op,57,第二种方法给E，T和F两个继承属性left_op和right_op分别表示左右两侧算符的优先级给它们一个综合属性self_op表示自身主算符的优先级再给一个综合属性code表示没有冗余括号的代码分别用1和2表示加和乘的优先级，用3表示id和(E)的优先级，用0表示左侧或右侧没有运算对象的情况,58,S EE.left_op=0

27、;E.right_op=0;print(E.code)E E1+TE1.left_op=E.left_op;E1.right_op=1;T.left_op=1;T.right_op=E.right_op;E.code=E1.code|“+”|T.code;E.self_op=1;E TT.left_op=E.left_op;T.right_op=E.right_op;E.code=T.code;E.self_op=T.self_op,59,T T1 F.T F.F idF.code=id.lexeme;F.self_op=3,60,F(E)E.left_op=0;E.right_op=0;F.self_op=if(F.left_op=F.right_op)thenE.self_op else 3F.code=if(F.left_op=F.right_op)thenE.code else“(”|E.code|“)”,61,作业,在C语言中，自增运算符只能作用于“左值”（如变量名），而3+和(id+id)+这样的表达式被编译时，编译器都会报告如下的错误：invalid lvalue in increment 现有如下简化的C语言表达式文法：E-E+E|(E)|E+|id|number 写出一个语法制导定义或翻译模式，它检查+的运算对象是否合法。,62,End,