搭建上下文无关文法分析器的时候，人们常常采取另外一种方法，即将语法规则直接用逻辑程序语言来表示，如PROLOG。可以证实的是，标准PROLOG的解析算法使用的搜索策略恰恰就是深度优先的自顶向下分析算法。所以，需要做的工作仅仅是寻找将上下文无关文法规则重新整理成PROLOG子句形式的方法。考虑如下的上下文无关文法规则：

S→ NP VP

采用公理的形式，这条规则可以重新表述为：“一个词的序列是合法的S。前提是该序列开头部分是一个合法的名词短语，其后跟着一个合法的动词短语。”如果按照位置顺序给句中的每个词编号，这个规则可以重述为：“如果存在位置p2，使得p1和p2之间有一个NP，同时p2和p3之间有一个VP，那么p1和p3之间是一个S。”在PROLOG中，这条规则可以表示为下面的公式。其中，变量采用大写字母开头的字符串表示：

s(P1, P3) :- np(P1, P2), vp(P2, P3)

为了建立这个分析过程，我们还要增加公理来列出句中所有的词及其在句中的位置。例如，句子“John ate the cat”可以表述为：

word(john, 1, 2)

word(ate, 2, 3)

word(the, 3, 4)

word(cat, 4, 5)

词典可以用一系列的谓词来定义，结果如下：

isart(the)

isname(john)

isverb(ate)

isnoun(cat)

歧义词会产生多个断言——其中，每个断言对应它们所属的一个句法类别。

对于每个句法类别，可以定义一个谓词。该谓词为真的惟一条件是，在两个特定位置之间的词语属于该类别，如下所示：

n(l, O) :– word(Word, I, O), isnoun(Word)

art(I, O) :- word(Word, I, O), isart(Word)

v(I, O) :- word(Word, I, O), isverb(Word)

name(I, O) :- word(Word, I, O), isname(Word)

使用图1所示的公理，通过证明谓词s(1，5）为真，可以证明“John ate the cat”是一个合法的句子，证明过程见图2。图2中存在一些同名的不同变量，容易造成混淆，这时就给变量名加上一个单引号（'），使之惟一。这个句子中谓词的证明流程和上下文无关文法的自顶向下分析流程是一致的，具体过程如下。任何时刻的待检验状态都可以表示为迄今为止需要检验的子目标列表。目标描述中已经包含了词的位置，因此在分析流程中，就不需要增加单独的列来记录词语的位置信息。后备状态也是采用子目标列表来表示的，由一个类似PROLOG的系统自动维护，并用来实现回溯过程。在这种系统中，典型的证明过程在任何时刻仅仅给出当前的状态。

图1 语法3.4基于PROLOG的表示

标准PROLOG搜索策略与深度优先的自顶向下的句法分析策略一样。因此，采用PROLOG构造的句法分析器与后者的计算复杂度都为C”，即以计算的步数为底，输入句子的长度为指数。实际上，即使是在最坏的情况下，基于PROLOG的语法也是非常高效的。可以考虑加入类似chart的机制来进一步提高算法的效率。当然，这样做的结果会丧失上下文无关规则与PROLOG规则之间的一些简单联系。

图2“John ate the cat”基于PROLOG算法的句法分析流程

尝试使用PROLOG写一些简单的语法，这是一件很值得我们去做的事情。由此，可以更好地理解自顶向下的深度优先搜索方法。通过PROLOG的跟踪工具，能得到和图2类似的算法运行过程。

责任编辑：admin