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

2、(G)=L(M),則稱G和M是等價的。關鍵詞：正規文法；有限自動機；等價性；構造方法目錄1課題綜述31.1目的31.2設計內容31.3設計原則42系統分析42.1正規式42.2有限自動機（有窮自動機）52.3NFA向DFA的轉換52.4正規式與有限自動機之間的轉換63系統設計63.1從正規文法到有限自動機63.11正規文法到有限自動機的等價性證明63.12 正規文法到有限自動機的構造方法83.2從有限自動機到正規文法83.21 有限自動機到正規文法的等價性證明83.22 有限自動機到正規文法的構造方法94代碼編寫105運行與測試141課題綜述1.1目的1.理解正規文法與有限自動機（FA）的本質

3、聯系；2.掌握正規文法與有限自動機之間相互轉化的算法原理；3.學會使用Visual C+等編程工具實現正規文法與有限自動機之間的相互轉化；1.2設計內容使用Visual C+/Visual C*等工具，設計軟件MySoft_3，可以實現以下功能：1.根據用戶輸入的文本文件（*.txt）的名稱，打開文件，并從文件中獲取文法的產生式、非終結符、終結符、開始符等基本信息；2.判斷該文法是否為正規文法，若是，則將其轉化為有限自動機；3.根據用戶輸入的文本文件（*.txt）的名稱，打開文件，并從文件中獲取有限自動機的狀態集、字母表、初態、終態集、轉移函數等基本信息；4.判斷該自動機是否合法，若合法，則將

4、其轉化為正規文法；1.3設計原則正規文法與有窮自動機有著特殊的關系，采用下面的規則可從正規文法G直接構造一個有窮自動機NFA M；使得L(M)=L(G)：（1）M的字母表與G的終結符相同；（2）為G中的每一個非終結符生成M的一個狀態，G的開始符S是開始狀態；（3）增加一個新狀態Z，作為NFA的終態；（4）對G中的形如A->tB的規則（其中T為終結符或，A為非終結符的產生式），構造M的一個轉換函數f(A,t)=B；（5）對G中形如A->t的產生式，構造M的一個轉換函數f（A，t）=Z。2系統分析2.1正規式正規式：正則表達式，表示正規集的工具。一個正規式對應一個正規文法（3型文法）之

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

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

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

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

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

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

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

12、)構造有限自動機M=( VN q，VT，d，q，S)的方法如下：將VN中每個符號視為一個狀態符號，增加一個新的初態符號q，q VN；對于產生式Aa（a VT ），則構造d(q，a)=A；對于產生式A1Aa（a VT ），則構造d(A，a)= A1。3.2從有限自動機到正規文法3.21 有限自動機到正規文法的等價性證明定理2：對于每一個有限自動機M，都存在一個右線性正規文法GR和左線性正規文法GL與之等價。證明：1.設DFAM=(S，d，S0，F)，分以下兩種情況進行證明：（1）若S0 F，則令GR=(,S, S0, P)，其中P是由以下規則定義的產生式集合，對任何a 及A,B S，若d(A，a

13、)=B，則：當B F時，令AaB；當B F時，令AaBa；顯然，上述得到的文法為一個右線性正規文法，下面說明它們的等價性(L(M)=L(GR) )。在DFAM中，對任何w *，不妨設w=a1a2ak，其中ai (i=1,2,k)，若S W，則存在一個最左推導：S0 a1A1 a1a2A2 a1aiAi a1aiai+1Ai+1 a1ak，因而，在M中存在一條從S0出發一次經過A1，Ak-1到達終態的通路，該通路上所有箭弧的標記依次為a1，ak。反之亦然。所以，w L(GR)當且僅當w L(M)，故L(M)=L(GR)。（2）若S0 F，因為d(S0,)= S0，所以 L(M)，但上面構造的L(

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

15、：X Akak Ak-1ak-1ak A2a2ak a1ak，即w L(GL)。反之亦然。所以，w L(GL)當且僅當w L(M)，故L(M)=L(GL)。（2）若S0 F，則 L(M)，但上面構造的L(GL)中不含。因此，需在文法中添加產生式X，這樣，就有L(M)=L(GL)。3.22 有限自動機到正規文法的構造方法上述定理的證明采用了構造性的證明方法，由此可以得出由有限自動機到正規文法的構造方法。從有限自動機M=( S，d，S0，F)構造右線性正規文法GR的方法如下：令GR=(,S, S0，P)，其中P是由以下規則定義的產生式集合：對任何d(A，a)=B,若B F，則令AaB；若B F，并

16、且B狀態有箭弧射出，則令AaBa；若B F，并且B狀態沒有箭弧射出，則令Aa；若S0 F，則令S0。從有限自動機M=( S，d，S0，F)構造左線性正規文法GL的方法如下：令GL=(,S, X，P)，其中P是由以下規則定義的產生式集合：對任何d(A，a)=B,若A不是初始狀態，則令BAa；若A是初始狀態，并且A狀態有箭弧射入，則令BAaa；若A是初始狀態，并且A狀態沒有箭弧射入，則令Ba；若S0 F，則令X。4代碼編寫*include<iostream>using namespace std;int main()int n, m;/n為自動機狀態的總數目/m為自動機終結符的數目in

17、t n_midd_stat, n_final_stat;/n_midd_stat為中間狀態的數目/n_final_stat為終態的數目cout << "請輸入自動機共有的狀態數目："cin >> n;char* stat = new charn;cout << "請輸入開始狀態："cin >> stat0;cout << "請輸入中間狀態的個數："cin >> n_midd_stat;cout << "請輸入分別中間狀態：" <

18、;< endl;for(int i1 = 0; i1 < n_midd_stat; i1+)cin >> stati1 + 1;n_final_stat = n - n_midd_stat - 1;cout << "最后分別輸入終態：" << endl;for(int i2 = 0; i2 < n_final_stat; i2+)cin >> statn_midd_stat + 1 + i2;cout << "請輸入終結符的數目："cin >> m;char* te

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

20、 n; j+)cout << "狀態" << stati << "能否直接推出狀態"<< statj;if(i = 0) && (j = 0)cout << " (若能則輸入相應的終結符，否則輸入"0")"elsecout << ""cin >> fij;cout << endl;/轉換成對應的文法cout << "由此自動機轉換成的對應的文法為：" &

21、lt;< 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 <<terminali5;cout &

22、lt;< ","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 <<endl;/輸出可

23、接受狀態增加的產生式，例如A->for(int i6 = 0; i6 < n_final_stat; i6+)cout << statn_midd_stat + 1 + i6 << "->" << endl;return 0;5運行與測試 測試程序使用的自動機用例：開始狀態：A；中間狀態：1個，為B；終態：2個，分別為C、D；終結符：2個，分別為a、b；裝換關系為StatABCDA0a0bB00b0Ca00bD0b0b（6）得到的結果如圖：總結經過一周的努力，終于把編譯原理這門課的課程設計做完了，由于學習理論的時候總是感

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