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

1、淮陰工學(xué)院編譯原理課程設(shè)計(jì)報(bào)告選題名稱: 正規(guī)文法與有限自動(dòng)機(jī)的相互轉(zhuǎn)換系（院）: 計(jì)算機(jī)工程學(xué)院專 業(yè):計(jì)算機(jī)科學(xué)與技術(shù)（軟件工程方向）班 級: 軟件1082 姓 名: 陳超 學(xué) 號(hào): 1081305202 指導(dǎo)教師: 高麗 王文豪 江波 于永彥學(xué)年學(xué)期: 2011 2012 學(xué)年 第 1 學(xué)期 2012 年 01 月 07 日摘要：正規(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í)別

2、的語言記作L(M)，如果有L(G)=L(M),則稱G和M是等價(jià)的。 關(guān)鍵詞：正規(guī)文法；有限自動(dòng)機(jī)；等價(jià)性；構(gòu)造方法目錄 TOC o 1-3 h z u HYPERLINK l _Toc315076723 1課題綜述 PAGEREF _Toc315076723 h 3 HYPERLINK l _Toc315076724 1.1目的 PAGEREF _Toc315076724 h 3 HYPERLINK l _Toc315076725 1.2設(shè)計(jì)內(nèi)容 PAGEREF _Toc315076725 h 3 HYPERLINK l _Toc315076726 1.3設(shè)計(jì)原則 PAGEREF _Toc31

3、5076726 h 4 HYPERLINK l _Toc315076727 2系統(tǒng)分析 PAGEREF _Toc315076727 h 4 HYPERLINK l _Toc315076728 2.1正規(guī)式 PAGEREF _Toc315076728 h 4 HYPERLINK l _Toc315076729 2.2有限自動(dòng)機(jī)（有窮自動(dòng)機(jī)） PAGEREF _Toc315076729 h 5 HYPERLINK l _Toc315076730 2.3NFA向DFA的轉(zhuǎn)換 PAGEREF _Toc315076730 h 5 HYPERLINK l _Toc315076731 2.4正規(guī)式與有限自動(dòng)

4、機(jī)之間的轉(zhuǎn)換 PAGEREF _Toc315076731 h 6 HYPERLINK l _Toc315076732 3系統(tǒng)設(shè)計(jì) PAGEREF _Toc315076732 h 6 HYPERLINK l _Toc315076733 3.1從正規(guī)文法到有限自動(dòng)機(jī) PAGEREF _Toc315076733 h 6 HYPERLINK l _Toc315076734 3.11正規(guī)文法到有限自動(dòng)機(jī)的等價(jià)性證明 PAGEREF _Toc315076734 h 6 HYPERLINK l _Toc315076735 3.12 正規(guī)文法到有限自動(dòng)機(jī)的構(gòu)造方法 PAGEREF _Toc315076735

5、h 8 HYPERLINK l _Toc315076736 3.2從有限自動(dòng)機(jī)到正規(guī)文法 PAGEREF _Toc315076736 h 8 HYPERLINK l _Toc315076737 3.21 有限自動(dòng)機(jī)到正規(guī)文法的等價(jià)性證明 PAGEREF _Toc315076737 h 8 HYPERLINK l _Toc315076738 3.22 有限自動(dòng)機(jī)到正規(guī)文法的構(gòu)造方法 PAGEREF _Toc315076738 h 9 HYPERLINK l _Toc315076739 4代碼編寫 PAGEREF _Toc315076739 h 10 HYPERLINK l _Toc3150767

6、40 5運(yùn)行與測試 PAGEREF _Toc315076740 h 141課題綜述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)化；1.2設(shè)計(jì)內(nèi)容使用Visual C+/Visual C#等工具，設(shè)計(jì)軟件MySoft_3，可以實(shí)現(xiàn)以下功能：1.根據(jù)用戶輸入的文本文件（*.txt）的名稱，打開文件，并從文件中獲取文法的產(chǎn)生式、非終結(jié)符、終結(jié)符、開始符等基本信息；2.判斷該文法是否為正規(guī)文法，若是，則將其轉(zhuǎn)化為有限自動(dòng)機(jī)；3.根據(jù)用戶輸入的文本文件（*.txt

7、）的名稱，打開文件，并從文件中獲取有限自動(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)造一個(gè)有窮自動(dòng)機(jī)NFA M；使得L(M)=L(G)：（1）M的字母表與G的終結(jié)符相同；（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ù)

8、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=x*y （x*代表x從1到無窮多個(gè)）A-x,A-y 則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，f，So，Z）1.S為一個(gè)有限狀態(tài)集合2.是一個(gè)字母表，它所包含的的每個(gè)元素稱為一個(gè)輸入字符；3.f是一個(gè)

9、從SX（笛卡爾乘積）至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.SoS，是唯一的初態(tài)；5.ZS，是一個(gè)終態(tài)集。NFA（NondeterministicFiniteAutomata）：不確定的有限自動(dòng)機(jī)如果理解了有限自動(dòng)機(jī)，則無限自動(dòng)機(jī)和它的區(qū)別就是上面的第四項(xiàng)。SoS，它的初態(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)集

10、合可以稱為這個(gè)有限狀態(tài)集合n個(gè)子集。按0,1,2的順序編號(hào)。4.因?yàn)檫@些子集之間的關(guān)系是輸入一個(gè)確定值確定的，所以這些子集之間存在一些關(guān)系，即把這些子集的關(guān)系寫出來完成NFA向DFA的轉(zhuǎn)換。如果不懂可以從網(wǎng)上找一個(gè)例子進(jìn)行理解。2.4正規(guī)式與有限自動(dòng)機(jī)之間的轉(zhuǎn)換任意的正規(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è)

11、右線性文法GR=（VT,VN,S,P），將VN中每個(gè)非終結(jié)符視為狀態(tài)符號(hào)，并增加一個(gè)新的終止符號(hào)f，（f VN）。令M=(VN f，VT，d，S，f)，其中狀態(tài)轉(zhuǎn)換函數(shù)d由以下規(guī)則定義：若對某個(gè)A VN及a VT ，P中有產(chǎn)生式Aa，則令d(A，a)=f；對任意的A VN及a VT ，設(shè)P中左端為A右端第一個(gè)符號(hào)為a的所有產(chǎn)生式為AaA1aA2aAk（不包括Aa），則令d(A，a)= A1，A2，Ak。顯然上述得到的M為一個(gè)NFA。到此，已說明存在一個(gè)FAM與該右線性文法對應(yīng)，下面說明它們的等價(jià)性(L(GR)=L(M) )。對右線性正規(guī)文法GR，在S W的最左推導(dǎo)過程中，利用AaB一次就相當(dāng)于

12、在M中從狀態(tài)A出發(fā)經(jīng)標(biāo)記為a的箭弧到達(dá)狀態(tài)B(包括a=的情形)。在推導(dǎo)過程的最后，利用Aa一次則相當(dāng)于在中從狀態(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)記符號(hào)依次連接起來恰好等于W，這就是說，W L(GR)當(dāng)且僅當(dāng)W L(M)，故L(GR)=L(M)。2. 設(shè)左線性文法GL=（VT,VN,S,P），將VN中每個(gè)非終結(jié)符視為狀態(tài)符號(hào)，并增加一個(gè)新的初始狀態(tài)符號(hào)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)

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

14、到狀態(tài)S有一條通路，其上所有箭弧的標(biāo)記符號(hào)依次連接起來恰好等于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=( VN f，VT，d，S，f)的方法如下：將VN中每個(gè)符號(hào)視為一個(gè)狀態(tài)符號(hào)，增加一個(gè)新的終態(tài)符號(hào)f，f VN；對于產(chǎn)生式Aa（a VT ），則構(gòu)造d(A，a)=f；對于產(chǎn)生式AaA1（a VT ），則構(gòu)造d(A，a)= A1。從左線性正規(guī)文法GL=(VT,VN,S,P)構(gòu)造有

15、限自動(dòng)機(jī)M=( VN q，VT，d，q，S)的方法如下：將VN中每個(gè)符號(hào)視為一個(gè)狀態(tài)符號(hào)，增加一個(gè)新的初態(tài)符號(hào)q，q VN；對于產(chǎn)生式Aa（a VT ），則構(gòu)造d(q，a)=A；對于產(chǎn)生式A1Aa（a VT ），則構(gòu)造d(A，a)= A1。3.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，d，S0，F(xiàn))，分以下兩種情況進(jìn)行證明：（1）若S0 F，則令GR=(,S, S0, P)，其中P是由以下規(guī)則定義的產(chǎn)生式集合，對任何a 及A,B S，若d(A，a)=B，

16、則：當(dāng)B F時(shí)，令A(yù)aB；當(dāng)B F時(shí)，令A(yù)aBa；顯然，上述得到的文法為一個(gè)右線性正規(guī)文法，下面說明它們的等價(jià)性(L(M)=L(GR) )。在DFAM中，對任何w *，不妨設(shè)w=a1a2ak，其中ai (i=1,2,k)，若S W，則存在一個(gè)最左推導(dǎo)：S0 a1A1 a1a2A2 a1aiAi 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)=L(GR)。（2）若S0 F，因?yàn)閐(S0,)= S0，所以 L(M)，但上面構(gòu)造的L(GR)中

17、不含。因此，需在文法中添加產(chǎn)生式S0，這樣，就有L(M)=L(GR)。2. 設(shè)DFAM=(S，d，S0，F(xiàn))，分以下兩種情況進(jìn)行證明：（1）若S0 F，則令GL=(,S, X, P)，其中X F，P是由以下規(guī)則定義的產(chǎn)生式集合，對任何a 及A,B S，若d(A，a)=B，則：當(dāng)AS0時(shí)，令BAa；當(dāng)A=S0時(shí)，令BaAa；顯然，上述得到的文法為一個(gè)左線性正規(guī)文法，下面說明它們的等價(jià)性(L(M)=L(GL) )。在DFAM中，對任何w *，不妨設(shè)w=a1a2ak，其中ai (i=1,2,k)，若存在一條從S0到X的通路，通路上所有箭弧的標(biāo)記依次為a1，ak，則在GL中一定存在一個(gè)最左推導(dǎo)：X A

18、kak Ak-1ak-1ak A2a2ak a1ak，即w L(GL)。反之亦然。所以，w L(GL)當(dāng)且僅當(dāng)w L(M)，故L(M)=L(GL)。（2）若S0 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，d，S0，F(xiàn))構(gòu)造右線性正規(guī)文法GR的方法如下：令GR=(,S, S0，P)，其中P是由以下規(guī)則定義的產(chǎn)生式集合：對任何d(A，a)=B,若B F，則令A(yù)aB；若B F，并且B狀態(tài)

19、有箭弧射出，則令A(yù)aBa；若B F，并且B狀態(tài)沒有箭弧射出，則令A(yù)a；若S0 F，則令S0。從有限自動(dòng)機(jī)M=( S，d，S0，F(xiàn))構(gòu)造左線性正規(guī)文法GL的方法如下：令GL=(,S, X，P)，其中P是由以下規(guī)則定義的產(chǎn)生式集合：對任何d(A，a)=B,若A不是初始狀態(tài)，則令BAa；若A是初始狀態(tài)，并且A狀態(tài)有箭弧射入，則令BAaa；若A是初始狀態(tài)，并且A狀態(tài)沒有箭弧射入，則令Ba；若S0 F，則令X。4代碼編寫#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_fin

20、al_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 stati1 + 1;n_final_stat = n - n_midd_stat - 1;cout 最后分別輸入終態(tài)： endl;for(int i2 = 0; i2 statn_midd_stat + 1 + i2;cout m;char* terminal = new charm;cout 請分別輸入終

21、結(jié)符： endl;for(int i3 = 0; i3 terminali3;cout endl;/構(gòu)造自動(dòng)機(jī)int i, j,k;char* f = new char*n;for(k=0;kn;k+)fk=new charn;cout 構(gòu)造自動(dòng)機(jī)： endl;for(i = 0; i n; i+)for(j = 0; j n; j+)cout 狀態(tài) stati 能否直接推出狀態(tài) statj;if(i = 0) & (j = 0)cout ? (若能則輸入相應(yīng)的終結(jié)符，否則輸入0);elsecout fij;cout endl;/轉(zhuǎn)換成對應(yīng)的文法cout 由此自動(dòng)機(jī)轉(zhuǎn)換成的對應(yīng)的文法為： en

22、dl;cout G=(;/ stat0;for(int i4 = 0; i4 n; i4+)if(i4 != 0)cout ,;cout stati4;cout ,;cout ;for(int i5 = 0; i5 m; i5+)if(i5 != 0)cout ,;cout terminali5;cout ,;cout P,;cout stat0 ),;cout 其中P為： endl;for(i = 0; i n; i+)for(j = 0; j n; j+)if(fij != 0)cout stati fij statj for(int i6 = 0; i6 n_final_stat; i6

23、+)cout statn_midd_stat + 1 + i6 endl;return 0;5運(yùn)行與測試 測試程序使用的自動(dòng)機(jī)用例：開始狀態(tài)：A；中間狀態(tài)：1個(gè)，為B；終態(tài)：2個(gè)，分別為C、D；終結(jié)符：2個(gè)，分別為a、b；裝換關(guān)系為StatABCDA0a0bB00b0Ca00bD0b0b（6）得到的結(jié)果如圖：總結(jié)經(jīng)過一周的努力，終于把編譯原理這門課的課程設(shè)計(jì)做完了，由于學(xué)習(xí)理論的時(shí)候總是感覺這門課程特別的復(fù)雜，有許多繁瑣的東西，起初以為課程設(shè)計(jì)的內(nèi)容會(huì)更加的復(fù)雜，后來認(rèn)真看了題目，和相對應(yīng)于課本上的內(nèi)容，我的這個(gè)題目還真的很簡單，只是用到了“數(shù)組”、“圖”這兩個(gè)數(shù)據(jù)結(jié)構(gòu)，再就是有兩個(gè)二層嵌套的

24、循環(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í)具有一定的檢測和指導(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è)完整編譯器的冰山一角。后面還有更多需要我們更加需要懂得的東西。致謝歷時(shí)將近一個(gè)月的時(shí)間終于將研究做完，在做課題過程中遇到了無數(shù)的困難和障礙，都在