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

摘 要：首先，介绍上下文无关语法系统，指出基于上下文无关语法的各种算法，具体分析Earley算法的实现过程。然后，建立词库和产生式规则库，结合实际例句，运用Earley算法完成一个英语句法剖析系统的全过程。利用该句法剖析系统，能对结构比较常用的英语句子进行剖析，并得到句子可能的句法结构。当然，本系统还存在规模不大和消歧等问题，有待进一步深入研究。

关键词：自然语言；上下文无关语法；Earley算法；句法剖析

中国分类号：TN919 文献标识码 ：A

文章编号：10053824（2013）01008404

0 引 言

自然语言就是人类使用的各种语言，是人类交流和学习的重要工具。第一台电子计算机诞生后不久，人们就开始思考是否可以借助计算机来处理自然语言，并随之产生了一门新兴的学科――自然语言理解（natural language understanding），它研究使用电子计算机来模拟人类处理语言的过程，使计算机能理解和运用人类的自然语言，并最终实现机器翻译、人机之间的自然语言通信等目标。为了使计算机能理解人类的话语，首先要通过语音识别来识别人类说话的声音，并将声音转换成相应的自然语言的字串；然后，再对字串进行分词处理，把字串分成一个个独立的具有实际意义的自然语言的词；此后，再对得到的词串进行语法分析，获得句子的准确的语法结构；最后，对句子进行语义分析，从而获得人类所说的话语的意义。本文主要分析自然语言的语法问题，并通过实际的编程语言来实现对自然语言的语法分析。

1 上下文无关语法及各种剖析算法

1.1 上下文无关语法

，从直观上说，这样的状态说明剖析算法已经成功找到了在输入的某个跨度上的一个特定的语法范畴。完成（completer）操作的目标就是查找输入中在这个位置的语法范畴，发现并且推进前面造出的所有状态。造新的状态时可以复制老的状态，但是要把点规则中的点跨过所预测的范畴向前推进[67]。

2 句法剖析器的实现

2.1 词库

词库包含单词表、词性标记集表、单词类型表、短语表、短语类型表、不规则名词表、不规则动词表、形容词的非规则比较级和最高级表、副词的非规则比较级和最高级表。

其中单词表包含6级全部词汇。

单词的词性标方面我们参考了Brown语料库的Penn Treebank的标记集，并在它的基础上做了一些改变。例如，在Penn Treebank标记集中，动词原型统一表示为VB，而我们给及物动词原型的标记为VTB，给不及物动词原形的标记为VIB，并且取消动词原形标记VB。

在单词类型表中，我们将根据单词的词性分别给每个单词赋以相应的标记。

同理，根据短语在句子中可能充当的角色，在短语类型表中给短语赋以相应的标记。

2.2 产生式规则

我们一共给出了48条产生式规则，描述了英语中句子或短语最通常的组成结构。

例如：S- >SUB VIB，其中：S表示句子，SUB表示主语，VIB 表示不及物动词。这样一个产生式规则表示一个句子可以由一个主语加上一个不及物动词组成。

2.3 详细的剖析步骤

这个系统的核心部分就是Earley算法。下面，我们将举出一个例子，并且给出详细的剖析步骤。

我们给出的例句是： He eats an apple.

经过前期处理后，我们将得到一个二维数组，如表1所示。

备注：S表示句子，SUB表示主语，VIB表示不及物动词原形，VTB表示及物动词原形，OBJ表示宾语，COP表示系动词，predi表示谓语，NP表示名词短语，PP表示人称代名词，NN表示名词，det表示限定性名词，nominal表示名词性成分，NN表示名词。

3 结束语

本文讨论的系统对英文句法剖析进行了一次尝试，取得了不错的效果，只要符合规则库中规则的英语句子，大约80%都可以剖析成功，但是仍然有大约20%的句子不能得到唯一的一个剖析结果，从而产生结构歧义。

但是本系统的规模不大，单词只有6 500多个，短语500多个，在产生式规则方面也未能完整地描述英语中所有的语法现象，这些方面还比较薄弱。最关键的是，使用Earley算法进行句法剖析的时候，一个句子有可能会得到多个结构，但是准确的结构只有一个，本文并未解决这个问题。总而言之，这个系统还有待扩充和进一步完善。参考文献：

[1] JURAFSKY D，MARTIN J H .自然语言处理综论[M]. 冯志伟，译.北京：电子工业出版社，2005：178246.

[2] 冯志伟.机器翻译研究[M].北京：中国对外翻译出版公司，2004：155243.

[3] 蒋岩，潘海华.形式语义学引论[M].北京：中国社会科学出版社，1998：4196.

[4] 王广义.机器翻译系统文法中语法和语义研究[J].中文信息学报，1999，13 （6）：15.

[5] 马竹根. 一种自然语言理解中语法分析的算法设计和实现[J].计算机时代， 2005（10）：13.

[6] 顾奎.浅析英语句法歧义[J].安徽水利水电职业技术学院学报，2006，6 （1）： 8890.

[7] 谷波，李茹，刘开瑛.采用空测策略的Earley算法[J].计算机科学， 2010，37（1）： 229232.