2.9 上下文无关语法的健全

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

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

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

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

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