【正文】 假定如下兩個(gè)成分 (表示在下頁(yè)圖中 )已預(yù)先定義： ART1: (CAT N N1: (CAT N ROOT the ROOT fish) AGR {3s 3p}) AGR {3s 3p}) 新成分 NP將通過(guò)規(guī)則 2’(NP?ART N)來(lái)生成。 對(duì)于每個(gè)形如 Fi=Gj的特征等式， a. 如果有一條從 CCi出發(fā)的標(biāo)記為 F的邊及一條從 CCj出發(fā)的標(biāo)記為 G的邊 ， 則 i. 沿 F邊到達(dá)節(jié)點(diǎn) Ni， 沿 G邊到達(dá)節(jié)點(diǎn) Nj； ii. 用圖合一算法對(duì) Ni和 Nj進(jìn)行合一，并 (在成功時(shí) )構(gòu)造新節(jié)點(diǎn) X； iii. 將所有指向 Ni或 Nj的改為指向 X； b. 如果沒(méi)有從 CCi出發(fā)的標(biāo)記為 F的邊 ， 但有一條從 CCj到節(jié)點(diǎn) Nj的標(biāo)記為 G的邊 ， 則添加一條從 CCi到節(jié)點(diǎn) Nj的標(biāo)記為 F的邊； c. 如果有一條從 CCi到節(jié)點(diǎn) Ni的標(biāo)記為 F的邊，但沒(méi)有從 CCj出發(fā)的標(biāo)記為 G的邊，則添加一條從 CCj到節(jié)點(diǎn) Ni的標(biāo)記為 G的邊。 對(duì)于每個(gè)形如 Fi=V的特征等式，其中 V是一個(gè)值。 作以 SCi為根節(jié)點(diǎn)的圖的一份拷貝 (稱拷貝的根節(jié)點(diǎn)為 CCi)， i=1,…,n 。 算法將構(gòu)造一個(gè)滿足所有特征等式的有向圖 。 通用特征系統(tǒng)與合一文法 (15) 給定規(guī)則 X0?X1 … Xn及一組形如 Fi=V的特征等式 。 通用特征系統(tǒng)與合一文法 (13) ? 運(yùn)用圖合一算法，可將下圖的兩個(gè)結(jié)構(gòu)合一為 N3: (CAT N ROOT fish AGR 3s) N1 fish CAT N {3s 3p} ROOT AGR N2 CAT N {3s} AGR 通用特征系統(tǒng)與合一文法 (14) ? 有了圖合一算法，我們就能夠得到構(gòu)造新成分的算法，而這可用于任何標(biāo)準(zhǔn)的分析器。 b. 如果沒(méi)有從 Nj到 NFj的標(biāo)記為 F的邊，則構(gòu)造一條從 N到 NFi的標(biāo)記為 F的邊。 對(duì)每條由 Ni指向 NFi的標(biāo)記為 F的邊 ， a. 如果有一條從 Nj到 NFj的標(biāo)記為 F的邊 ， 則遞歸地合一 NFi和 NFj。 b. 否則，兩個(gè)圖不能合一。 輸入 ：根節(jié)點(diǎn)為 Ni和根節(jié)點(diǎn)為 Nj的有向圖 若 Ni和 Nj相等，則成功并返回 Ni。 通用特征系統(tǒng)與合一文法 (12) ? 兩個(gè)特征結(jié)構(gòu)的合一可通過(guò)圖合一算法來(lái)定義。有向圖中沒(méi)有輸出邊 (outgoing)的節(jié)點(diǎn)稱為匯(sink)。例如，下面兩個(gè)成分可表示為如下頁(yè)所示的有向圖： N1: (CAT N N2: (CAT N ROOT fish AGR 3s) AGR {3s 3p}) 通用特征系統(tǒng)與合一文法 (10) N1 fish CAT N {3s 3p} ROOT AGR N2 CAT N {3s} AGR 通用特征系統(tǒng)與合一文法 (11) ? 在有向圖中沒(méi)有輸入邊 (ining)的節(jié)點(diǎn)稱為 源(source)，如前頁(yè)圖的節(jié)點(diǎn) N1和 N2。 1’. S?NP VP AGR=AGR1=AGR2 VFORM=VFORM2 2’. NP?ART N AGR=AGR1=AGR2 8’. VP?V ADJP SUBCAT1=_adjp VFORM=VFORM1 AGR=AGR1 10’. ADJP?ADJ 通用特征系統(tǒng)與合一文法 (9) ? 基于合一的形式系統(tǒng)可以通過(guò)將特征結(jié)構(gòu)表示為有向圖(Directed Acyclic graph, DAG)而精確定義。注意下標(biāo) 0也被省略。一個(gè)像 S?NP VP這樣的規(guī)則可以表述為如下的合一文法 X0?X1 X2 CAT0=S CAT1=NP CAT2=VP AGR0=AGR1=AGR2 VFORM0=VFORM2 這意味著成分 X0可由成分 X1和 X2組成的序列構(gòu)成，如果： X0的 CAT為 S、 X1的 CAT為 NP、 X2的 CAT為 VP、所有三個(gè)成分的 AGR特征值相同，且 X0與 X2的VFORM特征值相同。 事實(shí) 1 設(shè) F1和 F2是兩個(gè)特征結(jié)構(gòu)，它們有合一 F3，則它們一定也有唯一的最一般合一 F4，使 F4?F3。若除此之外，對(duì) F1和 F2的任何一個(gè)合一 F，皆有 F?F3，則 F3還是 F1和 F2的 最一般合一 。 通用特征系統(tǒng)與合一文法 (3) 如果特征結(jié)構(gòu) F2包含于 F1，記為 F2?F1。例如，特征結(jié)構(gòu) (CAT V) 包含特征結(jié)構(gòu) (CAT V ROOT cry) 因?yàn)榍耙唤Y(jié)構(gòu)的 ROOT特征可取任意值。 ? APPEND：把一個(gè)值附加到當(dāng)前寄存器的值中去。 擴(kuò)充轉(zhuǎn)移網(wǎng)絡(luò) (15) ? SETR：把一個(gè)值送入指定的寄存器。例如上面的第一句中不定式的主語(yǔ)是 Mary，第二句中不定式的主語(yǔ)則是 John。為了在 ATN中進(jìn)行同樣的分析，需要調(diào)用 VP的相應(yīng)網(wǎng)絡(luò)來(lái)進(jìn)行分析，但需要將該網(wǎng)絡(luò)的 VFORM寄存器的值預(yù)置為 inf。 SENDR動(dòng)作的作用在于向新網(wǎng)絡(luò)傳遞信息并指導(dǎo)新網(wǎng)絡(luò)對(duì)新成分的分析 。 例：分析句子 1 The 2 dog 3 saw 4 Jack 5 擴(kuò)充轉(zhuǎn)移網(wǎng)絡(luò) (7) 對(duì)第一個(gè) NP網(wǎng)絡(luò)調(diào)用的跟蹤： S網(wǎng)絡(luò)的邊 4 步驟 節(jié)點(diǎn) 位置 通過(guò)的邊 寄存器設(shè)置 2. NP 1 1 DET?the AGR?{3s 3p} 3. NP1 2 2(測(cè)試交集 HEAD?dog {3s 3p}?3s) 4. NP2 3 pop 返回 (NP DET the HEAD dog AGR 3s) 對(duì)第二個(gè) NP網(wǎng)絡(luò)調(diào)用的跟蹤： S網(wǎng)絡(luò)的邊 4 步驟 節(jié)點(diǎn) 位置 通過(guò)的邊 寄存器設(shè)置 7. NP 4 3 NAME?Jack AGR?3s 8. NP2 5 pop 返回 (NP NAME Jack AGR 3s) 擴(kuò)充轉(zhuǎn)移網(wǎng)絡(luò) (8) S網(wǎng)絡(luò)的跟蹤 步驟 節(jié)點(diǎn) 位置 所走的邊 寄存器設(shè)置 1. S 1 邊 4, 成功 SUBJ?(NP DET the (見(jiàn)對(duì) NP HEAD dog 網(wǎng)的跟蹤 ) AGR 3s) 5. S1 3 邊 5(測(cè)試 MAINV?saw 3s?{1s,1p, AGR?3s 2s,2p,3s,3p} 6. S2 4 邊 6, 成功 OBJ?(NP NAME Jack (見(jiàn)前面的跟蹤 ) AGR 3s) 9. S3 5 彈出邊成功 返回 (S SUBJ(NP DET the