属性文法

我们知道,许多编译程序采用属性文法和语法制导翻译方法对语义处理工作进行比较规范和抽象的描述。

  而一个属性文法包含一个上下文无关文法和一系列文法规则,语义规则是指:对于文法的每个产生式都配备了一组属性的计算规则

  语义规则附在文法的每个产生式上,而语法制导翻译是指在语法分析过程中,完成附加在所使用的产生式上的语义规则描述的动作。

  ·语法制导:基于语法分析中用到的文法产生式

  ·翻译:完成语义分析的各项功能,不仅指生成中间代码

  形式上讲,一个属性文法是一个三元组,A=(G,V,F),其中G是一个上下文无关文法;V是有穷的属性集,每个属性与文法的一个终结符或非终结符关联,属性加工的过程即是语义处理的过程。F是关于属性的属性断言或一组属性的计算规则(称为语义规则)。断言或语义规则与一个规则式关联,只引用该规则式左端或右端的终结符或非终结符关联的属性。形式化的东西看看就好,后面给出具体例子分析。

  

既然称之为属性文法,那么什么属性呢。这些属性代表与文法符号相关信息,比如它的类型、值、代码序列、符号表内容等等。属性与变量一样,可以进行计算和传递。可以类比我们平时写代码时候一些成员变量。。属性又分为综合属性和继承属性。

  

n在一个属性文法中,对应于每个产生式A→a都有一套与之相关联的语义规则,每条规则的形式为:

  b:=f(c1,c2,…,ck),只有在已知 c1-ck 值的基础上,才能计算属性值 b, 称属性 b 依赖于属性 c1-ck,至于c1-ck依赖于哪个,就得看由c1-ck在左侧的规则了。也就是看下面的规则了。

  这里,f是一个函数,而且或者

  1. b是A的一个综合属性并且c1,c2,…,ck是产生式右边文法符号的属性,或者

  2. b是产生式右边某个文法符号的一个继承属性并且c1,c2,…,ck 是A或产生式右边任何文法符号的属性。  属性b依赖于属性c1,c2,…,ck。

  属性文法中常用记号N·t表示与非终结符号N相关联的属性t。

  

注意:¨终结符只有综合属性,由词法分析器提供

  

¨非终结符既可有综合属性也可有继承属性,文法开始符号的所有继承属性作为属性计算前的初始值

  ¨在语法树中,一个结点的综合属性的值由其子结点的属性值确定。一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定

  根据包含的属性类型,属性文法分为:S-属性文法和L-属性文法

  S-属性文法是仅包括综合属性的属性文法;L -属性文法是包括综合属性和继承属性的属性文法。

  给出一个简单的实例说明上面的内容:

  

考虑非终结符A,B和C,其中,A有一个继承属性a和一个综合属性b,B有综合属性c,C有继承属性d。产生式A→BC可能有规则

  C.d:=B.c+1

  A.b:=A.a+B.c

  而属性A.a和B.c在其它地方计算

  为什么是这样的,因为此时A就是A,B是X1,C是X2,对于d来说,他是产生式右部C的一个属性,c是右部B的属性,属性d依赖于属性c,和1,所以它是C的继承属性,对于c来说,他是产生式右部B的一个属性,但是c不依赖于d,而是d依赖于c所以c属性类型无法确定,对于b,他是A的一个属性,并且a是A的属性,c是产生式右部的属性,所以b是A的综合属性,而对于a,因为不能确定a属性依赖于那个属性,所以。无法得知。从上面我可以得出一个规律,对于一个属性规则来说,一条规则只能确定其左侧的属性类型,而右侧的属性需要由一个由他在左侧的规则来确定。比如,可以看到上面的规则中,c和a都不能确定,就是因为在规则右侧。

  此部分可能理解不够深刻,如有错误欢迎指正。

  参考:

  http://jpkc.hdu.edu.cn/computer/byyl/online/5-2.htm

  http://metc.gdut.edu.cn/compile/nandian/n-8.htm   

comments powered by Disqus