基于Earley算法的英語句法剖析系統(tǒng).doc

基于Earley算法的英語句法剖析系統(tǒng)唐建 趙川（成都理工大學計算機科學與技術學院,成都,610059）摘要：本文研究的是，使用基于上下文無關文法的Earley算法對英語句子進行分析，并得到句子準確的語法結構。為此，我們建立了詞庫，產生式規(guī)則庫，并運用Earley算法實現(xiàn)了一個英語句法剖析系統(tǒng)。利用該句法剖析系統(tǒng)，我們能對結構比較常用的英語句子進行剖析，并得到句子可能的句法結構。 關鍵字：自然語言；上下文無關語法；Earley算法；句法剖析； English syntactic analysis system based on Earley AlgorithmTang Jian Zhao Chuan(College of Computer Science and Technology, Chengdu University of Technology ,Chengdu 610059)Abstract: The topic of this paper is using Earley Algorithm based on Context-Free Gramar to analyse english sentence and get the correct structure of sentence. Therefore,We established a words library,a rule library and realized a English syntactic analysis system by using Earley Algorithm.Using this system,We can analyse usual English structure and get the correct structure of sentence.Key Words: Natural Language Understanding; Context-Free Gramar; Earley Algorithm; Syntactic analysis1 引言 自然語言就是人類使用的各種語言，是人類交流和學習的重要工具。第一臺電子計算機誕生后不久，人們就開始思考是否可以借助計算機來處理自然語言，并隨之產生了一門新興的學科自然語言理解(Natural Language Understanding)，它研究使用電子計算機來模擬人類處理語言的過程，使計算機能理解和運用人類的自然語言，并最終實現(xiàn)機器翻譯、人機之間的自然語言通信等目標。為了使計算機能理解人類的話語，首先要通過語音識別來識別人類說話的聲音，并將聲音轉換成相應的自然語言的字串；然后，再對字串進行分詞處理，把字串分成一個個獨立的具有實際意義的自然語言的詞；此后，再對得到的詞串進行語法分析，獲得句子的準確的語法結構；最后，將對句子進行語義分析，從而獲得人類所說的話語的意義。本文主要分析自然語言的語法問題，并通過實際的編程語言來實現(xiàn)對自然語言的語法分析。2 上下文無關語法及各種剖析算法2.1 上下文無關語法模擬英語和其他自然語言成分結構的最常用數(shù)學系統(tǒng)是上下文無關語法(Context-Free Gramar)，它是美國語言學家喬姆斯基(N.Chomsky) 在上世紀50年代根據(jù)公理化方法提出的一種語言的形式描述理論。上下文無關語法又稱為短語結構語法(Phrase Structure Grammar)1。一個上下文無關語法由一套規(guī)則(rule)或產生式(production)以及單詞和符號的一個詞表(lexicon)組成1，每個規(guī)則表示語言中的符號的組成和排序方式。例如一個名詞詞組(NP)可以由一個限定詞(Det)和一個名詞性成分(Nominal)組成，那么這個產生式規(guī)則就可以寫為：NP - Det Nominal。產生式規(guī)則中有兩類符號，一類是表示具體的詞類，例如Det，它在產生式規(guī)則中不能再繼續(xù)擴展，它們被稱之為終極符號；而另一類，必須被繼續(xù)展開，例如NP和Nominal,它們被稱之為非終極符號。2.2 基于上下文無關語法的各種句法剖析算法在自然語言處理中，所謂句法剖析(Syntactic Parsing)，就是根據(jù)已經給出的上下文無關的產生式規(guī)則和詞表來識別一個輸入句子并且給這個句子指派一個正確的句法結構(例如，樹形圖，線圖)的過程2。一個句子，通過句法剖析，很有可能得到若干個句法結構，當然只有一個是準確的，我們可以繼續(xù)通過語義消歧等策略來找出唯一正確的結構，但這部分內容本文將不會進行討論?；谏舷挛臒o關語法的句法剖析算法有很多，例如自底向上剖析算法、自頂向下剖析算法、Earley算法(Earley于1970年提出)，CYK算法(Cocke-Younger-Kasami的簡寫)，富田算法(卡內基-梅隆大學的計算語言學家富田勝于1985年提出)。2.3 Earley算法標準的自底向上剖析和自頂向下剖析面臨著三個難題：左遞歸規(guī)則、歧義子樹重復剖析、無效子樹重復剖析，而Earley算法可以解決上述三個問題1。Earley算法是一種動態(tài)規(guī)劃算法，它的核心是一個從左到右的傳遞，它填充一個稱為線圖的二維數(shù)組Chartij，如果輸入句子中有N個單詞，則i=N+1。我們需要使用產生規(guī)則來對輸入的句子的結構進行自頂向下的預測，搜索所有可能的結構，在這樣的一個過程中，我們要向Chart數(shù)組中寫入狀態(tài)來準確的描述這樣的一個搜索過程。這種狀態(tài)包含三部分信息：1. 一個產生式規(guī)則。2. 這個產生規(guī)則所對應的句子中的成分在句子中所處的位置。3. 這個產生式規(guī)則中已經分析完成部分在整個句子中的位置，這里我們用一個點來標識這個位置，這樣形成的結構稱為點規(guī)則。為了解釋上述內容，我們給出下面這個例子： 圖 2-1 例句(Book that flight)剖析圖如圖 2-1所示，這個輸入句子為Book that flight，共有0、1、2、3 共四個狀態(tài)位。NP-Det.Nominal 1,2 是Chart數(shù)組中的一個狀態(tài)，其中NP-Det Nominal 是一個產生式規(guī)則；后面括號中的第一個數(shù) “1”表示NP 所對應的成分that flight在整個句子中處于1號狀態(tài)位的位置；括號中第二個數(shù)字“2”表示，Det已經完成分析，即已經找到Det對應that，接下來將要對Nominal進行分析，此時點的位置恰好對應句子的的2號狀態(tài)位。Earley剖析算法的基本操作是以從左向右的方式走過線圖中的由N+1(N為句子中的單詞個數(shù))個狀態(tài)組成的集合,按順序處理每個集合中的各個狀態(tài)。在每一步,根據(jù)具體情況將預測、掃描、完成這三個操作中的一個應用于每個狀態(tài)。直到在Chartij的最后一個一維數(shù)組中出現(xiàn)一個狀態(tài)S-. 0,N表示剖析已經成功。其中表示的是一個產生式規(guī)則的右邊部分1。預測、掃描、完成這三個操作中，預測(Predictor)的任務是造出一個新的狀態(tài)來表示在剖析過程中生成的自頂向下的預測1。預測應用于點規(guī)則中點的右側為非終極符號的情形。例如對狀態(tài)S-.VP 0,0進行預測，那么將會得到的其中一個預測結果是VP-.VTB NP 0,0,其中VTB表示及物動詞原型。當點規(guī)則中點的右側為終極符號(詞類范疇)時，就調用掃描(Scanner)來檢查輸入的符號串，并把對應于所預測的詞類范疇的狀態(tài)加入到線圖中，并且把點規(guī)則中的點跨過所遇見的輸入范疇，向前移動一個位置1。例如:VP-.VTB NP 0,0時，因為點后面的范疇是詞類，所以調用掃描操作在輸入中查找當前的單詞，而book是一個及物動詞，它與當前狀態(tài)中的預測相匹配，其結果是造出一個新的狀態(tài)VP-VTB.NP 0,1。當一個狀態(tài)中的點到達規(guī)則的右端時，從直觀上說，這樣的狀態(tài)說明剖析算法已經成功找到了在輸入的某個跨度上的一個特定的語法范疇。完成(Completer)操作的目標就是查找輸入中在這個位置的語法范疇，發(fā)現(xiàn)并且推進前面造出的所有狀態(tài)。造新的狀態(tài)時可以復制老的狀態(tài)，但是要把點規(guī)則中的點跨過所預測的范疇向前推進1。3 句法剖析器的實現(xiàn)3.1 詞庫詞庫包含單詞表、詞性標記集表、單詞類型表、短語表、短語類型表、不規(guī)則名詞表、不規(guī)則動詞表、形容詞的非規(guī)則比較級最高級表、副詞的非規(guī)則比較級最高級表。其中單詞表包含6級全部詞匯。單詞的詞性標方面我們參考了Brown語料庫的Penn Treebank的標記集，并在它的基礎上做了一些改變。例如，在Penn Treebank標記集中，動詞原型統(tǒng)一表示為VB，而我們給及物動詞原型的標記為VTB，給不及物動詞原形的標記為VIB，并且取消動詞原形標記VB。在單詞類型表中，我們將根據(jù)單詞的詞性分別給每個單詞賦以相應的標記。同理，根據(jù)短語在句子中可能充當?shù)慕巧?，在短語類型表中給短語賦以相應的標記。3.2 產生式規(guī)則我們的一共給出了48條產生式規(guī)則，描述了英語中句子或短語最通常的組成結構。例如: S-SUB VIB 其中，S表示句子，而SUB表示主語，VIB 表示不及物動詞，這樣一個產生式規(guī)則表示一個句子可以由一個主語加上一個不及物動詞組成。3.3 詳細的剖析步驟這個系統(tǒng)的核心部分就是Earley算法。下面，我們將舉出一個例子，并且給出詳細的剖析步驟。我們給出的例句是: He eats an apple.經過前期處理后，我們將得到一個二維數(shù)組，我們用表格描述如下：表 3-1 詞性標記數(shù)組詞標記hePPeatVTBanDetappleNN 在此基礎上，我們使用Earley算法來進行分析，以下是詳細的剖析步驟。 表3-2 Chart0 線圖的第一個一維數(shù)組規(guī)則操作S-.SUB VIB0,0PredictorS-.SUB VTB OBJ0,0PredictorS-.SUB COP PREDI0,0Predictor.SUB-. NP0,0PredictorSUB-. PP0,0Predictor.NP-.NN0,0Predictor我們首先從S開始預測，根據(jù)產生式規(guī)則，我們可以得到S-.SUB VIB、S-.SUB VTB OBJ這樣的結果，并把結果加入Chart0中，當然結果還不止這些，我們使用“.”略去其他的預測結果，當S所有可能性都預測完了，就取出第一條規(guī)則，因為點號右邊的符號“SUB”不是詞類范疇，所以對它進行預測，并把得到預測結果加入Chart0中。同理，再對SUB-. NP中的點右邊的NP進行預測，得到NP-.NN。然后再處理SUB-. PP，發(fā)現(xiàn)點右邊的是具體的詞類范疇PP，此時就調用“掃描”操作，在“表 3-1詞性標記數(shù)組”中發(fā)現(xiàn)數(shù)組第0單元中的he正是PP類型，與我們的預測是一致的，這樣就將掃描操作的結果加入到Chart1中。需要注意的是，此時點的位置已經移到1號位。 表3-3 Chart1 線圖的第二個一維數(shù)組 規(guī)則操作PP -he.0,1ScannerSUB- PP.0,1CompleterS-SUB. VIB0,1CompleterS-SUB. VTB OBJ0,1Completer.“PP-he. 0,1”表示我們已經完成了從0號位到1號位跨度的分析，根據(jù)這個結果，我們要調用“完成”操作，推進前面造出的狀態(tài)，在這里，就是“SUB-. PP”，我們把點號從0號位移到1號位置，表示PP已經被分析完成，這樣將得到“SUB- PP.”。同理繼續(xù)調用“完成”操作，繼續(xù)推進狀態(tài)，得到“S-SUB. VIB”，“ S-SUB. VTB OBJ”等。因為VTB是具體的詞類范疇，所以調用“掃描” 操作，在“表 3-1詞性標記數(shù)組”中發(fā)現(xiàn)數(shù)組第1單元中的eat 是VTB，這樣講掃描結果加入到Chart2中，點號向前推進。 表3-4 Chart2 線圖的第三個一維數(shù)組規(guī)則操作VTB-eat.1,2ScannerS-SUB VTB. OBJ0,2CompleterOBJ-.NP2,2PredictorOBJ-. PP2,2Predictor.NP-. Det Nominal2,2Predictor根據(jù)“VTB-eat.”調用“完成”操作，向前推進狀態(tài)，得到“S-SUB VTB. OBJ”，然后，再先后對OBJ、NP進行預測，得到“NP-. Det Nominal”，此時點號右邊的Det是具體的詞類范疇，調用“掃描”操作，得到“Det-an.”并填入Chart3中，點號向前推進。 表3-5 Chart3 線圖的第四個一維數(shù)組規(guī)則操作Det-an.2,3ScannerNP-Det. Nominal2,3CompleterNominal-.NN3,3PredictorNominal-.NN Nominal3,3Predictor根據(jù)“Det-an.”，我們調用“完成”操作，得到“NP-Det. Nominal”，然后再對Nominal進行預測。根據(jù)“Nominal-.NN”，我們調用掃描操作，得到“NN-apple.” 并填入Chart4中，點號向前推進。 表3-6 Chart4 線圖的第五個一維數(shù)組規(guī)則操作NN-apple.3,4ScannerNominal-NN.3,4CompleterNominal-NN.Nominal3,4CompleterNP-Det Nominal.2,4CompleterOBJ-NP.2,4CompleterS-SUB VTB OBJ.0,4Completer 根據(jù)“NN-apple.”連續(xù)調用“完成操作”，得到“S-SUB VTB OBJ.”，這是一個表示剖析成功的狀態(tài)。如果在整個剖析結束的時候，只有一個成功的狀態(tài)，這表示我們得到了這個句子準確的結構，否則的話，表示句子結構有歧義，必須進行消歧。但消歧策略，在這里，我們不做討論。備注：S表示句子，SUB表示主語，VIB表示不及物動詞原形，VTB表示及物動詞原形，OBJ表示賓語，COP表示