2.12 语法类型的隐喻比较

教科书声称“n型语法比n+1型语法更强大，n = 0，1，2”，并且经常可以读到这样的语句“一个正则（3型）语法不够强大以匹配括号内的”。有趣的是，看看到底是什么样的力量。天真，一个人可能以为它的力量是生成越来越大的集合，但这明显是不正确的：最大的可能的集合Σ^*，可以很容易由3型语法生成：

S^s --->[Σ]S| ε

[Σ]是语言中符号的缩写。只是当我们想要限制这个集合时，我们就需要更强大的语法。更强大的语法可以在正确和不正确的句子间定义更复杂的边界。有的边界定义的太好导致没有任何语法能描述它（也就是，通过任何生成过程）。

这个想法在图Fig 2.33中进行了比喻描述，图中一支玫瑰由越来越细的轮廓接近。在这个比喻中，玫瑰代表语言（想象语言中的句子就是玫瑰的分子）；语法就是为了描绘它的轮廓。一个正则语法只允许我们用水平直线和垂直线段来描绘花朵；直尺和T型尺就够了，但结果只是一个粗陋和机械的图片。CF语法能通过各个角度的直线和圆弧近似描绘；图画还是可以使用传统的圆规和直尺就够了。最终结果很生硬但好歹能辨认了。CS语法可以让我们用平滑的曲线包围花朵了，但是曲线太平滑了：它无法表现尖角，而且偏离了复杂的交点；不过，依旧有了非常逼真的效果图。不受限制的短语结构语法可以完美展现大概轮廓。一朵玫瑰不可能被限定在一种限定的描述中；其本质永远都是我们嗦无法企及的。

一个更简单更有效的例子，可以在一个能通过多种语法类型生成的Java¹程序的继承集合中找到。

• 所有词法正确的Java程序可以通过一个正则语法生成。一个Java程序词法是正确的，如果字符串中没有换行符，评论在文件结尾时被终止，且所有数值常量都是正确形式，等等。

• 所有语法正确的Java程序都可以通过一个上下文无关语法生成。这些程序在理论上都符合（CF）语法。

• 所有语义上去的Java程序都可以通过一个CS语法生成。这些都是通过一个Java编译器没有抛出错误信息的程序。

• 在有限时间内运行给定输入会终止的所有Java程序可以通过一个无限制的短语结构语法生成。然而，这种语法会非常复杂，因为它会包含Java库的进程和Java运行时间系统的详细描述。

• 解决给定问题（例如，下棋）的所有Java程序不能通过一个语法（尽管集合的描述时有限的）生成。