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

1、淮陰工學(xué)院編譯原理課程設(shè)計報告選題名稱: 正規(guī)文法與有限自動機的相互轉(zhuǎn)換系院: 計算機工程學(xué)院專 業(yè):計算機科學(xué)與技術(shù)軟件工程方向班 級: 軟件1082 姓 名: 陳超 學(xué) 號: 1081305202 指導(dǎo)教師: 高麗 王文豪 江波 于永彥學(xué)年學(xué)期: 2021 2021 學(xué)年 第 1 學(xué)期 2012 年 01 月 07 日摘要：正規(guī)文法包括左線性文法和右線性文法。由于正規(guī)文法和正規(guī)表達式在描述語言的能力上是等價的，而正規(guī)表達式和有限自動機在描述語言的能力上也是等價的，因此，正規(guī)文法和有限自動機之間也存在著等價性。通常，對于正規(guī)文法G和有限自動機M，G所定義的語言記作L(G)，M所能識別的語言記

2、作L(M)，如果有L(G)=L(M),那么稱G和M是等價的。 關(guān)鍵詞：正規(guī)文法；有限自動機；等價性；構(gòu)造方法目錄1課題綜述31.1目的31.2設(shè)計內(nèi)容31.3設(shè)計原那么42系統(tǒng)分析42.1正規(guī)式42.2有限自動機有窮自動機52.3NFA向DFA的轉(zhuǎn)換52.4正規(guī)式與有限自動機之間的轉(zhuǎn)換63系統(tǒng)設(shè)計63.1從正規(guī)文法到有限自動機63.11正規(guī)文法到有限自動機的等價性證明63.12 正規(guī)文法到有限自動機的構(gòu)造方法83.2從有限自動機到正規(guī)文法83.21 有限自動機到正規(guī)文法的等價性證明83.22 有限自動機到正規(guī)文法的構(gòu)造方法94代碼編寫105運行與測試141課題綜述1.1目的1.理解正規(guī)文法與有

3、限自動機FA的本質(zhì)聯(lián)系；2.掌握正規(guī)文法與有限自動機之間相互轉(zhuǎn)化的算法原理；3.學(xué)會使用Visual C+等編程工具實現(xiàn)正規(guī)文法與有限自動機之間的相互轉(zhuǎn)化；1.2設(shè)計內(nèi)容使用Visual C+/Visual C#等工具，設(shè)計軟件MySoft_3，可以實現(xiàn)以下功能：1.根據(jù)用戶輸入的文本文件*.txt的名稱，翻開文件，并從文件中獲取文法的產(chǎn)生式、非終結(jié)符、終結(jié)符、開始符等根本信息；2.判斷該文法是否為正規(guī)文法，假設(shè)是，那么將其轉(zhuǎn)化為有限自動機；3.根據(jù)用戶輸入的文本文件*.txt的名稱，翻開文件，并從文件中獲取有限自動機的狀態(tài)集、字母表、初態(tài)、終態(tài)集、轉(zhuǎn)移函數(shù)等根本信息；4.判斷該自動機是否合法

4、，假設(shè)合法，那么將其轉(zhuǎn)化為正規(guī)文法；1.3設(shè)計原那么正規(guī)文法與有窮自動機有著特殊的關(guān)系，采用下面的規(guī)那么可從正規(guī)文法G直接構(gòu)造一個有窮自動機NFA M；使得L(M)=L(G)：1M的字母表與G的終結(jié)符相同；2為G中的每一個非終結(jié)符生成M的一個狀態(tài)，G的開始符S是開始狀態(tài)；3增加一個新狀態(tài)Z，作為NFA的終態(tài)；4對G中的形如A->tB的規(guī)那么其中T為終結(jié)符或，A為非終結(jié)符的產(chǎn)生式，構(gòu)造M的一個轉(zhuǎn)換函數(shù)f(A,t)=B；5對G中形如A->t的產(chǎn)生式，構(gòu)造M的一個轉(zhuǎn)換函數(shù)fA，t=Z。2系統(tǒng)分析2.1正規(guī)式正規(guī)式：正那么表達式，表示正規(guī)集的工具。一個正規(guī)式對應(yīng)一個正規(guī)文法3型文法之間能夠

5、進行準換三個根本規(guī)那么：A->xB,B->y  那么 A=xy。A->xA|y  那么A=x*y  x*代表x從1到無窮多個A->x,A->y 那么A=x|y正規(guī)式主要用到了遞歸的思想，無論遇到多復(fù)雜的正規(guī)式都可以拆分成上面這三種形式，然后進行解題。2.2有限自動機有窮自動機DFADeterministic Finite Automation ：確定的有限自動機表達式：M=S，f，So，Z1.S為一個有限狀態(tài)集合2.是一個字母表，它所包含的的每個元素稱為一個輸入字符；3.f是一個從SX笛卡爾乘積至S的單值局部映射。fS，a=s'

6、;意味著當現(xiàn)在的狀態(tài)為s，輸入字符a時，將轉(zhuǎn)換到下一狀態(tài)s'.s'為s的一個后繼狀態(tài)。4.SoS，是唯一的初態(tài)；5.ZS，是一個終態(tài)集。NFANondeterministic Finite Automata：不確定的有限自動機如果理解了有限自動機，那么無限自動機和它的區(qū)別就是上面的第四項。SoS，它的初態(tài)不是唯一的，而是一個集合。2.3NFA向DFA的轉(zhuǎn)換這個轉(zhuǎn)換是一個比較簡單的過程。1.如果有一個不確定的有限自動機，那么可以轉(zhuǎn)化為圖的方式。此處不詳述怎樣轉(zhuǎn)圖的方式。2.先將初態(tài)確定，然后根據(jù)輸入的每個元素可以得到哪些狀態(tài)，依次列表。3.這些狀態(tài)集合可以稱為

7、這個有限狀態(tài)集合n個子集。按0,1,2的順序編號。4.因為這些子集之間的關(guān)系是輸入一個確定值確定的，所以這些子集之間存在一些關(guān)系，即把這些子集的關(guān)系寫出來完成NFA向DFA的轉(zhuǎn)換。如果不懂可以從網(wǎng)上找一個例子進行理解。2.4正規(guī)式與有限自動機之間的轉(zhuǎn)換任意的正規(guī)式都可以轉(zhuǎn)換為上述三種的表現(xiàn)形式。在一個有限自動機轉(zhuǎn)換為正規(guī)式時，就是考慮從初態(tài)到終態(tài)可以輸入哪些數(shù)據(jù)到達。而這些數(shù)據(jù)可以用哪種正規(guī)式概括進來。3系統(tǒng)設(shè)計 3.1從正規(guī)文法到有限自動機 3.11正規(guī)文法到有限自動機的等價性證明定理1：對于每一個右線性正規(guī)文法GR和左線性正規(guī)文法GL，都存在一個有限自動機M與之等價。證明：1.設(shè)右線性文法

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

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

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

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

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

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

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

15、kak Ak-1ak-1ak A2a2ak a1ak，即w L(GL)。反之亦然。所以，w L(GL)當且僅當w L(M)，故L(M)=L(GL)。2假設(shè)S0 F，那么 L(M)，但上面構(gòu)造的L(GL)中不含。因此，需在文法中添加產(chǎn)生式X，這樣，就有L(M)=L(GL)。3.22 有限自動機到正規(guī)文法的構(gòu)造方法上述定理的證明采用了構(gòu)造性的證明方法，由此可以得出由有限自動機到正規(guī)文法的構(gòu)造方法。從有限自動機M=( S，d，S0，F(xiàn))構(gòu)造右線性正規(guī)文法GR的方法如下：令GR=(,S, S0，P)，其中P是由以下規(guī)那么定義的產(chǎn)生式集合：對任何d(A，a)=B,假設(shè)B F，那么令A(yù)aB；假設(shè)B F，并

16、且B狀態(tài)有箭弧射出，那么令A(yù)aBa；假設(shè)B F，并且B狀態(tài)沒有箭弧射出，那么令A(yù)a；假設(shè)S0 F，那么令S0。從有限自動機M=( S，d，S0，F(xiàn))構(gòu)造左線性正規(guī)文法GL的方法如下：令GL=(,S, X，P)，其中P是由以下規(guī)那么定義的產(chǎn)生式集合：對任何d(A，a)=B,假設(shè)A不是初始狀態(tài)，那么令BAa；假設(shè)A是初始狀態(tài)，并且A狀態(tài)有箭弧射入，那么令BAaa；假設(shè)A是初始狀態(tài)，并且A狀態(tài)沒有箭弧射入，那么令Ba；假設(shè)S0 F，那么令X。4代碼編寫#include<iostream>using namespace std;int main()int n, m;/n為自動機狀態(tài)的總數(shù)目

17、/m為自動機終結(jié)符的數(shù)目int n_midd_stat, n_final_stat;/n_midd_stat為中間狀態(tài)的數(shù)目/n_final_stat為終態(tài)的數(shù)目cout << "請輸入自動機共有的狀態(tài)數(shù)目："cin >> n;char* stat = new charn;cout << "請輸入開始狀態(tài)："cin >> stat0;cout << "請輸入中間狀態(tài)的個數(shù)："cin >> n_midd_stat;cout << "請輸入分別中

18、間狀態(tài)：" << endl;for(int i1 = 0; i1 < n_midd_stat; i1+)cin >> stati1 + 1;n_final_stat = n - n_midd_stat - 1;cout << "最后分別輸入終態(tài)：" << endl;for(int i2 = 0; i2 < n_final_stat; i2+)cin >> statn_midd_stat + 1 + i2;cout << "請輸入終結(jié)符的數(shù)目："cin >&

19、gt; m;char* terminal = new charm;cout << "請分別輸入終結(jié)符：" << endl;for(int i3 = 0; i3 < m; i3+)cin >> terminali3;cout << endl;/構(gòu)造自動機int i, j,k;char* f = new char*n;for(k=0;k<n;k+)fk=new charn;cout << "構(gòu)造自動機：" << endl;for(i = 0; i < n; i+)for

20、(j = 0; j < n; j+)cout << "狀態(tài)" << stati << "能否直接推出狀態(tài)"<< statj;if(i = 0) && (j = 0)cout << "? (假設(shè)能那么輸入相應(yīng)的終結(jié)符，否那么輸入"0")"elsecout << "?"cin >> fij;cout << endl;/轉(zhuǎn)換成對應(yīng)的文法cout << "由此自動機

21、轉(zhuǎn)換成的對應(yīng)的文法為：" << endl;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 <&l

22、t;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 << stat

23、j <<endl;/輸出可接受狀態(tài)增加的產(chǎn)生式，例如A->for(int i6 = 0; i6 < n_final_stat; i6+)cout << statn_midd_stat + 1 + i6 << "->" << endl;return 0;5運行與測試 測試程序使用的自動機用例：開始狀態(tài)：A；中間狀態(tài)：1個，為B；終態(tài)：2個，分別為C、D；終結(jié)符：2個，分別為a、b；裝換關(guān)系為StatABCDA0a0bB00b0Ca00bD0b0b6得到的結(jié)果如圖：總結(jié)經(jīng)過一周的努力，終于把?編譯原理?這門課的課

24、程設(shè)計做完了，由于學(xué)習(xí)理論的時候總是感覺這門課程特別的復(fù)雜，有許多繁瑣的東西，起初以為課程設(shè)計的內(nèi)容會更加的復(fù)雜，后來認真看了題目，和相對應(yīng)于課本上的內(nèi)容，我的這個題目還真的很簡單，只是用到了“數(shù)組、“圖這兩個數(shù)據(jù)結(jié)構(gòu)，再就是有兩個二層嵌套的循環(huán)就能夠應(yīng)對這個題目了。有限自動機用于構(gòu)造詞法分析程序，正規(guī)文法用于構(gòu)造語法分析程序，它們分別是語言的識別工具和定義工具，在構(gòu)造高級程序設(shè)計語言的編譯程序時占有舉足輕重的地位。有限自動機作為語言詞法的識別工具，必須能夠識別由文法定義的所有詞法范疇；而文法作為語言語法的定義工具，也必須有能力定義有限自動機能識別的所有詞法范疇的規(guī)那么。從這一意義上講，有限自動機和正規(guī)文法在描述語言的能力上就存在著等價性，而由這些等價性推導(dǎo)出來的相互轉(zhuǎn)換方法，在構(gòu)造編譯程序時具有一定的檢測和指導(dǎo)作用。由于時間有限，這次的課程設(shè)計中我沒有考慮到不確定的自動機轉(zhuǎn)換成正規(guī)文法的情況，在以后的學(xué)習(xí)中一定將這種更加復(fù)雜的情況考慮進去，讓自己的程序更加的完整。經(jīng)過一學(xué)期的編譯原理這門課程的學(xué)習(xí)，我們深深的了解到了編譯器結(jié)構(gòu)的復(fù)雜程度，更了解了我們學(xué)習(xí)的高級語言的強大功能，我們做的課程設(shè)計只是一個完整編譯器的冰山一角。后面還有更多