第6讲--属性文法课件.ppt

《第6讲--属性文法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六讲属性文法和语法制导翻译属性文法基于属性文法的处理属性的计算S属性文法的自下而上计算L属性文法的自上而下计算1§1.属性文法属性文法是在上下文无关文法的基础上为每个文法符号（终结符或非终结符）配备若干个相关的“值”（称为属性）。这些属性代表与文法符号相关的信息，例如它的类型、值、代码序列、符号表内容等等。属性和变量一样，可以进行计算和传递。属性一般分为两类：综合属性：用于“自下而上”传递信息，继承属性：用于“自上而下”传递信息。属性加工的过程即是语义处理的过程，对于文法的每一个产生式都配备了一组属性的计算规

2、则，称为语义规则。2属性的类型综合属性：在语法树中，一个结点的综合属性的值由其子结点的属性值确定。通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。仅仅使用综合属性的属性文法称S-属性文法。继承属性：在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。可用继承属性来表示程序语言结构中的上下文依赖关系。3注意：（1）终结符只有综合属性，由词法分析器提供；（2）非终结符既可以有综合属性也可以有继承属性。文法开始符号的所有继承属性作为属性计算前的初始值。出现在产生式右边的继承属性和出

3、现在产生式左边的综合属性都必须提供一个计算规则。一般地，属性计算规则中只能使用相应产生式的文法符号的属性，这有利于产生式范围内“封装”属性的依赖性。出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或由属性计算器的参数提供。4在一个属性文法中，对应于每个产生式A都有一套与之相关联的语义规则，每条语义规则的形式为：b:=f(c1,c2,…,ck)其中f是一个函数，并且满足下面两种情况之一：（1）b是A的一个综合属性并且c1,c2,…ck是产

4、生式右边文法符号的属性；（2）b是产生式右边某个文法符号的一个继承属性并且c1,c2,…ck是A或产生式右边任何文法符号的属性。对这两种情况都称为属性b依赖于属性c1,c2,…,ck。5语义规则描述属性计算、静态语义检查、符号表操作、代码生成等。语义规则可能产生副作用（如产生代码），也可能不是变元的严格函数（即函数中还有其它没有列出的自变量如变量地址等），比如说某个规则可能给出可用的下一个数据单元的地址。这样的语义规则通常写成过程调用或过程段。6下表是一个台式计算器程序的属性文法。该计算器读入一个算术表达式，计算并

5、打印它的值，每个输入行以n作为结束。在这些语义规则中，一个整数综合属性val把每个非终结符E,T,F联系起来。记号digit具有综合属性lexval，其值由词法分析器提供。7LnE.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的带注释的语法树这是个带综合属性文法的例子，下面再来看一个继承属性的例子。8变量声明语句中，通过继承属性把类型信息传递给

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

7、合属性b，这样把每一个语义规则都写成b:=f(c1,c2,…ck)的形式。依赖图是一个有向图，为每一个属性设置一个结点：如果属性b依赖属性c，则从属性c的结点有一条有向边连到属性b的结点。12依赖图的画法例：属性A.a:=f(X.x,Y.y)对应于产生式AXY的语义规则。在依赖图中有三个相关结点：A.a,X.x,Y.y。由于A.a依赖于X.x，Y.y，所以有两条有向边从X.x到A.a，从Y.y连到A.a.如果与产生式AXY对应的语义规则还有：X.i:=g(A.a,Y.y)图中再增加两条有向边：从A.a连到X.i，

8、从Y.y连到X.i,因为X.i依赖于A.a和Y.y.13[例]依赖图当下面的产生式应用于语法树时，我们就像下图所示的那样把有向边加到依赖图中。产生式语义规则EE1+E2E.val:=E1.val+E2.val14[例]依赖图因为产生式DTL的语义规则L.in=T.type,从代表T.type的结点4有一条边连到代表L.in的结点5；因为产生