文档介绍：第四讲属性文法和语法制导翻译?属性文法?基于属性文法的处理?属性的计算?S属性文法的自下而上计算?L属性文法的自上而下计算 2§1. 属性文法属性文法是在上下文无关文法的基础上为每个文法符号(终结符或非终结符)配备若干个相关的“值”(称为属性)。这些属性代表与文法符号相关的信息,例如它的类型、值、代码序列?、符号表内容等等。属性和变量一样,可以进行计算和传递。属性一般分为两类: 综合属性: 用于“自下而上”传递信息, 继承属性: 用于“自上而下”传递信息。属性加工的过程即是语义处理的过程,对于文法的每一个产生式都配备了一组属性的计算规则,称为语义规则。 3属性的类型综合属性: 在语法树中,一个结点的综合属性的值由其子结点的属性值确定。通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。仅仅使用综合属性的属性文法称 S-属性文法。继承属性: 在语法树中,一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。可用继承属性来表示程序语言结构中的上下文依赖关系。 4 注意: (1)终结符只有综合属性,由词法分析器提供; (2)非终结符既可以有综合属性也可以有继承属性。文法开始符号的所有继承属性作为属性计算前的初始值。?出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。一般地,属性计算规则中只能使用相应产生式的文法符号的属性,这有利于产生式范围内“封装”属性的依赖性。?出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算,它们由其它产生式的属性规则计算或由属性计算器的参数提供。 5 在一个属性文法中,对应于每个产生式 A ??都有一套与之相关联的语义规则,每条语义规则的形式为: b:=f(c 1,c 2,…,c k) 其中 f是一个函数,并且满足下面两种情况之一: (1)b是A的一个综合属性并且 c 1,c 2,…c k是产生式右边文法符号的属性; (2)b是产生式右边某个文法符号的一个继承属性并且 c 1,c 2,…c k是A或产生式右边任何文法符号的属性。对这两种情况都称为属性 b依赖于属性 c 1,c 2,…,c k6语义规则描述属性计算、静态语义检查、符号表操作、代码生成等。语义规则可能产生副作用(如产生代码),也可能不是变元的严格函数(即函数中还有其它没有列出的自变量如变量地址等),比如说某个规则可能给出可用的下一个数据单元的地址。这样的语义规则通常写成过程调用或过程段。 7 下表是一个台式计算器程序的属性文法。该计算器读入一个算术表达式,计算并打印它的值,每个输入行以 n作为结束。在这些语义规则中,一个整数综合属性 val 把每个非终结符E,T,F 联系起来。记号 digit 具有综合属性 lexval ,其值由词法分析器提供。 := F?digit := F?(E) := T?F :=T * T?T 1*F := E?T :=E + E?E 1+T Print() L?E n 语义规则产生式 8 Ln =19 =15 =4 =15 =4 =3 =5 =4 =3 =5 =3 +* 句子 3*5+4 n的带注释的语法树这是个带综合属性文法的例子,下面再来看一个继承属性的例子。 9 addtype( ,) L?id L := addtype( ,) L? L 1 ,id := real T?real := integer T?int := D? T L 语义规则产生式变量声明语句中,通过继承属性把类型信息传递给每个标识符。问题:给出句子 real a,b,c 的带注释的语法树? 10