2.3 语法和语言的Chomsky层次结构

图Fig 2.3和2.5中的语法都很容易理解,而事实上一些简单的短语结构语法可以生成复杂的集合。然而,对于任何一组给定的语法通常都很难说是简单的。(虽然语法有无限的集合,但是在这我们还是说“一个给定集合的语法”。通过一个集合的语法,我们来解释任何做了同样工作的语法,并且不是过于复杂的。)理论上说如果一个集合最终可以生成(例如,通过一个程序),那么它就可以通过一个短语结构语法来生成,不过理论上没有表明这样做很容易,或者说语法是容易理解的。在这一节中要说明Manhattan龟的路劲尽量写出其语法,这些路劲中龟总是不能从起始点向西爬行的。(问题2.3)。

不考虑短语结构语法带来的智力问题,他们也表现出了基本和实际的问题。我们可以看出对这些集合没有普适的解析算法,而所有已知的特殊算法,要么效率很低要么就是很复杂;见3.4.2节。

也就是在尽可能的保持它们的生成力的情况下,约束短语结构语法超出控制的情况,这样就有了语法的Chomsky层次结构。这种层次结构分为了四种类型的语法,编号为0到3;引入第5种类型,也就是被称为类型4的类型,是有意义的。0型语法是(无限制的)短语结构语法,我们已经看到了它的例子。其他类型源于越来越被限制的语法规则中被允许的形式。每一种限制条件都带来深远的影响;最终语法逐渐变得更易于理解和掌握,但也逐渐不那么强大。幸运的是,这些不那么强大的语法依旧十分有用,甚至实际上比0型更有用。

我们现在先按顺序来看看前三个类型,然后接着在看看琐碎但有用的第四个类型。

生成0型语言的完全不同的方法,见示例Geffert[395]。