編譯原理報告：NFA轉(zhuǎn)DFA(詳解,附源代碼)

1、v1.0可編輯可修改編譯原理實習報告13*a子萬班級 姓名 日期*2015目錄1 .題目及需求分析 32 .設(shè)計分析33 .調(diào)試分析74 .用戶手冊75 .測試結(jié)果 76 .總結(jié) 77 .源代碼 8題目：NFA轉(zhuǎn)換為等價的DFA實習時間：【問題描述】 以定理“設(shè)L為一個由不確定的有窮自動機接受的集合，則存在一個接受L的確定的有窮自動機”為理論基礎(chǔ)，設(shè)計算法實現(xiàn)將不確定的有窮自動機(NFA)轉(zhuǎn)換為與之等價的確定的有窮自動機(DFA)?！净疽蟆?確定能夠表示FA的合適的結(jié)構(gòu)，以便 FA的輸入和輸出 設(shè)計的算法既要成功實現(xiàn)題目要求的功能，又要高效、魯棒 程序中的函數(shù)、變量等命名要規(guī)則，可讀性要強

2、(易懂)1 .需求分析(1)要將以狀態(tài)轉(zhuǎn)換圖表示的NFA轉(zhuǎn)換為DFA首先應設(shè)計一個結(jié)構(gòu)來表示FA,以便圖形式的FA便于輸入和輸出。(2)設(shè)計合適的算法來實現(xiàn) NFA的確定化，這里用子集法來構(gòu)造等價的DFA 測試數(shù)據(jù)：課本P59例轉(zhuǎn)換前的NFA轉(zhuǎn)換后的DFA2 .設(shè)計(1)數(shù)據(jù)結(jié)構(gòu)設(shè)計由于FA是一個圖，可想到用圖的存儲結(jié)構(gòu)來存儲FA但是，F(xiàn)A中兩個結(jié)點之間的路徑可以不只一條，這讓想考慮用鄰接矩陣來存儲的FA處理起來有點復雜，我采用的是“結(jié)點-邊-結(jié)點” 式的三元組來表示 FA。FA有多少條邊就應該有多少個這樣的三元組，以一個數(shù)組來存放這些三元組，那么一個FA就可以表示出來了。此外，由子集法的步驟

3、可見，集合(set)這一結(jié)構(gòu)應該使用，set結(jié)構(gòu)符合我們數(shù)學的集合要求，不含相同元素，并且兩個集合間還可以進行比較是否相等，十分有利于我們的程序?qū)崿F(xiàn)。表示FA的結(jié)構(gòu):/Triad(三元組)：S 一 aB 即(S,a,B)struct Triadchar start;集合與棧使用庫里面的標準集合、棧。即包含頭文件set、stack(2)文件結(jié)構(gòu)程序不是很復雜，加之使用到的數(shù)據(jù)結(jié)構(gòu)是標準庫里的，文件只有一個，其中有#include和#include。(3)程序基本框架概覽struct Triad ;/FA的基本組成結(jié)構(gòu)int main()初始化工作；determined。；/確定化(4)主要函數(shù)的

4、實現(xiàn)偽代碼具有簡明扼要的特點，利用偽代碼子來表示程序流程有利于理解和后續(xù)實現(xiàn)。子集法偽代碼：s0 - NFA的開始狀態(tài)集合 T e-closure(s0)把T加入到子集簇C(未標記)while ( 集合U - 在C中找到一個未標記的集合)標記U;此外，求e的傳遞閉包要利用棧這一數(shù)據(jù)結(jié)構(gòu)做輔助，其偽代碼如下:/求e-closure(T) 的偽代碼將T中的所有狀態(tài)全都壓入棧S、集合Uwhile(S非空兒t 一取棧頂元素；for( 每個從t狀態(tài)能通過空串轉(zhuǎn)換得到的狀態(tài)s)if(s不在U中兒再在偽代碼的基礎(chǔ)上來編寫這些核心函數(shù)就方便多了，具體代碼如下:set e_closure(set T, Tria

5、d G, int N) tart= t &Gi.edge=*) nd); nd); 將其壓棧return U;void determined(Triad G, int N, char* input, int n) tart;set T0,T1;(s0)；T1=e_closure(T0, G, N); mpty() & markedi=false & iMAX_NODES) markedi=true;for(int j=0; jn; j+)if(inputj != *)set U=e_closure(move(Ci, inputj, G, N), G, N);if(!() bool inC=fa

6、lse;int k=0;while(!Ck.empty() & kMAX_NODES)if(U=Ck)inC=true;break; k+;if(!inC)k=0;3 .調(diào)試分析優(yōu)點分析：NFA的輸入只要求輸入邊的條數(shù)即可開始輸入組成FA的基本結(jié)構(gòu)（即三元組），而有多少引起狀態(tài)轉(zhuǎn)換的輸入都交給程序自己去完成，這一點就顯得很簡潔，對于用戶來說也便捷！缺點分析：沒有可視化，整個程序的輸入輸出是通過控制臺完成的。解決辦法：可合適的使用MFCT視化編程完成（這個有余力可以考慮一下 ）。4 .用戶手冊該程序的使用十分簡單，直接按要求輸入相應數(shù)據(jù)就是。5 .測試數(shù)據(jù)及測試結(jié)果課本P59例：D:Profes

7、ional SoftwareXMicrosoft Vhul StudiQMyProjert5N2DDebugN2D. a 1 回6 .總結(jié)優(yōu)點通過這次的實習，對編譯原理NFA DFA及之間的等價轉(zhuǎn)換有了更加深刻的理解，也學會了利用偽代碼來設(shè)計程序，由框架到細節(jié)的實現(xiàn)，這種設(shè)計相當便利高效。團隊成員之間交流思想取長補 短也讓我學到了好多思想和方法。7 .源代碼#include#include#includeusing namespace std;tartGi.edgeGi.end;set Edge;for(int j=0; jN; j+)(Gj.edge);int n=();char* inpu

8、t=new charn;set:iterato門t;j=0;for (it = (); it != (); it+)inputj=*it;j+;determined N, input, n);return 0;set e_closure(set T, Triad G, int N)set U = T;stack S;set:iterator it;for (it = (); it != (); it+)(*it)；chart;while (!()t =()；()；for (int i=0;iN;i+)if (Gi.start= t & Gi.edge=*)(Gi.end);(Gi.end);r

9、eturn U;set move(set I, char a, Triad G口，int N)set U;set:iterator it;for (it = (); it != (); it+)for(int i=0; iN; i+)if (Gi.start= *it & Gi.edge=a)(Gi.end); return U;void determined(Triad G, int N, char* input, int n) coutendl確定后的 DFA:endl;bool markedMAX_NODES;for(int i=0; iMAX_NODES; i+)markedi=fal

10、se;set CMAX_NODES;char s0=G0.start;set T0,T1;(s0);T1=e_closure(T0, G, N);C0=T1;i=0;while(!Ci.empty() & markedi=false & iMAX_NODES) markedi=true;egin(); it != Ci.end(); it+)cout*it,;coutendl;*/for(int j=0; jn; j+)if(inputj != *)set U=e_closure(move(Ci, inputj, G, N), G, N); if(!() bool inC=false;int k=0;while(!Ck.empty() & kMAX_NODES)if(U=Ck)inC=true;break;k+;if(!inC)k=0;while(!Ck.empty() & kMAX_NODES) k+;Ck=U;couti inputj kendl;i+