2.12 语法类型的隐喻比较

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

Ss --->[Σ]S| ε

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

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

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

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

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

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

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

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

图1 Fig 2.33

1

我们在这里使用编程语言Java,因为我们希望读者或多或少能熟悉它。对于手册所给一个CF语法的,任何一种编程语言都可以做到。