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

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