句法分析树：自然语言分析技术精解

句法分析主要有两个作用：第一，对句子或短语结构进行分析，以确定构成句子的各个词、短语之间的关系以及各自在句子中的作用等，并将这些关系用层次结构加以表达；第二，对句法结构进行规范化。在对一个句子进行分析的过程中，如果把分析句子各成分间的关系的推导过程用树形图表示出来的话，那么这种图称为句法分析树。句法分析是由专门设计的分析器进行的，分析过程就是构造句法树的过程，将每个输入的合法语句转换为一棵句法分析树。

分析自然语言的方法主要分为两类：基于规则的方法和基于统计的方法。这里主要介绍基于规则的方法。

（一）短语结构文法

短语结构文法G的形式化定义如下：G＝（V1，Vn，S，P）

其中：V1是终结符的集合，终结符是指被定义的那个语言的词（或符号）；Vn是非终结符号的集合，这些符号不能出现在最终生成的句子中，是专门用来描述文法的；V是由V1和Vn共同组成的符号集，V＝V1∪Vn，V1∩Vn＝Φ；S是起始符，它是集合Vn中的一个成员；P是产生式规则集，每条产生式规则具有a→b形式，其中a∈V＋，b∈V*，a≠b，V*表示由V中的符号所构成的全部符号串（包括空符号串Φ）的集合，V＋表示V*中除空符号串Φ之外的一切符号串的集合。

采用短语结构文法定义的某种语言，是由一系列规则组成的。

例如，G＝（V1，Vn，S，P）

（二）乔姆斯基文法体系

乔姆斯基（Chomsky）以有限自动机为工具刻画语言的文法，把有限状态语言定义为由有限状态文法生成的语言，于1956年建立了自然语言的有限状态模型。乔姆斯基采用代数和集合论，把形式语言定义为符号序列，根据形式文法中所使用的规则集，定义了下列几种形式的文法：

（1）无约束短语结构文法，又称0型文法。

（2）上下文有关文法，又称1型文法。

（3）上下文无关文法，又称2型文法。

（4）正则文法，即有限状态文法，又称3型文法。

型号越高所受约束越多，生成能力就越弱，能生成的语言集就越小，也就是说型号的描述能力就越弱。

1.正则文法

正则文法又称有限状态文法，只能生成非常简单的句子。正则文法有两种形式：左线性文法和右线性文法。在一部左线性文法中，所有规则必须采用如下形式：

其中A∈Vn，x∈Vn，l∈V1，即A、B都是单独的非终结符，t是单独的终结符。而在一部右线性文法中，所有规则必须如下书写：

2.上下文无关文法

上下文无关文法的生成能力略强于正则文法。在一部上下文无关文法中，每一条规则都采用如下的形式：

其中A∈Vn，x∈V*，即每条产生式规则的左侧必须是一个单独的非终结符。(www.xing528.com)

在这种体系中，规则被应用时不依赖于符号A所处的上下文，因此称为上下文无关文法。上下文有关文法是一种满足以下约束的短语结构文法：对于每一条形式为：

的产生式，y的长度（即符号串y中的符号个数）总是大于或等于x的长度，而且x，y∈V*。

例如：AB→CDE是上下文有关文法中一条合法的产生式，但ABC→DE不是。这一约束可以保证上下文有关文法是递归的。这样，如果编写一个程序，在读入一个字符串后能最终判断出这个字符串是或不是由这种文法所定义的语言中的一个句子。

自然语言是一种与上下文有关的语言，上下文有关语言需要用1型文法描述。文法规则允许其左部有多个符号（至少包括一个非终结符），以指示上下文相关性，即上下文有关指的是对非终结符进行替换时需要考虑该符号所处的上下文环境。但要求规则的右部符号的个数不少于左部，以确保语言的递归性。对于产生式：

当用y替换A时，只能在上下文为a和b时才可进行。

由于上下文无关语言的句法分析远比上下文有关语言有效，因此希望在增强上下文无关语言的句法分析的基础上，实现自然语言的自动理解。ATN就是基于这种思想实现的一种自然语言句法分析技术。

3.无约束短语结构文法

如果不对短语结构文法的产生式规则的两边做更多的限制，而仅要求x中至少含有一个非终结符，那么即成为乔姆斯基体系中生成能力最强的一种形式文法，即无约束短语结构文法。

0型文法是非递归的文法，即无法在读入一个字符串后，最终判断出这个字符串是或不是由这种文法所定义的语言中的一个句子。因此，0型文法很少用于自然语言处理。

（三）句法分析树

在对一个句子进行分析的过程中，如果把分析句子各成分间关系的推导过程用树形图表示出来，那么这种图称为句法分析树，如图6－1所示。在句法分析树中，初始符号总是出现在树根上，终止符总是出现在叶上。

图6-1　句法分析树

（四）转移网络

句法分析中的转移网络由结点和带有标记的弧组成，结点表示状态，弧对应于符号，基于该符号，可以实现从一个给定的状态转移到另一个状态。重写规则和相应的转移网络如图6－2所示。

图6-2　重写规则的转移网络

用转移网络分析一个句子，首先从句子S开始启动转移网络。如果句子表示形成和转移网络的部分结构（NP）匹配，那么控制会转移带和NP相关的网络部分。这样，转移网络进入之间状态，然后接着检查VP短语，在VP的转移网络中，假设整个VP匹配成功，则控制会转移到终止状态，并结束。

扩充转移网络（Augmented Transition Net－work，ATN）文法属于一种增强型的上下文无关文法，即用上下文无关文法描述句子文法结构，并同时提供有效的方式将各种理解语句所需要的知识加到分析系统中，以增强分析功能，从而使应用ATN的句法分析程序具有分析上下文有关语言的能力。

ATN主要是对转移网络中的弧附加了过程而得到的。当通过一个弧的时候，附加在该弧上的过程就会被执行。这些过程的主要功能有：

（1）对文法特征进行赋值；

（2）检查数（Num－ber）或人称（第一、二或三人称）条件是否满足，并据此允许或不允许转移。