|
9.7.2 PARSIFAL的数据结构
为了实现确定性算法。句法分析器PARSIFAL采用了以下两个数据结构：
(1)激活结点堆栈(active node stack，简称ans)：用来存放未完成的成分。堆栈的工作方式是后进-先出；
(2)三单元成分缓冲器(three-place constituent buffer，简称3bf)：每个单元存放的可以是-个词，也可以是一个上位句法功能尚未确定的成分。缓冲器的工作方式是先进-先出。
输入句子中的每个词按从左至右的顺序被处理，每当一个词经过词法分析后便连同它的词典信息一起被装入缓冲器最左面的一个空单元。如果根据ans栈顶和3bf的当前状态，能够应用一条规则来构造出某种局部结构，便实行这种归并(如果栈顶成分参加这次归并，就意味着它被弹出堆栈)，并把归并结果存放在3bf的第一个单元里，然后重复上述归并过程；否则就把3bf第一单元的内容暂时推入ans寄存，并通过把新词装入3bf来重新开始新的一轮归并过程。直至3bf为空，且ans中只存有一个根结点S为止。
举例来说，输入句子为
"John should have scheduled the meeting."
(约翰应当安排好会议的日程。)
当"scheduled"-词被装入缓冲器时，ans和3bf的状态可表示如下：
：栈底 S1 (S DCL MAJOR S)/(PARSE-AUX CPOOL)
NP：(John)
(MODAL，PAST VSPL AUX)/(BuILD-AUX)
栈顶 MODAL：(should)
AUX1
：第1单元：WORD3(*HAVE VERB TENSELESS AUXVERB PRES V-3S)：(have)
第2单元：WORD4(*SCHEDULE COMP-OBJ VERB INF OBJ V-35 ED＝EN EN PART PAST ED)：(scheduled)
可以看到，在(ans中现在有两个成分,一个是栈底的根结点S1及其子结点NP(John，另一个是栈顶的结点AUX1及其子结点MODAL(should)；在结点S1和AUX1右面斜杠后的括号里记载着用来处理这个特定成分的规则包。处在栈顶位置的结点又叫做当前激活结点(本例中是AUX1)，只有与它相伴随的规则包才处于激活状态，也即收藏在这个规则包(本例中是助动词处理规则包BUILD-AUX)中的规则将被分析器优先使用来归并栈顶和缓冲器中的诸成分。与栈底结点S1相伴随的规则包PARSEAUX和CPOOL目前还不能应用，只有当S1重新出现在栈顶位置时，这两个规则包才被激活。
PARSIFAL的句法规则一般由三个成分组成，它们依次是优先级(一个正整数)，匹配模式和动作。下面是句法规则的书写形式：
 |
|
||||||||||||||||||||||||