[拼音]:shuwenfa [外文]:tree grammar ![]() 具有一组生成规则(产生式)的树语言(树的集合)产生系统。树文法是1969年W.S.布雷纳德首先提出的。短语结构文法生成语言的特点是字符与字符间存在从左到右的一维连接关系(称为链)。假使把一维的连接关系向多维推广,就可能把链推广为树。图中是树的一例,其中标号为b的最上端节点是树根,它有两个标号分别为b和a的子节点。前者是树叶,没有子节点。后者是中间节点,有两个标号为b的子节点,它们都是树叶。一般情形下,一棵树的树根用α=0表示,树根的子节点依次用α=1,2…表示,节点1的子节点依次用 α=1·1,1·2,…表示,等等。由所有这些表示树上的节点的α组成的集合,就是该树的树域。于是,以有限字母表∑的元素为标号的树(简称∑上的树)t,可以看成一个函数t: D-→∑,其中D是t的树域;对于 生成树语言的一种常用文法是有秩字母表(∑,r)上的扩展树文法
其中N是非终止符集;s∈N是起始符;P是产生式集。扩展树文法的特点是P中的产生式具有形式: ![]() 这里a属于∑; ![]() 一个可能的导出过程是: ![]() 和它相应的图形是: ![]() 上述Gt生成的树语言可以描述各种尺寸的字符H 。不同的字符类对应不同的扩展树文法,且可用树自动机来进行识别。树文法还可用于指纹图像分析。
|