正規(guī)文法與有限自動(dòng)機(jī)的相互轉(zhuǎn)換.

1、正規(guī)文法與有限自動(dòng)機(jī)的相互轉(zhuǎn)換二零一五年十二月二十七日目錄摘要 1關(guān)鍵詞 11 課題綜述 11.1 目的 11.2 設(shè)計(jì)內(nèi)容 11.3 設(shè)計(jì)原則 12 系統(tǒng)分析 22.1 正規(guī)式 22.2 有限自動(dòng)機(jī)（有窮自動(dòng)機(jī)） 22.3NFA向DFA勺轉(zhuǎn)換 32.4 正規(guī)式與有限自動(dòng)機(jī)之間的轉(zhuǎn)換 33 系統(tǒng)設(shè)計(jì) 43.1 從正規(guī)文法到有限自動(dòng)機(jī) 43.11 正規(guī)文法到有限自動(dòng)機(jī)勺等價(jià)性證明 43.12 正規(guī)文法到有限自動(dòng)機(jī)勺構(gòu)造方法 53.2 從有限自動(dòng)機(jī)到正規(guī)文法 63.21 有限自動(dòng)機(jī)到正規(guī)文法勺等價(jià)性證明 63.22 有限自動(dòng)機(jī)到正規(guī)文法勺構(gòu)造方法 74 運(yùn)行與測試 7總結(jié) 9參考文獻(xiàn) 9附錄 10

2、摘要：正規(guī)文法包括左線性文法和右線性文法 。由于正規(guī)文法和正規(guī)表達(dá)式在描述語言的能 力上是等價(jià)的，而正規(guī)表達(dá)式和有限自動(dòng)機(jī)在描述語言的能力上也是等價(jià)的，因此，正規(guī)文法和有限自動(dòng)機(jī)之間也存在著等價(jià)性。通常，對于正規(guī)文法G和有限自動(dòng)機(jī) M G所定義的語言記作L(G)，M所能識(shí)別的語言記作 L(M)，如果有L(G)=L(M),則稱G和M是等價(jià)的。關(guān)鍵詞： 正規(guī)文法；有限自動(dòng)機(jī)；等價(jià)性；構(gòu)造方法1課題綜述1.1 目的1. 理解正規(guī)文法與有限自動(dòng)機(jī)(FA)的本質(zhì)聯(lián)系；2. 掌握正規(guī)文法與有限自動(dòng)機(jī)之間相互轉(zhuǎn)化的算法原理；3. 學(xué)會(huì)使用 Visual C+ 等編程工具實(shí)現(xiàn)正規(guī)文法與有限自動(dòng)機(jī)之間的相互 轉(zhuǎn)

3、化；1.2 設(shè)計(jì)內(nèi)容使用Visual C+/Visual C# 等工具，設(shè)計(jì)軟件 MySof_3，可以實(shí)現(xiàn)以下功 能：1. 根據(jù)用戶輸入的文本文件( *.txt )的名稱，打開文件，并從文件中獲取 文法的產(chǎn)生式、非終結(jié)符、終結(jié)符、開始符等基本信息；2. 判斷該文法是否為正規(guī)文法，若是，則將其轉(zhuǎn)化為有限自動(dòng)機(jī)；3. 根據(jù)用戶輸入的文本文件( *.txt )的名稱，打開文件，并從文件中獲取 有限自動(dòng)機(jī)的狀態(tài)集、字母表、初態(tài)、終態(tài)集、轉(zhuǎn)移函數(shù)等基本信息；4. 判斷該自動(dòng)機(jī)是否合法，若合法，則將其轉(zhuǎn)化為正規(guī)文法；1.3 設(shè)計(jì)原則正規(guī)文法與有窮自動(dòng)機(jī)有著特殊的關(guān)系，采用下面的規(guī)則可從正規(guī)文法G直接構(gòu)造一

4、個(gè)有窮自動(dòng)機(jī)NFA M使得L(M)=L(G):(1) M的字母表與G的終結(jié)符相同；第 1 頁 共 13 頁(2) 為G中的每一個(gè)非終結(jié)符生成 M的一個(gè)狀態(tài)，G的開始符S是開始狀態(tài);(3) 增加一個(gè)新狀態(tài)Z,作為NFA的終態(tài)；(4) 對G中的形如A-tB的規(guī)則(其中T為終結(jié)符或，A為非終結(jié)符的產(chǎn)生式)，構(gòu)造M的一個(gè)轉(zhuǎn)換函數(shù)f(A,t)=B ；(5) 對G中形如A-t的產(chǎn)生式，構(gòu)造M的一個(gè)轉(zhuǎn)換函數(shù)f (A, t)=Z。2系統(tǒng)分析2.1 正規(guī)式正規(guī)式：正則表達(dá)式，表示正規(guī)集的工具。一個(gè)正規(guī)式對應(yīng)一個(gè)正規(guī)文法(3型文法)之間能夠進(jìn)行準(zhǔn)換三個(gè)基本規(guī)則：A-xB,B-y 則 A=xy。A-xA|y 則A=

5、x*y ( x*代表x從1到無窮多個(gè))A-x,A-y 貝U A=x|y正規(guī)式主要用到了遞歸的思想，無論遇到多復(fù)雜的正規(guī)式都可以拆分成上面 這三種形式，然后進(jìn)行解題。2.2有限自動(dòng)機(jī)(有窮自動(dòng)機(jī))DFA ( Deterministic Finite Automation):確定的有限自動(dòng)機(jī)表達(dá)式：M=( S，E，f，So, Z)1.S為一個(gè)有限狀態(tài)集合2. 刀是一個(gè)字母表，它所包含的的每個(gè)元素稱為一個(gè)輸入字符；3. f是一個(gè)從SXE (笛卡爾乘積)至S的單值部分映射。f (S, a) =s意味 著當(dāng)現(xiàn)在的狀態(tài)為s，輸入字符a時(shí)，將轉(zhuǎn)換到下一狀態(tài)s.s為s的一個(gè)后繼 狀態(tài)。4.So S,是唯一的初

6、態(tài)；NFA( Non determi ni sticFiniteAutomata):不確定的有限自動(dòng)機(jī)如果理解了有限自動(dòng)機(jī)，則無限自動(dòng)機(jī)和它的區(qū)別就是上面的第四項(xiàng)。So? S,它的初態(tài)不是唯一的，而是一個(gè)集合。2.3NFA向DFA的轉(zhuǎn)換這個(gè)轉(zhuǎn)換是一個(gè)比較簡單的過程。1. 如果有一個(gè)不確定的有限自動(dòng)機(jī)，則可以轉(zhuǎn)化為圖的方式。此處不詳述怎 樣轉(zhuǎn)圖的方式。2. 先將初態(tài)確定，然后根據(jù)輸入的每個(gè)元素可以得到哪些狀態(tài)，依次列表。3. 這些狀態(tài)集合可以稱為這個(gè)有限狀態(tài)集合 n個(gè)子集。按0,1,2的順序 編號。4. 因?yàn)檫@些子集之間的關(guān)系是輸入一個(gè)確定值確定的，所以這些子集之間存在一些關(guān)系，即把這些子集的關(guān)

7、系寫出來完成NFA向 DFA的轉(zhuǎn)換。如果不懂可以從網(wǎng)上找一個(gè)例子進(jìn)行理解。2.4正規(guī)式與有限自動(dòng)機(jī)之間的轉(zhuǎn)換S5任意的正規(guī)式都可以轉(zhuǎn)換為上述二種的表現(xiàn)形式。在一個(gè)有限自動(dòng)機(jī)轉(zhuǎn)換為正規(guī)式時(shí)，就是考慮從初態(tài)到終態(tài)可以輸入哪些數(shù)據(jù)到達(dá)。而這些數(shù)據(jù)可以用哪種正規(guī)式概括進(jìn)來。3系統(tǒng)設(shè)計(jì)3.1 從正規(guī)文法到有限自動(dòng)機(jī)3.11正規(guī)文法到有限自動(dòng)機(jī)的等價(jià)性證明定理1:對于每一個(gè)右線性正規(guī)文法 GR和左線性正規(guī)文法 GL都存在一個(gè) 有限自動(dòng)機(jī)M與之等價(jià)。證明：1. 設(shè)右線性文法GR=（VT,VN,S,P）,將VN中每個(gè)非終結(jié)符視為狀態(tài)符號， 并增加一個(gè)新的終止符號f，（f VN ）。令M=（VN f，VT，d，

8、S，f），其中 狀態(tài)轉(zhuǎn)換函數(shù)d由以下規(guī)則定義：若對某個(gè) A VN及a VT ，P中有產(chǎn)生式 A a,則令 d（A，a）=f ;對任意的A VN及a VT ，設(shè)P中左端為A右端第一個(gè)符號為a的所有 產(chǎn)生式為A aA1 I aA2丨I aAk （不包括A a），則令d（A，a）= A1，A2,， Ak。顯然上述得到的M為一個(gè)NFA到此，已說明存在一個(gè)FAM與該右線性文法 對應(yīng)，下面說明它們的等價(jià)性（L（GR）=L（M）。對右線性正規(guī)文法GR在S W的最左推導(dǎo)過程中，利用A aB一次就相當(dāng)于 在M中從狀態(tài)A出發(fā)經(jīng)標(biāo)記為a的箭弧到達(dá)狀態(tài)B（包括a= &的情形）。在推導(dǎo)過 程的最后，利用A a一次則相當(dāng)

9、于在M中從狀態(tài)A出發(fā)經(jīng)標(biāo)記為a的箭弧到達(dá)終態(tài)f(包括a= 的情形)綜上所述，在正規(guī)文法GR中，S W的充要條件是：在M中，從狀態(tài)S到狀態(tài) f有一條通路，其上所有箭弧的標(biāo)記符號依次連接起來恰好等于W這就是說，WL(GR)當(dāng)且僅當(dāng) W L(M)，故 L(GR)=L(M)。2. 設(shè)左線性文法GL=(VT,VN,S,P)，將VN中每個(gè)非終結(jié)符視為狀態(tài)符號， 并增加一個(gè)新的初始狀態(tài)符號 q,( q VN)。令M=(VN q，VT，d，q，S)， 其中狀態(tài)轉(zhuǎn)換函數(shù) d 由以下規(guī)則定義： 若對某個(gè)A VN及a VT ，P中有產(chǎn)生式A-a，則令d(q，a)=A; 對任意的A VN及a VT ，設(shè)P中所有右端第

10、一個(gè)符號為 A,第二個(gè)符 號為a的所有產(chǎn)生式為 A1-Aa A2-Aa，AK Aa則令d(A，a)= A1, A2， Ak。顯然上述得到的M為一個(gè)NFA到此，已說明存在一個(gè)FAM與該左線性文法 對應(yīng)，下面說明它們的等價(jià)性 (L(GL)=L(M) ) 。對左線性正規(guī)文法GL，在S W的最左推導(dǎo)過程中，利用B-Aa一次就相當(dāng)于 從狀態(tài)A出發(fā)經(jīng)標(biāo)記為a的箭弧到達(dá)狀態(tài)B(包括a=的情形)。在推導(dǎo)的最后， 利用A a 一次則相當(dāng)于在M中從狀態(tài)q出發(fā)經(jīng)標(biāo)記為a的箭弧到達(dá)狀態(tài)A(包括 a=的情形)。綜上所述，在正規(guī)文法 GL中，S W的充要條件是：在M中，從狀 態(tài)q到狀態(tài)S有一條通路，其上所有箭弧的標(biāo)記符號

11、依次連接起來恰好等于W這就是說，W L(GL)當(dāng)且僅當(dāng) W L(M)，故L(GL)=L(M)。3.12 正規(guī)文法到有限自動(dòng)機(jī)的構(gòu)造方法 上述定理的證明采用了構(gòu)造性的證明方法，由此可以得出由正規(guī)文法到有限 自動(dòng)機(jī)的構(gòu)造方法。從右線性正規(guī)文法GR=(VT,VN,S,P)構(gòu)造有限自動(dòng)機(jī)M=( VNf，VT，d，S， f) 的方法如下： 將VN中每個(gè)符號視為一個(gè)狀態(tài)符號，增加一個(gè)新的終態(tài)符號f，f VN ; 對于產(chǎn)生式 A-a(a VT )，則構(gòu)造 d(A， a)=f； 對于產(chǎn)生式 A-aA1(a VT )，則構(gòu)造 d(A， a)= A1 。從左線性正規(guī)文法 GL=(VT,VN,S,P)構(gòu)造有限自動(dòng)機(jī)

12、 M=(VNq，VT, d，q，S) 的方法如下： 將VN中每個(gè)符號視為一個(gè)狀態(tài)符號，增加一個(gè)新的初態(tài)符號q, q VN; 對于產(chǎn)生式 Z a (a VT )，則構(gòu)造d(q , a)=A； 對于產(chǎn)生式 A1Aa (a VT )，則構(gòu)造d(A, a)= A1 03.2 從有限自動(dòng)機(jī)到正規(guī)文法3.21 有限自動(dòng)機(jī)到正規(guī)文法的等價(jià)性證明定理2:對于每一個(gè)有限自動(dòng)機(jī) M都存在一個(gè)右線性正規(guī)文法 GR和左線性 正規(guī)文法GL與之等價(jià)。證明:1. 設(shè)DFAM=(S E, d, SO, F)，分以下兩種情況進(jìn)行證明：(1) 若SO F,則令GR=(E,S, SO, P)，其中P是由以下規(guī)則定義的產(chǎn)生式 集合，

13、對任何a E及A,B S，若d(A, a)=B,貝U: 當(dāng)B F時(shí)，令A(yù)-aB; 當(dāng)B F時(shí)，令A(yù) aBI a；顯然，上述得到的 文 法為一 個(gè) 右線性 正規(guī)文法， 下面說 明它們的等 價(jià)性 (L(M)=L(GR) ) 0在DFAM中，對任何 w E*，不妨設(shè)w=a1a2ak,其中ai E (i=1,2,k), 若S W,則存在一個(gè)最左推導(dǎo)：S0a1A1a1a2A2a1aiAi a1aiai+1Ai+1 a1ak,因而，在M中存在一條從S0出發(fā)一次經(jīng)過A1,，Ak-1到達(dá)終態(tài)的通 路，該通路上所有箭弧的標(biāo)記依次為 a1,，ak。反之亦然。所以，w L(GR)當(dāng) 且僅當(dāng) w L(M)，故 L(M

14、)=L(GR)。(2) 若S0 F,因?yàn)閐(S0, )= S0,所以 L(M)，但上面構(gòu)造的L(GR)中不 含&。因此，需在文法中添加產(chǎn)生式 S0 &，這樣，就有L(M)=L(GR)o2. 設(shè)DFAM=(S E, d, S0, F)，分以下兩種情況進(jìn)行證明：(1)若S0 F,則令GL=(E,S, X, P)，其中X F, P是由以下規(guī)則定義的產(chǎn) 生式集合，對任何a E及A,B S，若d(A, a)=B,貝U: 當(dāng)2 S0時(shí)，令B Aa； 當(dāng)A=S0時(shí)，令4a I Aa；顯然，上述得到的文法為一個(gè)左線性正規(guī)文法，下面說明它們的等價(jià)性(L(M)=L(GL) )在DFAM中，對任何 w刀*，不妨設(shè)w

15、=a1a2ak,其中ai刀(i=1,2,k), 若存在一條從SO到X的通路，通路上所有箭弧的標(biāo)記依次為 al,，ak，則在 GL中一定存在一個(gè)最左推導(dǎo)： X Akak Ak-1ak-1ak A2a2ak alak， 即w L(GL)。反之亦然。所以，w L(GL)當(dāng)且僅當(dāng)w L(M)，故L(M)=L(GL)。(2)若SO F,則 L(M)，但上面構(gòu)造的L(GL)中不含。因此，需在文法 中添加產(chǎn)生式X-&，這樣，就有L(M)=L(GL)。3.22 有限自動(dòng)機(jī)到正規(guī)文法的構(gòu)造方法上述定理的證明采用了構(gòu)造性的證明方法，由此可以得出由有限自動(dòng)機(jī)到正 規(guī)文法的構(gòu)造方法。從有限自動(dòng)機(jī)M=( S，E，d，S

16、O, F)構(gòu)造右線性正規(guī)文法GR的方法如下： 令GR=(E ,S, SO，P)，其中P是由以下規(guī)則定義的產(chǎn)生式集合：對任何 d(A， a)=B, 若B F，則令L aB; 若B F，并且B狀態(tài)有箭弧射出，則令 A-aB I a；若B F，并且B狀態(tài)沒 有箭弧射出，則令A(yù) a； 若SO F,貝U令SO &。從有限自動(dòng)機(jī)M=( S,E, d, SO, F)構(gòu)造左線性正規(guī)文法GL的方法如下：令GL=(E,S, X , P)，其中P是由以下規(guī)則定義的產(chǎn)生式集合：對任何 d(A， a)=B, 若A不是初始狀態(tài)，則令B Aa； 若A是初始狀態(tài)，并且A狀態(tài)有箭弧射入，則令B Aal a；若A是初始狀 態(tài)，并

17、且A狀態(tài)沒有箭弧射入，則令B a； 若SO F,則令X 04 運(yùn)行與測試中間狀態(tài)：1個(gè)，為B; 終態(tài)：2個(gè)，分別為C、D;終結(jié)符：2個(gè)，分別為a b;裝換關(guān)系為：StatABCDA0a0bB00b0Ca00bD0b0b(6) 得到的結(jié)果如圖:沁 -E:vcbianyiDebugbianyi. eze*符n目：4態(tài) 狀數(shù): 的R個(gè)態(tài) 有.的狀 茯態(tài)喬 動(dòng)始卿 自幵AAAA后分別輸入終態(tài)鬻嚴(yán)2flflubo ah ARCDHBCQABiCTXBguD 態(tài)態(tài)態(tài)態(tài)態(tài)衣哭心態(tài)態(tài)態(tài)態(tài)態(tài)衣關(guān)冬心態(tài)7? ?1工 r-丄 r- b/llyl1ylp/ I# r-丄 r-丄 f/ I y F/ *!出岀出出出岀岀

18、岀岀出出出出岀出出JI.宜直直直宜育直直直直言宜育直直直 衣否否否否否否否否否否否否否否否否-知ttib&MtiH 匕 H0b匕b匕七Kttl.d&JJ匕 Btt0七匕居0也匕 tnAAABRBBCCCCDDDD 造態(tài)新暦態(tài)衣笑關(guān)心態(tài)態(tài)蕊蕊怒衣裳叢態(tài)由此自動(dòng)機(jī)轉(zhuǎn)換成的對應(yīng)的文法為：Mad課乂*人其申P(guān)為:-aB-bD-bC-bDIi-bDC- - Press any lew to continue第8頁共13頁總結(jié)經(jīng)過一周的努力，終于把編譯原理這門課的大作業(yè)做完了，由于學(xué)習(xí)理論的 時(shí)候總是感覺這門課程特別的復(fù)雜，有許多繁瑣的東西，起初以為課程設(shè)計(jì)的內(nèi) 容會(huì)更加的復(fù)雜，后來認(rèn)真看了題目，和相對應(yīng)

19、于課本上的內(nèi)容，我的這個(gè)題目 還真的很簡單，只是用到了“數(shù)組”、“圖”這兩個(gè)數(shù)據(jù)結(jié)構(gòu)，再就是有兩個(gè)二 層嵌套的循環(huán)就能夠應(yīng)對這個(gè)題目了。有限自動(dòng)機(jī)用于構(gòu)造詞法分析程序，正規(guī)文法用于構(gòu)造語法分析程序，它們分別 是語言的識(shí)別工具和定義工具 ，在構(gòu)造高級程序設(shè)計(jì)語言的編譯程序時(shí)占有舉足 輕重的地位。有限自動(dòng)機(jī)作為語言詞法的識(shí)別工具，必須能夠識(shí)別由文法定義的 所有詞法范疇；而文法作為語言語法的定義工具，也必須有能力定義有限自動(dòng)機(jī) 能識(shí)別的所有詞法范疇的規(guī)則。從這一意義上講，有限自動(dòng)機(jī)和正規(guī)文法在描述 語言的能力上就存在著等價(jià)性，而由這些等價(jià)性推導(dǎo)出來的相互轉(zhuǎn)換方法，在構(gòu) 造編譯程序時(shí)具有一定的檢測和指

20、導(dǎo)作用。由于時(shí)間有限 ，這次的課程設(shè)計(jì)中我沒有考慮到不確定的自動(dòng)機(jī)轉(zhuǎn)換成正規(guī)文法 的情況，在以后的學(xué)習(xí)中一定將這種更加復(fù)雜的情況考慮進(jìn)去，讓自己的程序更 加的完整。經(jīng)過一學(xué)期的編譯原理這門課程的學(xué)習(xí) ，我們深深的了解到了編譯器結(jié)構(gòu)的復(fù)雜 程度，更了解了我們學(xué)習(xí)的高級語言的強(qiáng)大功能，我們做的課程設(shè)計(jì)只是一個(gè)完 整編譯器的冰山一角。后面還有更多需要我們更加需要懂得的東西。參考文獻(xiàn)1 陳火旺等程序設(shè)計(jì)語言編譯原理（第3版）M.北京：國防工業(yè)出版社， 2000. 72 胡元義 . 編譯原理教程（第二版） M. 西安：西安電子科技大學(xué)出版社， 2006. 83 劉堅(jiān) . 編譯原理基礎(chǔ) M. 西安：西安電子科技大學(xué)出版社， 2002. 44 呂映芝 . 編譯原理 M. 北京：清華大學(xué)出版社， 1998 .5附錄#includeusing namespace std;int main()int n, m;/n 為自動(dòng)機(jī)狀態(tài)的總數(shù)目/m 為自動(dòng)機(jī)終結(jié)符的數(shù)目int n_midd_stat, n_final_stat;/n_midd_stat 為中間狀態(tài)的數(shù)目/n_final_stat 為終態(tài)的數(shù)目cout n;char* stat = new charn;cout stat0;cout n_midd_stat;cout 請輸入分別中間狀態(tài)： endl;for(int i1 = 0; i1 sta