搭建上下文無關(guān)文法分析器的時(shí)候，人們常常采取另外一種方法，即將語法規(guī)則直接用邏輯程序語言來表示，如PROLOG。可以證實(shí)的是，標(biāo)準(zhǔn)PROLOG的解析算法使用的搜索策略恰恰就是深度優(yōu)先的自頂向下分析算法。所以，需要做的工作僅僅是尋找將上下文無關(guān)文法規(guī)則重新整理成PROLOG子句形式的方法?？紤]如下的上下文無關(guān)文法規(guī)則：

S→ NP VP

采用公理的形式，這條規(guī)則可以重新表述為：“一個(gè)詞的序列是合法的S。前提是該序列開頭部分是一個(gè)合法的名詞短語，其后跟著一個(gè)合法的動(dòng)詞短語?！比绻凑瘴恢庙樞蚪o句中的每個(gè)詞編號(hào)，這個(gè)規(guī)則可以重述為：“如果存在位置p2，使得p1和p2之間有一個(gè)NP，同時(shí)p2和p3之間有一個(gè)VP，那么p1和p3之間是一個(gè)S?！痹赑ROLOG中，這條規(guī)則可以表示為下面的公式。其中，變量采用大寫字母開頭的字符串表示：

s(P1, P3) :- np(P1, P2), vp(P2, P3)

為了建立這個(gè)分析過程，我們還要增加公理來列出句中所有的詞及其在句中的位置。例如，句子“John ate the cat”可以表述為：

word(john, 1, 2)

word(ate, 2, 3)

word(the, 3, 4)

word(cat, 4, 5)

詞典可以用一系列的謂詞來定義，結(jié)果如下：

isart(the)

isname(john)

isverb(ate)

isnoun(cat)

歧義詞會(huì)產(chǎn)生多個(gè)斷言——其中，每個(gè)斷言對(duì)應(yīng)它們所屬的一個(gè)句法類別。

對(duì)于每個(gè)句法類別，可以定義一個(gè)謂詞。該謂詞為真的惟一條件是，在兩個(gè)特定位置之間的詞語屬于該類別，如下所示：

n(l, O) :– word(Word, I, O), isnoun(Word)

art(I, O) :- word(Word, I, O), isart(Word)

v(I, O) :- word(Word, I, O), isverb(Word)

name(I, O) :- word(Word, I, O), isname(Word)

使用圖1所示的公理，通過證明謂詞s(1，5）為真，可以證明“John ate the cat”是一個(gè)合法的句子，證明過程見圖2。圖2中存在一些同名的不同變量，容易造成混淆，這時(shí)就給變量名加上一個(gè)單引號(hào)（'），使之惟一。這個(gè)句子中謂詞的證明流程和上下文無關(guān)文法的自頂向下分析流程是一致的，具體過程如下。任何時(shí)刻的待檢驗(yàn)狀態(tài)都可以表示為迄今為止需要檢驗(yàn)的子目標(biāo)列表。目標(biāo)描述中已經(jīng)包含了詞的位置，因此在分析流程中，就不需要增加單獨(dú)的列來記錄詞語的位置信息。后備狀態(tài)也是采用子目標(biāo)列表來表示的，由一個(gè)類似PROLOG的系統(tǒng)自動(dòng)維護(hù)，并用來實(shí)現(xiàn)回溯過程。在這種系統(tǒng)中，典型的證明過程在任何時(shí)刻僅僅給出當(dāng)前的狀態(tài)。

圖1 語法3.4基于PROLOG的表示

標(biāo)準(zhǔn)PROLOG搜索策略與深度優(yōu)先的自頂向下的句法分析策略一樣。因此，采用PROLOG構(gòu)造的句法分析器與后者的計(jì)算復(fù)雜度都為C”，即以計(jì)算的步數(shù)為底，輸入句子的長度為指數(shù)。實(shí)際上，即使是在最壞的情況下，基于PROLOG的語法也是非常高效的?？梢钥紤]加入類似chart的機(jī)制來進(jìn)一步提高算法的效率。當(dāng)然，這樣做的結(jié)果會(huì)喪失上下文無關(guān)規(guī)則與PROLOG規(guī)則之間的一些簡單聯(lián)系。

圖2“John ate the cat”基于PROLOG算法的句法分析流程

嘗試使用PROLOG寫一些簡單的語法，這是一件很值得我們?nèi)プ龅氖虑?。由此，可以更好地理解自頂向下的深度?yōu)先搜索方法。通過PROLOG的跟蹤工具，能得到和圖2類似的算法運(yùn)行過程。

責(zé)任編輯：admin