资源描述:
《编译原理:第六章 属性文法和语法制导翻译.ppt》由会员上传分享,免费在线阅读,更多相关内容在PPT专区-天天文库。
1、编译原理第六章属性文法和语法制导翻译6.1属性文法属性文法(也称属性翻译文法)Knuth在1968年提出在上下文无关文法的基础上,为每个文法符号(终结符或非终结符)配备若干相关的“值”(称为属性)。属性代表与文法符号相关信息,如类型、值、代码序列、符号表内容等属性可以进行计算和传递语义规则:对于文法的每个产生式都配备了一组属性的计算规则属性综合属性:“自下而上”传递信息继承属性:“自上而下”传递信息在一个属性文法中,对应于每个产生式A→都有一套与之相关联的语义规则,每条规则的形式为:b:=f(c1,c2,…,ck)这里,f是一个函数,而且或者1.b是A的一
2、个综合属性并且c1,c2,…,ck是产生式右边文法符号的属性,或者2.b是产生式右边某个文法符号的一个继承属性并且c1,c2,…,ck是A或产生式右边任何文法符号的属性。属性b依赖于属性c1,c2,…,ck。属性文法的说明(1)(1)终结符只有综合属性,它由词法分析器提供例如digit.lexval表示单词符号“数”的词法值id.entry表示单词符号“标识符”的符号表入口(2)非终结符既可以有综合属性也可以有继承属性,在属性文法的语义规则中计算(3)关于属性计算的规定①文法的开始符号的所有继承属性作为属性计算前的初始值。②一般来讲,对出现在产生式AX1X
3、2…Xn左边的非终结符A的综合属性和出现在产生式右部的符号Xi的继承属性都必须提供一个计算规则。4③与产生式AX1X2…Xn相关联的属性计算规则只能是A.综合属性和Xi.继承属性的计算。不能有A的继承属性和Xi的综合属性的计算规则。④出现在产生式左边非终结符A的继承属性和出现在产生式右边符号Xi的综合属性不由所给的产生式的属性计算规则进行计算,它们由其它产生式的属性规则计算。⑤属性计算规则中只能使用相应产生式AX1X2…Xn的文法符号A,X1,X2,…,Xn的属性,这有利于在产生式范围内“封装”属性的依赖性。属性文法的说明(2)5语义规则所描述的工作语义
4、规则所描述的工作可以是任何希望的翻译工作,如:属性计算、静态语义检查、符号表操作、中间代码生成、报告出错,等等。语义规则可能产生副作用(如产生代码),也可能不是变元的严格函数b:=f(c1,c2,…,ck),如某个规则给出可用的下一个数据单元的地址。这样的语义规则通常写成过程调用或过程段---这时认为定义了一个虚属性。9/15/20216Ch6.属性文法和语法制导翻译例,考虑非终结符A,B和C,其中,A有一个继承属性a和一个综合属性b,B有综合属性c,C有继承属性d。产生式A→BC可能有规则C.d:=B.c+1A.b:=A.a+B.c而属性A.a和B.c在其
5、它地方计算产生式L→EnE→E1+TE→TT→T1*FT→FF→(E)F→digit语义规则print(E.val)E.val:=E1.val+T.valE.val:=T.valT.val:=T1.val*F.valT.val:=F.valF.val:=E.valF.val:=digit.lexval综合属性在语法树中,一个结点的综合属性的值由其子结点的属性值确定。使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值仅仅使用综合属性的属性文法称S-属性文法产生式L→EnE→E1+TE→TT→T1*FT→FF→(E)F→digit语义规则print(E
6、.val)E.val:=E1.val+T.valE.val:=T.valT.val:=T1.val*F.valT.val:=F.valF.val:=E.valF.val:=digit.lexval3*5+4n的带注释的语法树digit.lexval=3F.val=3T.val=3*digit.lexval=5F.val=5T.val=15E.val=15+digit.lexval=4F.val=4T.val=4E.val=19nL产生式语义规则L→Enprint(E.val)E→E1+TE.val:=E1.val+T.valE→TE.val:=T.valT→
7、T1*FT.val:=T1.val*F.valT→FT.val:=F.valF→(E)F.val:=E.valF→digitF.val:=digit.lexval继承属性在语法树中,一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定用继承属性来表示程序设计语言结构中的上下文依赖关系很方便产生式语义规则D→TLL.in:=T.typeT→intT.type:=integerT→realT.type:=realL→L1,idL1.in:=L.inaddtype(id.entry,L.in)L→idaddtype(id.entry,L.in)句子rea
8、lid1,id2,id3的带注释的语法树id1L,i