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

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

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

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

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

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

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

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

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

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

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

責任編輯：admin