属性文法PPT学习教案

1、属性文法属性文法第1页/共62页第2页/共62页出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。一般地，属性计算规则中只能使用相应产生式的文法符号的属性，这有利于产生式范围内“封装”属性的依赖性。出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或由属性计算器的参数提供。第3页/共62页第4页/共62页第5页/共62页产生式语义规则LE nPrint(E.val)EE1+TE.val:=E1.val+T.valETE.val:=T.valTT1*FT.val:=T1.valF.valTFT.

2、val:=F.valF(E)F.val:=E.valFdigitF.val:=digit.lexval第6页/共62页LnE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=5digit.lexval=4F.val=3digit.lexval=5digit.lexval=3+*句子3*5+4n的带注释的语法树这是个带综合属性文法的例子，下面再来看一个继承属性的例子。第7页/共62页产生式产生式语义规则语义规则D D T L T LL.in:=T.typeL.in:=T.typeT T intintT.type:= T.type:= intege

3、rintegerT T realrealT.type:= T.type:= realrealL L L L1 1 ,id,idL L1 1.in:=L.in .in:=L.in addtype(addtype(id.entryid.entry,L.in),L.in)L L ididaddtype(addtype(id.entryid.entry,L.in),L.in)变量声明语句中，通过继承属性把类型信息传递给每个标识符。问题：给出句子real a,b,c 的带注释的语法树？第8页/共62页第9页/共62页对输入串的翻译=根据语义规则进行计算得出结果第10页/共62页第11页/共62页第12页

4、/共62页第13页/共62页每一个与L产生式有关的语义规则addtype(id.entry,L.in)都产生一个虚属性，结点6、8和10都是为这些虚属性构造的。第14页/共62页第15页/共62页对每个非终结符号：多次重复计算所有能够计算的继承属性最后计算所有能够计算的综合属性第16页/共62页计算语义规则，完成有关语义分析和代码生成动作的时机：自上而下分析中一个产生式匹配输入串成功时；自下而上分析中一个产生式被用于进行归约时。第17页/共62页第18页/共62页 抽象语法树中的每一个结点可以由包含几个域的记录来实现。 在一个运算符号对应的结点中,一个域标识运算符号,其它域包含指向运算分量的结

5、点的指针。 通常，运算符号叫做这个结点的标号。进行翻译时，抽象语法树中的结点可能会用附加域来存放结点的属性值(或指向属性的指针）。表达式3*5+4的抽象语法树抽象语法树(AST)：语法分析树的压缩形式。叶子结点：终结符的综合属性、文法开始符号的继承属性以下以表达式为例，说明如何构造AST。第19页/共62页产生式语义规则EE1+TE.nptr:=mknode(+,E1.nptr+T.nptr)ETE.nptr:=T.nptrTT1*FT.nptr:=mknode(*,T1.nptr+F.nptr)TFT.nptr:=F.nptrF(E)F.nptr:=E.nptrFidF.nptr:=mkle

6、af(id,id.entry)Fnumber F.nptr:=mkleaf(number,number.val)综合属性nptr表示函数调用返回的指针。第20页/共62页E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+F.nptrF.nptridnumididnum 5+指向符号表中a的入口指向符号表中b的入口第21页/共62页E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+F.nptrF.nptridnumididnum 5+指向符号表中a的入口指向符号表中b的入口第22页/共62页E.nptrT.nptrE.nptrT.nptrF

7、.nptridT.nptr+F.nptrF.nptridnumididnum 5+指向符号表中a的入口指向符号表中b的入口第23页/共62页E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+F.nptrF.nptridnumididnum 5+指向符号表中a的入口指向符号表中b的入口第24页/共62页E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+F.nptrF.nptridnumididnum 5+指向符号表中a的入口指向符号表中b的入口第25页/共62页E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+F

8、.nptrF.nptridnumididnum 5+指向符号表中a的入口指向符号表中b的入口第26页/共62页E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+F.nptrF.nptridnumididnum 5+指向符号表中a的入口指向符号表中b的入口第27页/共62页E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+F.nptrF.nptridnumididnum 5+指向符号表中a的入口指向符号表中b的入口第28页/共62页E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+F.nptrF.nptridnu

9、mididnum 5+指向符号表中a的入口指向符号表中b的入口第29页/共62页 如果一个属性文法是S-属性文法，那么在计算每个语义规则时，分析栈中栈顶处正好就是计算语义规则时需要用到的其它属性值。第30页/共62页 假设图中的栈是由一对数组state和val来实现的。每一个state元素都是一个指向LR(1)分析表的指针（或索引）。（注意，文法符号隐含在state中而不需要存储在栈中）。然而，如果像前面LR分析时的那样把文法符号存入栈中时，那么当第i个state对应的符号为A时，vali中就存放语法树中与结点A对应的属性值。 设当前栈顶由指针top指示。我们假设综合属性是刚好在每次归约前计算

10、的。假设语义规则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中。第31页/共62页第32页/共62页第33页/共62页第34页/共62页第35页/共62页第36页/共62页第37页/共62页第38页/共62页第39页/共62页第40页/共62页 构造语法树的翻译模式： 使用属性p来保

11、存语法子树的根结点指针 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)第41页/共62页第42页/共62页l思考：实现上述算术表达式文法的翻译模式，产生语法树。第43页/共62页第44页/共62页R : i, sT : nptr+ : addoplexeme第45页/共62页1.从翻译模式中去掉嵌入在产生式中间的动作2.分析栈中的继承属性 复写规则：能够预知属性值在栈中的存放位置3.模拟继承属性的计算 不能预知属性值在栈中的存放位置时，通过模拟非终结符、修改翻译模式归结为2中的情形4.用综合属性代替继承属性 改变基础文法以避免继承属性 详见参考书第46页/共62页第47页/共62页第48页/共62页第49页/共62页S.LLBLBBRRBRBB第50页/共62页B 1B. val = 1第51页/共62页必要的括号必要的括号习题三第52页/共62页E TE. c