3.4.3 2型语法

幸运的是，CF（2型）语法的解析算法相比于0型和1型要著名的多。使用CF和FS语法中几乎所有实用的解析都做过了，并且在上下午无关语法的解析中几乎所有遇到的问题都被解决了。这么大差距的原因可以在CF语法生成过程中找到：句子形式中的一个非终结符的演变是完全独立于其余非终结符的演变的，并且相反的是，在解析过程中，我们可以结合部分解析树而不理会它们的历史。在上下午相关语法中这些都不是正确的。

自顶向下和自底向上解析过程都很容易适用于CF语法。在下面的例子中，我们应使用简单的语法

3.4.3.1 自顶向下CF语法解析

在自顶向下CF语法解析中，我们从起始符号入手，并尝试产生输出。这里的关键词是预测和匹配。句子形式中任何时候都有一个最左侧非终结符A，而解析器系统的尝试预测一个A的恰当的替代品，在这个位置的输入中一旦有兼容的符号被发现，那A的产物就应该开始了。这个最左侧的非终结符也被称为预测过程的目标。

想想图Fig 3.5中的例子，其中Object就是最左侧的非终结符，也就是“目标”。在这种情况下，解析器将首先预测Object的the Noun，然后会立即推翻这个替换项，因为the的位置被要求是一个a。接下来，解析器将会尝试a Noun，这个将会被暂时接受。a匹配上了，新的最左侧非终结符就成了Noun。当Noun最终生成了dog时，这个解析器就成功了。解析器将会为Object尝试第三次预测，ProperName；这个替换项不会被立即拒绝，因为解析器无法知道ProperName不能起始于一个a。它将在稍后阶段中失败。

这种方法有两个严重的问题。虽然理论上，它可以处理任意的CF语法，但如果被单纯的照章办事的执行的话，可能会在一些语法中走到死循环中。这个可以通过使用一些特殊技术来避免掉，这在大多数自顶向下解析器中处理了；这个将在第6章中详细讲解。第二个问题是算法必须符合时间指数分布，因为任何一次预测都可能被证明是错误的，并且需要在反复试错中纠正。上面的例子显示了可以通过预处理语法来增加一些效率：其优势在于可以预先知道哪些记号可以开启ProperName，以避免预测注定会失败的替代项。这对于语法中的大多数非终结符来说是正确的，而且这种信息可以很容易的从语法中计算出来并存储在一个表中供解析中使用。对于一个合理的语法集合，可以实现一个线性时间依赖项，比如第8章将会解释的。

3.4.3.2 自底向上CF语法解析

在自底向上的CF语法解析中，我们从输入开始，然后尽量减少它与起始符号的差距。这里的关键字是转移和缩减。当我们在过程中时，我们手中有了一个由输入缩减而来的句子形式。在这个句子中的耨个地方必定有一个段（子字符串），其是这个句子形式的最后一步生成步骤的结果。这一段对应于生成规则A→α的右侧α，而且必须被缩减到A。段和生成规则一起被称为句子形式的句柄，有一个相当拟合的表达式；见图Fig 3.6。（当生成规则在段的发现中是显而易见的，那匹配的段通常单独被称为“句柄”。通常我们会遵守这种习惯，不过我们认为称之为句柄段要更明确一些。）

诀窍是找到句柄。它必须是一个规则的右侧，所以我们从寻找这种右侧开始，通过将句子形式中的符号转换到内部管理机制中。当我们找到这样一个右侧，我们向着其左侧对其进行缩减，然后重复这个过程直到只剩下起始符号。用这种方式我们不一定能找到正确的句柄；如果我们犯错，那将会在接下来的步骤中卡主，然后将不得不撤销一些步骤，然后转向更多的符号并再次尝试。在图Fig 3.6中，我们本可以让a Noun向着Object缩减，但最后大胆走向了死胡同。

这种方式有两个本质上相同的问题，在自顶向下技术中。它可能产生循环，并且在有ε规则的语法中也可能会这样：它将在所有的地方持续找到空的生成。这个可以通过触及语法来纠正。并且可以花费服从指数分布的时间，因为句柄的正确识别必须通过试错来完成。同样的，对语法做预处理往往会有帮助：在语法中很明显，Subject可以通过追逐来找到，但Object却不能。所以如果下一个符号是追逐的，那将一个句柄缩减至Object是无意义的。