通过有限状态自动机发现正确的路径，或者发现对于输入的正确的转录，可以看成是一个搜索问题。例如，对于FSA来说，剖析就是在自动机中搜索一切可能的路径空间。在句法剖析中，剖析可以看成是对于一个句子搜索一切可能的剖析树空间并发现正确的剖析树。搜索一切可能的路径空间可以用FSA的结构来定义，所以，搜索一切可能的剖析树空间也可以用语法来定义。例如，我们来考虑如下的ATIS中的句子：

Book that flight.   （1）

可以使用图2中的微型语法和词表，其中包括英语CFG规则。指派给这个句子的正确的剖析树如图1所示。

怎样使用图2中的语法来给例句（1）指派图1中的剖析树呢？在这种情况下，只存在一个剖析树，但是也可能存在一个以上的剖析树。剖析搜索的目标是发现以初始符号S为根并且恰好覆盖整个输入符号串的一切剖析树。无论选择什么搜索算法，这里明显地存在着两种约束有助于指导这种搜索。第一种约束来自数据，即输入句子本身。如果最后的剖析树是正确的，它必须有三个叶子，而且这三个叶子应该分别是book，that和flight。第二种约束来自语法。如果最后的剖析树是正确的，它必须有一个根，这个根就是初始符号S。

关于经验主义和理性主义的论战，我们可以认识到，这两种约束同时也就产生了大多数剖析算法使用的两种搜索策略：一种是自顶向下或目标制导的搜索（goal-directed search）,一种是自底向上或数据制导的搜索（data-directed search）。

责任编辑：admin