自然语言的处理.ppt

1 第第3章章 自然语言的处理自然语言的处理23.1 基本概念基本概念3信息的主要载体语言信息的主要载体语言语言的两种形式文字和声音语言的两种形式文字和声音 文字和声音作为语言的两个不同形式的载体，所承文字和声音作为语言的两个不同形式的载体，所承载的信息占整个信息组成的载的信息占整个信息组成的90以上。以上。如何让计算机实现人们希望实现的语言处理功能如何让计算机实现人们希望实现的语言处理功能？如何让计算机真正实现海量的语言信息的自动处如何让计算机真正实现海量的语言信息的自动处理和有效利用？理和有效利用？4自然自然语语言言处处理理（NaturalLanguageProcessing，简简称称NLP）是利用）是利用计计算机算机为为工具，工具，对对人人类类特有的特有的书书面形式和口面形式和口头头形式的自然形式的自然语语言的信息言的信息进进行各种行各种类类型型处处理和加工的技理和加工的技术术。冯冯志志伟伟自然自然语语言的言的计计算机算机处处理理NLP是用是用计计算机通算机通过过可可计计算的方法算的方法对对自然自然语语言的言的各各级语级语言言单单位（字、位（字、词词、语语句、篇章等）句、篇章等）进进行行转转换换、传输传输、存、存储储、分析等加工、分析等加工处处理的理理的理论论和方法。和方法。5其它名称其它名称 自然语言理解自然语言理解(Natural Language Understanding)计算语言学计算语言学(Computational Linguistics)现代语言学的一大分支，它是用计算机理现代语言学的一大分支，它是用计算机理解、生成和处理自然语言，即它的研究范解、生成和处理自然语言，即它的研究范围不仅涵盖语言信息的处理，还包括语言围不仅涵盖语言信息的处理，还包括语言的理解和生成。的理解和生成。6研究语言的目的研究语言的目的研究语言的目的研究语言的目的为为语语言言构构造造出出足足够够精精细细的的计计算算模模型型，以以便便能能够够写写出出由计算机程序来完成的涉及自然语言的各种任务。由计算机程序来完成的涉及自然语言的各种任务。计算模型的用途计算模型的用途作为科学研究的目的可以探索语言交流的本质；作为科学研究的目的可以探索语言交流的本质；作为实用的目的能够实现有效的人机通信。作为实用的目的能够实现有效的人机通信。终极目标终极目标能能够够给给出出一一些些模模型型，这这些些模模型型在在完完成成阅阅读读、写写作作、听、说等任务时能够接近人的行为。听、说等任务时能够接近人的行为。7 不不关关注注与与所所使使用用的的特特定定媒媒介介相相关关的的问问题题，例例如如手手写写输输入入、键键盘盘输输入入或或语语音音输入的问题。输入的问题。关注关注在词语识别完成后理解和使用在词语识别完成后理解和使用语言的过程。语言的过程。NLP的历史的历史u20世世纪纪50年代起步年代起步u提出机器翻提出机器翻译译等重要等重要问题问题u50年代年代-60年代采用模式匹配法和文法分析方法年代采用模式匹配法和文法分析方法u对对基于理解和基于基于理解和基于统计统计方法的方法的讨论讨论u60年代后期衰落年代后期衰落u70-80年代采用了面向受限域的深入理解方法年代采用了面向受限域的深入理解方法u80年代后期至今年代后期至今统计统计方法占据主流方法占据主流u大大规规模模语语料可用，料可用，计计算机性能大幅提高算机性能大幅提高u互互联联网的迅速网的迅速发发展展为为NLP提供了提供了实验实验数据来源和新的数据来源和新的应应用用场场景景893.2 自然语言处理技术可以为我们做自然语言处理技术可以为我们做什么？什么？1、信息、信息检检索索http:/微微软软：106,000,000条（条（8年前年前2,060,000条）条）微微软软，亚亚洲研究院：洲研究院：1,060,000条条微微软软，亚亚洲研究院，研究方向：洲研究院，研究方向：116,000条条微微软软，亚亚洲研究院，自然洲研究院，自然语语言言处处理：理：38,900条条08年年7月一万月一万亿亿个网个网页页，每天数十，每天数十亿亿增加增加获获得的信息只有得的信息只有1被有效利用被有效利用“框框”计算计算“框计算框计算”是是20092009年年8 8月月1818日，百度董事长兼首席日，百度董事长兼首席执行官李彦宏在执行官李彦宏在20092009百度百度技术创新大会上所提出的技术创新大会上所提出的全新技术概念。用户只要全新技术概念。用户只要在在“百度框百度框”中输入服务中输入服务需求，系统就能明确识别需求，系统就能明确识别这种需求，并将该需求分这种需求，并将该需求分配给最优的内容资源或应配给最优的内容资源或应用提供商处理，最终精准用提供商处理，最终精准高效地返回给用户相匹配高效地返回给用户相匹配的结果。这种高度智能的的结果。这种高度智能的互联网需求交互模式，以互联网需求交互模式，以及及“最简单可依赖最简单可依赖”的信的信息交互实现机制与过程，息交互实现机制与过程，称之为称之为“框计算框计算”。10112、借助于语言信息处理的、借助于语言信息处理的web智能智能1213微软亚洲研究院微软亚洲研究院人立方人立方输入输入“王菲王菲”得到的人物关系图得到的人物关系图15Ex-1:Thespiritiswilling,butthefleshisweak.（心有余，而力不足。）（心有余，而力不足。）译译：精神是愿意的：精神是愿意的,但骨肉是微弱的。但骨肉是微弱的。(Systran，现现在已在已经经能能够够正确翻正确翻译译)Ex-2:3、机器翻译、机器翻译16在网在网络络上上输输入入“问问句句”，自，自动给动给出精确地答案。出精确地答案。自自动问动问答系答系统统的的结结构构三个模三个模块块：提提问处问处理模理模块块（Question-Processing）；）；文献文献处处理模理模块块（Document-Processing）；）；答案的提取和构造模答案的提取和构造模块块（AnswerExtractionandFormulation）。）。冯冯志志伟伟4、自动问答系统、自动问答系统17 如如“给我找出所有有关在给我找出所有有关在1986年到年到1990年之间曾经年之间曾经尝试而最终失败且金额超过尝试而最终失败且金额超过1亿美元的融资收买的亿美元的融资收买的文章。文章。”处理方法：处理方法：1 1、对数据库的每篇文章建立一种表示形式、对数据库的每篇文章建立一种表示形式 2 2、这种表示形式能用于后续的推理、这种表示形式能用于后续的推理 5、复杂的检索任务、复杂的检索任务18输入：美欧贸易摩擦升级输入：美欧贸易摩擦升级识别结果：美欧贸易摩擦识别结果：美欧贸易摩擦生机生机输入：新技术的发展日新月异输入：新技术的发展日新月异识别结果：新识别结果：新纪录纪录的发展日新月异的发展日新月异6、语音识别、语音识别19信息过滤，信息安全信息过滤，信息安全文摘生成文摘生成问答系统，人机交互问答系统，人机交互语言教学语言教学文字输入，文字编辑与排版文字输入，文字编辑与排版语音翻译语音翻译网络内容管理与知识发现网络内容管理与知识发现 201.3 关于关于“理解理解”的理解的理解 他他说说：“她她这这个人真有意思个人真有意思(funny)”。她。她说说：“他他这这个人怪有意思的个人怪有意思的(funny)”。于是人。于是人们们以以为为他他们们有有了意思了意思(wish)，并，并让让他向她意思意思他向她意思意思(express)。他火。他火了：了：“我根本没有那个意思我根本没有那个意思(thought)”！她也生气了：！她也生气了：“你你们这们这么么说说是什么意思是什么意思(intention)”？事后有人？事后有人说说：“真有意思真有意思(funny)”。也有人。也有人说说：“真没意思真没意思(nonsense)”。生活生活报报1994.11.13.第六版第六版21人脑对语言的理解是一个复杂的思维过程。人脑对语言的理解是一个复杂的思维过程。自然语言理解技术同多个学科有着千丝万缕的关系。自然语言理解技术同多个学科有着千丝万缕的关系。语言学：研究语言本身的结构语言学：研究语言本身的结构语言心理学：语言心理学：研究人类生成和理解语言的过程研究人类生成和理解语言的过程逻辑学：逻辑学：计算机科学计算机科学人工智能人工智能数学与统计学数学与统计学 22一种测试一种测试机器机器是不是具备是不是具备人类智能人类智能的方法。的方法。图灵测试图灵测试231.4 自然语言理解研究的基本问题自然语言理解研究的基本问题研究的层次研究的层次语法学：研究语句的组成结构，包括词和短语语法学：研究语句的组成结构，包括词和短语 在语句中的作用等。在语句中的作用等。为什么一句话可以这么说也可以那么说？为什么一句话可以这么说也可以那么说？24研究的研究的层层次次语义语义学：研究如何从一个学：研究如何从一个语语句中推句中推导词导词的意的意义义，以及以及这这些些词词在在该语该语句中句法句中句法结结构中的作用来推构中的作用来推导导出出该语该语句的意句的意义义。这这句句话说话说了什么？了什么？(1)今天中午我吃食堂。今天中午我吃食堂。(2)这这个人真牛。个人真牛。(3)这这个人眼下没些什么，那个人嘴不太好。个人眼下没些什么，那个人嘴不太好。25研究的研究的层层次次语语用学：研究在不同上下文中的用学：研究在不同上下文中的语语句的句的应应用，用，以及上下文以及上下文对语对语句理解所句理解所产产生的影响。生的影响。为为什么要什么要说这说这句句话话？（1）火，火！）火，火！（2）A:看看看看鱼鱼怎么怎么样样了？了？B:我我刚刚才翻了一下。才翻了一下。自然语言理解的基本模型自然语言理解的基本模型汉语的特点：汉语的特点：p汉语是大字符集（汉语是大字符集（GBK字符集字符集）的意音文字（图形）的意音文字（图形符号既代表语素，又代表音节的文字系统）；符号既代表语素，又代表音节的文字系统）；p汉语词与词之间没有空格，没有形态变化；汉语词与词之间没有空格，没有形态变化；p汉语的同音词较多；汉语的同音词较多；p字形复杂；字形复杂；p汉语的语法研究尚未规范化；汉语的语法研究尚未规范化；p汉语的语言学知识的量化与形式化工作滞后。汉语的语言学知识的量化与形式化工作滞后。271.5 汉语的自然语言理解汉语的自然语言理解英语只有英语只有26 个字母个字母,中文却有中文却有44 908 个汉字个汉字(中华大辞典中华大辞典)。英语有。英语有1500 年历史年历史牛津英语辞典牛津英语辞典收词收词40 多万条。汉语长达六千多年历史多万条。汉语长达六千多年历史中华大辞典中华大辞典收词六十多万条收词六十多万条,比英比英语多语多50%。这一特性为汉字的输入。这一特性为汉字的输入和计算机编码造成了极大的困难。和计算机编码造成了极大的困难。西方语言的形态对于计算机来说就是西方语言的形态对于计算机来说就是标记；汉语以字为基本单位，词之间标记；汉语以字为基本单位，词之间没有明显的标记，需要词的切分，而没有明显的标记，需要词的切分，而分词本身有一定的错误率，降低了后分词本身有一定的错误率，降低了后续处理的实际效果。汉语词本身没有续处理的实际效果。汉语词本身没有性、数、格、时态变化等形态标志，性、数、格、时态变化等形态标志，给语义分析增加了困难。给语义分析增加了困难。方块汉字由象形文字演化而方块汉字由象形文字演化而来，汉字字形的信息量较大，来，汉字字形的信息量较大，给计算机的内部信息压缩和给计算机的内部信息压缩和文字显示制造了困难。文字显示制造了困难。汉语句子中词序虽同可能意义迥异；虚词汉语句子中词序虽同可能意义迥异；虚词并非非用不可，特别是在口语里，虚词更并非非用不可，特别是在口语里，虚词更少，因此虚词只能是解决词与词、句与句少，因此虚词只能是解决词与词、句与句关系问题的辅助手段；关系问题的辅助手段；“意合意合”包含着许包含着许多语言环境、语言背景和语言风格知识以多语言环境、语言背景和语言风格知识以及缺省问题，如何全面把握有关意义的诸及缺省问题，如何全面把握有关意义的诸项要素，并把它形式化，是最大的难题。项要素，并把它形式化，是最大的难题。281、交集型切分歧义问题交集型切分歧义问题 乒乓球乒乓球/拍拍卖卖/完完/了了 乒乓球乒乓球拍拍/卖卖/完完/了了 美美国国/会通过对台售武法案会通过对台售武法案 美美/国国会会/通过对台售武法案通过对台售武法案汉语自然语言理解的难点汉语自然语言理解的难点292、未登录词（新词）问题未登录词（新词）问题汉语词典中未列入的词汉语词典中未列入的词包括：包括：专专有有名名词词：中中文文人人名名、地地名名、机机构构名名称称、外外国国译译名、时间词名、时间词重叠词：高高兴兴重叠词：高高兴兴派生词：一次性用品派生词：一次性用品专业术语：互联网专业术语：互联网303、词性岐义问题、词性岐义问题 多多词词性性和和多多词词义义是是语语言言的的一一种种普普遍遍现现象象，汉汉语语这这种现象比西方语言严重得多。种现象比西方语言严重得多。和和 根根据据现现代代汉汉语语词词典典，可可以以有有五五种种读读音音：he2；he4；hu2；huo2；huo4 六六种种词词性性：名名词词、形形容容词词、连连词词、动动词词、介介词词、量词量词 十六种不同的词义十六种不同的词义314、否定、否定词词和和语义语义上的混乱上的混乱汉汉语语上上的的否否定定词词“不不”有有时时并并不不表表示示否否定定。相相反反，反而会更肯定。反而会更肯定。如：如：“可不是可不是”比比“可是可是”更可是。更可是。325、汉语汉语的岐的岐义结义结构（短构（短语语歧歧义义）岐岐义义结结构构是是句句子子自自生生固固有有的的，必必须须在在整整个个语语境境环环境下才可能消歧，自境下才可能消歧，自动动消歧是很消歧是很难难的。的。u彩色彩色铅铅笔盒子笔盒子彩色彩色铅铅笔盒子笔盒子彩色彩色铅铅笔笔盒子盒子u他在看病他在看病他在他在给别给别人看病人看病大夫大夫给给他看病他看病6、汉语汉语的的词义词义岐岐义义l打打乒乓乒乓球球l打打电话电话l打打毛衣毛衣7、语语用岐用岐义义你真你真讨厌讨厌！341.6 自然语言处理技术自然语言处理技术如何描述一种语言？如何描述一种语言？u穷举：穷举：u给出语言中所有的句子；给出语言中所有的句子；u只适合含有有限多个句子的语言。只适合含有有限多个句子的语言。u文法：文法：u给出可以生成语言中所有句子的方法；给出可以生成语言中所有句子的方法；u当且仅当能够用该方法产生的句子属于该语言。当且仅当能够用该方法产生的句子属于该语言。u自动机：自动机：u给出识别该语言中句子的机械方法；给出识别该语言中句子的机械方法；u可以检验输入句子是否属于该语言。可以检验输入句子是否属于该语言。按技术路线分为：按技术路线分为：基于语言学规则的语言处理技术基于语言学规则的语言处理技术基于统计的语言处理技术基于统计的语言处理技术 两者结合两者结合 1、基于语言学规则的语言处理技术、基于语言学规则的语言处理技术通过对语言学知识的形式化、形式化规则的算法通过对语言学知识的形式化、形式化规则的算法化，以及算法实现等步骤将语言学知识转化为计化，以及算法实现等步骤将语言学知识转化为计算机可以处理的形式。算机可以处理的形式。强调语言学家对语言现象的认识。强调语言学家对语言现象的认识。采用非歧义的规则形式描述或解释歧义行为或歧采用非歧义的规则形式描述或解释歧义行为或歧义特性。义特性。37理性主义方法理性主义方法语言学家语言学家：撰写：撰写“规则库规则库”（包括（包括“词典词典”）计算机学家计算机学家：编写算法程序，对：编写算法程序，对“规则库规则库”进行解进行解释和执行。释和执行。382、基于统计的语言处理技术、基于统计的语言处理技术从大规模真实语料库中获得各级语言单位上的统计从大规模真实语料库中获得各级语言单位上的统计信息，并依据较低级语言单位上的统计信息，用相信息，并依据较低级语言单位上的统计信息，用相关的统计推理技术计算较高级语言单位上的统计信关的统计推理技术计算较高级语言单位上的统计信息。息。注重用数学方法注重用数学方法概率论与数理统计。概率论与数理统计。能从代表自然语言规律的大规模真实文本中发现知能从代表自然语言规律的大规模真实文本中发现知识，抽取语言现象或统计规律（从大量的语言数据识，抽取语言现象或统计规律（从大量的语言数据中获得语言的知识结构）。中获得语言的知识结构）。39经验主义方法经验主义方法语言学家语言学家：建立：建立“语料库语料库”经科学取样和加工的经科学取样和加工的大规模电子文本库。大规模电子文本库。存放的是在语言的实际使用中真实出现过的语言材料；存放的是在语言的实际使用中真实出现过的语言材料；以电子计算机为载体承载语言知识的基础资源；以电子计算机为载体承载语言知识的基础资源；真实语料需要经过加工（分析和处理），才能成为有用的真实语料需要经过加工（分析和处理），才能成为有用的资源。资源。计算机学家计算机学家：建立统计模型：建立统计模型 利用语料库训练模型参数利用语料库训练模型参数 编写算法解决问题编写算法解决问题40二者区别二者区别研究对象不同研究对象不同u基于规则的方法主要研究人的语言知识结构，实际基于规则的方法主要研究人的语言知识结构，实际的语言数据只提供了这种内在知识的间接证据。的语言数据只提供了这种内在知识的间接证据。u基于统计的方法研究对象就是实际的语言数据。基于统计的方法研究对象就是实际的语言数据。41二者区别二者区别理论基础不同理论基础不同u基于规则的方法是基于乔姆斯基的语言理论基于规则的方法是基于乔姆斯基的语言理论的。通过语言所必须遵守的一系列原则来描的。通过语言所必须遵守的一系列原则来描述语言，以此判断一个句子是正确的还是错述语言，以此判断一个句子是正确的还是错误的。误的。u基于统计的方法基于香农的信息论。将语言基于统计的方法基于香农的信息论。将语言事件赋予概率，作为其可信度，由此来判断事件赋予概率，作为其可信度，由此来判断一个句子是常见的还是罕见的。一个句子是常见的还是罕见的。42二者区别二者区别范围不同范围不同u基于规则的方法通过对一些特定领域或范围基于规则的方法通过对一些特定领域或范围内的语言现象的研究来得到对人的语言能力内的语言现象的研究来得到对人的语言能力的认识，而这些语言现象在实际应用中可能的认识，而这些语言现象在实际应用中可能并不常见。并不常见。u基于统计的方法偏重于对语料库中人们实际基于统计的方法偏重于对语料库中人们实际使用的普通语言现象的统计表述。使用的普通语言现象的统计表述。43二者区别二者区别方法不同方法不同u基于规则的方法：符号处理系统。基于规则的方法：符号处理系统。u基于统计的方法偏重于对语料库中人们实际基于统计的方法偏重于对语料库中人们实际使用的普通语言现象的统计表述。使用的普通语言现象的统计表述。441.7 基于语言学规则的语言处理技术基于语言学规则的语言处理技术规则举例规则举例新新词词抽取的常抽取的常规规则规规则：1、If(pos(A)=NAND(pos(B)=VORpos(B)=Aorpos(B)=NORpos(B)=Q)ThenABisnew该规则该规则表示表示:如果由两个如果由两个词词构成的二元构成的二元组组中中A为为名名词词，而而B为动词为动词或形容或形容词词或名或名词词或量或量词词，则则将将该该二元二元组组做做标记标记，认为认为是新是新词词。2、If(pos(A)=VANDpos(B)=A)ThenABisnew例如：减肥，模仿秀例如：减肥，模仿秀46分分词结词结果中含果中含词词数最少数最少等价于在有向等价于在有向图图中搜索最短路径中搜索最短路径方法：最小匹配算法方法：最小匹配算法n分段；分段；n逐段统计最短路径（逐段统计最短路径（dijkstra算法：用于计算一个节算法：用于计算一个节点到其他所有节点的最短路径）；点到其他所有节点的最短路径）；n得到若干分词结果：得到若干分词结果：n发展发展/中中/国家国家n发展发展/中国中国/家；家；n统计排歧。统计排歧。最少分词问题最少分词问题4748按处理对象的不同，可分为：按处理对象的不同，可分为：1、字字处理技术处理技术2、词词处理技术处理技术 词是自然语言中最小的有意义的构成单位，词是自然语言中最小的有意义的构成单位，是最基本的研究对象。词处理主要包括分词、词是最基本的研究对象。词处理主要包括分词、词性标注、词义消歧。性标注、词义消歧。3、语句语句处理技术处理技术4、篇章篇章处理技术处理技术基于规则的句法分析理论和方法基于规则的句法分析理论和方法uChomsky的形式语言理论的形式语言理论u上下文无关文法上下文无关文法u转移生成文法转移生成文法u扩充转移网络扩充转移网络491、chomsky的形式的形式语语言理言理论论用用G表示形式表示形式语语法，法，G定定义为义为四元四元组组：G=（Vn,Vt,S,P）（1）Vt：终结终结符集合。符集合。是一个形式是一个形式语语言的基本符号。它言的基本符号。它们们能在能在一个形式一个形式语语法的推法的推导规则导规则的的输输入或入或输输出字符串存在，而且它出字符串存在，而且它们们不能被分解成更小的不能被分解成更小的单单位。一个位。一个语语法的法的规则规则不能改不能改变终结变终结符符。下面的下面的语语法有两个法有两个规则规则：xxaxax在在这这种种语语法之中，法之中，a是一个是一个终结终结符，因符，因为为没有没有规则规则可以把可以把a变变成成别别的符号。不的符号。不过过，有两个，有两个规则规则可以把可以把x变变成成别别的符号，所的符号，所以以x是非是非终结终结符。一个形式符。一个形式语语法所推法所推导导的形式的形式语语言必言必须须完全完全由由终结终结符构成。符构成。54短语结构语法短语结构语法（2）Vn：非：非终结终结符集合符集合，是可以被取代的符号，不能，是可以被取代的符号，不能处处于生于生成成过过程的程的终终点，即在点，即在实际实际句子中不出句子中不出现现。在上下文无关文法。在上下文无关文法中，每个推中，每个推导规则导规则的左的左边边只能有一个非只能有一个非终结终结符而不能有两个符而不能有两个以上的非以上的非终结终结符或符或终结终结符。符。（3）S：起始符号。：起始符号。一个一个语语法中必法中必须须有一个起始符号，有一个起始符号，这这个起个起始符号属于非始符号属于非终结终结符的集合。符的集合。（4）P：重写：重写规则规则，也叫做，也叫做产产生式生式规则规则集合集合（产生式的形式是产生式的形式是P Pa a）。）。55采用短语结构语法对英语子集语法的描述采用短语结构语法对英语子集语法的描述G=（Vn,Vt,S,P）Vn=S，NP，VP，PP，N，V，Prep，Det；Vt=the,girl,letter,pencil,write,witha；S=s；P：uSNPVP.该规则该规则表示表示“句子句子”由由“名名词词短短语语动词动词短短语语”组组成成uNPDetN.该规则该规则表示表示“名名词词短短语语”由由“冠冠词词名名词词”组组成成uVPVPPP.该规则该规则表示表示“动词动词短短语语”由由“动词动词短短语语介介词词短短语语”组组成成56uVPVNP.该规则该规则表示表示“动词动词短短语语”由由“动词动词名名词词短短语语”组组成成uPPPrepNP.该规则该规则表示表示“介介词词短短语语”由由“介介词词名名词词短短语语”组组成成uDetthe|a.该规则该规则表示表示“冠冠词词”由由the或或a组组成成uNgirl|letter|pencil.该规则该规则表示表示“名名词词”由由girl或或letter或或pencil组组成成uVwrite.该规则该规则表示表示“动词动词”由由write组组成成uPrepwith.该规则该规则表示表示“介介词词”由由with组组成成57n在在对对一个句子分析一个句子分析过过程中，如果把分析句子各成分程中，如果把分析句子各成分间间关系的推关系的推导过导过程用程用树树形形图图表示出来的表示出来的话话，那么，那么这这种种图图称作句法分析称作句法分析树树。n对对句子句子“thegirlwritestheletterwithapencil”进进行行分析的分析的语语法法树树如下：如下：58句法分析句法分析树树语法树中的叶子结点语法树中的叶子结点语法树中的叶子结点语法树中的叶子结点即为分析的句子。即为分析的句子。即为分析的句子。即为分析的句子。例：已知例：已知汉语汉语句子的分句子的分词词和和词词性性标标注注结结果如下：果如下：他他/PRON教教/V我我/PRON学学/V日日语语/N请请画出画出该该句子的句子的语语法法树树，并，并给给出上下文无关出上下文无关规则规则。G=（Vt,Vn,S,P）Vn=S，PRON，V，OBJECT，NVt=他他,教教,我我,学学,日日语语S=SP:SPRONVOBJECTOBJECTN|SPRON他他|我我V教教|学学N日日语语59PRON主语主语OBJECT宾语宾语0型文法（型文法（type 0 grammar）上下文有关文法（上下文有关文法（CSG）如果所有产生式都有右边部分长度如果所有产生式都有右边部分长度大于等于左边部分，那么大于等于左边部分，那么G是上下是上下文有关文法文有关文法上下文无关文法（上下文无关文法（CFG）如果如果所有产生式的左边如果如果所有产生式的左边部分都是单个非终极符号，部分都是单个非终极符号，那么那么G是上下文无关文法是上下文无关文法正则文法（正则文法（RG）如果所有产生式的右边部分如果所有产生式的右边部分都是以终极符号开始、含有都是以终极符号开始、含有至多一个非终极符号、如果至多一个非终极符号、如果有非终极符号则出现在最右有非终极符号则出现在最右边，那么边，那么G是正则文法。是正则文法。请判断以下文法的类型请判断以下文法的类型G1:G1:SCDSCDAbbAAbbACaCACaCABaaBBaaBCbCB CbCB BbbBBbbBADaD ADaD CaCaBDbD BDbD DbDbAabDAabDG1G1是上下文有关文法是上下文有关文法请判断以下文法的类型请判断以下文法的类型G2:SaB,G2:SaB,AbAAAbAASbA,SbA,BbBbAa,Aa,BbSBbSAaS,AaS,BaBBBaBBG2G2是上下文无关文法是上下文无关文法请判断以下文法的类型请判断以下文法的类型G3:S0A G3:S0A A1BA1B S1B S1B B1B B1B S0 B1 S0 B1 A0A A0A B0 B0 A0S A0SG3G3是正则文法是正则文法自动机自动机文法、语言和自动机文法、语言和自动机2、上下文无关文法、上下文无关文法3、转换生成文法、转换生成文法4、扩充转移网络、扩充转移网络（1）有限状态转移网络）有限状态转移网络u以冠词以冠词“The”开头的一类名词短语开头的一类名词短语NP的转移网络，它可以的转移网络，它可以拥有零个或多个形容词；最后以一个名词结尾。拥有零个或多个形容词；最后以一个名词结尾。u组成：一组状态（或称结点）和一组弧组成。组成：一组状态（或称结点）和一组弧组成。u例子：输入例子：输入“theprettypicture”。从起始状态从起始状态NP开始，只有一条标注着开始，只有一条标注着“the”的外射弧。由于输入串中的的外射弧。由于输入串中的the能同它匹配，所以能同它匹配，所以“the”从输入串中删除，过程进入图中的状态从输入串中删除，过程进入图中的状态NP1。此时输入串是此时输入串是“prettypicture”，由于第一个，由于第一个“pretty”的词类是的词类是ADJ，同标注同标注ADJ的弧匹配，于是的弧匹配，于是“pretty”从输入串中删除，但沿着从输入串中删除，但沿着ADJ弧转弧转移的结果是再次回到这个移的结果是再次回到这个NP1状态。状态。此时输入串只剩下此时输入串只剩下“picture”，由于它是一个名词，因此发生了沿，由于它是一个名词，因此发生了沿N弧弧前进到结束状态的转移。输入串成为空串，分析成功。前进到结束状态的转移。输入串成为空串，分析成功。这这个句子的个句子的识别还识别还可以在网可以在网络络中走其它弧，如由中走其它弧，如由状状态态c输输入入“swallow”也可以走弧也可以走弧cd，但接下来，但接下来输输入入“flies”时时就被拒就被拒绝识别绝识别了。由此可看出网了。由此可看出网络络识别识别的的过过程程应应找出各种可能的路径，因此算法找出各种可能的路径，因此算法要采用要采用并行算法或回溯算法并行算法或回溯算法。96(1)(1)并行算法。并行算法的关键是在任何一个状态并行算法。并行算法的关键是在任何一个状态都要选择所有可以到达下一个状态的弧都要选择所有可以到达下一个状态的弧,同时进同时进行试验。行试验。(2)(2)回溯算法。回溯算法则是在所有可以通过的弧回溯算法。回溯算法则是在所有可以通过的弧中选出一条往下走中选出一条往下走,并保留其他可能性并保留其他可能性,以便必要以便必要时可以回过来选择之。这种方式需要一个堆栈结时可以回过来选择之。这种方式需要一个堆栈结构。构。（2）递归转移网络（）递归转移网络（RTN）l是对是对有限转移网络的一种扩展有限转移网络的一种扩展，在，在RTN中每条弧的中每条弧的标注不仅可以是一个终结符（词或词类），而且可标注不仅可以是一个终结符（词或词类），而且可以是一个用来指明另一个网络名字的非终结符。以是一个用来指明另一个网络名字的非终结符。l例如，下面是一部上下文无关语法：例如，下面是一部上下文无关语法：SNPVNPPP*NPTADJ*NPP*PPPNPX*表示符号表示符号X可以出可以出现现零次或多次。零次或多次。（3）扩充转移网络（）扩充转移网络（ATN）ATN ATN语法属于一种增强型的上下文无关语法，即语法属于一种增强型的上下文无关语法，即用上下文无关文法描述句子文法结构，并同时提供用上下文无关文法描述句子文法结构，并同时提供有效的方式将各种理解语句所需要的知识加到分析有效的方式将各种理解语句所需要的知识加到分析系统中，以增强分析功能，从而使得应用系统中，以增强分析功能，从而使得应用ATNATN的句法的句法分析程序具有分析上下文有关语言的能力。分析程序具有分析上下文有关语言的能力。ATN ATN主要是对转移网络中的弧附加了过程而得到主要是对转移网络中的弧附加了过程而得到的。当通过一个弧的时候，附加在该弧上的过程就的。当通过一个弧的时候，附加在该弧上的过程就会被执行。这些过程的主要功能是（会被执行。这些过程的主要功能是（I I）对文法特征对文法特征进行赋值；进行赋值；(II)II)检查数（检查数（numbernumber）或人称（第一、或人称（第一、二或三人称）条件是否满足，并据此允许或不允许二或三人称）条件是否满足，并据此允许或不允许转移。转移。ATN在三方面对在三方面对RTN作了作了扩展扩展和和增强增强：（1）添置了一组）添置了一组寄存器寄存器，用来存储分析过程中得，用来存储分析过程中得到的中间结果和有关信息。到的中间结果和有关信息。例如，例如，“小王研究鲁迅的文章小王研究鲁迅的文章”可能先被分析可能先被分析为为NPVP，但发现后面的词是，但发现后面的词是“发表发表”，则要，则要回到前面的某个转移点重新分析，选择另一条路。回到前面的某个转移点重新分析，选择另一条路。（2）每条弧上除了用句法范畴来标注以外，可以附）每条弧上除了用句法范畴来标注以外，可以附加任意加任意测试测试，只有当弧上的这种测试成功之后才，只有当弧上的这种测试成功之后才能用这条弧。能用这条弧。（3）每条弧上还可以附加某些）每条弧上还可以附加某些动作动作，当通过一条，当通过一条弧时，相应的动作便被依次执行，这些动作主要弧时，相应的动作便被依次执行，这些动作主要用来用来设置或修改寄存器的内容设置或修改寄存器的内容。例：一个简单的名词短语例：一个简单的名词短语(NP)的扩充转移网的扩充转移网 络，络，网络中弧上的条件和操作如下所示：网络中弧上的条件和操作如下所示：u该网络主要是用来检查该网络主要是用来检查NPNP中的中的数的一致值问题数的一致值问题。u特征特征是是Number(Number(数数),),有两个值：有两个值：singular(singular(单数单数)和和plural(plural(复数复数),),缺省值是缺省值是(空空)。uC C是弧上的条件是弧上的条件,A,A是弧上的操作是弧上的操作,*,*是当前词是当前词,proper,proper是专用名词是专用名词,detdet是限定词是限定词,PP,PP是介词短语是介词短语,*.Number,*.Number是当前词的是当前词的“数数”。u该扩充转移网络有一个网络名该扩充转移网络有一个网络名NPNP。网络。网络NPNP可以是其可以是其他网络的一个子网络他网络的一个子网络,也可以包含其他网络也可以包含其他网络,如其中如其中的的PPPP就是一个子网络就是一个子网络,这就是网络的递归性。这就是网络的递归性。u弧弧NP-1将当前词的将当前词的Number放入当前放入当前NP的的Number中；中；u而弧而弧NP-4则要求当前则要求当前noun的的Number与与NP的的Number是是相同时，或者相同时，或者NP的的Number为空时为空时,将将noun作为作为NP的的Number，这就要求，这就要求det的数和的数和noun的数是一致的。因的数是一致的。因此此thisbook,thebook,thebooks,thesebooks都可顺利通都可顺利通过这一网络过这一网络,但是但是thisbooks,或或thesebook就无法通过。就无法通过。u如果当前如果当前NP是一个代词是一个代词(pron.)或者专用名词或者专用名词(proper),那么网络就从那么网络就从NP-5或或NP-6通过通过,这时这时NP的数就是代词或的数就是代词或专用名词的数。专用名词的数。PP是一个修饰前面名词的介词短语是一个修饰前面名词的介词短语,一一旦到达旦到达PP弧就马上转入子网络弧就马上转入子网络PP.例：一个句子的例：一个句子的ATN,主要用来识别主、被动态的句子。主要用来识别主、被动态的句子。nS网络中所涉及的功能名和特征维包括：网络中所涉及的功能名和特征维包括：n功能名：功能名：Subject(主语主语),Direct-Obj(直接宾语直接宾语),Main-Verb(谓语动谓语动词词),Auxs.(助动词助动词),Modifiers(修饰语修饰语)。n特征维：特征维：nVoice(语态语态)：Active(主动态主动态),Passive(被动态被动态),缺省值是缺省值是Active。nType(动词类型动词类型)：Be,Do,Have,Modal,Non-Aux,缺省值是缺省值是Non-AuxanForm(动词式动词式)：Inf不定式不定式),Present(现在式现在式),Past(过去式过去式),Pres-part(现在分词现在分词),Past-part(过去分词过去分词),缺省值是缺省值是Present。lSubject即把当前成分放入名为即把当前成分放入名为Subject的功能寄存器的功能寄存器(当前当前成分作主语成分作主语)。l是一种添加操作是一种添加操作,Auxs.Main-Verb就是将当前的谓语动词就是将当前的谓语动词添加到添加到Auxs功能寄存器中功能寄存器中(原来原来Auxs中可能已有内容中可能已有内容)。l在在S网络中网络中,当弧当弧S-2遇到第一个动词时遇到第一个动词时,就把它置入就把它置入Main-Verb,但是在接下来的弧但是在接下来的弧S-3中发现中发现Main-Verb中刚才被置入的是助动中刚才被置入的是助动词词,网络操作就把网络操作就把Main-Verb中的内容添加到中的内容添加到Auxs寄存器的尾部。寄存器的尾部。若若Auxs为空为空,添加操作与赋值是相同的添加操作与赋值是相同的,但是当但是当Auxs非空时非空时(有几有几个助动词个助动词),这即是一个添加操