第九章 句法分析

　　9.2 短语结构语言

　　在开始讨论自然语言的句法分析之前，有必要扼要回顾一下形式语言理论和短语结构语法。下面给出句子、语言和语法的形式化定义。
定义 定义9.1
  一个句子是一个符号串，这个串由选自某种语言词汇表中的一个或多个符号(词)组成。
定义 定义9.2
  一种语言是一个句集，它包含了属于这种语言的全部句子。
定义 定义9.3
  一部语法是对一个句集的一种有限的形式化描述。

　　语法可采用不同形式来定义。如果一种语言只包含有限个句子，那么可以通过逐一枚举的方式来定义。然而大多数有研究价值的语言通常都拥有无限多个句子。描述这类语言的方法之一是编写一部程序，然后读入一个符号串，让机器来判断这是不是一个句子。这样的程序叫做这种语言的识别器(recognizer)。一个识别器在读入一个符号串以后，将输出："这是一个句子"，或"这不是一个句子"。另一种描述方法是利用一种基于产生式的形式化工具。这种被广泛用来描写形式语言和自然语言的工具被称为产生式语法或短语结构语法(phrase-structure grammar)。

　　9.2.1 短语结构语法
　　一部短语结构语法G可以用如下的四元组来定义：
　　　　G＝(T，N，S，P)
其中，T是终结符的集合，终结符是指被定义的那个语言的词(或符号)；
　　　N是非终结符的集合，这些符号不能出现在最终生成的句子中，是专门用来描述语法的。显然，T和N的并构成了符号集V，而且T和N不相交，因此有：
　　　　V＝T∪N，
　　　　T∩N＝φ (φ表示空集)；
　　　S是起始符，它是集合N中的一个成员；
　　　P是一个产生式规则集。每条产生式具有如下的形式：
　　　　a→b
　　　其中a∈V+，b∈V*，且a≠b；V*表示由V中的符号所构成的全部符号串(包括空符号串φ)的集合，V+表示V*中除φ之外的一切符号串的集合。
　　在一部短语结构语法中，基本运算就是把一个符号串重写为另一个符号串。如果a→b是一条产生式，我们就可以通过用b来置换a，重写任何一个包含子串a的符号串，并用符号""表示对符号串所作的这种运算。所以，如果u，v∈V*，有
　　　　uavubv
就说uav直接产生ubv，或ubv是由uav直接推导出来的。举例来说，如果定义了一部语法G，其中S是起始符，且
　　　　N＝{S}
　　　　T＝{a，b，c}
　　　　P＝{S→aSc，S→b}
于是从串S开始，应用第一条产生式可得到串aSc，然后应用第二条产生式得到串abc：
　　　　SaScabc
或者可以重复应用第一条产生式两次，然后再用第二条产生式，得到
　　　　SaScaaSCCaabcc
如果S1,S2,…,Sn都是符号串，且
　　　　S1S2…Sn
记作
　　　　S1Sn
就说S1产生Sn，或者说Sn是由S1推导出来的。因此，对于上面定义的简单语法有
　　　　Sabc
　　　　SaaScc
　　　　等等。
通过以不同的顺序来应用这些产生式，就可以从同一个符号产生许多不同的串。由一部短语结构语法定义的语言就是可以从起始符S推导出来的全部终结符串的集合。可见，由上面这部简单语法所定义的语言是
　　　　b，abc，aabcc，aaabccc，…
　　一个程序如果能根据一部特定的语法来确定一个句子的推导，就称它为一个句法分析器(parser)。
　　一般来说，如果把语法G所定义的语言记作L(G)，则
　　　　L(G)＝{W|W∈T*，且SW}
这条定义的意思是，对于所有的符号串W，如果W是由终结符所组成的串，且用语法G可以从起始符S中推导出W，那么符号串W的集合就是由语法G所生成的语言L(G)。
　　换言之，一个符号串要属于L(G)必须满足以下两个条件：
　　(1)该符号串只包含终结符；
　　(2)该符号串能根据语法G从起始符S推导出来。