[拼音]：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_∑表示∑上全體樹的集合，由擴展樹文法G_t生成的樹語言是T_∑的子集。由于樹中的符號具有多維連接關系，不少模式可以用樹來描述，從而得到一個樹文法。例如對于字符識別來說，若設a，b分別代表基元“-”和“│”,則英文字符H 對應有下列產生式的擴展樹文法G_t：

一個可能的導出過程是：

和它相應的圖形是：

上述G_t生成的樹語言可以描述各種尺寸的字符H 。不同的字符類對應不同的擴展樹文法，且可用樹自動機來進行識別。樹文法還可用于指紋圖像分析。

參考書目

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

建筑資質代辦咨詢熱線：18382209800

標簽：樹文法

版權聲明：本文采用知識共享 署名4.0國際許可協議 [BY-NC-SA] 進行授權

文章名稱：《樹文法》

文章鏈接：http://www.whatpixieswear.com/14269.html

該作品系作者結合建筑標準規范、政府官網及互聯網相關知識整合。如若侵權請通過投訴通道提交信息，我們將按照規定及時處理。