樹文法
[拼音]：shuwenfa
[外文]：tree grammar
具有一組生成規(guī)則（產(chǎn)生式）的樹語言(樹的集合)產(chǎn)生系統(tǒng)。樹文法是1969年W.S.布雷納德首先提出的。短語結(jié)構(gòu)文法生成語言的特點是字符與字符間存在從左到右的一維連接關(guān)系（稱為鏈）。假使把一維的連接關(guān)系向多維推廣，就可能把鏈推廣為樹。圖中是樹的一例，其中標號為b的最上端節(jié)點是樹根,它有兩個標號分別為b和a的子節(jié)點。前者是樹葉，沒有子節(jié)點。后者是中間節(jié)點，有兩個標號為b的子節(jié)點,它們都是樹葉。一般情形下，一棵樹的樹根用α＝0表示，樹根的子節(jié)點依次用α＝1，2…表示，節(jié)點1的子節(jié)點依次用 α＝1?1，1?2，…表示，等等。由所有這些表示樹上的節(jié)點的α組成的集合，就是該樹的樹域。于是，以有限字母表∑的元素為標號的樹(簡稱∑上的樹)t,可以看成一個函數(shù)t: D-→∑,其中D是t的樹域;對于是樹t上的節(jié)點α 的標號；是t(α )的秩，即樹t上節(jié)點α 的子節(jié)點數(shù)。對于圖中的樹，,節(jié)點標號和對應(yīng)的秩是：,
生成樹語言的一種常用文法是有秩字母表（∑,r）上的擴展樹文法
,
其中N是非終止符集;s∈N是起始符；P是產(chǎn)生式集。擴展樹文法的特點是P中的產(chǎn)生式具有形式：
這里a屬于∑；屬于N；r(a)是a的秩。用T∑表示∑上全體樹的集合，由擴展樹文法Gt生成的樹語言是T∑的子集。由于樹中的符號具有多維連接關(guān)系，不少模式可以用樹來描述，從而得到一個樹文法。例如對于字符識別來說，若設(shè)a，b分別代表基元“-”和“│”,則英文字符H 對應(yīng)有下列產(chǎn)生式的擴展樹文法Gt：
一個可能的導(dǎo)出過程是：
和它相應(yīng)的圖形是：
上述Gt生成的樹語言可以描述各種尺寸的字符H 。不同的字符類對應(yīng)不同的擴展樹文法，且可用樹自動機來進行識別。樹文法還可用于指紋圖像分析。
- 參考書目
-
- K.S.Fu,Syntactic Pattern Recognition and Applications, Prentice-Hall，Englewood Cliffs, N.J.，1982.
建筑資質(zhì)代辦咨詢熱線：13198516101
標簽：樹文法
版權(quán)聲明：本文采用知識共享 署名4.0國際許可協(xié)議 [BY-NC-SA] 進行授權(quán)
文章名稱：《樹文法》
文章鏈接：http://www.fjemb.com/14269.html
該作品系作者結(jié)合建筑標準規(guī)范、政府官網(wǎng)及互聯(lián)網(wǎng)相關(guān)知識整合。如若侵權(quán)請通過投訴通道提交信息，我們將按照規(guī)定及時處理。
咨詢熱線：13198516101 
