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

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