2.9 上下文无关语法的健全

所有种类的语法都可能包含无用的规则,这些规则在任何成功的生成过程中都不能成为一个有用的角色。一个生成过程是成功的,当它一一个终结符结尾时。生成尝试可能失败,通过卡住(下一步没有可替代的)或者进入一种没有替代序列能移除掉所有的非终结符的境地的情况。0型语法被卡住的一个示例如下:

图1

当我们从S的第一个规则开始,一切都进展顺利并且生成了终结符x。但是当我们从S的第二条规则(规则2)开始时,我们就被卡住了,而当我们从规则3开始时,我们就发现进入了一个无限循环中,生成越来越多的C。规则2、3和5永远都不会产生一个成功的生成过程:他们是无意义的规则,并且也无法在不影响语言生成的情况下从语法中移除掉。

无用的规则并不是根本性的问题:它们不会妨碍正常的生成过程。尽管如此,它们依旧是语法中的枯木,而总有人会想移除它们。并且,当他们出现在由程序员指定的语法中时,它们可能会指向某些错误,那就会想要检测它们并给出警告或错误信息。

上述语法的问题很容易理解,但可以表明,大多数情况下是很难判定在0型或1型语法中的一条规则是无用的:不可能有一种算法能在所有情况下都正确判断。然而,对上下文无关语法来说,这个问题就是相当容易解决的了。

在上下文无关语法中的规则可能是无用的,因为三个原因:它们可能包含未定义的非终结符,从起始符号开始可能无法到达它们,以及它们可能无法生存任何东西。接下来我们会详细讨论这些缺陷;2.9.5节给出了一个算法可以帮助语法拜托这些缺陷。