基于Earley算法的英语句法剖析系统.doc

基于Earley算法的英语句法剖析系统唐建 赵川（成都理工大学计算机科学与技术学院,成都,610059）摘要：本文研究的是，使用基于上下文无关文法的Earley算法对英语句子进行分析，并得到句子准确的语法结构。为此，我们建立了词库，产生式规则库，并运用Earley算法实现了一个英语句法剖析系统。利用该句法剖析系统，我们能对结构比较常用的英语句子进行剖析，并得到句子可能的句法结构。 关键字：自然语言；上下文无关语法；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)，它研究使用电子计算机来模拟人类处理语言的过程，使计算机能理解和运用人类的自然语言，并最终实现机器翻译、人机之间的自然语言通信等目标。为了使计算机能理解人类的话语，首先要通过语音识别来识别人类说话的声音，并将声音转换成相应的自然语言的字串；然后，再对字串进行分词处理，把字串分成一个个独立的具有实际意义的自然语言的词；此后，再对得到的词串进行语法分析，获得句子的准确的语法结构；最后，将对句子进行语义分析，从而获得人类所说的话语的意义。本文主要分析自然语言的语法问题，并通过实际的编程语言来实现对自然语言的语法分析。2 上下文无关语法及各种剖析算法2.1 上下文无关语法模拟英语和其他自然语言成分结构的最常用数学系统是上下文无关语法(Context-Free Gramar)，它是美国语言学家乔姆斯基(N.Chomsky) 在上世纪50年代根据公理化方法提出的一种语言的形式描述理论。上下文无关语法又称为短语结构语法(Phrase Structure Grammar)1。一个上下文无关语法由一套规则(rule)或产生式(production)以及单词和符号的一个词表(lexicon)组成1，每个规则表示语言中的符号的组成和排序方式。例如一个名词词组(NP)可以由一个限定词(Det)和一个名词性成分(Nominal)组成，那么这个产生式规则就可以写为：NP - Det Nominal。产生式规则中有两类符号，一类是表示具体的词类，例如Det，它在产生式规则中不能再继续扩展，它们被称之为终极符号；而另一类，必须被继续展开，例如NP和Nominal,它们被称之为非终极符号。2.2 基于上下文无关语法的各种句法剖析算法在自然语言处理中，所谓句法剖析(Syntactic Parsing)，就是根据已经给出的上下文无关的产生式规则和词表来识别一个输入句子并且给这个句子指派一个正确的句法结构(例如，树形图，线图)的过程2。一个句子，通过句法剖析，很有可能得到若干个句法结构，当然只有一个是准确的，我们可以继续通过语义消歧等策略来找出唯一正确的结构，但这部分内容本文将不会进行讨论。基于上下文无关语法的句法剖析算法有很多，例如自底向上剖析算法、自顶向下剖析算法、Earley算法(Earley于1970年提出)，CYK算法(Cocke-Younger-Kasami的简写)，富田算法(卡内基-梅隆大学的计算语言学家富田胜于1985年提出)。2.3 Earley算法标准的自底向上剖析和自顶向下剖析面临着三个难题：左递归规则、歧义子树重复剖析、无效子树重复剖析，而Earley算法可以解决上述三个问题1。Earley算法是一种动态规划算法，它的核心是一个从左到右的传递，它填充一个称为线图的二维数组Chartij，如果输入句子中有N个单词，则i=N+1。我们需要使用产生规则来对输入的句子的结构进行自顶向下的预测，搜索所有可能的结构，在这样的一个过程中，我们要向Chart数组中写入状态来准确的描述这样的一个搜索过程。这种状态包含三部分信息：1. 一个产生式规则。2. 这个产生规则所对应的句子中的成分在句子中所处的位置。3. 这个产生式规则中已经分析完成部分在整个句子中的位置，这里我们用一个点来标识这个位置，这样形成的结构称为点规则。为了解释上述内容，我们给出下面这个例子： 图 2-1 例句(Book that flight)剖析图如图 2-1所示，这个输入句子为Book that flight，共有0、1、2、3 共四个状态位。NP-Det.Nominal 1,2 是Chart数组中的一个状态，其中NP-Det Nominal 是一个产生式规则；后面括号中的第一个数 “1”表示NP 所对应的成分that flight在整个句子中处于1号状态位的位置；括号中第二个数字“2”表示，Det已经完成分析，即已经找到Det对应that，接下来将要对Nominal进行分析，此时点的位置恰好对应句子的的2号状态位。Earley剖析算法的基本操作是以从左向右的方式走过线图中的由N+1(N为句子中的单词个数)个状态组成的集合,按顺序处理每个集合中的各个状态。在每一步,根据具体情况将预测、扫描、完成这三个操作中的一个应用于每个状态。直到在Chartij的最后一个一维数组中出现一个状态S-. 0,N表示剖析已经成功。其中表示的是一个产生式规则的右边部分1。预测、扫描、完成这三个操作中，预测(Predictor)的任务是造出一个新的状态来表示在剖析过程中生成的自顶向下的预测1。预测应用于点规则中点的右侧为非终极符号的情形。例如对状态S-.VP 0,0进行预测，那么将会得到的其中一个预测结果是VP-.VTB NP 0,0,其中VTB表示及物动词原型。当点规则中点的右侧为终极符号(词类范畴)时，就调用扫描(Scanner)来检查输入的符号串，并把对应于所预测的词类范畴的状态加入到线图中，并且把点规则中的点跨过所遇见的输入范畴，向前移动一个位置1。例如:VP-.VTB NP 0,0时，因为点后面的范畴是词类，所以调用扫描操作在输入中查找当前的单词，而book是一个及物动词，它与当前状态中的预测相匹配，其结果是造出一个新的状态VP-VTB.NP 0,1。当一个状态中的点到达规则的右端时，从直观上说，这样的状态说明剖析算法已经成功找到了在输入的某个跨度上的一个特定的语法范畴。完成(Completer)操作的目标就是查找输入中在这个位置的语法范畴，发现并且推进前面造出的所有状态。造新的状态时可以复制老的状态，但是要把点规则中的点跨过所预测的范畴向前推进1。3 句法剖析器的实现3.1 词库词库包含单词表、词性标记集表、单词类型表、短语表、短语类型表、不规则名词表、不规则动词表、形容词的非规则比较级最高级表、副词的非规则比较级最高级表。其中单词表包含6级全部词汇。单词的词性标方面我们参考了Brown语料库的Penn Treebank的标记集，并在它的基础上做了一些改变。例如，在Penn Treebank标记集中，动词原型统一表示为VB，而我们给及物动词原型的标记为VTB，给不及物动词原形的标记为VIB，并且取消动词原形标记VB。在单词类型表中，我们将根据单词的词性分别给每个单词赋以相应的标记。同理，根据短语在句子中可能充当的角色，在短语类型表中给短语赋以相应的标记。3.2 产生式规则我们的一共给出了48条产生式规则，描述了英语中句子或短语最通常的组成结构。例如: S-SUB VIB 其中，S表示句子，而SUB表示主语，VIB 表示不及物动词，这样一个产生式规则表示一个句子可以由一个主语加上一个不及物动词组成。3.3 详细的剖析步骤这个系统的核心部分就是Earley算法。下面，我们将举出一个例子，并且给出详细的剖析步骤。我们给出的例句是: He eats an apple.经过前期处理后，我们将得到一个二维数组，我们用表格描述如下：表 3-1 词性标记数组词标记hePPeatVTBanDetappleNN 在此基础上，我们使用Earley算法来进行分析，以下是详细的剖析步骤。 表3-2 Chart0 线图的第一个一维数组规则操作S-.SUB VIB0,0PredictorS-.SUB VTB OBJ0,0PredictorS-.SUB COP PREDI0,0Predictor.SUB-. NP0,0PredictorSUB-. PP0,0Predictor.NP-.NN0,0Predictor我们首先从S开始预测，根据产生式规则，我们可以得到S-.SUB VIB、S-.SUB VTB OBJ这样的结果，并把结果加入Chart0中，当然结果还不止这些，我们使用“.”略去其他的预测结果，当S所有可能性都预测完了，就取出第一条规则，因为点号右边的符号“SUB”不是词类范畴，所以对它进行预测，并把得到预测结果加入Chart0中。同理，再对SUB-. NP中的点右边的NP进行预测，得到NP-.NN。然后再处理SUB-. PP，发现点右边的是具体的词类范畴PP，此时就调用“扫描”操作，在“表 3-1词性标记数组”中发现数组第0单元中的he正是PP类型，与我们的预测是一致的，这样就将扫描操作的结果加入到Chart1中。需要注意的是，此时点的位置已经移到1号位。 表3-3 Chart1 线图的第二个一维数组 规则操作PP -he.0,1ScannerSUB- PP.0,1CompleterS-SUB. VIB0,1CompleterS-SUB. VTB OBJ0,1Completer.“PP-he. 0,1”表示我们已经完成了从0号位到1号位跨度的分析，根据这个结果，我们要调用“完成”操作，推进前面造出的状态，在这里，就是“SUB-. PP”，我们把点号从0号位移到1号位置，表示PP已经被分析完成，这样将得到“SUB- PP.”。同理继续调用“完成”操作，继续推进状态，得到“S-SUB. VIB”，“ S-SUB. VTB OBJ”等。因为VTB是具体的词类范畴，所以调用“扫描” 操作，在“表 3-1词性标记数组”中发现数组第1单元中的eat 是VTB，这样讲扫描结果加入到Chart2中，点号向前推进。 表3-4 Chart2 线图的第三个一维数组规则操作VTB-eat.1,2ScannerS-SUB VTB. OBJ0,2CompleterOBJ-.NP2,2PredictorOBJ-. PP2,2Predictor.NP-. Det Nominal2,2Predictor根据“VTB-eat.”调用“完成”操作，向前推进状态，得到“S-SUB VTB. OBJ”，然后，再先后对OBJ、NP进行预测，得到“NP-. Det Nominal”，此时点号右边的Det是具体的词类范畴，调用“扫描”操作，得到“Det-an.”并填入Chart3中，点号向前推进。 表3-5 Chart3 线图的第四个一维数组规则操作Det-an.2,3ScannerNP-Det. Nominal2,3CompleterNominal-.NN3,3PredictorNominal-.NN Nominal3,3Predictor根据“Det-an.”，我们调用“完成”操作，得到“NP-Det. Nominal”，然后再对Nominal进行预测。根据“Nominal-.NN”，我们调用扫描操作，得到“NN-apple.” 并填入Chart4中，点号向前推进。 表3-6 Chart4 线图的第五个一维数组规则操作NN-apple.3,4ScannerNominal-NN.3,4CompleterNominal-NN.Nominal3,4CompleterNP-Det Nominal.2,4CompleterOBJ-NP.2,4CompleterS-SUB VTB OBJ.0,4Completer 根据“NN-apple.”连续调用“完成操作”，得到“S-SUB VTB OBJ.”，这是一个表示剖析成功的状态。如果在整个剖析结束的时候，只有一个成功的状态，这表示我们得到了这个句子准确的结构，否则的话，表示句子结构有歧义，必须进行消歧。但消歧策略，在这里，我们不做讨论。备注：S表示句子，SUB表示主语，VIB表示不及物动词原形，VTB表示及物动词原形，OBJ表示宾语，COP表示