4 一般非定向分析

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

Unger方法是自顶向下的;如果输入属于这个语言,则必须从语法的起始符号开始衍生,比如S。因此,它必须从起始符号的右侧开始衍生,比如A1A2...Am。这反过来又意味着*A1*必须可以推倒出输入的第一部分,A2必须可以推倒出第二部分,等等。如果输入的句子是t1t2...tn,这个需求可以描述如下:

图1

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

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

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