把特征結(jié)構(gòu)與合一運(yùn)算結(jié)合到Earley算法中的目的有兩個(gè)：第一，使用特征結(jié)構(gòu)，從而為剖析的組成成分提供更豐富的表達(dá)方式；第二，阻止成分進(jìn)入破壞合一約束的非良構(gòu)成分的線圖中。只要最小限度地改變?cè)瓉?lái)的Earley算法，就可以達(dá)到這樣的目的。

第一個(gè)改變是改變?cè)谠瓉?lái)的代碼中使用的各種表達(dá)方法。Earley算法在運(yùn)算時(shí)要使用一套無(wú)裝飾的上下文無(wú)關(guān)語(yǔ)法規(guī)則，來(lái)填充一種稱為線圖的數(shù)據(jù)結(jié)構(gòu)，這種線圖由狀態(tài)的集合組成。在剖析的終點(diǎn)，構(gòu)成線圖的狀態(tài)可以表示對(duì)于輸入的一切可能的剖析結(jié)果。因此，我們要進(jìn)行的改變首先從改變上下文無(wú)關(guān)語(yǔ)法規(guī)則和線圖中的狀態(tài)開始。

在改變規(guī)則時(shí)，除了它們當(dāng)前的成分之外，還包括從它們的合一約束推導(dǎo)出的特征結(jié)構(gòu)。更具體地說(shuō)，我們將使用由規(guī)則列出的約束來(lái)建立特征結(jié)構(gòu)，把特征結(jié)構(gòu)表示為DAG，以便在剖析過(guò)程中與規(guī)則一起使用它們。

我們來(lái)研究如下的帶有合一約束的上下文無(wú)關(guān)規(guī)則：

S → NP VP

=

把這些約束轉(zhuǎn)變?yōu)樘卣鹘Y(jié)構(gòu)，得到如下的結(jié)構(gòu)：

在這個(gè)推導(dǎo)中，我們首先對(duì)上下文無(wú)關(guān)規(guī)則中的每個(gè)部分創(chuàng)建頂層特征，在這個(gè)例子中，這些頂層特征是S，NP和VP；使用這樣的方法，把各種不同的約束結(jié)合到一個(gè)單獨(dú)的結(jié)構(gòu)中。然后，順著約束中的路徑等式，進(jìn)一步再把各種成分加到這個(gè)結(jié)構(gòu)中。注意，這只是一種純粹的表記法的變換，DAG和約束等式中包含的信息都是完全一樣的。但是，把各種約束捆綁到一個(gè)單獨(dú)的特征結(jié)構(gòu)中，這樣的形式就可以直接放到合一算法中。

第二個(gè)改變是改變用于表示Earley算法中局部剖析的狀態(tài)。原來(lái)的狀態(tài)包括所用的上下文無(wú)關(guān)規(guī)則、表示規(guī)則已經(jīng)完成部分的點(diǎn)的位置、狀態(tài)的開始和終止位置以及表示狀態(tài)中已完成子部分的其他狀態(tài)的一個(gè)表?，F(xiàn)在再加上一個(gè)附加的區(qū)域，這個(gè)區(qū)域包含表示與狀態(tài)相應(yīng)的特征結(jié)構(gòu)的DAG。注意，當(dāng)一個(gè)規(guī)則首次被PREDICTOR用來(lái)建立一個(gè)狀態(tài)時(shí)，與狀態(tài)相聯(lián)系的DAG將由規(guī)則中檢索出來(lái)的DAG組成。例如，當(dāng)PREDICTOR使用上面的S規(guī)則而進(jìn)入到線圖中的一個(gè)狀態(tài)時(shí)，上面給出DAG將是初始的DAG。我們把狀態(tài)表示如下，其中DAG表示上面給出的特征結(jié)構(gòu)：

S → ?NP VP, [0,0], [], Dag

給出了這些新增加的表示之后，就可以來(lái)改變算法本身了。在行動(dòng)方面的最重要的改變是：當(dāng)通過(guò)擴(kuò)充現(xiàn)有狀態(tài)建立一個(gè)新狀態(tài)時(shí)，在COMPLETER程序中發(fā)生了變化。我們知道，當(dāng)一個(gè)完成的成分加到線圖中時(shí)，就要調(diào)用COMPLETER。COMPLETER的任務(wù)是發(fā)現(xiàn)并擴(kuò)充線圖中現(xiàn)有狀態(tài)，這個(gè)狀態(tài)正在查找與新完成的成分相容的成分。因此，COMPLETER是一種結(jié)合兩個(gè)狀態(tài)中的信息建立新狀態(tài)的功能，它要使用合一的操作。

更具體地說(shuō)，COMPLETER通過(guò)發(fā)現(xiàn)現(xiàn)有狀態(tài)的方式，把一個(gè)新的狀態(tài)加到線圖中，并把現(xiàn)有狀態(tài)中的“.”由新的完成狀態(tài)向前推進(jìn)。當(dāng)直接在“.”后面的成分的范疇與新完成的成分的范疇相匹配時(shí)，就可以把“.”向前推進(jìn)。為了便于使用特征結(jié)構(gòu)，我們可以改變這樣的做法，而把與新的完成狀態(tài)相聯(lián)系的特征結(jié)構(gòu)與被推進(jìn)的特征結(jié)構(gòu)中的適當(dāng)部分進(jìn)行合一。如果這樣的合一取得成功，那么新狀態(tài)的DAG就接受合一后的結(jié)構(gòu)，并進(jìn)入線圖中。如果合一失敗，則沒有新的狀態(tài)進(jìn)入線圖中。COMPLETER的這種改變情況如圖2所示。

圖2 修改Earley算法使之包括合一運(yùn)算