版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領
文檔簡介
1、學 號: 0121204930233課 程 設 計題 目正規(guī)文法G與有窮自動機FA相互轉換學 院計算機科學與技術學院專 業(yè)軟件工程班 級軟件1201姓 名張立煒指導教師何九周2014年12月26日課程設計任務書學生姓名: 張立煒 專業(yè)班級: 軟件1201 指導教師: 何九周 工作單位:計算機科學與技術學院題 目: 正規(guī)文法G與有窮自動機FA相互轉換初始條件:程序設計語言:主要使用C語言的開發(fā)工具,或者采用LEX、YACC等工具,也可利用其他熟悉的開發(fā)工具。算法:可以根據(jù)編譯原理課程所講授的算法進行設計。要求完成的主要任務:(包括課程設計工作量及其技術要求,說明書撰寫等具體要求)1. 明確課程設
2、計的目的和重要性,認真領會課程設計的題目,讀懂課程設計指導書的要求,學會設計的基本方法與步驟,學會如何運用前修知識與收集、歸納相關資料解決具體問題的方法。嚴格要求自己,要獨立思考,按時、獨立完成課程設計任務。2. 主要功能包括:利用算符優(yōu)先分析方法和思想對某些語句進行語法分析與語義分析,生成相應的中間代碼。學會正確運用語法規(guī)則,并能應用所學的方法解決存在的問題。給出語法分析方法及中間代碼形式的描述、文法和屬性文法的設計。3. 進行總體設計,詳細設計:包括算法的設計和數(shù)據(jù)結構設計。系統(tǒng)實施、調試,合理使用出錯處理程序。4. 設計報告:要求層次清楚、整潔規(guī)范、不得相互抄襲。正文字數(shù)不少于0.3萬字
3、。包含內(nèi)容:課程設計的題目。目錄。正文:包括引言、需求分析、總體設計及開發(fā)工具的選擇,設計原則(給出語法分析方法及中間代碼形式的描述、文法和屬性文法的設計),數(shù)據(jù)結構與模塊說明(功能與流程圖)、詳細的算法設計、軟件調試、軟件的測試方法和結果、有關技術的討論、收獲與體會等。結束語。參考文獻。附錄:軟件清單(或者附盤)。時間安排: 消化資料、系統(tǒng)調查、形式描述1天系統(tǒng)分析、總體設計、實施計劃3天撰寫課程設計報告書1天指導教師簽名: 2014年 12月 26日系主任(或責任教師)簽名: 2014年 12月 26日目錄課程設計任務書11引言3 1.1目的31.2設計內(nèi)容31.3設計原則42需求分析42
4、.1正規(guī)式42.2有限自動機(有窮自動機)52.3NFA向DFA的轉換52.4正規(guī)式與有限自動機之間的轉換63數(shù)據(jù)結構和模塊說明63.1從正規(guī)文法到有限自動機63.11正規(guī)文法到有限自動機的等價性證明63.12 正規(guī)文法到有限自動機的構造方法83.2從有限自動機到正規(guī)文法83.21 有限自動機到正規(guī)文法的等價性證明83.22 有限自動機到正規(guī)文法的構造方法94詳細設計105軟件測試和結果146收獲與體會.157結束語.168參考文獻.171引言1.1目的1.理解正規(guī)文法與有限自動機(FA)的本質聯(lián)系;2.掌握正規(guī)文法與有限自動機之間相互轉化的算法原理;3.學會使用Visual C+等編程工具實
5、現(xiàn)正規(guī)文法與有限自動機之間的相互轉化;1.2設計內(nèi)容使用Visual C+/Visual C#等工具,設計軟件MySoft_3,可以實現(xiàn)以下功能:1.根據(jù)用戶輸入的文本文件(*.txt)的名稱,打開文件,并從文件中獲取文法的產(chǎn)生式、非終結符、終結符、開始符等基本信息;2.判斷該文法是否為正規(guī)文法,若是,則將其轉化為有限自動機;3.根據(jù)用戶輸入的文本文件(*.txt)的名稱,打開文件,并從文件中獲取有限自動機的狀態(tài)集、字母表、初態(tài)、終態(tài)集、轉移函數(shù)等基本信息;4.判斷該自動機是否合法,若合法,則將其轉化為正規(guī)文法;1.3設計原則正規(guī)文法與有窮自動機有著特殊的關系,采用下面的規(guī)則可從正規(guī)文法G直接
6、構造一個有窮自動機NFA M;使得L(M)=L(G):(1)M的字母表與G的終結符相同;(2)為G中的每一個非終結符生成M的一個狀態(tài),G的開始符S是開始狀態(tài);(3)增加一個新狀態(tài)Z,作為NFA的終態(tài);(4)對G中的形如A->tB的規(guī)則(其中T為終結符或,A為非終結符的產(chǎn)生式),構造M的一個轉換函數(shù)f(A,t)=B;(5)對G中形如A->t的產(chǎn)生式,構造M的一個轉換函數(shù)f(A,t)=Z。2需求分析2.1正規(guī)式正規(guī)式:正則表達式,表示正規(guī)集的工具。一個正規(guī)式對應一個正規(guī)文法(3型文法)之間能夠進行準換三個基本規(guī)則:A->xB,B->y 則 A=xy。A->
7、xA|y 則A=x*y (x*代表x從1到無窮多個)A->x,A->y 則A=x|y正規(guī)式主要用到了遞歸的思想,無論遇到多復雜的正規(guī)式都可以拆分成上面這三種形式,然后進行解題。2.2有限自動機(有窮自動機)DFA(Deterministic Finite Automation ):確定的有限自動機表達式:M=(S,f,So,Z)1.S為一個有限狀態(tài)集合2.是一個字母表,它所包含的的每個元素稱為一個輸入字符;3.f是一個從SX(笛卡爾乘積)至S的單值部分映射。f(S,a)=s'意味著當現(xiàn)在的狀態(tài)為s,輸入字符a時,將轉換到下一狀態(tài)s'.s
8、9;為s的一個后繼狀態(tài)。4.SoS,是唯一的初態(tài);5.ZS,是一個終態(tài)集。NFA(Nondeterministic Finite Automata):不確定的有限自動機如果理解了有限自動機,則無限自動機和它的區(qū)別就是上面的第四項。SoS,它的初態(tài)不是唯一的,而是一個集合。2.3NFA向DFA的轉換這個轉換是一個比較簡單的過程。1.如果有一個不確定的有限自動機,則可以轉化為圖的方式。此處不詳述怎樣轉圖的方式。2.先將初態(tài)確定,然后根據(jù)輸入的每個元素可以得到哪些狀態(tài),依次列表。3.這些狀態(tài)集合可以稱為這個有限狀態(tài)集合n個子集。按0,1,2的順序編號。4.因為這些子集之間的關系是
9、輸入一個確定值確定的,所以這些子集之間存在一些關系,即把這些子集的關系寫出來完成NFA向DFA的轉換。如果不懂可以從網(wǎng)上找一個例子進行理解。2.4正規(guī)式與有限自動機之間的轉換任意的正規(guī)式都可以轉換為上述三種的表現(xiàn)形式。在一個有限自動機轉換為正規(guī)式時,就是考慮從初態(tài)到終態(tài)可以輸入哪些數(shù)據(jù)到達。而這些數(shù)據(jù)可以用哪種正規(guī)式概括進來。3設計原則 3.1從正規(guī)文法到有限自動機 3.11正規(guī)文法到有限自動機的等價性證明定理1:對于每一個右線性正規(guī)文法GR和左線性正規(guī)文法GL,都存在一個有限自動機M與之等價。證明:1.設右線性文法GR=(VT,VN,S,P),將VN中每個非終結符視為狀態(tài)符號,并增加一個新的
10、終止符號f,(f VN)。令M=(VN f,VT,d,S,f),其中狀態(tài)轉換函數(shù)d由以下規(guī)則定義:若對某個A VN及a VT ,P中有產(chǎn)生式Aa,則令d(A,a)=f;對任意的A VN及a VT ,設P中左端為A右端第一個符號為a的所有產(chǎn)生式為AaA1aA2aAk(不包括Aa),則令d(A,a)= A1,A2,Ak。顯然上述得到的M為一個NFA。到此,已說明存在一個FAM與該右線性文法對應,下面說明它們的等價性(L(GR)=L(M) )。對右線性正規(guī)文法GR,在S W的最左推導過程中,利用AaB一次就相當于在M中從狀態(tài)A出發(fā)經(jīng)標記為a的箭弧到達狀態(tài)B(包括a=的情形)。在推導過程的最后,利用A
11、a一次則相當于在中從狀態(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. 設左線性文法GL=(VT,VN,S,P),將VN中每個非終結符視為狀態(tài)符號,并增加一個新的初始狀態(tài)符號q,(q VN)。令M=(VN q,VT,d,q,S),其中狀態(tài)轉換函數(shù)d由以下規(guī)則定義:若對某個A VN及a VT ,P中有產(chǎn)生式Aa,則令d(q,a)=A;對任意的A VN及a VT ,設P中所有右端第一個符號為
12、A,第二個符號為a的所有產(chǎn)生式為A1Aa,A2Aa,AKAa,則令d(A,a)= A1,A2,Ak。顯然上述得到的M為一個NFA。到此,已說明存在一個FAM與該左線性文法對應,下面說明它們的等價性(L(GL)=L(M) )。對左線性正規(guī)文法GL,在S W的最左推導過程中,利用BAa一次就相當于從狀態(tài)A出發(fā)經(jīng)標記為a的箭弧到達狀態(tài)B(包括a=的情形)。在推導的最后,利用Aa一次則相當于在中從狀態(tài)q出發(fā)經(jīng)標記為a的箭弧到達狀態(tài)A(包括a=的情形)。綜上所述,在正規(guī)文法GL中,S W的充要條件是:在M中,從狀態(tài)q到狀態(tài)S有一條通路,其上所有箭弧的標記符號依次連接起來恰好等于W,這就是說,W L(GL
13、)當且僅當W L(M),故L(GL)=L(M)。3.12 正規(guī)文法到有限自動機的構造方法上述定理的證明采用了構造性的證明方法,由此可以得出由正規(guī)文法到有限自動機的構造方法。從右線性正規(guī)文法GR=(VT,VN,S,P)構造有限自動機M=( VN f,VT,d,S,f)的方法如下:將VN中每個符號視為一個狀態(tài)符號,增加一個新的終態(tài)符號f,f VN;對于產(chǎn)生式Aa(a VT ),則構造d(A,a)=f;對于產(chǎn)生式AaA1(a VT ),則構造d(A,a)= A1。從左線性正規(guī)文法GL=(VT,VN,S,P)構造有限自動機M=( VN q,VT,d,q,S)的方法如下:將VN中每個符號視為一個狀態(tài)符號
14、,增加一個新的初態(tài)符號q,q VN;對于產(chǎn)生式Aa(a VT ),則構造d(q,a)=A;對于產(chǎn)生式A1Aa(a VT ),則構造d(A,a)= A1。3.2從有限自動機到正規(guī)文法3.21 有限自動機到正規(guī)文法的等價性證明定理2:對于每一個有限自動機M,都存在一個右線性正規(guī)文法GR和左線性正規(guī)文法GL與之等價。證明:1.設DFAM=(S,d,S0,F(xiàn)),分以下兩種情況進行證明:(1)若S0 F,則令GR=(,S, S0, P),其中P是由以下規(guī)則定義的產(chǎn)生式集合,對任何a 及A,B S,若d(A,a)=B,則:當B F時,令AaB;當B F時,令AaBa;顯然,上述得到的文法為一個右線性正規(guī)文
15、法,下面說明它們的等價性(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出發(fā)一次經(jīng)過A1,Ak-1到達終態(tài)的通路,該通路上所有箭弧的標記依次為a1,ak。反之亦然。所以,w L(GR)當且僅當w L(M),故L(M)=L(GR)。(2)若S0 F,因為d(S0,)= S0,所以 L(M),但上面構造的L(GR)中不含。因此,需在文法中添加產(chǎn)生式S0,這樣,就有L(M)=L(GR)。2. 設DFAM=
16、(S,d,S0,F(xiàn)),分以下兩種情況進行證明:(1)若S0 F,則令GL=(,S, X, P),其中X F,P是由以下規(guī)則定義的產(chǎn)生式集合,對任何a 及A,B S,若d(A,a)=B,則:當AS0時,令BAa;當A=S0時,令BaAa;顯然,上述得到的文法為一個左線性正規(guī)文法,下面說明它們的等價性(L(M)=L(GL) )。在DFAM中,對任何w *,不妨設w=a1a2ak,其中ai (i=1,2,k),若存在一條從S0到X的通路,通路上所有箭弧的標記依次為a1,ak,則在GL中一定存在一個最左推導:X Akak Ak-1ak-1ak A2a2ak a1ak,即w L(GL)。反之亦然。所以,
17、w L(GL)當且僅當w L(M),故L(M)=L(GL)。(2)若S0 F,則 L(M),但上面構造的L(GL)中不含。因此,需在文法中添加產(chǎn)生式X,這樣,就有L(M)=L(GL)。3.22 有限自動機到正規(guī)文法的構造方法上述定理的證明采用了構造性的證明方法,由此可以得出由有限自動機到正規(guī)文法的構造方法。從有限自動機M=( S,d,S0,F(xiàn))構造右線性正規(guī)文法GR的方法如下:令GR=(,S, S0,P),其中P是由以下規(guī)則定義的產(chǎn)生式集合:對任何d(A,a)=B,若B F,則令AaB;若B F,并且B狀態(tài)有箭弧射出,則令AaBa;若B F,并且B狀態(tài)沒有箭弧射出,則令Aa;若S0 F,則令S
18、0。從有限自動機M=( S,d,S0,F(xiàn))構造左線性正規(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詳細算法設計#include<iostream>using namespace std;int main()int n, m;/n為自動機狀態(tài)的總數(shù)目/m為自動機終結符的數(shù)目int n_midd_stat, n_final_stat;/n_midd_stat為中間狀態(tài)的
19、數(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 << "請輸入分別中間狀態(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 << "請輸入終結符的數(shù)目:"cin >> m;char* terminal = new charm;cout << "請分別輸入終結
21、符:" << 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 < n; j+)cout << "狀態(tài)" << s
22、tati << "能否直接推出狀態(tài)"<< statj;if(i = 0) && (j = 0)cout << "? (若能則輸入相應的終結符,否則輸入"0")"elsecout << "?"cin >> fij;cout << endl;/轉換成對應的文法cout << "由此自動機轉換成的對應的文法為:" << 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軟件的測試與結果 測試程序使用的自動機用例:開始狀態(tài):A;中間狀態(tài):1個,為B;終態(tài):2個,分別為C、D;終結符:2個,分別為a、b;裝換關系為StatABCDA0a0bB00b0Ca00bD0b0b 收獲與體會經(jīng)過一個學期的編譯原理相關內(nèi)容的學習和幾周的調試與編寫程序,課程設計的任務終于完成了,在這過程中有出現(xiàn)過各種各樣的問題與學習的不足,感謝傳授我知識的老師和幫我一起調試解決問題的同學。做的過程中有許許
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025土建分包合同書范文
- 2024年物流運輸合同標的貨物運輸服務合同
- 2025年度產(chǎn)業(yè)地產(chǎn)開發(fā)商與物業(yè)產(chǎn)業(yè)配套服務合同協(xié)議3篇
- 2025版區(qū)塊鏈技術應用合同標的智能合約設計與安全審計3篇
- 2025版智能商業(yè)綜合體物業(yè)收購協(xié)議3篇
- 2025年度市場營銷SaaS工具銷售及實施服務合同3篇
- 2025年度辦公樓單間租賃及安全保衛(wèi)服務協(xié)議3篇
- 2024年食品連鎖加盟協(xié)議6篇
- 2025版光伏發(fā)電工程承包合同已備案3篇
- 2024年綠色建筑示范區(qū)土方開挖與回填施工合同3篇
- 線路施工測量-弧垂觀測
- 湖南省印刷業(yè)揮發(fā)性有機物排放標準2017
- 2024年蘇州市軌道交通集團有限公司招聘筆試參考題庫附帶答案詳解
- 2024年1月電大國家開放大學期末試題及答案:農(nóng)村政策法規(guī)
- (高清版)DZT 0261-2014 滑坡崩塌泥石流災害調查規(guī)范(1:50000)
- T-AII 008-2023 深度學習算法框架通用接口規(guī)范
- 計算機類復試面試問題匯總(200多道題)
- 廣東省廣州市番禺區(qū)2023-2024學年九年級上學期期末英語試題【含答案解析】
- 粵教版高中物理必修一課后習題答案(1-4章)
- 云南省紅河哈尼族彝族自治州2022-2023學年高一上學期期末物理試題(解析版)
- 長沙衛(wèi)生職業(yè)學院單招參考試題庫(含答案)
評論
0/150
提交評論