高效率可解析文法是計算機科學及其應用領域內很基本和重要的研究課題。高效率可解析性意味著能夠節(jié)省計算機的空間和時間。著名的LL(k)和LR(k)文法已被證明可無回溯地線性時間或線性空間解析。對于上下文自由文法CFL的一般解析算法是著名的CKY和Earley算法，兩者的時間和空間復雜度分別都是0(n3)和0(n2)。等價于對稱矩陣文法IAG(成員問題為NP完全問題，等價問題為不可決定問題)的UPAG(Unicluely Parsable Arrav Grammar)文法被證明可無回朔解析，其真子集可線性時間解析。在文獻中討論了一般短語結構生成文法的無回朔可一義解析性及其圖靈等價性，定義了稱為UPG(Uniquely arsable Gmmmar)的文法類，并證明了該類文法的無回朔一義可解析性及其圖靈等價性。這里討論一般短語結構生成文法的無回朔可一義解析性及其圖靈等價性。首先定義一個稱作OFG(Ovedap—Free Grammar)的生成文法系統(tǒng)，其對規(guī)則的限制條件比UPG的限制條件更強，但證明它仍然具有圖靈通用性(與圖靈機的等價性)和無回朔一義可解析性(無回溯無失敗可解析)。最后討論了OFG文法解析等問題。
2 定義
定義2．1一個無重疊生成文法(簡稱0FG)是一個系統(tǒng)式中：N和T分別是非終止符和終止符集合，S是啟始符，它是N的一個元素，$是限界符，它不屬于上面任何一個集合，P是重寫規(guī)則的集合，其中任一重寫規(guī)則具有：
這里α，β∈(N∪T)，α≠β，A∈N，且每個規(guī)則滿足下列條件：
重寫規(guī)則的左部至少有一個非終結符，其右部不能是$5，S$,$S$或S。
對任意兩個重寫規(guī)則r1=α1→β1和r2=α2→β2，應滿足：①不存在δ，β′1,β'2∈(N∪T∪{$})+使得β1=β′1δ和β2=δβ′2，即β1和β2不能有任何相互重疊的部分；②如果存在γ，γ′∈(N∪T∪{$}){$})*使β1=γβ2γ'，則r1=r2。
令η∈{N∪T)+,α→β是P中的任意一個規(guī)則，如果存在γ，δ∈(N∪T∪{$})*，使得η=γaδ，則稱規(guī)則α→β可應用于η。通過對η應用規(guī)則α→β，可以得到ζ=γβδ,對此，稱在G中ζ可由應用規(guī)則α→β從η直接推導而得，記為，或簡記為的自反傳遞閉包記為如果存在ξ1，ξ2，…，ξn-1使得，則記為在G為默認的情況下，分別簡記為
令η∈(N∪T)+，若為G中的一個推導句型，稱η為G中的一個句型。對于任一文法G，其生成的語言定義為：
定義2．2一個確定性圖靈機(簡稱DTM)是一個系統(tǒng)M：
式中：Q是狀態(tài)集合，∑是輸入符號的集合，Г帶符號集合，是一個移動函數，a0∈Г是一個空白符號，q0是初始狀態(tài)，qf是終止狀態(tài)。
假設M具有一個向右無限的符號帶，M總是從符號帶的最左端位置以初始狀態(tài)開始移動讀寫頭，且讀寫頭右側永不存在不連續(xù)字符帶(圖林機在任何時候都不向連續(xù)字符帶的中間寫空白字符，只能在最右端寫空白字符)。這樣的假設并不影響M的通用性。
定義2.3設C是一類文法系統(tǒng)或一類圖靈機，L[C]表示該類系統(tǒng)所生成或接受的語言的集合，稱為C的語言類，即：
L[C]={L(G)|G∈C}
3 圖靈通用性
引理3．1 OFG所生產的語言類是DTM接受的語言類的子集，即
證明：很顯然，對任何一個0FG文法G均可以容易地構造一個等價的Cllomsky O型文法G′，故O型文法]。而三L[Cllomsky 0型文法]=L[DMT]?；蚝唵蔚卣f，L[OFG]是遞歸可枚舉集的子集。
引理3．2 DTM接受的語言類是0FG所生產的語言類的子集，即：
證明：可以用0FG來模擬任一個確定的圖靈機的逆過程。不失一般性，假設圖靈機具有右無窮長帶，且在任何狀態(tài)下具有連續(xù)的字符序列，在任何時候都不向字符帶中段上寫空白字符。
依據上面的定義，文法G將逆向地來模擬確定的圖靈機M的動作。如果M最終能接受一個帶而停止，則一定存在一個G能模擬M。因此L(G)和L(M)相等。由于M的確定性，這樣構造的G是滿足OFG的規(guī)則要求的。故結論得證。
4 無回朔一義可解析性
定義4．1 設上長度為m的串。又設α→β是一個規(guī)則且β=xixi+1…xi+|β|-1(1≤i≤m)是η的子串，則稱α→β在位置i可逆用于η，且稱(α→β，i)是η的一個逆用項。
對于η中的所有逆用項可以從左到右排列，從而可得到一個序列(α1→β1,i1)，(α2→β2,i2)，…，(αn→βn,in)，注意其中可存在許多相同的逆用項，但序號不同。用RAS(η)來表示該序列，n稱為該序列的長度。
如果從η的第i個位置的逆用項逆向使用規(guī)則α→β推導出ξ，則說ξ是從η第i位直接逆推導出的，記為或簡寫為很明顯當且僅當
關系的自反傳遞閉包用表示。關系的定義類似于的定義。
定義4．2 設η是G的一個推導句型，且
如果對于任意j(1≤j≤m)存在唯一的ξ和唯一的n使
則稱η是無回朔一義可解析的。如果G的全部句型無回朔可一義解析，則稱G是無回朔一義可解析的。
定義4.3 任一0FG G是無回朔一義可解析的。
證明：用歸納法，一步可推導出的任意推導句型是無回朔一義可解析的。設k步推導出的句型是無回朔一義可解析的，則可證明k+1步推導出的句型無回朔一義可解析的。具體證明如下?；A步：如果顯然η是無回朔一義可解析的。歸納步驟：設滿足是無回朔一義可解析的，即對任意的i，存在逆用項(αi→βi，ji)和唯一的ξk和n(ηk,i)使得
對滿足的任意η，存在且ξ是無回朔一義可解析的(回朔解析步為h)。很顯然，RAS(ξ)由RAS(ξ1)，(α→β，j)，RAS(ξ2)組成，且RAS(ξ1)和RAS(ξ2)均在RAS(ξ)中。η可能的解析如下：
(b)從RAS(ξ1)或RAS(ξ2)逆用項(αξ→βξ,i)開始，注意OFG文法規(guī)則的無重疊性，η的解析是由ηk的解析中某一步加入逆用(α→β,_)步構成，即在使用(α→β,_)逆用項的前后解析均具有ηk的解析性質，解析總步數加1，即
顯然，n+1和ηk對于iξ是唯一的。
無回朔一義可解析性表明．對于推導句型中的任意位置的逆用項可以在任何需要的時候應用它而不會改變解析的成功。任何解析步中出現的逆用項也可以被同時并行替換。
5 OFG的解析算法
根據定理4．1，可以直接得到如下異常簡單的解析算法，其對于OFG全集可無回朔一義解析。
算法5．1
(1)cw=$x$，x是一個被解析的字。
(2)if cw=$s$則成功解析并終止。
(3)隨機地在cw中找一逆用項(α→β,i)，且將其應用于
cw，這里α→β,∈P。如果無逆用項則解析失敗并終止。
(4)跳到(2)。
定理5．1 x在L(G)中當且僅當算法5．1終止并成功解析。
證明：由無回朔一義可解析性定理可證明。
算法中采用了隨機選擇的策略，也可以使用最左優(yōu)先或任意的解析策略。
6 結論
根據上面的討論，0FG具有下列性質：
OFG具有通用性(與圖靈機等價性)(定理3．1)，
OFG具有一義可解析性(定理4．1)，
OFG存在十分簡單的解析算法(算法5．1)。
需要進一步討論的問題是能否找到有用的OFG文法子集，在該子集上實現更有效的解析。另一個問題是希望能找到CFG與0FG子集的轉換關系，因為CFG的簡明方便性，與CFG對應的OFG文法將有較廣泛的應用。
下載文檔
