语言的基本原理

形式语言被定义为一个（可能是无限的）字符串集合。每个字符串由终结符串连而成，终结符有时也被称为词语。例如，在一阶逻辑的语言中，终结符包括∧和 P，“P∧Q”是一个典型的字符串。而字符串“PQ∧”则不是该语言的成员。形式语言，诸如一阶逻辑和 Java，都有严格的数学定义。这与自然语言正好相反，诸如中文、丹麦语和英语，没有严格定义却被一个说话者群体所使用。在本章中，我们将试图把自然语言当作形式语言进行处理，尽管我们认识到这种匹配并不是完美的。

语法是详细说明一种语言的有限规则集合。形式语言无一例外具有正式的语法，写在手册或书籍中。自然语言没有这样的正式语法，但是语言学家努力通过科学调查的过程发现语言中的特性，然后将他们的发现编纂成语法。到目前为止，还没有任何一个语言学家完全成功。注意，语言学家是科学家，努力按照其本来面目定义一种语言。还有一些规范语法学家，他们试图规定一种语言应该是什么样的。他们创造了诸如“不要分开不定式”之类的规则，这些规则有时被写入体例指南中，但是与实际语言的用法相关性不大。

形式语言和自然语言都把一个含义（或称为语义）与每个有效的字符串联系起来。例如，在数学语言中，我们可能会有一条规则说：如果“X”和“Y”是表达式，那么“X+Y”也是表达式，而且它的语义就是X与Y的和。在自然语言中，同样重要的是理解一个字符串的语用：在一个特定情景下说出的字符串的实际含义。含义不仅仅存在于词语本身内部，还存在于根据其所出现的环境对该词语的解释之中。

很多语法规则的形式化表示都是基于短语结构的——即字符串是由来自不同范畴的、被称为短语的子串构成的。例如，短语“the wumpus”，“the king”以及“the agent in the corner”都属于名词短语（noun phrase，或缩写为NP）的范畴。采用上述方法辨识短语有两个原因。第一，短语通常对应于自然语义元素，根据这些语义元素能够构造话语的含义，例如，名词短语指代的是世界中的事物。第二，范畴化的短语能够帮助我们描述语言中的合法字符串。我们可以说，任何一个名词短语都可以与一个诸如“is dead”之类的动词短语（verb phrase，或缩写为VP）搭配而构成一个属于语句（sentence或缩写为S）范畴的短语。如果没有名词短语和动词短语这些中间概念，要解释为什么“the wumpus is dead”是一个语句而“the wumpus dead is”不是一个语句将非常困难。

诸如NP、VP以及S的范畴名称都被称为非终结符。语法使用重写规则定义非终结符。我们将采用附录B第B.1节中所描述的巴克斯-瑙鲁范式（BNF）作为重写规则。在这种符号表示中，诸如

S → NP VP

的规则的含义就是S可以由任何一个NP后伴随着任何一个VP组成。

生成能力

语法的形式化表示可以根据它们的生成能力加以分类：即它们所能表示的语言集合。乔姆斯基（Chomsky，1957）仅根据重写规则形式的不同定义了 4 类语法形式化表示。这些类型可以按照一个层次结构排列，其中每种类型都可以用来描述能力比它低的类型所能描述的全部语言，以及某些额外的语言。下面我们列出这个层次结构，描述能力最强的类型优先：

递归可枚举语法使用无约束的重写规则：重写规则的左右两侧都可以包含任意数量的终结符和非终结符，就像规则A B → C中一样。这种语法与图灵机具有同等的表达能力。

上下文有关语法的约束只是重写规则的右件必须包含至少与该规则左件同样数量的符号。“上下文有关”这个名称来自这样的事实：比如规则A S B → A X B的意思就是如果S出现在前有A后有B的上下文中，则可以重写为X。上下文有关语法能够表示诸如anbncn（a的n个副本后面跟着相同数量的b和c的一个序列）这样的语言。

在上下文无关语法（或简称CFG）中，每个重写规则的左件由一个单独的非终结符组成。因此，每条规则许可在任何上下文中把该非终结符重写为规则的右件。CFG在自然语言和程序设计语言的语法中很流行，虽然现在广泛接受的观念是至少有些自然语言不是上下文无关的（Pullum，1991）。上下文无关语法能够表示anbn，但不能表示anbncn。

正则语法是约束最强的一种类型。每条重写规则的左件是一个单独的非终结符，而右件是一个终结符，其后还可以跟着一个可选的非终结符。正则语法与有限状态自动机具有同等的表达能力。它们不太适合于程序设计语言，因为它们不能表示诸如对称的嵌套括号一类的结构（anbn语言的一个变种）。它们能表示的程度最接近的就是a*b*，由任意数量的a后面跟着任意数量的b组成的一个序列。

尽管层次中等级越高的语法表达能力越强，但是处理它们的算法的效率也越低。到 20 世纪 80年代中期之前，语言学家一直把注意力集中在上下文无关和上下文有关语言上。从那时开始，出于对上兆字节甚至上吉字节的联机文本进行非常快速的处理的需要（即使以不完备的分析为代价），致使正则语法逐渐成为研究重点。正如Fernando Pereira指出的那样：“年纪越大，我研究的乔姆斯基语法层次越低”。为了理解他究竟说的是什么，可以比较阅读Pereira和Warren（1980）以及Mohri， Pereira和Riley（2002）的两篇文章。