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

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

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

3、表示出來了。此外，由子集法的步驟可見， 集合(set)這一結(jié)構(gòu)應(yīng)該使用，set結(jié)構(gòu)符合我們數(shù)學(xué)的集合要求， 不含相同元素，并且兩個(gè)集合間還可以進(jìn)行比較是否相等，十分有利于我們的程序?qū)崿F(xiàn)。表示FA的結(jié)構(gòu)：/Triad（三元組）：S 一 aB 即（S,a,B） struct Triadchar start;char edge;char end;集合與棧使用庫里面的標(biāo)準(zhǔn)集合、棧。即包含頭文件set、stack（2）文件結(jié)構(gòu)其中有程序不是很復(fù)雜，加之使用到的數(shù)據(jù)結(jié)構(gòu)是標(biāo)準(zhǔn)庫里的，文件只有一個(gè)N2D.cpp,#include<set> 和 #include<starck> 。（3

4、）程序基本框架概覽struct Triad ; int main()初始化工作； determined。;e_closure() move() determined() / FA的基本組成結(jié)構(gòu)確定化求£閉包求集合的x弧轉(zhuǎn)換確定化（4）主要函數(shù)的實(shí)現(xiàn)偽代碼具有簡明扼要的特點(diǎn)，利用偽代碼子來表示程序流程有利于理解和后續(xù)實(shí)現(xiàn)。子集法偽代碼：s0 集合TNFA的開始狀態(tài)e-closure(s0)把T加入到子集簇 C（未標(biāo)記）while (集合U 在C中找到一個(gè)未標(biāo)記的集合 標(biāo)記U;)for（對于隼-種輸入即 a、b）U e-closure(move(T, a)if（U不是C的子集）把U加入到

5、子集簇C（未標(biāo)記）有 T 一 aU 此外，求£的傳遞閉包要利用棧這一數(shù)據(jù)結(jié)構(gòu)做輔助，其偽代碼如下:求e-closure(T)的偽代碼將T中的所有狀態(tài)全都?jí)喝霔、集合Uwhile(S非空兒t 一取棧頂元素；for(每個(gè)從t狀態(tài)能通過空串轉(zhuǎn)換得到的狀態(tài)s)if(s不在U中兒把狀態(tài)s加入U(xiǎn);把狀態(tài)s壓入S;return U; 集合U即為所求的e閉包再在偽代碼的基礎(chǔ)上來編寫這些核心函數(shù)就方便多了，具體代碼如下:set<char> e_closure(set<char> T, Triad G, int N) 求 e 的傳遞閉包一set<char> U =

6、T;/U用來存放 T中元素的e閉包stack<char> S; 輔助棧set<char>:iterator it; /用于集合遍歷的迭代器for (it = U.begin(); it != U.end(); it+) 將 U 中的元素全部壓棧 S.push(*it);chart;while (!S.empty()棧非空t = S.top();/棧頂元素S.pop();for (int i=0;i<N;i+) 查找元素的e閉包 if (Gi.start= t && Gi.edge='*') 找到元素的 e 閉包 U.insert(G

7、i.end);將其放入集合 US.push(Gi.end);將其壓棧 return U;void determined(Triad G, int N, char* input, int n)/確定化函數(shù)的實(shí)現(xiàn)cout<<endl<<"確定后的 DFA:"<<endl;bool markedMAX_NODES;/用于標(biāo)示集合for(int i=0; i<MAX_NODES; i+)markedi=false;set<char> CMAX_NODES;/存放確定化過程中產(chǎn)生的集合char s0=G0.start;set<

8、;char> T0,T1;T0.insert(s0);T1=e_closure(T0, G, N); / 始態(tài)的 £ 閉包C0=T1;i=0;while(!Ci.empty() && markedi=false && i<MAX_NODES) markedi=true;for(int j=0; j<n; j+)if(inputj != '*')set<char> U=e_closure(move(Ci, inputj, G, N), G , N); if(!U.empty() bool inC=false;

9、int k=0;while(!Ck.empty() && k<MAX_NODES) if(U=Ck)inC=true; break;k+;if(!inC)k=0;while(!Ck.empty() && k<MAX_NODES)k+;Ck=U;cout<<i<<" "<<inputj<<k<<endl;i+;/下面求出確定化后的終態(tài)cout<<"終態(tài)為："；i=0;while(!Ci.empty()bool is_final_state=f

10、alse;set<char>:iterator it;for (it = Ci.begin(); it != Ci.end(); it+)if(*it = '#')is_final_state=true;break;if(is_final_state) cout<<i<<","i+;cout<<endl;3 .調(diào)試分析優(yōu)點(diǎn)分析：NFA的輸入只要求輸入邊的條數(shù)即可開始輸入組成FA的基本結(jié)構(gòu)（即三元組），而有多少引起狀態(tài)轉(zhuǎn)換的輸入都交給程序自己去完成，這一點(diǎn)就顯得很簡潔，對于用戶來說也便捷！缺點(diǎn)分析：沒有可視化，整

11、個(gè)程序的輸入輸出是通過控制臺(tái)完成的。解決辦法：可合適的使用 MFC可視化編程完成（這個(gè)有余力可以考慮一下）。4 .用戶手冊該程序的使用十分簡單，直接按要求輸入相應(yīng)數(shù)據(jù)就是。5 .測試數(shù)據(jù)及測試結(jié)果課本P59例4.8 :6 .總結(jié)優(yōu)點(diǎn)通過這次的實(shí)習(xí)，對編譯原理NFA、DFA及之間的等價(jià)轉(zhuǎn)換有了更加深刻的理解，也學(xué)會(huì)了利用偽代碼來設(shè)計(jì)程序，由框架到細(xì)節(jié)的實(shí)現(xiàn)，這種設(shè)計(jì)相當(dāng)便利高效。團(tuán)隊(duì)成員之間交流思想取長 補(bǔ)短也讓我學(xué)到了好多思想和方法。7 .源代碼#include<set>#include<stack>#include<iostream>using names

12、pace std;/Triad(三元組)：S f aB 即(S,a,B)struct Triadchar start;char edge;char end;set<char> e_closure(set<char>, Triad, int);set<char> move(set<char>, char, Triad口，int);void determined(Triad , int, char*, int);const int MAX_NODES=20;int main()int N;cout<<"請輸入邊數(shù)："&

13、lt;<endl;cin>>N;Triad* G=new TriadN;cout<<"請輸入正規(guī)文法(*代表£ ,#代表終態(tài)，約定輸入時(shí)先輸入以始態(tài)開始的三元組):"<<endl;for(int i=0; i<N; i+)cin>>Gi.start>>Gi.edge>>Gi.end;set<char> Edge;for(int j=0; j<N; j+)Edge.insert(Gj.edge);int n=Edge.size();char* input=new c

14、harn;set<char>:iterator it;j=0;for (it = Edge.begin(); it != Edge.end(); it+)inputj=*it;j+;determined© N, input, n);return 0; set<char> e_closure(set<char> T, Triad G口，int N) set<char> U = T;stack<char> S;set<char>:iterator it;for (it = U.begin(); it != U.end

15、(); it+)S.push(*it);chart;while (!S.empty()t = S.top();S.pop();for (int i=0;i<N;i+)if (Gi.start= t && Gi.edge='*')U.insert(Gi.end);S.push(Gi.end);return U;set<char> move(set<char> I, char a, Triad G, int N) set<char> U;set<char>:iterator it;for (it = I.begi

16、n(); it != I.end(); it+)for(int i=0; i<N; i+)if (Gi.start= *it && Gi.edge=a)U.insert(Gi.end);return U;void determined(Triad G, int N, char* input, int n) cout<<endl<<"確定后的 DFA:"<<endl;bool markedMAX_NODES;for(int i=0; i<MAX_NODES; i+) markedi=false;set<ch

17、ar> CMAX_NODES;char s0=G0.start;set<char> T0,T1;T0.insert(s0);T1=e_closure(T0, G, N);C0=T1;i=0;while(!Ci.empty() && markedi=false && i<MAX_NODES) markedi=true;下面被注釋代碼可用于輸出圖中求出來的集合/*set<char>:iterator it;cout<<i<<":"for (it = Ci.begin(); it != C

18、i.end(); it+) cout<<*it<<","cout<<endl;*/for(int j=0; j<n; j+)if(inputj != '*')set<char> U=e_closure(move(Ci, inputj, G , N), G, N); if(!U.empty() bool inC=false;int k=0;while(!Ck.empty() && k<MAX_NODES) if(U=Ck)inC=true;break; k+; if(!inC)k=0;while(!Ck.empty() && k<MAX_NODES) k+;Ck=U;cout<<i<<" "<<inputj<<" "<<k&l