4 一般非定向分析

在这章中我们将会介绍两种解析方法，都是无向的：Unger法和CYK法。这些方法被称为无向性，因为它们以看似任意的方向接受输入。它们要求在解析开始之前，所有的输入都存储在内存中。

Unger方法是自顶向下的；如果输入属于这个语言，则必须从语法的起始符号开始衍生，比如S。因此，它必须从起始符号的右侧开始衍生，比如A₁A₂...A_m。这反过来又意味着*A₁*必须可以推倒出输入的第一部分，A₂必须可以推倒出第二部分，等等。如果输入的句子是t₁t₂...t_n，这个需求可以描述如下：

Unger方法试图找到适合这个需求的输入的分区。这是一个递归问题：如果一个非终结符*A_i要推导出输入的某个部分，则这部分的一个分区必须适应A_i*的右侧。最终，这样的右侧必须由仅有终结符号组成，并且这些可以很容易与当前的输入部分相匹配。

CYK方法用另一种方法来解决这个问题：它试图在输入的右侧中找到出现的部分；每当找到一个，它就在推导出这一部分的左侧的位置标记一下。用相对应的左侧来替换右侧出现的部分，结果会产生输入的一些句子形式。这些句子形式再次成为查询右侧的对象。最终，我们可能会找到一个句子形式，可以同时派生输入句子和属于起始符号的右侧。

在接下来的两节中，将会对这些方法进行详细介绍。