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