武漢理工編譯原理課設(shè)

1、學(xué) 號(hào)： 0121204930233課 程 設(shè) 計(jì)題 目正規(guī)文法G與有窮自動(dòng)機(jī)FA相互轉(zhuǎn)換學(xué) 院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院專 業(yè)軟件工程班 級(jí)軟件1201姓 名張立煒指導(dǎo)教師何九周2014年12月26日課程設(shè)計(jì)任務(wù)書學(xué)生姓名： 張立煒 專業(yè)班級(jí)： 軟件1201 指導(dǎo)教師： 何九周 工作單位：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院題 目: 正規(guī)文法G與有窮自動(dòng)機(jī)FA相互轉(zhuǎn)換初始條件：程序設(shè)計(jì)語(yǔ)言:主要使用C語(yǔ)言的開(kāi)發(fā)工具，或者采用LEX、YACC等工具，也可利用其他熟悉的開(kāi)發(fā)工具。算法：可以根據(jù)編譯原理課程所講授的算法進(jìn)行設(shè)計(jì)。要求完成的主要任務(wù):（包括課程設(shè)計(jì)工作量及其技術(shù)要求，說(shuō)明書撰寫等具體要求）1. 明確課程設(shè)

2、計(jì)的目的和重要性，認(rèn)真領(lǐng)會(huì)課程設(shè)計(jì)的題目，讀懂課程設(shè)計(jì)指導(dǎo)書的要求，學(xué)會(huì)設(shè)計(jì)的基本方法與步驟，學(xué)會(huì)如何運(yùn)用前修知識(shí)與收集、歸納相關(guān)資料解決具體問(wèn)題的方法。嚴(yán)格要求自己，要獨(dú)立思考，按時(shí)、獨(dú)立完成課程設(shè)計(jì)任務(wù)。2. 主要功能包括：利用算符優(yōu)先分析方法和思想對(duì)某些語(yǔ)句進(jìn)行語(yǔ)法分析與語(yǔ)義分析，生成相應(yīng)的中間代碼。學(xué)會(huì)正確運(yùn)用語(yǔ)法規(guī)則，并能應(yīng)用所學(xué)的方法解決存在的問(wèn)題。給出語(yǔ)法分析方法及中間代碼形式的描述、文法和屬性文法的設(shè)計(jì)。3. 進(jìn)行總體設(shè)計(jì)，詳細(xì)設(shè)計(jì)：包括算法的設(shè)計(jì)和數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)。系統(tǒng)實(shí)施、調(diào)試，合理使用出錯(cuò)處理程序。4. 設(shè)計(jì)報(bào)告：要求層次清楚、整潔規(guī)范、不得相互抄襲。正文字?jǐn)?shù)不少于0.3萬(wàn)字

3、。包含內(nèi)容：課程設(shè)計(jì)的題目。目錄。正文：包括引言、需求分析、總體設(shè)計(jì)及開(kāi)發(fā)工具的選擇，設(shè)計(jì)原則（給出語(yǔ)法分析方法及中間代碼形式的描述、文法和屬性文法的設(shè)計(jì)），數(shù)據(jù)結(jié)構(gòu)與模塊說(shuō)明（功能與流程圖）、詳細(xì)的算法設(shè)計(jì)、軟件調(diào)試、軟件的測(cè)試方法和結(jié)果、有關(guān)技術(shù)的討論、收獲與體會(huì)等。結(jié)束語(yǔ)。參考文獻(xiàn)。附錄：軟件清單（或者附盤）。時(shí)間安排： 消化資料、系統(tǒng)調(diào)查、形式描述1天系統(tǒng)分析、總體設(shè)計(jì)、實(shí)施計(jì)劃3天撰寫課程設(shè)計(jì)報(bào)告書1天指導(dǎo)教師簽名： 2014年 12月 26日系主任（或責(zé)任教師）簽名： 2014年 12月 26日目錄課程設(shè)計(jì)任務(wù)書11引言3 1.1目的31.2設(shè)計(jì)內(nèi)容31.3設(shè)計(jì)原則42需求分析42

4、.1正規(guī)式42.2有限自動(dòng)機(jī)（有窮自動(dòng)機(jī)）52.3NFA向DFA的轉(zhuǎn)換52.4正規(guī)式與有限自動(dòng)機(jī)之間的轉(zhuǎn)換63數(shù)據(jù)結(jié)構(gòu)和模塊說(shuō)明63.1從正規(guī)文法到有限自動(dòng)機(jī)63.11正規(guī)文法到有限自動(dòng)機(jī)的等價(jià)性證明63.12 正規(guī)文法到有限自動(dòng)機(jī)的構(gòu)造方法83.2從有限自動(dòng)機(jī)到正規(guī)文法83.21 有限自動(dòng)機(jī)到正規(guī)文法的等價(jià)性證明83.22 有限自動(dòng)機(jī)到正規(guī)文法的構(gòu)造方法94詳細(xì)設(shè)計(jì)105軟件測(cè)試和結(jié)果146收獲與體會(huì).157結(jié)束語(yǔ).168參考文獻(xiàn).171引言1.1目的1.理解正規(guī)文法與有限自動(dòng)機(jī)（FA）的本質(zhì)聯(lián)系；2.掌握正規(guī)文法與有限自動(dòng)機(jī)之間相互轉(zhuǎn)化的算法原理；3.學(xué)會(huì)使用Visual C+等編程工具實(shí)

5、現(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）的名稱，打開(kāi)文件，并從文件中獲取文法的產(chǎn)生式、非終結(jié)符、終結(jié)符、開(kāi)始符等基本信息；2.判斷該文法是否為正規(guī)文法，若是，則將其轉(zhuǎn)化為有限自動(dòng)機(jī)；3.根據(jù)用戶輸入的文本文件（*.txt）的名稱，打開(kāi)文件，并從文件中獲取有限自動(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直接

6、構(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的開(kāi)始符S是開(kāi)始狀態(tài)；（3）增加一個(gè)新?tīng)顟B(tài)Z，作為NFA的終態(tài)；（4）對(duì)G中的形如A->tB的規(guī)則（其中T為終結(jié)符或，A為非終結(jié)符的產(chǎn)生式），構(gòu)造M的一個(gè)轉(zhuǎn)換函數(shù)f(A,t)=B；（5）對(duì)G中形如A->t的產(chǎn)生式，構(gòu)造M的一個(gè)轉(zhuǎn)換函數(shù)f（A，t）=Z。2需求分析2.1正規(guī)式正規(guī)式：正則表達(dá)式，表示正規(guī)集的工具。一個(gè)正規(guī)式對(duì)應(yīng)一個(gè)正規(guī)文法（3型文法）之間能夠進(jìn)行準(zhǔn)換三個(gè)基本規(guī)則：A->xB,B->y  則 A=xy。A->

7、xA|y  則A=x*y  （x*代表x從1到無(wú)窮多個(gè)）A->x,A->y 則A=x|y正規(guī)式主要用到了遞歸的思想，無(wú)論遇到多復(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è)從SX（笛卡爾乘積）至S的單值部分映射。f（S，a）=s'意味著當(dāng)現(xiàn)在的狀態(tài)為s，輸入字符a時(shí)，將轉(zhuǎn)換到下一狀態(tài)s'.s

8、9;為s的一個(gè)后繼狀態(tài)。4.SoS，是唯一的初態(tài)；5.ZS，是一個(gè)終態(tài)集。NFA（Nondeterministic Finite Automata）：不確定的有限自動(dòng)機(jī)如果理解了有限自動(dòng)機(jī)，則無(wú)限自動(dòng)機(jī)和它的區(qū)別就是上面的第四項(xiàng)。SoS，它的初態(tài)不是唯一的，而是一個(gè)集合。2.3NFA向DFA的轉(zhuǎn)換這個(gè)轉(zhuǎn)換是一個(gè)比較簡(jiǎn)單的過(guò)程。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的順序編號(hào)。4.因?yàn)檫@些子集之間的關(guān)系是

9、輸入一個(gè)確定值確定的，所以這些子集之間存在一些關(guān)系，即把這些子集的關(guān)系寫出來(lái)完成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)來(lái)。3設(shè)計(jì)原則 3.1從正規(guī)文法到有限自動(dòng)機(jī) 3.11正規(guī)文法到有限自動(dòng)機(jī)的等價(jià)性證明定理1：對(duì)于每一個(gè)右線性正規(guī)文法GR和左線性正規(guī)文法GL，都存在一個(gè)有限自動(dòng)機(jī)M與之等價(jià)。證明：1.設(shè)右線性文法GR=（VT,VN,S,P），將VN中每個(gè)非終結(jié)符視為狀態(tài)符號(hào)，并增加一個(gè)新的

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

11、a一次則相當(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)依次連接起來(lái)恰好等于W，這就是說(shuō)，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ī)則定義：若對(duì)某個(gè)A VN及a VT ，P中有產(chǎn)生式Aa，則令d(q，a)=A；對(duì)任意的A VN及a VT ，設(shè)P中所有右端第一個(gè)符號(hào)為

12、A，第二個(gè)符號(hào)為a的所有產(chǎn)生式為A1Aa，A2Aa，AKAa，則令d(A，a)= A1，A2，Ak。顯然上述得到的M為一個(gè)NFA。到此，已說(shuō)明存在一個(gè)FAM與該左線性文法對(duì)應(yīng)，下面說(shuō)明它們的等價(jià)性(L(GL)=L(M) )。對(duì)左線性正規(guī)文法GL，在S W的最左推導(dǎo)過(guò)程中，利用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到狀態(tài)S有一條通路，其上所有箭弧的標(biāo)記符號(hào)依次連接起來(lái)恰好等于W，這就是說(shuō)，W L(GL

13、)當(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；對(duì)于產(chǎn)生式Aa（a VT ），則構(gòu)造d(A，a)=f；對(duì)于產(chǎn)生式AaA1（a VT ），則構(gòu)造d(A，a)= A1。從左線性正規(guī)文法GL=(VT,VN,S,P)構(gòu)造有限自動(dòng)機(jī)M=( VN q，VT，d，q，S)的方法如下：將VN中每個(gè)符號(hào)視為一個(gè)狀態(tài)符號(hào)

14、，增加一個(gè)新的初態(tài)符號(hào)q，q VN；對(duì)于產(chǎn)生式Aa（a VT ），則構(gòu)造d(q，a)=A；對(duì)于產(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：對(duì)于每一個(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)生式集合，對(duì)任何a 及A,B S，若d(A，a)=B，則：當(dāng)B F時(shí)，令A(yù)aB；當(dāng)B F時(shí)，令A(yù)aBa；顯然，上述得到的文法為一個(gè)右線性正規(guī)文

15、法，下面說(shuō)明它們的等價(jià)性(L(M)=L(GR) )。在DFAM中，對(duì)任何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)過(guò)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)中不含。因此，需在文法中添加產(chǎn)生式S0，這樣，就有L(M)=L(GR)。2. 設(shè)DFAM=

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

17、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)生式集合：對(duì)任何d(A，a)=B,若B F，則令A(yù)aB；若B F，并且B狀態(tài)有箭弧射出，則令A(yù)aBa；若B F，并且B狀態(tài)沒(méi)有箭弧射出，則令A(yù)a；若S0 F，則令S

18、0。從有限自動(dòng)機(jī)M=( S，d，S0，F(xiàn))構(gòu)造左線性正規(guī)文法GL的方法如下：令GL=(,S, X，P)，其中P是由以下規(guī)則定義的產(chǎn)生式集合：對(duì)任何d(A，a)=B,若A不是初始狀態(tài)，則令BAa；若A是初始狀態(tài)，并且A狀態(tài)有箭弧射入，則令BAaa；若A是初始狀態(tài)，并且A狀態(tài)沒(méi)有箭弧射入，則令Ba；若S0 F，則令X。4詳細(xì)算法設(shè)計(jì)#include<iostream>using 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)的

19、數(shù)目/n_final_stat為終態(tài)的數(shù)目cout << "請(qǐng)輸入自動(dòng)機(jī)共有的狀態(tài)數(shù)目："cin >> n;char* stat = new charn;cout << "請(qǐng)輸入開(kāi)始狀態(tài)："cin >> stat0;cout << "請(qǐng)輸入中間狀態(tài)的個(gè)數(shù)："cin >> n_midd_stat;cout << "請(qǐng)輸入分別中間狀態(tài)：" << endl;for(int i1 = 0; i1 < n_midd_stat

20、; 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 << "請(qǐng)輸入終結(jié)符的數(shù)目："cin >> m;char* terminal = new charm;cout << "請(qǐng)分別輸入終結(jié)

21、符：" << endl;for(int i3 = 0; i3 < m; i3+)cin >> terminali3;cout << endl;/構(gòu)造自動(dòng)機(jī)int i, j,k;char* f = new char*n;for(k=0;k<n;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)" << s

22、tati << "能否直接推出狀態(tài)"<< statj;if(i = 0) && (j = 0)cout << "? (若能則輸入相應(yīng)的終結(jié)符，否則輸入"0")"elsecout << "?"cin >> fij;cout << endl;/轉(zhuǎn)換成對(duì)應(yīng)的文法cout << "由此自動(dòng)機(jī)轉(zhuǎn)換成的對(duì)應(yīng)的文法為：" << endl;cout << "G=("/&

23、lt;< 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,&

24、quot;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;/輸出可接受狀態(tài)增加的產(chǎn)生式，例如A->for(int i6 = 0; i6 < n

25、_final_stat; i6+)cout << statn_midd_stat + 1 + i6 << "->" << endl;return 0;5軟件的測(cè)試與結(jié)果 測(cè)試程序使用的自動(dòng)機(jī)用例：開(kāi)始狀態(tài)：A；中間狀態(tài)：1個(gè)，為B；終態(tài)：2個(gè)，分別為C、D；終結(jié)符：2個(gè)，分別為a、b；裝換關(guān)系為StatABCDA0a0bB00b0Ca00bD0b0b 收獲與體會(huì)經(jīng)過(guò)一個(gè)學(xué)期的編譯原理相關(guān)內(nèi)容的學(xué)習(xí)和幾周的調(diào)試與編寫程序，課程設(shè)計(jì)的任務(wù)終于完成了，在這過(guò)程中有出現(xiàn)過(guò)各種各樣的問(wèn)題與學(xué)習(xí)的不足，感謝傳授我知識(shí)的老師和幫我一起調(diào)試解決問(wèn)題的同學(xué)。做的過(guò)程中有許許