第6讲--属性文法

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

1、第六讲第六讲 属性文法和属性文法和语法制导翻译语法制导翻译u属性文法属性文法u基于属性文法的处理基于属性文法的处理u属性的计算属性的计算uS S属性文法的自下而上计算属性文法的自下而上计算uL L属性文法的自上而下计算属性文法的自上而下计算21. 1. 属性文法属性文法 属性文法是在上下文无关文法的基础上为每个文属性文法是在上下文无关文法的基础上为每个文法符号（终结符或非终结符）配备若干个相关的法符号（终结符或非终结符）配备若干个相关的“值值”（称为（称为属性属性）。这些属性代表与文法符号相）。这些属性代表与文法符号相关的信息，例如它的类型、值、代码序列关的信息，例如它的类型、值、代码序列 、

2、符号表、符号表内容等等。属性和变量一样，可以进行计算和传递。内容等等。属性和变量一样，可以进行计算和传递。 属性一般分为两类：属性一般分为两类：综合属性：综合属性：用于用于“自下而上自下而上”传递信息，传递信息，继承属性：继承属性：用于用于“自上而下自上而下”传递信息。传递信息。 属性加工的过程即是语义处理的过程，对于文属性加工的过程即是语义处理的过程，对于文法的每一个产生式都配备了一组属性的计算规则，法的每一个产生式都配备了一组属性的计算规则，称为语义规则。称为语义规则。3属性的类型 综合属性综合属性： 在语法树中，一个结点的综合属性的值由其子在语法树中，一个结点的综合属性的值由其子结点的属

3、性值确定。通常使用结点的属性值确定。通常使用自底向上自底向上的方法在每的方法在每一个结点处使用语义规则计算综合属性的值。仅仅一个结点处使用语义规则计算综合属性的值。仅仅使用综合属性的属性文法称使用综合属性的属性文法称S-S-属性文法。属性文法。 继承属性继承属性： 在语法树中，一个结点的继承属性由此结点的在语法树中，一个结点的继承属性由此结点的父结点父结点和和/ /或或兄弟结点的某些属性确定。可用继承兄弟结点的某些属性确定。可用继承属性来表示程序语言结构中的上下文依赖关系。属性来表示程序语言结构中的上下文依赖关系。4 注意：注意：（1 1）终结符只有综合属性，由词法分析器提供；）终结符只有综合

4、属性，由词法分析器提供；（2 2）非终结符既可以有综合属性也可以有继承属性。）非终结符既可以有综合属性也可以有继承属性。文法开始符号的所有继承属性作为属性计算前的初文法开始符号的所有继承属性作为属性计算前的初始值。始值。出现在产生式右边的继承属性和出现在产生式出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。一左边的综合属性都必须提供一个计算规则。一般地，属性计算规则中只能使用相应产生式的般地，属性计算规则中只能使用相应产生式的文法符号的属性，这有利于产生式范围内文法符号的属性，这有利于产生式范围内“封封装装”属性的依赖性。属性的依赖性。出现在产生式左边的继承属性和

5、出现在产生式出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则规则进行计算，它们由其它产生式的属性规则计算或由属性计算器的参数提供。计算或由属性计算器的参数提供。5 在一个属性文法中，对应于每个产生式在一个属性文法中，对应于每个产生式A A都有一套与之相关联的都有一套与之相关联的语义规则语义规则，每条语义规，每条语义规则的形式为：则的形式为： b:=f(c b:=f(c1 1,c,c2 2,c,ck k) ) 其中其中f f是一个函数是一个函数，并，并且满足下面两种情况之一：且满足下面

6、两种情况之一： （1 1）b b是是A A的一个综合属性并且的一个综合属性并且c c1 1,c,c2 2,c,ck k是是产生式右边文法符号的属性；产生式右边文法符号的属性； （2 2）b b是产生式右边某个文法符号的一个继是产生式右边某个文法符号的一个继承属性并且承属性并且c c1 1,c,c2 2,c,ck k是是A A或产生式右边任何文或产生式右边任何文法符号的属性。法符号的属性。 对这两种情况都对这两种情况都称为属性称为属性b b依赖于依赖于属性属性c c1 1,c,c2 2, , c, , ck k。6语义规则语义规则 描述属性计算、静态语义检查、符号表描述属性计算、静态语义检查、符

7、号表操作、代码生成等。语义规则可能产生操作、代码生成等。语义规则可能产生副作副作用用（如产生代码），也可能不是变元的严格（如产生代码），也可能不是变元的严格函数（即函数中还有其它没有列出的自变量函数（即函数中还有其它没有列出的自变量如变量地址等），比如说某个规则可能给出如变量地址等），比如说某个规则可能给出可用的下一个数据单元的地址。这样的语义可用的下一个数据单元的地址。这样的语义规则通常写成过程调用或过程段。规则通常写成过程调用或过程段。7 下表是一个台式计算器程序的属性文法。该计算器读入下表是一个台式计算器程序的属性文法。该计算器读入一个算术表达式，计算并打印它的值，每个输入行以一个算术表

8、达式，计算并打印它的值，每个输入行以n n作为结作为结束。束。 在这些语义规则中，一个整数综合属性在这些语义规则中，一个整数综合属性valval把每个非终结把每个非终结符符E,T,FE,T,F联系起来。记号联系起来。记号digitdigit具有综合属性具有综合属性lexvallexval，其值由，其值由词法分析器提供。词法分析器提供。产生式语义规则LE nPrint(E.val)EE1+TE.val:=E1.val+T.valETE.val:=T.valTT1*FT.val:=T1.valF.valTFT.val:=F.valF(E)F.val:=E.valFdigitF.val:=digit

9、.lexval8LnE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=5digit.lexval=4F.val=3digit.lexval=5digit.lexval=3+*句子句子3 3* *5+45+4n n的带注释的语法树的带注释的语法树这是个带综合属性文法的例子，下面再来看一这是个带综合属性文法的例子，下面再来看一个继承属性的例子。个继承属性的例子。9产生式产生式语义规则语义规则D D T L T LL.in:=T.typeL.in:=T.typeT T intintT.type:= T.type:= integerintegerT

10、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 的带注释的语法树的带注释的语法树？10112.2. 基于属性文法的处理方法基于属性文法的

11、处理方法 对单词符号串进行语法分析，构造语法分析树，对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树，并在语法树的各结点处然后根据需要遍历语法树，并在语法树的各结点处按语义规则进行计算。按语义规则进行计算。 输入串输入串语法树语法树依赖图依赖图按次序计算语义规则按次序计算语义规则 这种由源程序的语法结构所驱动的处理办法就这种由源程序的语法结构所驱动的处理办法就是是语法制导翻译语法制导翻译。 语义规则的计算可能语义规则的计算可能产生代码产生代码、在、在符号表符号表中存中存放信息、给出放信息、给出错误信息错误信息或执行任何或执行任何其它动作其它动作。对输入串的翻译对输入串的翻译=根