2.9.5 清理上下文无关语法
通常情况下，人们提供的语法不会包含未定义，不可到达或非生成性的非终结符。如果出现了，那几乎可以肯定是一个失误（或者是用来测试的！），然后我们就要检测和报告出来。然而，这种异常情况很容易出现在生成的语法或由其他语法转换所引入的语法中，这种情况下我们就希望能检测到然后“清理”一下语法。清理语法也是十分重要的，当我们获取解析森林语法的解析结果时（3.7.4节，13章以及其他很多地方）。
从一个上下文无关语法中检测和删除无用非终结符和规则的算法包含两个步骤：移除非生成性规则以及移除不可到达的非终结符。令人惊叹的由于未定义的非终结符，似的移除无用的规则并不是必须的：第一步为我们自动完成了这个过程。
我们将使用图Fig 2.27中的语法来进行演示。它看起来相当单纯：它的所有非终结符都是定义了的，而且它也没有表现出任何可疑的结构。
2.9.5.1 移除非生成性规则
我们通过找到一个生成性规则来寻找非生成性的规则。我们的算法取决于观测，如果一个规则的右侧包含的符号都是生成性的则这个规则就是生成性的。终结符是生成性的因为它能生成终结符，空也是生成性的因为它能生成空字符串。如果一个非终结符有一个生成性规则对应于它那它也是生成性的，但问题是起初我们并不知道哪条规则是生成性的，因为这本身就是我们在努力寻找的。
我们解决这个问题，首先通过使所有规则和非终结符都是“不知道”的。现在我们来看图Fig 2.27的语法，对于每一条我们不知道的规则，其右侧的成员都是生成性的，那我们就标记这条规则和它定义的非终结符为“生成性”的。这将为规则A--->a, C--->c, 以及E--->e产生标记，还有非终结符A, C和E。
现在我们知道的更多了，并且可以将这些用于对语法的第二轮扫描了。这使我们能标记规则B--->bC以及非终结符B，因为现在C已知是生成性的了。第三轮确定了S--->AB和S。第四轮没有产生新的东西，所以也就没有进行第五轮的必要了。
现在我们知道S, A, B, C和E是生成性的，但是D、F以及规则S--->DE还是标记“不知道”的。然而我们知道了更多的：知道我们尝试了生成性的所有可能路径，并且没有为D、F以及S的第二条规则找到任何可能的路径。这意味着我们现在可以更新一下对于“非生成性”的“不确定性”的信息了。D、F的规则以及S的第二条规则可以从语法中移除了；结果如果Fig 2.28所示。这就使得D、F成为了未定义的，而S仍然留在语法中因为它是生成性的，虽然有一个非生成性规则。
看看当语法中包含一个未定义的非终结符，例如U，将会发生什么，是一件有趣的事情。首先U将被预定义为“不知道”的，而因为没有规则定义它，它将一直保持“不知道”状态。因此，任何右侧有着U的规则R都将会是“不知道”的。最终两者都会被定义为“非生成性”的，然后所有的R规则都会被移除。可以看到“未定义的非终结符”只是“非生成性”的非终结符的一种特殊情况：因为它没有规则，所以他是非生成性的。
上述知识改进的算法使我们关于闭包算法的第一个例子。闭包算法有两个主要特点：初始化，是对最初了解的一个评估，部分源于其现状和“不知道的”部分；推导规则，介绍从几个地方获取的信息是如何结合的。对于我们的问题的推导规则是：
对于每一个我们知道其右侧的所有成员都是生成性的规则，标记它定义的规则和非终结符为“生成性”的。
推导规则一直重复直到没有不在有任何变化，这一点在闭包算法中是隐式的。然后初步的“不知道”类型就会变成一个更明确的“非X”，“X”是算法被设定来检测的属性。
因为预先知道所有依旧是“不知道”状态的最终都将会变成“非X”，所以许多闭包算法的描述和实现直接跳过整个“不知道”步骤，而直接初始化所有的为“非X”。在执行中，这不会有太大差别，因为计算机内存中位的意义不是在计算机中而是在程序员脑中，但是在打印书本描述中这种做法就是不优雅的也是让人疑惑的，因为初始化语法中的所有非终结符为“非生成性”是不正确的。
本书中我们会看到很多闭包算法的例子；在3.9节中会有详细的讨论。
2.9.5.2 移除不可到达的非终结符
一个非终结符存在至少一个句子形式就可以称为是可到达的或可访问的，从开始出现的起始符号开始。所以如果对一些α和β存在SαAβ那么非终结符A就是可到达的。
我们通过找到“生成性”的规则和非终结符来找到非生成性的那些。同样的，我们通过找到可到达的非终结符来找到不可到达的那些。为此，我们可以使用以下的闭包算法。首先，起始符号被标记为“可到达的”；这就是初始化。然后，语法中每一个标记了A的A→α形式的规则，α中所有的非终结符都会被标记；这就是推导规则。我们持续应用推导规则直到不再有变化产生。现在剩下的未标记的非终结符就是不可到达的，而他们对应的规则可以被删除了。
第一轮标记A和B；第二轮标记C，第三轮没有任何不变化。结果就是--一个干净的语法--见图Fig 2.29。如图Fig 2.27中可到达和生成性的规则E--->e，子啊移除非生成性规则后变成了孤立的，然后被第二步的清理算法给删除掉了。
移除不可到达的规则不会导致在一个可到达的规则中使用的非终结符N变成未定义的，因为只有当移除了N的所有定义的规则才能变成未定义的，但是又因为N已经是可到达的，所以上诉过程将不会移除它的任何一条规则。对相同参数的稍微修改可以看出移除不可到达的规则不能导致一个在可到达规则中使用的非终结符N变成非生成性的：生成性的N，否则无法在前面的清理步骤中留存下来，只能通过移除它的定义规则来使之成为非生成性的，但是由于N是可到达的，上面的过程将不会移除它的任何规则。这最后表明在移除了非生成性的非终结符以及移除了不可到达的非终结符之后，我们没有必要再做一遍移除非生成性的非终结符。
然而有趣的是请注意，如果先移除不可到达的非终结符然后在移除非生成性的规则将有可能导致语法再次含有不可到达的非终结符。图Fig 2.27的语法是一个例子。
此外需要注意的是，清理一个语法可能回移除所有的规则，包括其实符号的规则，描述空语言的语法就是例子；见2.6节。
移除非生成性规则是一个自底向上的过程：只有底层，终结符所处的位置，才能知道哪些是生成性的。移除不可到达的非终结符是一个自顶向下的过程：只有顶层，起始符号所处的位置，才知道哪些是可到达的。