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

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

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

3、見,集合(set)這一結(jié)構(gòu)應(yīng)該使用,set結(jié)構(gòu)符合我們數(shù)學(xué)的集合要求,不含相同元素,并且兩個集合間還可以進(jìn)行比擬是否相等,十分有利于我們的程序?qū)崿F(xiàn).表示FA的結(jié)構(gòu)：/Triad三元組：S一aB即S,a,BstructTriadcharstart;charedge;charend;文檔大全集合與棧使用庫里面的標(biāo)準(zhǔn)集合、棧.即包含頭文件set、stack轉(zhuǎn)換前的NFA轉(zhuǎn)換后的DFA實用標(biāo)準(zhǔn)文案2文件結(jié)構(gòu)程序不是很復(fù)雜,加之使用到的數(shù)據(jù)結(jié)構(gòu)是標(biāo)準(zhǔn)庫里的,文件只有一個N2D.cpp,#include和#include.3程序根本框架概覽4主要函數(shù)的實現(xiàn)偽代碼具有簡明扼要的特點,利用偽代碼子來表示程序流

4、程有利于理解和后續(xù)實現(xiàn).子集法偽代碼：s0集合TNFA的開始狀態(tài)e-closure(s0)把T參加到子集簇C未標(biāo)記while(集合U在C中找到一個未標(biāo)記的集合標(biāo)記U;)for對于隼-種輸入即a、bUe-closure(move(T,a)ifU不是C的子集把U參加到子集簇C未標(biāo)記有T一aU此外,求的傳遞閉包要利用棧這一數(shù)據(jù)結(jié)構(gòu)做輔助,其偽代碼如下:文檔大全其中有structTriad;intmain()初始化工作；determined.;e_closure()move()determined()/FA的根本組成結(jié)構(gòu)/確定化求閉包求集合的x弧轉(zhuǎn)換/確定化實用標(biāo)準(zhǔn)文案求e-closure(T)的偽代

5、碼將T中的所有狀態(tài)全都壓入棧S、集合Uwhile(S非空兒t一取棧頂元素；for(每個從t狀態(tài)能通過空串轉(zhuǎn)換得到的狀態(tài)s)if(s不在U中)把狀態(tài)s參加U;把狀態(tài)s壓入S;)returnU;集合U即為所求的e閉包再在偽代碼的根底上來編寫這些核心函數(shù)就方便多了,具體代碼如下:sete_closure(setT,TriadG,intN)求e的傳遞閉包一setU=T;/U用來存放T中元素的e閉包stackS;/輔助棧set:iteratorit;/用于集合遍歷的迭代器for(it=U.begin();it!=U.end();it+)將U中的元素全部壓棧S.push(*it);chart;while(

6、!S.empty()棧非空t=S.top();/棧頂元素S.pop();for(inti=0;iN;i+)查找元素的e閉包if(Gi.start=t&Gi.edge=*)/找到元素的e閉包U.insert(Gi.end);將其放入集合US.push(Gi.end);/將其壓棧)returnU;)文檔大全實用標(biāo)準(zhǔn)文案voiddetermined(TriadG,intN,char*input,intn)/確定化函數(shù)的實現(xiàn)coutendl確定后的DFA:endl;boolmarkedMAX_NODES;/用于標(biāo)示集合for(inti=0;iMAX_NODES;i+)markedi=false;set

7、CMAX_NODES;/存放確定化過程中產(chǎn)生的集合chars0=G0.start;setT0,T1;T0.insert(s0);T1=e_closure(T0,G,N);/始態(tài)的閉包C0=T1;i=0;while(!Ci.empty()&markedi=false&iMAX_NODES)markedi=true;for(intj=0;jn;j+)if(inputj!=*)setU=e_closure(move(Ci,inputj,G,N),G,N);if(!U.empty()boolinC=false;intk=0;while(!Ck.empty()&kMAX_NODES)if(U=Ck)in

8、C=true;break;k+;if(!inC)k=0;while(!Ck.empty()&kMAX_NODES)k+;Ck=U;coutiinputjkendl;i+;/下面求出確定化后的終態(tài)cout終態(tài)為：；i=0;while(!Ci.empty()boolis_final_state=false;set:iteratorit;for(it=Ci.begin();it!=Ci.end();it+)if(*it=#)is_final_state=true;break;if(is_final_state)couti,;i+;coutendl;文檔大全實用標(biāo)準(zhǔn)文案3 3.調(diào)試分析優(yōu)點分析：NFA

9、的輸入只要求輸入邊的條數(shù)即可開始輸入組成FA的根本結(jié)構(gòu)即三元組,而有多少引起狀態(tài)轉(zhuǎn)換的輸入都交給程序自己去完成,這一點就顯得很簡潔,對于用戶來說也便捷！缺點分析：沒有可視化,整個程序的輸入輸出是通過限制臺完成的.解決方法：可適宜的使用MFC可視化編程完成這個有余力可以考慮一下.4 4.用戶手冊該程序的使用十分簡單,直接按要求輸入相應(yīng)數(shù)據(jù)就是.5 5.測試數(shù)據(jù)及測試結(jié)果課本P59例4.8:6 6.總結(jié)優(yōu)點通過這次的實習(xí),對編譯原理NFA、DFA及之間的等價轉(zhuǎn)換有了更加深刻的理解,也學(xué)會了利用偽代碼來設(shè)計程序,由框架到細(xì)節(jié)的實現(xiàn),這種設(shè)計相當(dāng)便利高效.團(tuán)隊成員之間交流思想取長補短也讓我學(xué)到了好多思

10、想和方法.文檔大全實用標(biāo)準(zhǔn)文案7 7.源代碼#include#include#includeusingnamespacestd;/Triad(三元組)：SfaB即(S,a,B)structTriadcharstart;charedge;charend;sete_closure(set,Triad,int);setmove(set,char,Triad,int);voiddetermined(Triad,int,char*,int);constintMAX_NODES=20;intmain()intN;cout請輸入邊數(shù):N;Triad*G=newTriadN;cout請輸入正規(guī)文法(*代表,#

11、代表終態(tài),約定輸入時先輸入以始態(tài)開始的三元組):endl;for(inti=0;iGi.startGi.edgeGi.end;setEdge;for(intj=0;jN;j+)Edge.insert(Gj.edge);intn=Edge.size();char*input=newcharn;set:iteratorit;j=0;for(it=Edge.begin();it!=Edge.end();it+)inputj=*it;j+;文檔大全實用標(biāo)準(zhǔn)文案determined(G,N,input,n);return0;)sete_closure(setT,TriadG,intN)(setU=T;s

12、tackS;set:iteratorit;for(it=U.begin();it!=U.end();it+)S.push(*it);chart;while(!S.empty()(t=S.top();S.pop();for(inti=0;iN;i+)(if(Gi.start=t&Gi.edge=*)(U.insert(Gi.end);S.push(Gi.end);)returnU;)setmove(setI,chara,TriadG,intN)setU;set:iteratorit;for(it=I.begin();it!=I.end();it+)for(inti=0;iN;i+)if(Gi.s

13、tart=*it&Gi.edge=a)U.insert(Gi.end);)returnU;文檔大全實用標(biāo)準(zhǔn)文案)voiddetermined(TriadG,intN,char*input,intn)coutendl確定后的DFA:endl;boolmarkedMAX_NODES;for(inti=0;iMAX_NODES;i+)markedi=false;setCMAX_NODES;chars0=G0.start;setT0,T1;T0.insert(s0);T1=e_closure(T0,G,N);C0=T1;i=0;while(!Ci.empty()&markedi=false&iMAX_

14、NODES)markedi=true;下面被注釋代碼可用于輸出圖中求出來的集合/*set:iteratorit;couti:;for(it=Ci.begin();it!=Ci.end();it+)cout*it,;coutendl;*/for(intj=0;jn;j+)if(inputj!=*)setU=e_closure(move(Ci,inputj,G,N),G,N);if(!U.empty()boolinC=false;intk=0;while(!Ck.empty()&kMAX_NODES)if(U=Ck)inC=true;break;)k+;)if(!inC)k=0;文檔大全實用標(biāo)準(zhǔn)文案while(!Ck.empty()&kMAX_NODE