一个用于机器人自然语言理解的英语句法分析系统

? 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. 1f67e2d4b14e852458fb57b3 1996年11月机器人　ROBO T 　N ov .,19960中国科学院机器人学开放研究实验室基金资助项目.1995-12-05收稿

一个用于机器人自然语言理解的英语句法分析系统0

张嘉音

(中国科学院沈阳自动化研究所　110015)

摘　要　在低挡微机中速度较慢的串行处理硬设备条件下,利用本文提出的启发式概念,分层搜索和匹配策略以及设置最大搜索长度等方法,可使推理速度提高一个数量级以上.此外,通过引入语义信息,分阶段消除歧义,自顶向下与自底向上相结合,以及把一般疑问句一律变成相应陈述句的方法,解决了自动英语句法分析中的一系列难题,缩小了知识库的规模.

关键词　上下文有关文法,分析策略和搜索策略,最大搜索长度,推理速度,启发式处理

1　引言

自然语言理解研究的是怎样用计算机理解自然语言,其目标是构造出具有人的理解能力的计算机系统.本文讨论的是对书面语言的理解.机器人在“理解”英语这种自然语言的过程中,句法分析是必不可少的.机器人的接收到一个英语名子后,经过句法分析,就知道了句中哪个部分是主语和谓语,哪个部分是宾语、定语、状语等.而这些都是通过语法树来表示的.

实质上,句法分析的作用就是把英语句子中单词之间线性顺序的表层结构转换成用语法树这种数据结构来表示的深层结构,这对于机器人“理解”英语这一自然语言以及最终实现英汉翻译机器人这一很可能是跨世纪的研究课题来说,都迈出了具有重要意义的一步.实际上,有相当多的英语句子,一旦正确地分析出其句法结构,只要从存放在计算机内的英汉字典中查出每个单词或词组的第一个汉译,就可得到比较通顺的译文.

除翻译机器人外,其他机器人所面对的语言环境只是自然英语全集中的一个子集,子集中的句子都是比较简单的.这就在某种程度上减少了问题的复杂性,有利于把主要精力集中到那些当前必须解决的难点上去.英语句法分析的主要难点之一在于英语单词的多词性特征.如单词L ike 就具有下列6种词性及相应的汉译:11动词(喜欢);21名词(爱好);31形容词(相像的);41副词(可能,多半);51介词(像);61连词(如同,好像).下面给出相应的例句.

11I like s m ok ing .(及物动词)

Do as you like .(不及物动词)

21H is likes and dislikes 1(名词)

31T he tw o bu ilding are very like .(形容词)

41V ery like ,he w ill com e tom o rrow .(副词)

51Don’t treat m e like a guest .(介词)

61I hop e I can do it like you do .(连词)

在利用英语句法知识库对英语句子进行句法分析时,必须用到句中每个单词的词性及相邻单词之间的词性搭配关系.若不希望出现遗漏,可顺序取出单词的每一种词性及其各种组合,并与知识库中的规则进行匹配.单词的词性越多,则所需搜索的状态空间就越大.例如,若

? 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. 1f67e2d4b14e852458fb57b3 一个英语句子由10个单词组成,每个单词有3种词性,则最大搜索次数为310,即59049次;若英语句子由20个单词组成,每个单词有2种词性,则最大搜索次数为220,即1048576次.因此,如何有效地减少搜索次数,提高搜索效率是英语句法分析系统中要解决的关键问题之一.2　系统概述

本系统是基于规则的数据驱动型推理系统,由知识库、综合数据库和控制程序3大部分组成.知识库包括一个含有10万多词条的机内英汉字典和15个英语句法分析规则库.综合数据库或称“黑板”,实际上是由多种不同的数据结构所组成的公共数据区,用来存放句法分析的中间结果和最终结果.控制程序是一个由9000多行源程序所组成的推理控制软件包,用C 语言书写.硬设备用的是一台8兆字节内存的386微机,在X I N EX 汉字操作系统的环境下工作

.2.1　工作流程

图1　一个英语例句的语法树

句法分析流程简图如图1所示.如果知

识库中所有的规则库已全部用完,仍不能生

成完整的句子,就说明当前读入的句子是不

合法句,句法分析以失败告终.

经过多次的成功匹配、归结和推理过

程,如果能够把读入的那个句子最后归结成

一个表示完整句子的符号Stc ,就证明句法

分析已成功地结束了,同时也得到了该句子

的语法树.

2.2　理论依据

根据形式语言和自动机理论,英语文法

G 可由一个四元组

　　(V N ,V T ,P roducti on ,Stc )

定义,其中:有限的非终极符集合

　V N ={Stc ,Sst ,V P ,N P ,P P ,AD P ,

M V p ,N ,V ,X ,A ,D ,P ,R ,M ,U ,C ,A rt ,In t ,M ark }上式等号右端花括号中的符号,按顺序分别表示:句子,子句,动词短语,名词短语,介词短语,形容词或副词短语,数量词短语,名词,动词,助动词,形容词,副词,介词,代词,数词,量词,连词,冠词,感叹词,以及标点符号.实际用到的符号要更复杂些,如,动词V 又细分为及物动词V t ,不及物动词V i ,双宾动词V d 等;代词R 又细分为人称代词R P ,物主代词RA h 等;副词D 又细分为时间副词D t ,地点副词D l 等;……有限的终极符集合

V T ={w o rd w o rd ∈dicti onary ∨w o rd ∈Punctuati on }

上式等号右端花括号中的dicti onary 表示存放在计算机中的英汉字典,Punctuati on 表示英语中所用到的各种标点符号的集合.

产生式规则集合P roducti on 包含英语句法知识库中的全部规则.起始符

S tc ∈V N

在集合VN 和V T 中不得含有相同的元素.

显然,并不是所有由英文字母,空格和标点符号所组成的符号串都是英语句子,英语句子333第18卷第6期张嘉音:　一个用于机器人自然语言理解的英语句法分析系统

? 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. 1f67e2d4b14e852458fb57b3

只是上述符号串全集中的一个子集.只有符合上述文法G 的符号串才是合法英语句.换句话说,机器人读入一个符号串之后,经过图2中的工作流程,有限次使用文法G 中的产生式规则,如果最后能归结成起始符S tc ,则称这个符号串是一个合法的英语句;否则,就是不合法句.

是

显示:“不合法句,拒收!”关闭当前规则库,打开下一个规则库,并令其为当前规则库

从匹配起点开始至句尾止,取每个

元素的第一个词性作为其当前词性

把匹配起点移至句中下一个元素

否是否已达到最大搜索长度?

是

否

是否已到达句子尾部?

是

不是是

当前规则库是否是最后一个?

是是否已搜索完全部状态空间?

否

找出下一个词性序列组合

失败

句法分析

结束

句法分析

成功

显示句法分析结果(语法树)是否已生成一个完整句子?

否

用新归结出的语法成份取代句中原来相应的元素组归结出一个较高层的语法成份并生成相应的新结点是

否

是否满足执行条件?

成功

失败

匹配成功否?

从当前规则库中下一条规则开始继续进行试匹配

从当前规则库中第一条规则开始逐一进行试匹配

令句中第一个元素为匹配起点

设置当前最大搜索长度

打开第一个规则库关命其为当前规则库

取句中每个词的第一个词性作为当前词性生成语法树的叶结点集合

查字典得到每个词的全部词性读入一个英语句子启动图2　英语句法分析流程简图

2.3　英语句法规则库

433　　　　机　器　人1996年11月

? 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. 1f67e2d4b14e852458fb57b3 本系统的英语句法规则库(以下简称规则库)中的规则由3部分组成:前提部分,由%a 引出,遇到下一个%结束;执行条件部分,由%i 引出,遇到下一个%结束;结论部分,由%i 引出,遇到!结束.前提部分和结论部分是每条规则都必须有的,而执行条件部分是可有可无的.当没有执行条件部分时就表示,只要能与前提部分匹配成功,则无条件地去执行其结论部分的动作.例如,在名词短语规则库中有这样两条规则:

%aR P %z N P (Cen t :R P )!

%aRA h [A ]+N %i m ark [＄3+1]……%z N P (Cen t :N ;det :RA h ;m odi :[A ]+;ch :N P (D et (RA h )A ([A ]+)@(N )))!

第一条规则表示,当前词性序列组合中,只要有任何一个元素是R P (人称代词),就能与本条规则匹配成功,并无条件地去执行结论部分的动作:归结成一个名词短语N P ,其中心词(Cen t )就是这个人称代词;第二条规则表示,在当前词性序列组合中,若以其中的某一个元素为匹配起点,第一个元素是物主代词RA h ,后面紧接着是0至n 个连续的形容词[A ]+,然后名词N ,就能与本条规则匹配成功.此条规则有执行条件部分,因此要检查是否满足执行条件.若满足,才能去执行结论部分的动作:归结成一个名词短语N P .本条规则中的执行条件部分没有写完全,已写出的m ark [＄3+1]是一个谓词公式(以下简称谓词),意思是,规则前提部分第三项后面紧接着的那一个元素(用＄1表示)如果是标点符号则本谓词的值为真;否则为假.在规则的执行条件部分有时还用到一些别的谓词,如检查句中某元素是否位于句首的谓词begin ,检查某元素的当前词性是否等于指定词性的谓词eq ,检查当前匹配起点前面是否存在指定类型动词的谓词leadv ,检查某动词短语中的动词是否为原形形式的谓词o rif 等.实际上,在执行条件部分用到的经常是好几个谓词用“与”、“或”、“非”符号连接起来所组成的条件表达式,只有当整个条件表达式的值为真时才去执行结论部分的动作.

在规则中引入执行条件后,就可以反映出产生式规则两端的上下文条件,这相当于

Chom sky 所定义的上下文有关文法中的产生式形式

[2]Α1A Α2→Α1ΒΑ2

中的上下文条件Α1和Α2

.因此,本句法分析系统中所采用的文法G 至少是一种上下文有关文法,它等价于一个确定状态的图灵机,故有能力用来描述、识别和分析英语这一种自然语言.它既能接收合法的英语句,又能拒收不合法句[1].

2.4　时间要求

对英语句子进行句法分析所需花费的时间与知识库中规则的数量以及英语句子的长度有关.句子长度对分析它所需时间的影响比规则数量的影响要大得多.分析时间至少与句子长度的平方成正比;在比较复杂的情况下,甚至与句子长度的立方成正比.需要指出的是,如果搜索策略和分析策略选择不当,则完成句法分析所需要的时间会更长[4].

3　分析策略和搜索策略

本系统是在低挡微机(386)上实现的,因此,如何千方百计地提高其推理速度是系统设计时要考虑的首要问题.

3.1　分析策略和启发式处理概念

分析策略可选用并行处理或回溯方式,自顶向下或自底向上.

本系统引入了“启发式处理”的概念.即,利用现有的串行处理CPU 硬件设备,自底向上5

33第18卷第6期张嘉音:　一个用于机器人自然语言理解的英语句法分析系统

? 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. 1f67e2d4b14e852458fb57b3 地用顺序推导的方式来模拟并行处理的功能.从宏观上说就是,先把英语句子中的每一个名词短语、形容词短语都归结出来,然后再逐步向高层推进、顺序归结出介词短语、副词短语、动词短语、简单句、子句、主从复合句或并列复合句.“启发式处理”方法的速度虽然没有真并行处理那样快,但同样可以遍历全体状态空间,不会因存在搜索不到的死角而找不到所存在的解.

与真并行处理不同,现在不是存储而是搜索所有可能出现的每一种组合情况,只保存匹配成功的句法结构,这就大大减少了对存储空间的需求.从微观上说“启发式处理”在具体的规则库中,可显示出其特有的优越性.例如,在动词短语规则库中有这样一条规则:

%a {V t ,3}N P %i m ark [＄2+1]%z V P (……)!

其中{V t ,3}表示与此项成功匹配的元素可以具有任意多种词性,但其中必须含有及物动词这一词性.假设一个英语句子中的某一个词具有多个词性,而恰巧其最后一个词性才是及物动词.有了这条规则后,就不再需要像本文引言中所说的那样,经过成千上万次搜索最后才找到这个词的及物动词词性,然后与另一条规则:

%a V t N P %i m ark [＄2+1]%z V P (……)!

匹配成功而归结成一个动词短语.显然,在本系统中引入“启发式处理”机制后,可使推理速度大为提高.

3.2　搜索策略

计算机的搜索时间的长短直接影响系统的工作效率.在本系统中,采用了下列搜索策略.第一,化整为零,分段搜索.知识库中规则越多搜索的时间越长.我们把整个知识库分割成许多独立的小规则库.在进行句法分析时,按照事先规定好的顺序,每次只搜索一个规则库.采用分段搜索策略,由于可避免每次都去搜索整个知识库,故可使总的搜索时间大大缩短.

第二,根据每个规则库的具体情况,设置不同的最大搜索长度.最大搜索长度由该规则库中前提部分最长的那一条规则决定.无论英语句子有多长,一旦超过最大搜索长度,一律停止继续搜索.这就从根本上扭转了当句子的长度增大时,对其进行句法分析所花费的时间呈恶性增长(至少与句子长度的平方或正比)的不利局面.

第三,对每个规则库中的各条规则,按下列优化原则排序;常用规则排在前面,以减少平均搜索时间;当有多条规则其前提部分的头部相同时,按前提部分长度递减的顺序排列,使长规则比短规则优先得到匹配,从而实现既可缩减执行条件部分的内容又可避免出错;同理,当有多条规则的前提部分完全相同时,则把执行条件最苛刻的排在前面,次苛刻的排在中间,最宽松的排在后面,无条件的排在最后.

3.3　小结

本系统采用自底向上方式,利用启发信息实现分层、分阶段地搜索和匹配.在每一层中通过一个由句首开始从左向右逐步移动的机制和设置最大搜索长度的办法来进一步缩小状态空间,在此基础上再采用宽度优先搜索方式遍历有可能存在解的全部状态空间.同时引入“启发式处理”的概念,在速度较慢的串行处理硬设备条件下可把推理速度提高一个数量级以上.原来需要3分多钟才能分析完的句子,现在不到10秒钟就可分析完毕.上面所说的启发信息,实际上是很容易理解的,那就是:句子是由各种短语组成的,短语是由相邻或不相邻的词组成的,而所有这些句子成份都是可以分阶段、分层次进行分析和处理的.这也是我们把知识库分割成许多小规则库的依据.

633　　　　机　器　人1996年11月

? 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. 1f67e2d4b14e852458fb57b3 4　其他设计特点

本系统引入时间和地点的语义信息,解决了介词短语中单纯靠文法很难解决的一大批时间和地点状态语的分析难题.对于具有句法二义性的短语成份(如,how ,long ),则采用分阶段消除歧义的方法,在短语分析和句子分析阶段逐步解决.此外,对于某些结构特殊的句子,如特殊疑问句和不是由连词加句子而是通过改变语序所形成的子句等,无法完全按自底向上的顺序分析;为此,专门设计了一种机制,实现了局部上自顶向下的处理功能.本系统还把39种不同类型的一般疑问句一律变成相应的陈述句后再进行分析,可避免建立繁琐的一般疑问句规则库,缩小了知识库的规模.由于本系统可以低挡微机中高效运行,并实现对一般较简单英语句子的“理解”,故可用于智能机器人实验(如教学实验)系统的人机交互中.

参　考　文　献

1　Hopcroft John E ,U llr m an Jeffrey D .Fo r m al L anguages am d T heir R elati om to A utom ata ,A ddison 2W esley Publish ing Company ,1969

2　Hopcroft John E,U ll m an Jeffrey D.Introducti on to A utom ata T heo ry,L anguages,and Computati on,A ddison 2W esley Publish ing Compang,1979

3　N ilsson N ils J.P rinci p les of A rtificial Intelligence,T i oga Publish ing Company,1982

4　W inograd T erry ,L anguage as a Congnitive P rocess ,A ddison -W esley Publish ing Company ,1983

5　何成武.自动机理论及其应用.科学出版社,1990

6　刘开瑛,郭炳炎.自然语言处理.科学出版社,1991

AN ENG L ISH S Y NTACT I C ANALY SIS S Y STE M APPL IED

T O ROB OT NATURAL LANGUAGE UND ERSTAND ING

ZHAN G J iayin

(S heny ang Institu te of A u to m a tion ,the Ch inese A cad e my of S cien ics ,　110015)

　Abstract 　U nder the conditi on of serial p rocessing hardw are in low 2end m icrocomputers the speed of w h ich is low er ,the inference p rocess can be sped up mo re than 10ti m es by m eans of the concep t of “heuristic p ro 2

cessing ”,h ierarch ical search strategy and m atch ing strategy ,and setting the m axi m un search length p resent 2ed in th is paper .Further mo re ,a serial p roblem s of autom atic english parsing have been so lved and the size of know ledgebase has been reduced after intraducing sem antic info r m ati on ,staged reso lving syntax am biguities ,integrating Top 2dow n and Bo ttom 2up analysis ,and transfo r m ing all Yes N o questi ons into co rresponding

declarative sentences

.　Key words 　Context 2sensitive gramm ar ,parsing strategies and search strategies ,the m axi m um search length ,inference speed ,heuristic p rocessing

作者简介

　张嘉音:男,59岁,副研究员.研究领域:机器翻译,自然语言理解,管理信息系统,数据库应用系统.

733第18卷第6期张嘉音:　一个用于机器人自然语言理解的英语句法分析系统

本文来源：https://www.bwwdw.com/article/xzhe.html