属性文法

短语结构文法的基础上加入每个短语和整个句子语义信息所构成的文法。1968年D.E.克努特对上下文无关语言的语义进行了形式说明。在对一个由上下文无关文法产生的句子进行分析的过程中(见句法分析),为每一个产生相应短语的非终止符确定一个与该短语的语义对应的属性。属性分为“继承的”与“综合的”两种,继承属性的意义来自一个短语的上下文,而综合属性则反映短语内所建立起来的那些关系。整个一条链的意义是由把句法分析过程中所用的产生式的属性加以联系的规则所确定的。属性文法在给出句法规则的同时,还给出相应的语义规则。语义规则能简化句法规则。例如描述一组不同边长的三角形集合的文法是一个上下文敏感文法,它的产生式规则是

其中S是起始符;N={S,B,A}是非终止符集;Σ={a,b,c}是图中有向线段基元的集合:

图

如果引入基元长度的属性La,Lb和Lc,并令Cat(ɑ,b)表示ab之间的连接关系,Cat(ɑ,b)=(+,θ)表示把a的尾端与b的始端相连接,且ab线段间的夹角为θ,则上述三角形集合可用下列的句法规则和与每条句法规则相应的语义规则得到:

这是一个正则文法,它比上述的上下文敏感文法要简单得多。属性文法既考虑模式的结构关系,又具有处理噪声和数值运算的能力,用它对模式进行描述和识别兼有决策理论方法和结构方法两者的特点,所以在模式识别领域中受到广泛的注意。它的一个重要性质是可以在句法部分和语义部分之间进行折衷,即如果使语义部分变得复杂一些,句法部分就可以变得简单一些,反之亦然。实际上模式识别中的统计方法和句法方法可以看成是属性文法的两种极端情况。统计方法把整个模式作为一个特征向量即模式的属性来研究,句法方法只考虑文法而不讨论语义。属性文法把这两者适当结合起来,就可以比较容易地解决某些模式识别问题。