Knuth提出的属性文法与编译原理的关系

1968年，Knuth首次提出了属性文法（也称为属性翻译文法）这一概念。这种文法以上下文无关文法为基础，为文法中的终结符和非终结符配备了若干相关的“值”（称为属性）。这些属性代表的是与文法符号有关的信息，比如它的类型、值、代码序列以及符号表的内容等。属性与变量一样，可以进行计算和传递，并且通常把属性分为综合属性和继承属性两类。对属性进行加工的过程就是语义处理的过程。

在属性文法中，对于文法的每个产生式A→α都配备了一组关于属性的计算规则，形如：

属性文法

b:=f(c1,c2,…,ck)

该规则称为语义规则。其中，f是一个函数，如果

（1）b是A的一个综合属性，并且c1、c2、…、ck是A的其他属性或产生式右边文法符号的属性；或者

（2）b是产生式右边某个文法符号的一个继承属性，并且c1、c2、…、ck是A或产生式右边任何文法符号的属性。

在这两种情况下，都说属性b依赖于属性c1、c2、…、ck，即b的值由c1、c2、…、ck来决定。

由上可以看出，综合属性用于“自下而上”传递信息，继承属性用于“自上而下”传递信息，同时应该注意：(www.xing528.com)

（1）终结符只有综合属性，其值由词法分析器提供；

（2）非终结符既可以有综合属性，也可以有继承属性，但文法开始符号的所有继承属性用作属性计算前的初始值。

一般来说，对出现在产生式左边的综合属性和右边的继承属性都必须提供一个计算规则，而且规则中只能使用相应产生式中文法符号的属性。另外还需注意，产生式左边的继承属性和右边的综合属性不能在该产生式对应的语义规则中进行计算，应该由其他产生式的语义规则计算或由属性计算器的参数提供。

语义规则所描述的工作主要包括属性计算、静态语义检查、符号表操作以及代码生成等。语义规则可能产生副作用（如产生代码），也可能不是变元的严格函数（如某个规则给出可用的下一个数据单元的地址），这样的语义规则通常写成过程调用或过程段的形式。

例如，在表6-1所示的属性文法中，非终结符E、T、F都有综合属性value。在每个产生式所对应的语义规则中，产生式左边非终结符的属性值value是从右边非终结符的属性值value计算出来的。终结符digit有一个综合属性lexvalue，其值由词法分析器提供。与产生式L→E#对应的语义规则仅仅是一个用来打印E所产生的算术表达式的值的过程，它可以看作是L的一个虚属性。

表6-1　一个简单的属性文法

需要说明的是，在上述文法中，对同一非终结符以下标的形式做了区分，目的是消除对其属性值引用的二义性。