第十章自然语言理解

第十章自然语言理解第一页，共六十页，编辑于2023年，星期一10.1自然语言理解概述

什么是语言和语言理解？自然语言理解与人类的哪些智能有关？自然语言理解的系统如何组成?等等。这些问题是我们开始研究自然语言理解时感兴趣的。

10.1.1语言和语言理解

语言是用于传递信息的表示方法、约定和规则的集合，它由语句组成，每个语句又由单词组成；组成语句和语言时，应遵循一定的语法与语义规则。如果没有各种口语和书面语，如英语、华语、法语和德语等，人类之间思想、感情和技术交流就难以想象。语言是随着人类社会和人类自身的发展而不断进化的。研究自然语言理解，必须对自然语言构成有基本认识。第二页，共六十页，编辑于2023年，星期一

语言是音义结合的词汇和语法体系，是实现思维活动的物质形式。语言是一个符号体系，但与其他符号体系又有所区别。

语言是以词为基本单位的，词汇又受到语法的支配才可构成有意义的句子，句子按一定的形式再构成篇章等。词汇又可分为词和熟语。熟语就是一些词的固定组合，如汉语中的成语。词又由词素构成，“教师”是由“教”和“师”这两个词素所构成的。词素是构成词的最小的有意义的单位。“教”这个词素本身有教育和指导的意义，“师”则包含了“人”的意义。第三页，共六十页，编辑于2023年，星期一

语法是语言的组织规律。语法规则制约着如何把词素构成词，词构成词组和句子。语言正是在这种严密的制约关系中构成的。用词素构成词的规则叫构词法，如教+师→教师。一个词又有不同的词形、单数、复数、阴性、阳性等等。这种构造词形的规则称为构形法，如教师+们→教师们。这里只是在原来的词后面加上一个复数意义的词素，所构成的并不是一个新的词，而是同一词的复数形式。构形法和构词法称为词法。

第四页，共六十页，编辑于2023年，星期一语法中的另一部分就是句法。句法也可分成两部分：词组构造法和造句法。词组构造法是词搭配成词组的规则，如红+铅笔→红铅笔。这里“红”是一个修饰铅笔的形容词，它与名词“铅笔”组合成了一个新的名词。造句法则是用词或词组造句的规则，“我是计算机科学系的学生”，这是按照汉语造句法构造的句子。下图就是上述语法构造的一个完整的图解。另一方面，语言是音义结合的，每个词汇有其语音形式。一个词的发音由一个或多个音节组合而成，音节又由音素构成，音素分为元音音素和辅音音素。音素是指一个发音动作所构成的最小的语音单位。第五页，共六十页，编辑于2023年，星期一

语言

词汇语法

词熟语词法句法词素构词法词组构造法造句法构形法语言的构成图第六页，共六十页，编辑于2023年，星期一

从微观上讲，语言理解是指从自然语言到计算机系统内部之间的一种映射。从宏观上看，语言理解是指机器能够执行人类所期望的某些语言功能。这些功能包括：

(1)回答有关提问；

(2)提取材料摘要；

(3)文本释义；

(4)不同语言翻译。自然语言理解是语言学、逻辑学、生理学、心理学、计算机科学和数学等相关学科发展和结合而形成的一门交叉学科；它能够理解口头语言或书面语言。语言交流实际上是一种基于知识的通信。

第七页，共六十页，编辑于2023年，星期一

对自然语言的理解是一个十分艰难的任务，即使建立一个只能理解片言断语的计算机系统，也是很不容易的。这中间有大量的极为复杂的编码和解码问题。一个能够理解自然语言的计算机系统就像一个人那样需要上下文知识以及根据这些知识和信息进行推理的过程。自然语言不仅有语义、语法和语音问题，而且还存在模糊性等问题。具体地说，自然语言理解的困难是由下列3个因素引起的：

(1)目标表示的复杂性；

(2)映射类型的多样性；

(3)源表达中各元素间交互程度的差异性。

第八页，共六十页，编辑于2023年，星期一第九页，共六十页，编辑于2023年，星期一第十页，共六十页，编辑于2023年，星期一第十一页，共六十页，编辑于2023年，星期一第十二页，共六十页，编辑于2023年，星期一10.1.4自然语言理解研究的进展

机器翻译是自然语言理解最早的研究领域。

70年代初期，语言理解对话系统的研究取得进展。伍兹的LUNAR系统、威诺甘德的SHRDLU系统和香农的MARGIE系统等是语言理解对话系统的典型实例。新型的智能计算机要求设计出更为友好的人机界面，使自然语言、文字、图象和声音等信号能直接输入计算机。口语理解研究促进人机对话系统走向实用化。自然语言是表示知识最为直接的方法。因此，自然语言理解的研究也为专家系统的知识获取提供了新的途径。此外，自然语言理解的研究已促进计算机辅助语言教学(CALI)和计算机语言设计(CLD)等的发展。第十三页，共六十页，编辑于2023年，星期一10.1.5自然语言理解过程的层次

语言虽然表示成一连串的文字符号或者一串声音流，但其内部事实上是一个层次化的结构，从语言的构成中就可以清楚的看到这种层次性。一个文字表达的句子是由词素→词或词形→词组或句子，而用声音表达的句子则是由音素→音节→音词→音句，其中每个层次都是受到语法规则的制约。因此，语言的分析和理解过程也应当是一个层次化的过程。许多现代语言学家把这一过程分为5个层次：语音分析、词法分析、句法分析和语义分析和语用分析。虽然这种层次之间并非是完全隔离的，但是这种层次化的划分的确有助于更好地体现语言本身的构成。第十四页，共六十页，编辑于2023年，星期一

1、语音分析在有声语言中，最小可独立的声音单元是音素，音素是一个或一组音，它可与其他音素相区别。语音分析则是根据音位规则，从语音流中区分出一个个独立的音素，再根据音位形态规则找出一个个音节及其对应的词素或词。

2、词法分析

其主要目的是找出词汇的各个词素。如unchangeable是由un-change-able构成的。在英语语言中，找出句子中的词汇是一件很容易的事，因为词与词之间是由空格来分隔的。但要找出各个词素就复杂得多，如importable，它可以是im-port-able或improt-able。而在汉语中要找出一个个词素则是很容易的，每个字就是一个词素。但要切分出各个词就远不是那么容易。如“我们研究所有东西”，可以是“我们—研究所—有—东西”也可以是“我们—研究—所有—东西”。第十五页，共六十页，编辑于2023年，星期一

3、句法分析

是对句子和短语的结构进行分析。自动句法分析的方法很多，有短语结构语法、格语法、扩充转移网络、功能语法等等。句法分析的目的就是找出词、短语等的相互关系以及各自在句子中的作用等，并以一种层次结构来加以表达。这种层次结构可为反映从属关系，直接成分关系，也可是语法功能关系。

4、语义分析

通过分析找出词义、结构意义及其结合意义，从而确定语言所表达的真正含义或概念。在语言自动理解中，语义愈来愈成为一个重要的研究内容。

5、语用分析

研究所在外界环境对语言使用所产生的影响。描述了语言的环境知识、语言与语言使用者在某个给定语言环境中的关系。第十六页，共六十页，编辑于2023年，星期一

词法分析的主要目的是从句子中切分出单词,找出词汇的各个词素,从中获得单词的语言学信息并确定单词的词义。不同的语言对词法分析有不同的要求，例如英语和汉语就有较大的差别。汉语中每个字就是一个词素，找出各个词素相当容易，但要切分出各个词就非常困难。在英语中单词之间用空格自然分开，很容易找出句子的每个词汇，但英语单词有词性、数、时态、派生、变形等，要找出各个词素就复杂得多。例如program可变化出programming,programmable,programmed,programs和programmer等。如果把某些词素的派生、变形、数、时态等变化都收入词典将是非常庞大，但它们的词根只有一个。支持词素分析，可以极大地压缩自然语言理解系统中电子词典的规模。第十七页，共六十页，编辑于2023年，星期一第十八页，共六十页，编辑于2023年，星期一

10.3

句法分析

句法分析目的就是找出词、短语等的相互关系以及各自在句子中的作用，并以一种层次结构来加以表达。下面介绍基于规则的句法分析方法：

第十九页，共六十页，编辑于2023年，星期一

一部短语结构语法定义的语言L(G)就是从起始符S推导出终结符号串W的集合，是由一系列产生式规则组成的。下面给出一个简单的短语结构语法。

例10.1

G=（T，N，S，P）

T={the,man,killed,a,deer,likes}N={S,NP,VP,N,ART,V,Prep,PP}S=SP:(1)S→NP+VP(2)NP→N(3)NP→ART+N(4)VP→V(5)VP→V+NP(6)ART→the|a(7)N→man|deer(8)V→killed|likes第二十页，共六十页，编辑于2023年，星期一10.3.3句法模式匹配和转移网络

句法分析最为简单、直观的方法也许就是模式匹配。句法模式匹配就是采用句法模式来对语言的句子进行匹配从而进行的句法分析。例如：bearslovehoney可用句法模式noun+verb+noun来匹配；句子的主语有许多模式noun，adj.+noun，adj.+adj.+noun，adj.+adj.+adj+noun，…,对此可采用形式化的表达方式（adj.*noun），其中*表示可有可无且可重复出现。一个句子可以表示成：（pronoun∨（adj.*noun））verb（pronoun∨（adj.*noun））第二十一页，共六十页，编辑于2023年，星期一转移网络(TN)q0nounpron.q2q1adjq3qTverbverbpron.nounq4q5adj但是自然语言是非常多样化的，因而需要有许多模式。这些模式可用状态转移图来表示，这种用状态转移图来表示的表达方式称之为转移网络（TN，transitionnetwork）。如下图所示，图中，q0,q1,…，qT是状态，q0是初态，qT是终态。弧上给出了状态转移的条件以及转移的方向。该网络可用于分析句子也可用于生成句子。第二十二页，共六十页，编辑于2023年，星期一用TN来识别句子Thelittleorangeducksswallowflies的过程如表10.1。（这里忽略了词法分析，网络如图所示）表10.1句子识别过程

第二十三页，共六十页，编辑于2023年，星期一识别过程到达f状态(终态)，所以该句子被成功地识别了。分析结果如下图所示。从上述过程中可以看出，这个句子还可以在网络中走其他弧，如词ducks也可以走弧，但接下来的swallow就找不到合适的弧了。此时对应于这个路径，该句子就被拒识了。由此看出，网络识别的过程中应找出各种可能的路径，因此算法要采用并行或回溯机制。转移网络实例图第二十四页，共六十页，编辑于2023年，星期一

1.并行算法

并行算法的关键是在任何一个状态都要选择所有可以到达下一个状态的弧，同时进行试验。

2.回溯算法

回溯算法则是在所有可以通过的弧中选出一条往下走，并保留其他的可能性，以便必要时可回过来选择之。这种方式需要一个堆栈结构。转移网络实例图第二十五页，共六十页，编辑于2023年，星期一10.3.4扩充转移网络

扩充转移网络ATN是由伍兹(Woods)在1970年提出的，之后卡普兰(Kaplan)等人对其作了一些改进。ATN是由一组网络所构成的，每个网络都有一个网络名，每条弧上的条件扩展为条件加上操作。这种条件和操作采用寄存器的方法来实现，在分析树的各个成分结构上都放上寄存器，用来存放句法功能和句法特征，条件和操作将对它们不断地进行访问和设置。ATN弧上的标记也可以是其他网络的标记名，因此ATN是一种递归网络（任何一个网络都可以调用包括它自己在内的任何其他网络）。在ATN中还有一种空弧jump，它不对应一个句法成分也不对应一个输入词汇。第二十六页，共六十页，编辑于2023年，星期一

ATN的每个寄存器由两部分构成：句法特征寄存器和句法功能寄存器。在特征寄存器中，每一维特征都有一个特征名和一组特征值，以及一个缺省值来表示。如“数”的特征维可有两个特征值“单数”和“复数”，缺省值可以是空值。英语中动词的形式可以用一维特征来表示：Form：present,past,present-participle,past-participle.Default:present.功能寄存器则反映了句法成分之间的关系和功能。分析树的每个节点都有一个寄存器，寄存器的上半部分是特征寄存器，下半部分是功能寄存器。图10.5所示是一个简单的名词短语(NP)的扩充转移网络，网络中弧上的条件和操作如下：第二十七页，共六十页，编辑于2023年，星期一NP-1：fg

A：Number*.NumberNP-4：ghC：Number=*.NumberorφA：Number*.NumberNP-5：fhA：Number*.NumberNP-6：fh

A：Number=*.Number

ghfNP7:pp8:send3:adj4:noun2:jump1:det5:pron.6:prop.名词短语(NP)的扩充转移网络第二十八页，共六十页，编辑于2023年，星期一

该网络主要是用来检查NP中的数的一致值问题。其中用到的特征是Number(数)，它有两个值Singular(单数)和plural(复数)，缺省值是φ(空)。C是弧上的条件，A是弧上的操作，*是当前词，proper是专用名词，Det是限定词，PP是介词短语，*.Number当前词的“数”。该扩充转移网络有一个网络名NP。弧NP-1将当前词的Number放入当前NP的Number中，而弧NP-4则要求当前noun的Number与NP的Number是相同时，或者NP的Number为空时，将noun作为NP的Number，这就要求det的数和noun的数是一致的。因此，thisbook，thebook，thebooks，thesebooks都可顺利通过这一网络，但是thisbooks，或thesebook就无法通过。如果当前NP是一个代词(Pron.)或者专用名词(Proper)，则网络就从NP-5或NP-6通过，这时NP的数就是代词或专用名词的数。PP是修饰前面名词的介词短语，一旦到达PP弧就马上转入子网络PP。第二十九页，共六十页，编辑于2023年，星期一

S网络中所涉及的功能名和特征维包括：

功能名：Subject(主语)，DirectObj（直接宾语），Main-Verb（谓语动词），Auxs（助动词），Modifiers（修饰语）。

Voice（语态）特征维：Active（主动态），Passive（被动态），缺省值是Actire；

Type（动词类型）：Be,Do,Have,Modal,Non-Aux,缺省值是Non-Aux；

Form（动词式）：Inf（不定式），Present（现在式），Past（过去式），pres-part（现在分词），Past-Part(过去分词)，缺省值是Present

下图是一个句子的ATN，主要用来识别主、被动态的句子，从中可以看到功能寄存器的应用第三十页，共六十页，编辑于2023年，星期一网络描述如下：S-1：ab

A：Subject*.S-2：bc

A：Main-Verb*.S-3：cc（判断谓词动词类型）

C：Main-Verb.Type=Be，Do，HaveorModal

A：Auxs<=Main-Verb，Main-Verb*.S-4：cd

C：*.Form=Past-partandMain-Verb.Type=Be

A：Voice←Passive，Auxs<=Main-Verb,

Main-Verb←*.,*.Direct-Obj←Subject,

Subject←dummy-NP（形式主语，可能暂时为空节点）第三十一页，共六十页，编辑于2023年，星期一S-5:cd

A：Direct-Obj*.S-6:dd

A：Modifiers<=*.S-7：dd

C：Voice=PassiveandSubject=dummy-NPand*.Prep=“by”A：Subject*.Prep-ObjectS-8：dNoConditions,actionsorinitializations.

S-8是赋值操作

Subject*即把当前成分放入名为Subject的功能寄存器。<=是一种添加操作，Auxs<=Main-Verb就是将当前的谓语动词添加到Auxs功能寄存器中(原来Auxs可能已有内容)。第三十二页，共六十页，编辑于2023年，星期一

S网络中，当弧S-2遇到第一个动词时，就把它置入Main-Verb，但是在接下来的弧S-3中发现Main-Verb中刚才被置入的是助动词，网络操作就把Main-Verb中的内容添加到Auxs寄存器的尾部。若Auxs是空时，添加操作与赋值是相同的，但是当Auxs非空时(有几个助动词)这是一个添加操作。另外，网络中有一种dummy节点，这是一种空节点，用来表示一种形式上的或者预示的成分，如形式上的主语等。弧S-4和S-7就是对于被动态句子的分析和处理。弧S-4主要是识别被动态的谓语动词，一旦确认是被动态，则将当前的主语作为直接宾语，弧S-7是处理被动态句子中by所引导的介词短语，该介词的宾语就是实际上的主语。第三十三页，共六十页，编辑于2023年，星期一

一完整的ATN是相当复杂的，在实现过程中还必须解决许多问题，如非确定性分析、弧的顺序、等等。ATN方法在自然语言理解的研究中得到了广泛的应用。10.3.5词汇功能语法(LFG)

词汇功能语法是由卡普兰和布鲁斯南在1982年提出的，它是一种功能语法，但是更加强调词汇的作用。LFG用一种结构来表达特征、功能、词汇和成分的顺序。ATN语法和转换语法都是有方向性的，ATN语法的条件和操作要求语法的使用是有方向的，因为寄存器只有在被设置过之后才可被访问。LFG的一个重要工作就是通过互不矛盾的多层描述来消除这种有序性限制。

第三十四页，共六十页，编辑于2023年，星期一

LFG对句子的描述分为两部分：直接成分结构(Constituentstructure)和功能结构(Functionalstructure)。C-structure是由上下文无关语法产生的表层分析结果,结点采用名词短语标记来标注。通过附加到语法规则和词条定义上的功能方程式经过一系列代数变换产生F-structure。

LFG采用两种规则：加入下标的上下文无关的语法规则和词条信息。下表给出了一些词汇功能语法的规则和词条信息。

其中↑表示规则左侧的那个结点，如规则中NP的↑就是S，VP的↑也是S；↓则表示当前结点结点本身。因此，(↑Subject)=↓就表示S的主语是当前NP。方程式↑=↓说明VP的全部属性都应转移给支配它的S结点。“＜＞”中表达的是句法模式，Hand=＜(↑Subject),(↑Object)，(↑Object-2)＞，表示谓语动词hand要有一个主语、一个直接宾语和一个间接宾语。例如，对于句子：Agirlhandedthebabythetoys.

第三十五页，共六十页，编辑于2023年，星期一LFG语法规则与词条语法规则第三十六页，共六十页，编辑于2023年，星期一首先利用句法规则可以推导出它的C-structure直接成分结构如下图所示:句法树中带标号的非叶结点，用具体的变量xi替代，并建立功能描述方程。方程的建立只要将语法规则和词条规则中的↑用父节点变量来替代，↓用当前节点变量来代替即可。第三十七页，共六十页，编辑于2023年，星期一规则S→NPVP的下标有两组方程：一个是(↑Subject)=↓，替换得到(x1Subject)=x2；另一个是↑=↓，即x1=x3。在词汇规则中，词a对应了两条规则

(↑Definiteness)=Indefinite，(↑Number)=Singular，词a的父节点是NP，即x2，所以得到方程式

(x2Definiteness)=Indefinite,(x2Number)=Singular其他功能描述方程如下表所示：第三十八页，共六十页，编辑于2023年，星期一上述方程式通过合并和变量替代求得这个方程组的解，获得的解即句子的功能结构（F-structure），如下图所示。第三十九页，共六十页，编辑于2023年，星期一上述过程如果能够得到一组以上解，则句子就是可识别的，并获得一个以上分析结果。分析获得多个解则说明原句子中存在着歧义现象，无解则说明无法识别。

LFG同样也可以用于句子的生成。分析和生成的区别仅在于第一步，分析是由句子到C-structure,而生成则是由上下文无关语法直接产生C-structure和句子。同样如果通过求解最终可有一个以上的解，则该句子就是正确的。第四十页，共六十页，编辑于2023年，星期一句子一般有简单句和复合句之分。简单句的理解比复合句要容易，又是理解复合句的基础。因此，我们首先讨论简单句的理解，然后讨论复合句的理解。10.5.1

简单句的理解方法

由于简单句是可以独立存在，因而为了理解一个简单句，即建立起一个和该简单句相对应的机内表达，需要做以下两方面的工作：

(1)理解语句中的每一个词。

(2)用这些词组成一个可表达整个语句意义的结构。

第一项工作看起来很容易，似乎只是查一下字典就可以解决。而实际上由于许多单词有不止一种含义，因而只由单词本身往往不能确定其在句中的确切含义，需要通过语法分析和上下关系等才能最终确定。10.5

句子的自动理解第四十一页，共六十页，编辑于2023年，星期一例如，单词diamond有“菱形”、“棒球场”和“钻石”三种意思，在语句“JohnsawSusan′sdiamondshimmeringfromacrosstheroom.”中，由于“shimmering”的出现，则显然“diamond”是“钻石”的含义，因为“菱形”和“棒球场”都不会闪光。再如在语句“I′llmeetyouatthediamond.”中，由于“at”后面需要一个时间或地点作为它的宾语，因而显然这里的“diamond”是“棒球场”的含义，而不能是其它含义。

第二项也是一个比较困维的工作。因为要联合单词来构成表示一个句子意义的结构，需要依赖各种信息源，其中包括所用语言的知识、语句所涉及领域的知识以及有关该语言使用者应共同遵守的习惯用法的知识。第四十二页，共六十页，编辑于2023年，星期一由于这个解释过程涉及到许多事情，因而常常将这项工作分成以下3个部分来进行：

句法分析

将单词之间的线性次序变换成一个显示单词如何与其它单词相关联的结构。

语义分析

各种意义被赋于由句法分析程序所建立的结构，即在句法结构和任务领域内对象之间进行映射变换。

语用分析

为确定真正含义，研究语言所在的外界环境对语言使用所产生的影响。实际上这3个阶段之间是相互关联的，总是以各种方法相互影响着。尽管在某种程度上把它们分开是有效的，但绝对分开是不可能的。第四十三页，共六十页，编辑于2023年，星期一

1.关键字匹配法最简单的自然语言理解方法，也许要算是关键字匹配法了，它在一些特定场合下是有效的。其方法简单归纳起来是这样的：在程序中规定匹配和动作两种类型的样本。然后建立一种由匹配样本到动作样本的映射。当输入语句与匹配样本相匹配时，就去执行相应样本所规定的动作，这样从外表看来似乎机器真正实现了能理解用户问话的目的。例如在一个列车运行数据库系统中，规定了以下几个匹配样本：第四十四页，共六十页，编辑于2023年，星期一

(a)从<处所>到<处所>有<车种>吗?

(b)从<处所>到<处所>有<?数量><车种>?

(c)从<处所>到<处所>有<?指数量><车种>?

(d)<车次>在<处所>停吗?

(e)<车次>经过<处所>吗?

(f)<车次>有<车组>吗?

(g)到<处所>的<车种>都有<车组>吗?

(h)<车次><?原因>没有<车组>?

(i)<车次><?原因>有<车组>?

(j)<车次><?时刻>从<处所>开出?

(k)<车次><?时刻>到达<处所>?

(l)从<处所>到<处所><?指数量><车次>最快?第四十五页，共六十页，编辑于2023年，星期一其中，<…>可与任何具有规定特性的单词匹配，如<处所>可以和“北京”、“上海”等表示地点的单词匹配；<车种>可以和“特快”、“直快”等匹配；<?数量>可与“几趟”等匹配；<?指数量>可与“哪几趟”等匹配；<车组>可与“餐车”、“卧铺”等匹配，<?原因>可与“为什么”、“怎么”等匹配；<?时刻>可与“什么时候”、“几点”等匹配。如果你输入：“从北京到上海有特快吗?”该语句刚好与第一个匹配样本相匹配，从而系统也就“理解”了你的问话，并去检索数据库，查看从北京到上海是否有特快，然后给出回答。这种关键字匹配的方法，在类似的数据库咨询系统中作为自然语言接口，显得特别有效。第四十六页，共六十页，编辑于2023年，星期一

2.句法分析树法关键字匹配法虽然简单，但却忽略了语句中的大量信息，为确保语句含义的细节不被忽略，必须确定其语句结构上的细节，这就是要进行文法分析。为此，必须首先给出说明该特定语言中符号串结构的文法，以便为每个符合文法规则的语句产生一个称为文法分析树的结构。关于文法的形式，在许多自然语言处理程序中提出过很多各不相同的定义，下面我们给出一种文法的形式化定义。文法G在其形式上为如下的四元组：G=(V，T，P，S)其中，V为有穷非空集，称作总词汇表；T为V的一个非空子集，称作终结字母表，而N=V-T称作非终结字母表（不能出现在最终生成的句子中，是专门用于描述的语法）；P为如下形式的有穷产生式规则集：α→β；S是起始符

第四十七页，共六十页，编辑于2023年，星期一式中，α∈V*NV*，β∈V*，*表示它前面的字符可以重复出现任意次；S为非终结字母表的一个元素，称为起始符。下面给出的是一个英语子集的简单文法：

S

NPVP(a)

NP

DetN(b)

VP

VNP(c)

VP

VPP(d)

PP

PrepNP(e)

Det

the|a(f)

N

Joe｜girl｜letter|pencil|boy|dog(g)

V

hit｜write|kick(h)

Prep

with|at(i)

ADJS∈｜ADJ｜ADJS(j)

ADJ

little｜big(k)

NP1

ADJSN(l)其中，大写为非终结符，而小写的是终结符，∈表示空字符串第四十八页，共六十页，编辑于2023年，星期一下图是对语句“Joehittheball.”进行句法分析而建立的文法分析树。第四十九页，共六十页，编辑于2023年，星期一使用给定文法，对输入语句进行分析找到一个文法分析树的过程，可以看成是一个搜索过程。为实现该过程，可以使用自顶向下的处理方法，这和正向推理有些相象：首先搜索对象从起始符S开始，然后应用P中的规则，用规则的右边部分替换搜索对象，然后同被分析句子中的单词进行匹配比较，如果匹配，则从搜索对象和输入句子的遗留部分继续进行搜索，一层一层地向下产生树的各个分支，直到一个完整的句子结构被生成出来为止。如果该结构与输入语句相匹配，则成功结束；否则，如果还没有分析到句子末尾，而搜索对象已经为空，这时就需要回溯，重新选择适用规则，生成其它的句子结构，直到结束为止。

例：下面采用自顶向下回溯算法对句子“thegirlwritestheletterwithapencil”进行分析。第五十页，共六十页，编辑于2023年，星期一搜索步骤搜索对象规则输入句子中遗留部分（1）S

(a)

thegirlwritestheletterwithapencil（2）NPVP(b)thegirlwritestheletterwithapencil（3）DetNVP(f)thegirlwritestheletterwithapencil（4）theNVP删除thegirlwritestheletterwithapencil（5）NVP(g)girlwritestheletterwithapencil（6）girlVP删除girlwritestheletterwithapencil（7）VP(c)writestheletterwithapencil（8）VNP(h)writestheletterwithapencil（9）writesNP删除writestheletterwithapencil（10）NP(b)theletterwithapencil（11）DetN(f)theletterwithapencil（12）theN删除theletterwithapencil（13）N(g)letterwithapencil（14）letter删除letterwithapencil（15）withapencil这时，句子中还有遗留部分，但搜索对象中却已变空，分析过程已无法继续，只得回溯。回溯到第（7）步，看看是否还能利用别的规则进行分析。第五十一页，共六十页，编辑于2023年，星期一（7’）VP(d)writestheletterwithapencil（16）VPP(c)writestheletterwithapencil（17）VNPPP

(h)writestheletterwithapencil（18）writesNPPP删除writestheletterwithapencil（19）NPPP(b)theletterwithapencil（20）DetNPP(f)theletterwithapencil（21）theNPP删除theletterwithapencil（22）NPP(g)letterwithapencil（23）letterPP删除letterwithapencil（24）PP(e)withapencil（25）PrepNP(i)withapencil（26）withNP删除withapencil（27）NP(b)apencil（28）DetN(f)apencil（29）aN删除apencil（30）N(g)pencil（31）pencil删除pencil（32）NILNIL第五十二页，共六十页，编辑于2023年，星期一在应用规则f、g、h、I、k对搜索对象进行替换时，由于规则的右边有多个单词可供选择，这时，可根据句子遗留部分的第一个单词确定。也可以使用自底向上的处理方法，这和逆向推理有些相似：以输入语句的句首词为基础，首先从P中查找合适的规则逐级向上归约（产生式倒过来用），试图把这些词归并成较大的结构成分，如短语或子句等，然后再对这些成分进行进一步的组合，反向生成文法分析树，直到树的根节点是起始符S为止。本算法实际上分移进、归约两个步骤。在移进－归约过程中信息以“栈”的形式存放，主要的操作有移进、归约、拒绝、接受。栈中存放着分析过程的有关“历史”信息，分析时根据这些历史信息和当前正在处理的符号串来决定是移进还是归约。第五十三页，共六十页，编辑于2023年，星期一

所谓移进，就是把一个尚未处理过的单词符号移入栈顶，并等待更多的信息到来之后再做决定；所谓归约，就是对栈顶的那些与某一语法规则右边相匹配的符号，用该语法规则左边的符号来取代。用这两种操作对栈中符号和输入符号串进行处理，直到输入串处理完毕且栈中只剩初始符S时，就认为输入符号串被接受。例：采用移进－归约算法对句子“theboykicksthedog”进行自底向上的分析的过程如下：第五十四页，共六十页，编辑于2023年，星期一步骤栈操作输入句子中遗留部分（1）theboykicksthedog（2）the移进boykicksthedog（3