树文法

来自术语
跳转至: 导航搜索

    用来生成树结构组成的语言,是对乔姆斯基形式文法的扩展,其重写规则的左右两端不再是线性的符号串,而是树结构。

属性[编辑]

相关术语 语言学 英文名 tree grammar
提出者 W.S.布雷纳德 属性 树语言
中文名 树文法

文法[编辑]

生成树语言的一种常用文法是有秩字母表(∑,r)上的扩展树文法$$,!!其中N是非终止符集;s∈N是起始符;P是产生式集。扩展树文法的特点是P中的产生式具有形式:这里a属于∑;属于N;r(a)是a的秩。用T∑表示∑上全体树的集合,由扩展树文法Gt生成的树语言是T∑的子集。由于树中的符号具有多维连接关系,不少模式可以用树来描述,从而得到一个树文法。例如对于字符识别来说,若设a,b分别代表基元“-”和“│”,则英文字符H对应有下列产生式的扩展树文法Gt:   $$!!   一个可能的导出过程是:   $$!! 和它相应的图形是: 上述Gt生成的树语言可以描述各种尺寸的字符H。不同的字符类对应不同的扩展树文法,且可用树自动机来进行识别。树文法还可用于指纹图像分析。



链接[编辑]

Zhishi.me http://zhishi.me/hudongbaike/resource/树文法