我們通過剖析That flight 來研究這個過程。假設(shè)在That flight中That已經(jīng)被識別出來，當(dāng)時的狀態(tài)如下：

現(xiàn)在來研究下面的情況，這時剖析器已經(jīng)處理了flight，并由此產(chǎn)生了如下的狀態(tài)：

為了推進NP規(guī)則，分析器把在Dag2的NOMINAL特征中發(fā)現(xiàn)的特征結(jié)構(gòu)與在NP的Dag1的NOMINAL特征中發(fā)現(xiàn)的特征結(jié)構(gòu)進行合一。正如在原來的算法中那樣，我們建立起一個新狀態(tài)來表示現(xiàn)有狀態(tài)已經(jīng)被向前推進這一事實。這個新狀態(tài)的DAG也就是上面合一的結(jié)果所形成的DAG。

對于原來算法的最后一個改變是檢查已包含在線圖中的狀態(tài)。在原來的算法中，ENQUEUE這個功能拒絕進入線圖中的與該線圖已有的狀態(tài)“等同”（identical）的任何狀態(tài)。所謂“等同”意味著規(guī)則相同，開始位置和結(jié)束位置相同，點“.”的位置相同。這種檢查使得算法可以避免與左遞歸規(guī)則相關(guān)的無窮遞歸問題。

在帶合一約束的剖析中，我們的狀態(tài)當(dāng)然會更復(fù)雜，因為這時的狀態(tài)中具有與其相關(guān)聯(lián)的特征結(jié)構(gòu)。在原來的標(biāo)準(zhǔn)看來似乎等同的狀態(tài)，現(xiàn)在事實上可能是不同的，因為與它們聯(lián)系的DAG可能有所不同。要解決這樣的問題顯然只需要擴充等同性的檢查，使得這種檢查包含與狀態(tài)有關(guān)聯(lián)的DAG，不過我們還可以改善這種解決辦法。

之所以要求改善，是因為要進行等同性的檢查。這種改善的目的在于阻止把無用狀態(tài)加到線圖中，以免造成浪費，這種改善對于剖析的影響可由現(xiàn)有狀態(tài)來實現(xiàn)。換言之，我們希望阻止那些造成重復(fù)工作的狀態(tài)進入線圖中，這些工作最終可以由其他狀態(tài)來完成。當(dāng)然，很顯然這是關(guān)于等同狀態(tài)的問題，但這也是線圖中的狀態(tài)的問題，這個問題比研究新狀態(tài)更具有一般性我們來研究下面的情況，其中線圖包含的狀態(tài)的Dag沒有對Det進行約束。

NP → ?Det NP, [i, i], [], Dag

這樣的狀態(tài)只是說，它期待在位置i有一個Det，任何的Det都可以做到這一點。

現(xiàn)在來研究如果剖析器試圖把一個新狀態(tài)插入到線圖中，而線圖中的狀態(tài)與這個狀態(tài)完全等同，只是DAG限制Det為單數(shù)時的情況。在這樣的場合，盡管有關(guān)狀態(tài)不等同，但是在線圖中添加新狀態(tài)不能得到什么東西，因此這樣的插入被阻止。

為了看到這一點，讓我們來考慮所有的情況。如果添加一個新狀態(tài)，則單數(shù)Det在兩個狀態(tài)中都是匹配的，而且兩個狀態(tài)都要向前推進。由于特征的合一，兩個狀態(tài)都有DAG指出它們的Det都是單數(shù)，其結(jié)果是線圖中的狀態(tài)成倍增加。如果遇到復(fù)數(shù)的Det，那么新狀態(tài)將拒絕這個Det，并且不向前推進，而這時老的規(guī)則將向前推進，進入線圖中的一個新狀態(tài)。另一方面，如果不把新狀態(tài)放入線圖中，復(fù)數(shù)或單數(shù)的Det將與更一般的狀態(tài)相匹配，并且向前推進，這將導(dǎo)致把一個新狀態(tài)加到線圖中。注意，除了避免成倍增加狀態(tài)的數(shù)目之外，這種情況與把新狀態(tài)加到線圖中的情形是完全一樣的?？偠灾?，把一個比在線圖中的狀態(tài)更加特殊的狀態(tài)加到線圖中，最后還是一無所獲。

可喜的是，我們可以使用前面討論過的“蘊涵于”（subsumption）的概念，形式化地描述特征結(jié)構(gòu)中的“一般化”（generalization）和“特殊化”（specialization）之間的關(guān)系。這意味著，改變ENQUEUE的一種合適的辦法是檢查一個新建立的狀態(tài)是不是蘊涵于線圖的任何現(xiàn)有狀態(tài)中。如果是，就不允許它進入線圖中。更具體地說，如果一個新狀態(tài)與現(xiàn)有狀態(tài)的規(guī)則相同，開始和結(jié)束位置相同，子部分相同，點“·”的位置相同，并且如果存在狀態(tài)的DAG蘊涵于新狀態(tài)的DAG（也就是說，DagwuDagmew),那么這個新狀態(tài)就不能加到線圖中。對于原來的Earley的ENQUEUE過程的必要改變，可參見圖2。

責(zé)任編輯：admin