什么是树文法?

[拼音]：shuwenfa

[外文]：tree grammar

具有一组生成规则（产生式）的树语言(树的集合)产生系统。树文法是1969年W.S.布雷纳德首先提出的。短语结构文法生成语言的特点是字符与字符间存在从左到右的一维连接关系（称为链）。假使把一维的连接关系向多维推广，就可能把链推广为树。图中是树的一例，其中标号为b的最上端节点是树根,它有两个标号分别为b和a的子节点。前者是树叶，没有子节点。后者是中间节点，有两个标号为b的子节点,它们都是树叶。一般情形下，一棵树的树根用α＝0表示，树根的子节点依次用α＝1，2…表示，节点1的子节点依次用 α＝1·1，1·2，…表示，等等。由所有这些表示树上的节点的α组成的集合，就是该树的树域。于是，以有限字母表∑的元素为标号的树(简称∑上的树)t,可以看成一个函数t: D-→∑,其中D是t的树域;对于


是树t上的节点α 的标号；


是t(α )的秩，即树t上节点α 的子节点数。对于图中的树，


,节点标号和对应的秩是：


,

生成树语言的一种常用文法是有秩字母表（∑,r）上的扩展树文法

,

其中N是非终止符集;s∈N是起始符；P是产生式集。扩展树文法的特点是P中的产生式具有形式：

这里a属于∑；


属于N；r(a)是a的秩。用T∑表示∑上全体树的集合，由扩展树文法Gt生成的树语言是T∑的子集


。由于树中的符号具有多维连接关系，不少模式可以用树来描述，从而得到一个树文法。例如对于字符识别来说，若设a，b分别代表基元“-”和“│”,则英文字符H 对应有下列产生式的扩展树文法Gt：

一个可能的导出过程是：

和它相应的图形是：

上述Gt生成的树语言可以描述各种尺寸的字符H 。不同的字符类对应不同的扩展树文法，且可用树自动机来进行识别。树文法还可用于指纹图像分析。

参考书目

K.S.Fu,Syntactic Pattern Recognition and Applications, Prentice-Hall，Englewood Cliffs, N.J.，1982.