基于上下文无关语法的英语句法剖析系统.docx_第1页
基于上下文无关语法的英语句法剖析系统.docx_第2页
基于上下文无关语法的英语句法剖析系统.docx_第3页
基于上下文无关语法的英语句法剖析系统.docx_第4页
基于上下文无关语法的英语句法剖析系统.docx_第5页
已阅读5页,还剩32页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

基于上下文无关语法的英语句法剖析系统摘 要本毕业设计做的是基于上下文无关语法的英语句法剖析系统。本系统可分为语料库和程序处理两个模块。语料库模块由包含5492个考研词汇的词汇表、796个常用短语的短语表、非规则动词表、第三人称单数表、非规则名词表、规则表、标记集表以及对词汇表、常用短语表进行标记所产生的包含7359个单词标记的单词标记表和包含796个短语标记的短语标记表。其中非规则动词表、非规则名词表、第三人称单数表、规则表、标记集表以及单词标记表和短语标记表都是手工进行标记,输入所建立的。程序处理模块可分为单词识别、句子分解和句法剖析3个部分。单词识别部分是对输入的英文句子进行分词处理,然后对分离出的每个词在语料库中进行检索,对于变形后的单词要将其还原成原型然后再检索,检索成功则将所检索的单词进行词性标记,否则输出相应的处理信息。句子分解部分是对单词识别的结果予以分析,将其中的短语作为一个整体元素给予词性标记,最终将句中各元素及其标记以树状的形式显示出来。句法剖析部分是在前两个部分的基础上对用户所输入的句子进行句法结构的剖析,分析出句中各元素在句中所占的角色。若句法剖析成功则以树状的形式将用户所输入的句子的结构显示出来,否则输出相应的处理信息。 关键字:自然语言理解 语料库 单词识别 句子分解 句法剖析Context-free grammar based Analysis system of English AyntaxAbstractThis projection is to do context-free grammar based analysis system of English syntax. The system can be divided into two modules.The first is corpus and the second is Program processing. There are some tables in the corpus,such as words table,phrase table,irregular verb form,the third person singular form,irregular noun form,rules table, mark set table,word type table,phrase type table.There 5492 words in the words table and 796 phrases in the phrase table.there are 7359 records in the word type table and 796 records in the phrase table.Word type table marked by hand,and so is phrase type table.Program processing module can be divided into word recognition,sentence decomposition and syntactic snalysis.The function of word recognition is to isolate words from the sentence which user input.The function of sentence decomposition is to isolate the independent element in the sentence which user input.Syntactic snalysis is on the basis of the first two steps,its function is to analysis of sentence which user input.If the result of analysis is right,output the result to the screen.Otherwise output the sentence can not be analyzed.Key words: Natural Language Understanding Corpus Word Recognition Sentence Decomposition Syntactic Analysis目录第一章 前言31.1课题研究的背景知识31.2研究自然语言理解的意义3第二章 系统概要设计32.1系统实现所基于的理论知识32.2系统实现功能概述32.3系统实现方法概述32.31语料库设计32.32程序设计构架3第三章 系统详细设计与实现33.1语料库设计与实现33.1.1语料库工具简介Oracle33.1.2语料库的具体存储内容33.2 系统功能的程序实现33.2.1开发环境简介332.2系统界面设计33.2.3系统程序实现的主要源代码3第4章 系统测试及扩充34.1系统测试34.2系统进行进一步扩充与完善的构想3结论3致谢3参考文献3第一章 前言1.1课题研究的背景知识 本论文做的的是基于上下文无关语法的英语句法剖析系统,是属于自然语言理解范畴的。自然语言理解是计算机科学领域与人工智能领域中的一个重要方向。它研究能实现人与计算机之间用自然语言进行有效通信的各种理论和方法。自然语言理解(Natural Language Understanding)是人工智能的分支学科。研究用电子计算机模拟人的语言交际过程,使计算机能理解和运用人类社会的自然语言如汉语、英语等,实现人机之间的自然语言通信,以代替人的部分脑力劳动,包括查询资料、解答问题、摘录文献、汇编资料以及一切有关自然语言信息的加工处理。这在当前新技术革命的浪潮中占有十分重要的地位。研制第5代计算机的主要目标之一,就是要使计算机具有理解和运用自然语言的功能。 自然语言理解是一门新兴的边缘学科,内容涉及语言学、心理学、逻辑学、声学、数学和计算机科学,而以语言学为基础。自然语言理解的研究,综合应用了现代语音学、音系学语法学、语义学、语用学的知识,同时也向现代语言学提出了一系列的问题和要求。本学科需要解决的中心问题是:语言究竟是怎样组织起来传输信息的?人又是怎样从一连串的语言符号中获取信息的?这一领域的研究将涉及自然语言,即人们日常使用的语言,包括中文、英文、俄文、日文、德文、法文等,所以它与语言学的研究有着密切的联系,但又有重要的区别。自然语言处理并不是一般地研究自然语言,而在于研制能有效地实现自然语言通信的计算机系统,特别是其中的软件系统。因而它是计算机科学的一部分。自然语言理解从 20世纪 60年代初开始研究,由于 N.乔姆斯基在语言学理论上的突破和此后各家理论的发展,以及计算机功能的不断提高,目前已经取得了一定的成果,分为语音理解和书面理解两个方面。 语音理解 用口语语音输入,使计算机听懂语音信号,用文字或语音合成输出应答。方法是先在计算机里贮存某些单词的声学模式,用它来匹配输入的语音信号,称为语音识别。这只是一个初步的基础,还不能达到语音理解的目的。因为单凭声学模式无法辨认人和人之间、同一个人先后发音之间的语音差别,也无法辩认连续语流中的语音变化;必须综合应用语言学知识,以切分音节和单词,分析句法和语义,才能理解内容,获取信息。60年代至70年代初期,研究工作一直停留在单词的语音识别上,进展不大。直到70年代中期才有所突破,建立了一些实验系统,能够理解连续语音的内容,但是还限于少数简单的语句(见自然语言语音理解系统)。 书面理解 用文字输入,使计算机看懂文字符号,也用文字输出应答。这方面的进展较快,70年代初期取得突破,中期以后又有所发展。目前已能在一定的词汇、句型和主题范围内查询资料,解答问题,阅读故事,解释语句等,有的系统已付诸应用。 由于绝大多数语种使用的是拼音文字,计算机识别拼音字母已无问题,而输入又是按单词分别拼写,因此书面理解一般没有切分音节和单词的问题,只需直接分析词汇、句法和语义。但是汉语用的是汉字,无论是用汉字编码输入还是将来计算机能直接认识汉字,都要首先解决切分单词的问题,因为输入就是一连串汉字,词和词之间没有空隔。 书面理解的基本方法是:在计算机里贮存一定的词汇、句法规则、语义规则、推理规则和主题知识。语句输入后,计算机自左至右逐词扫描,根据词典辨认每个单词的词义和用法;根据句法规则确定短语和句子的组合;根据语义规则和推理规则获取输入句的含义;查询知识库,根据主题知识和语句生成规则组织应答输出。目前已建成的书面理解系统应用了各种不同的语法理论和分析方法,如生成语法、系统语法、格语法、语义语法等,都取得了一定的成效。1.2研究自然语言理解的意义 自然语言理解是一个非常有魅力的研究领域。语言现象看似简单,实际上却反映了人类智慧中最复杂也最本质的特点。自然语言理解的研究不仅仅是一种方法和工具,而且对我们了解人类语言的奥秘,开启人类的智慧之门有着重要影响。现代计算机虽然具有非常强大的计算能力,但是在处理语言的时候,应用起来仍让人感觉有些力不从心。当电子计算机刚刚诞生的时候,人们首先想到的应用领域之一就是语言的利用计算机进行自动翻译。不过,语言理解和处理的复杂性和困难程度远远超过人们的预料。自然语言理解研究也因此经历过一段跌宕起伏的时期。到现在,人们已经充分认识到自认语言理解的复杂性和难度,不过这并未降低世界各地研究者对这个领域的研究热情。近年来,这一领域的各种新思想和新方法不断涌现,一方面是由于信息社会所带来的巨大需求在有力地推动着这个领域的研究工作,另一方面也是因为这个学科本身的魅力在吸引着众多的科学家投入到这项研究工作中来。自然语言理解是一门非常复杂的学科,虽然现在的技术还达不到向人类那样真正的理解自然语言的要求,但在这个领域已经取得的研究成果仍然是相当丰富多彩的。在长期的研究中,这门学科形成了一整套的理论和方法,不仅能够加深我们对人类语言现象的理解,而且能够确实解决涉及自然语言的应用中遇到的很多实际问题。自然语言理解将为下一次地计算机革命提供动力。近年来,虽然在计算机硬件方面有了巨大的进步,但在诸如图形和多媒体之类的计算机应用软件方面,我们所使用的用户界面和20年前仍然豪无二致。我们与计算机的交互方式还停留在从计算机给出的一个可先集合中选择命令的阶段。也就是说,不得不为计算机来改变我们的行为。在未来,为适应人类解决问题和行动的方式,应该是计算机做出改变。界面应该是目标驱动的,并且充分建立在一种复杂的算法基础上,这种算法能够自动推测用户的意图,并以一种符合用户直觉的自然方式向用户返回信息。而自然语言理解将在这种进程中扮演一个关键的角色,因为语言是人类交流的最自然的形式。第二章 系统概要设计2.1系统实现所基于的理论知识所谓的上下文无关就是对一个句子的处理是仅就句子本身而言的,而不考虑句子所处的上下文的环境。一个上下文无关的语法由一套规则或产生式以及单词和符号的一个词表组成,每个规则表示语言中的符号的组成和排序方式。在上下文无关语法中所用的符号分为两类。与语言中的单词相对应的符号成为终极符号,词表是引入这些终极符号的规则的集合。表示这些终极符号的聚类或概括性的符号成为非终极符号。在每个上下文无关的规则中,箭头右边的项是一个或者多个终极符号和非终极符号构成的有序表,而箭头的左边是一个单独的非终极符号,表示某种聚类或概括性。上下文无关语法定义的形式语言是从指定的的初始符号开始推导出来的符号串的集合。每个语法必须有一个指定的初始符号,这个符号通常称为S,由于上下文无关语法通常用来定义句子,所以S通常可以解释为“句子”。在某个简化的英语语法中,由S推导出的符号串的集合就是句子的集合。Earley算法是一种基于动态规划的上下文无关剖析算法。由于使用了很多动态规划的解,这种算法消除了回溯方法中固有的子问题重复求解的弊病,把外观上的指数时间复杂度问题降低到多项式时间复杂度问题。Earley算法的核心是一个从左到右的传递,它填充一个称为线图的数组,如果输入有N个单词,则线图含有N+1个项目。对于句子中每个单词的位置,线图包含一个状态表来表示已经生成的部分剖析树。在句子结尾,线图把对于给定输入的所有可能的剖析结果简洁地进行编码。每个可能的子树表示可以被需要它的所有的剖析共享。用图形来表示,我们将在某一状态的语法规则的右手边中,使用一个点来标志识别这个状态所走过的进程。这样形成的结构成为点规则。一个状态对于输入的位置用两个数来表示,分别说明该状态开始的位置以及点所在的位置。Earley算法的基本操作是以从左向右的方式走过线图中的由N+1个状态组成的集合,按顺序处理每个集合中的各个状态。在每一步,根据具体情况将预测、扫描、完成三个操作中的一个应用于每个状态。在每个场合,这样的操作的结果会增加一个新的状态,这个新的状态或者加在当前状态的后面,或者加在该线图的下一个状态的集合中。这样的算法始终通过线图向前移动,每向前移动一步增加一个新的状态,这些状态从来不会被抹掉,当算法向前移动之后,就再也不会回溯到前面已走过的线图项目中。在最后一个线图项目的状态表中的状态S a,0,N表示剖析已成功。2.2系统实现功能概述 本系统所实现的功能是对用户所输入的英文句子进行基于上下文无关语法的句法剖析。剖析的具体功能是识别出用户所输入的英文句子的整体结构,并将句子的整体结构以及句中各独立元素在句中所充当的角色和词性标识并以简明的形式显示出来。2.3系统实现方法概述本系统的实现可分为语料库设计和程序实现两个模块。2.31语料库设计语料库由单词表(Words),单词类型表(Word_Type),短语表(Phrase),短语类型表(Phrase_Type), 不规则名词表(irregular_noun),不规则动词表(irregular_verb),规则表(Rule),TreeBank 标记集表,非规则第三人称单数表(irregular_verb_3sg)组成。其中单词表(Words)是由5500考研词汇组成的,单词类型表(WordType)是对单词表进行标记产生的,,短语表(Phrase)是由常用短语组成的,短语类型表(Phrase_Type)是由对短语表中的短语进行标记产生的,不规则名词表(irregular_noun),不规则动词表(irregular_verb)是由一部分变化形式不规则的动名词组成的,TreeBank 标记集表是由要对单词进行标记的形式的信息组成的,规则表是参照英语语法书编制的一些英语语法规则。 其中规则表很重要,在剖析英语语法时参照的语法规则都是依据规则表中的标记规则进行的。 语料库中的各张表的信息如下对单词,短语的标记参考表标记说明例子CC连接词and,but,orCD 基数词one,two,threeDT限定词a,theEX存在词thereFW外来词汇mea culpaIN介词of,in,byJJ形容词yellowJJR形容词比较级biggerJJS形容词最高级wildestMD情态动词can,shouldNN名词llamaNNS名词复数llamasNNP专有名词 单数IBMNNPS专有名词 复数carolinasPDT前置限定词, 前置限定成分all,bothPOS所有词结尾 sPP人称代词l,you,hePP$所有格代词your,onesRB副词quickly,neverRBR副词比较级fasterRBS副词最高级fastestRP小品词,介词和连词是小品词up,offSYM符号,标记 +,%,&TOtotoUH叹词, 感叹词ah,oopsVB动词eatVBD动词过去式ateVBG动名词eatingVBN过去分词eatenVBPverb,non-3sg preseatVBZ动词第3人称eatsWDT限定词which,thatWPwh-代名词what,whoWPSwhoseWRBWH-副词how,whereVTB及物动词mobVIB非及物动词manufacture 表2.31 -1 标记表规则表中的单词角色标记记为主语SUB谓语PRED表语PREDI宾语OBJ补语COMP定语ATTR状语ADVMOD同位语APP系动词COP名词短语NP名词性成分NOMINAL介词短语INP不定式短语TOP动名词短语VBGPthe 本身THE表2.31 -2 单词角色标记表单词(Words)表列名类型含义WordIDnumber(8)单词编号Wordvarchar(50)单词表2.31 -3 单词表单词类型(WordType)表列名类型含义RowNonumber(8)记录编号WordIDnumber(8)单词编号WordTypevarchar2(20)单词标记Meaningvarchar2(50)单词解释 表2.31 -4 单词类型表短语(Phrase)表列名类型含义PhraseIDnumber(5)短语编号Phrasevarchar2(50)短语表2.31 -5 短语表短语类型(Phrase_Type)表列名类型含义RowNonumber(5)记录编号PhraseIDnumber(5)短语编号PhraseTypevarchar2(10)短语标记Meaningvarchar2(50)短语解释表2.31 -6短语类型表非规则名词(irregular_noun)表列名类型含义word_idnumber(4)序号wordvarchar2(50)原形word_plvarchar2(50)名次复数表2.31 -7非规则名词表非规则动词(irregular_verb)表verb_idnumber(4)序号verbvarchar2(50)动词原形verb_pastvarchar2(50)动词过去式verb_past_partvarchar2(50)动词过去分词verb_idnumber(4)序号表2.31 -8非规则动词表规则(Rule)表列名类型含义RuleIDROWID规则编号LeftPartOfRulevarchar(50)规则左部LeftPartOfRulevarchar(50)规则右部表2.31 -9规则表TreeBank 标记集表列名类型含义Markervarchar2(20)标记EngDescverchar2(50)英文描述ChinaDescnvarchar2(50)中文描述表2.31 -10标记集表非规则动词第三人称单数(irregular_verb_3sg)表列名类型含义RowNonumber(3)编号Wordvarchar2(50)动词原形Word_3SGvarchar2(50)动词第三人称单数表2.31 -11非规则动词第三人称单数2.32程序设计构架2.32.1程序实现方法概述本系统的实现可分为单词识别、句子分解、句子剖析3个步骤。1.单词识别:将用户所输入的英语句子分解为单词,根据单词的特征进行分类并在语料库中检索。若检索成功则给单词标识词性并出来,否则输出错误信息。2.句子分解:在单词识别的基础上将用户所输入的句子中的短语作为一个独立的元素识别并标识出来。将句中各独立的元素以树状的形式显示出来。3.句子剖析:在单词识别、句子分解的基础上根据Earley算法对用户所输入的英语句子进行基于上下文无关语法的句法剖析,将剖析结果以树状的形式显示出来。2.32.2程序实现流程图单词识别部分的流程图图2.32.2-1 单词识别功能的总流程图图2.32.2-1只是对但此时别模块的总体设计流程图,其中忽略了很多重要细节,现补充如下单词以s结尾的处理部分为图2.32.2-2单词以ed结尾的处理部分为 图2.32.2-3以ing结尾的处理部分为图2.32.2-4句子分解部分的流程图图2.32.2-5单词分解部分已将用户输入句中的单词进行了分析,所以此部分是在单词分解的基础上分析句子的组成元素。本系统将句中的一个词组作为一个元素。短语识别部分的流程图为 图2.32.2-6第三章 系统详细设计与实现3.1语料库设计与实现3.1.1语料库工具简介Oracle本系统的语料库使用Oracle10g标准版开发的。oracle是殷墟(yn Xu)出土的甲骨文(oracle bone inscriptions)的英文翻译的第一个单词,在英语里是“神谕”的意思。Oracle是世界领先的信息管理软件开发商,因其复杂的关系数据库产品而闻名。Oracle数据库产品为财富排行榜上的前1000家公司所采用,许多大型网站也选用了Oracle系统。Oracle10g 的一个引人注目之处就是管理上的极大简化。大量复杂的配置和部署设置被取消或者简化。常见的操作过程被自动化。对不同区域的大多数调整和管理操作的到简化。Oracle10g的主要优点有:1.简化的数据库配置与升级 2.自动存储管理 3.自动的基于磁盘备份与恢复 4.应用优化 5.自动化统计收集 6.自动化实例调整 7.自动化内存调整 3.1.2语料库的具体存储内容面已经介绍了语料库的实现是由数据库中的若干表组成的,并且也说明了个张表的具体信息。下面是各表在数据库中具体存储的内容:单词(Words)表单词表包括5492个考研词汇,限于篇幅这里只列出表中部分内容 图 3.1.2-1 单词类型(WordType)表由于WordType表是对words表进行标记产生的,并且由于一个单词往往有多个词性,所以WordType表要比words表还要大,因此在此也只列出WordType表的部分信息图 3.1.2-2短语(Phrase)表同理,由于Phrase表的数据也较多只列出部分信息 图 3.1.2-3 短语类型(Phrase_Type)表由于时间的关系只是对Phrase表中的一部分短语进行了标记,同理也只列出短语类型表中的部分信息图 3.1.2-4非规则名词(irregular_noun)表 图 3.1.2-5非规则动词(irregular_verb)表图 3.1.2-6 TreeBank 标记集表 图 3.1.2-7非规则第三人称单数(irregular_verb_3sg)表图 3.1.2-8注:将Words表与WordType表分开存储是为了数据的独立性,当Words表中的数据破坏时,不至于影响WordType表。同理Phrase表与Phrase_Type表分开存储也是基于这个原因。同时还将Words表与WordType表通过WordID字段建立连接,Phrase表与Phrase_Type表通过PhraseID建立了连接。规则(Rule)表图 3.1.2-9规则表是英语语法规则的集合,具体如图 3.1.2-9所示。其中LEFT_PART表示可以被扩展的成分,RIGHT_PART表示能将LEFT_PART扩展为怎样的形式。而具体的标记所代表的含义可参照2.3.1节语料库整体设计中的表2.31 -2 单词角色标记表。3.2 系统功能的程序实现 3.2.1开发环境简介本系统用的开发环境是Microsoft Visual Studio 2008。Microsoft Visual Studio 2008是面向Windows Vista、Office 2007、Web 2.0的下一代开发工具,代号“Orcas”,是对Visual Studio 2005一次及时、全面的升级。 VS2008引入了250多个新特性,整合了对象、关系型数据、XML的访问方式,语言更加简洁。使用Visual Studio 2008可以高效开发Windows应用。设计器中可以实时反映变更,XAML中智能感知功能可以提高开发效率。同时Visual Studio 2008支持项目模板、调试器和部署程序。Visual Studio 2008可以高效开发Web应用,集成了AJAX 1.0,包含AJAX项目模板,它还可以高效开发Office应用和Mobile应用。32.2系统界面设计图 3.2.2-1 系统界面本系统实现的功能明确,故系统界面做的尽可能简洁、友好、易用。基于此设计出的系统界面如图 3.2.2-1所示。系统界面注解:当用户在输入句子的文本框中输入英语句子后,要首先进行单词识别才能进行后续工作。由于单词识别主要是为句子分解和句法剖析部分服务的,所以当点下单词识别按钮后系统并不会将单词识别的结果显示出来,但此时系统以对用户所输入的句子进行了单词识别。3.2.3系统程序实现的主要源代码单词识别部分的主要代码为private void btn_recognize_Click(object sender, EventArgs e) string inputString = rtb_sentence.Text.ToString(); words = inputString.Split( );/将句子拆分成单个的词 wordBaseForm = new Stringwords.Length; WordType = new Stringwords.Length;/ 建立一个数组用来存储单词可能的标记。 RealWordType = new Stringwords.Length;/某单词真实的标记 Element = new Stringwords.Length; / 存储句子元素,由于用户输入的句子中还有可能有短语的成分,此时将短语整体作为句中的一个元素 ElementType = new Stringwords.Length;/句子元素真实的标记 WordRecognize(); private void WordRecognize() int i = 0; foreach(string w in words) if (WordSelect(w, i) /查询词表 GetRealWordType(i); else /在词表中没有查询到 if( w.EndsWith(s) if (!NounPlVerg3SgJudgement(w, i) /判断是否为名词复数或者是动词第三人称单数 if (!IrregularWrodSearch(w, i) UnknownWord(i);/若既不是名词复数或者是动词第三人称单数也不是动词的过去分词或过去式则给出错误信息 else if (w.EndsWith(ed) if (VerbPastJudgement(w, i) RealWordTypei = _VBD_VBN_JJ; /给单词标记-过去式,当然也有可能是过去分词,也有可能是形容词,具体根据上下文分析。 else UnknownWord(i); else if (w.EndsWith(ing) if (VerbGerundJudgement(w, i) RealWordTypei = _VBG_JJ; /给单词标记-动名词,也有可能是形容词,具体根据上下文分析。 else UnknownWord(i); else SpecialWrodSearch(w, i); i = i + 1; / words 数组的序号加1 句子分解部分的主要代码为 private void btn_DivideSentence_Click(object sender, EventArgs e) DivedeSentence();/分解句子 ElementPresent();/将句子分解结果以树的形式呈现出来 本部分代码实现分解句子以及短语识别:private void DivedeSentence() int len = wordBaseForm.Length; int j; SentenceDivede sd = new SentenceDivede(); for (int i = 0; i -1)/若句子剖析成功则以树状的形式显示出来 StackOfMarker = new string50; PointerOfStack = 0; tv_analyses.Nodes.Clear(); tv_analyses.ItemHeight = 25; ChartStatus cs = charta, b; TreeNode node = new TreeNode(); node.Text = S; tv_analyses.Nodes.A

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论