3.4.2 0型和1型语法

一个任意的0型语法的识别问题是不可解的，这在形式语言学上是一个显著的成果。这意味着不会有一种算法，它接受一个任意的0型语法以及一个任意的字符串，然后在有限的时间内告诉我们这个语法是否能能生成这个字符串。可以证明这种说法，但是证明过程非常令人生畏，并且它不能提供任何能窥探到造成这种现象的原因。这是一个逆向的证明：我们能证明，如果存在这样一种算法，我们就能构造第二个算法，其能证明语法只能在永远不终止的情况下才能终止。由于这在逻辑上是不成立的，并且由于其余所有的前提在证明过程中都表明我们不得不得出一个结论就是，在我们最初的前提下，0型语法的识别器在逻辑上是不可能的。令人信服，但精神上却难以接受。完整的证明见Hopcroft and Ullman [391, pp. 182-183], or Révész [394, p. 98]。

为一定数量的0型语法构建一个识别器却是很有可能的，通过使用某种特定的技术。然而这种技术却不能对所有0型语法起效。事实上，不论我们收集了多少种技术，总会有这些技术不起作用的语法存在。在某种意义上，我们只是不能使我们的识别器足够复杂。

对于1型语法，这种情况却是完全不同的。1型语法的生成规则不能使句子形式收敛这个看似无关紧要的属性，让我们可以为自底向上的NDA构建一个至少原则上能起作用的控制机制，而不考虑语法。这个控件的内部管理包含一组可能在输入的句子中发挥作用的句子形式；它开始只包含输入的句子。NDA的每一次移动都是一次还原，根据语法。现在这个控制将NDA的所有可能的移动都应用在内部管理的所有句子形式中，以任意顺序的方式，并将每一个结果添加至内部管理中，如果不是已经存在的话。这个动作会一直持续到所有的句子都完成了所有可能的移动并得到了结果。由于没有哪个NDA移动可以使句子形式变长（因为所有的右侧至少是与其左侧的长度相当），并且由于句子形式的数量有限，与输入字符串长短相当，这最终都是会发生的。现在我们在内部管理的句子形式中找到仅只包含起始符号的那一个。如果它确实存在，那我们就识别出了输入字符串；如果不存在，那输入字符串就不属于这个语法所代表的语言。如果我们还记得，在一些额外的管理机制中，我们是如何得到这个起始符号的句子形式，我们就已经得到了解析过程。而所有的这些都依赖于大量的书记工作，而我们并不打算讨论这个，因为反正也没有人这么做。

综上所述，我们并不能总是为0型语法构建解析器，但如果是1型语法那我们就能做到。为这种类型的语法构建一个实用、合理高效的解析器，是一个非常困难的问题，但是在过去的40年中一直保持缓慢但稳定的进展（见18.1.1节（电子版））。这不是一个热搜话题，主要是因为0型和1型语法是出了名的不友好并且永远不会被广泛应用的。然而并不是完全没有用处，因为一个好的0型语法解析器可能会让定理证明器¹有一个好的开端。

对人类不友好的思虑并不适用于两级语法。有一个实用的两级语法解析器将棒极了，因为这将会让解析技术（以及其所有的内置自动化技术）应用到更广泛领域中相比于现在，尤其是上下文条件很重要的情况。两级语法解析情况的目前的可能性在15.2.3节中讲述。

所有已知的0型、1型以及无限制的两级语法的的解析算法，都有指数级分布的时间依赖项。