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

S→ NP VP

采用公理的形式，這條規(guī)則可以重新表述為：“一個詞的序列是合法的S。前提是該序列開頭部分是一個合法的名詞短語，其后跟著一個合法的動詞短語。”如果按照位置順序給句中的每個詞編號，這個規(guī)則可以重述為：“如果存在位置p2，使得p1和p2之間有一個NP，同時p2和p3之間有一個VP，那么p1和p3之間是一個S。”在PROLOG中，這條規(guī)則可以表示為下面的公式。其中，變量采用大寫字母開頭的字符串表示：

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

為了建立這個分析過程，我們還要增加公理來列出句中所有的詞及其在句中的位置。例如，句子“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)

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

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

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

圖1 語法3.4基于PROLOG的表示

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

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

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

責任編輯：admin