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