图2 自顶向下的句法分析流程

在这个例子中，分析成功的原因在于：成功分析出来的第一条边在最后的每一种可能分析结果中恰恰都是正确无误的。然而，如果分析的句子是“The green faded”，那么，该算法最后会分析失败。因为分析算法开始就将green归为形容词，接下来又找不到名词，而实际上green既可以是形容词，也可以是名词。要解决此类问题，需要在算法的运行中保存尽可能多的后续状态，而我们在CFG自顶向下句法分析算法中就是这样做的。

现在，我们采用这项技术来分析下面的句子：

1 One2 saw3 the4 man5

句法分析器最初会试着将句子的开始片段“one saw”分析为名词短语，但是找不到相应的动词。因此，算法回溯，从名词短语“one”开始，最终找到成功的分析结果。整个分析的流程如图3所示。在每个步骤当中，当前分析状态采用三元组（当前节点、当前状态和返回点）的形式表

示。同时，我们还给出了各种可能的回溯状态。图中也给出了用来产生新状态和对应后备状态的各条边。

图3 可回溯的自顶向下的RTN句法分析

本例的跟踪流程和前面的例子基本一样，不同之处有两点。在步骤2中，从节点NP出发，有两条边可以接受词语“one”。边NP/2将“one”归入数词并产生了下一个当前节点；而边NP/3认为它是个名词，并生成一个后备状态。实际上，在后续过程中，当我们发现从节点S1出发的边没有一条能接受输入词“the”时，就在步骤6中用到了该后备状态。

当然，一般来说，句子产生的后备状态会比这个简单的例子多得多。这种情况下，一般都会有一个可能后备状态表。按照表的组织方式，可以设定访问后备状态的不同顺序。

为了利用chart句法分析的长处，我们还可以采用类似chart的结构，构造一个RTN分析器。在RTN系统中，这种chart通常称为良构子串表(WFST，well-fommed substring table)。当通过弹出边的时候，当前分析的成分就加入到WFST中；而当我们遇到压入边的时候，在调用子网之前，需要核对WFST。如果chart中已经包含了压入边类型的成分，就直接利用这些成分，而不重复调用子网。采用WFST的RTN与chart分析器具有相同的复杂度K * n³(数学表达式，指数形式），其中n是句子的长度。

责任编辑：admin