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