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

學(xué)號：******班級：******姓名：******日期：2023目錄題目及需求分析……………3設(shè)計(jì)分析……………………3調(diào)試分析……………………7用戶手冊……………………7測試結(jié)果……………………7總結(jié)…………7源代碼………8題目：NFA轉(zhuǎn)換為等價(jià)的DFA實(shí)習(xí)時(shí)間：【問題描述】以定理“設(shè)L為一個(gè)由不確定的有窮自動機(jī)接受的集合，則存在一個(gè)接受L的確定的有窮自動機(jī)”為理論基礎(chǔ)，設(shè)計(jì)算法實(shí)現(xiàn)將不確定的有窮自動機(jī)(NFA)轉(zhuǎn)換為與之等價(jià)的確定的有窮自動機(jī)(DFA)?！净疽蟆看_定能夠表示FA的合適的結(jié)構(gòu)，以便FA的輸入和輸出設(shè)計(jì)的算法既要成功實(shí)現(xiàn)題目要求的功能，又要高效、魯棒程序中的函數(shù)、變量等命名要規(guī)則，可讀性要強(qiáng)(易懂)需求分析(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。(3)測試數(shù)據(jù):課本P59例4.8轉(zhuǎn)換前的NFA轉(zhuǎn)換后的DFA2．設(shè)計(jì)//Triad(三元組)：S→aB即（S,a,B）//Triad(三元組)：S→aB即（S,a,B）structTriad{charstart;charedge;charend;};集合與棧使用庫里面的標(biāo)準(zhǔn)集合、棧。即包含頭文件set、stack文件結(jié)構(gòu)程序不是很復(fù)雜，加之使用到的數(shù)據(jù)結(jié)構(gòu)是標(biāo)準(zhǔn)庫里的，文件只有一個(gè)N2D.cpp，其中有#include<set>和#include<starck>。程序基本框架概覽structTriad{};//FA的基本組成結(jié)構(gòu)structTriad{};//FA的基本組成結(jié)構(gòu)intmain(){初始化工作；determined();//確定化}e_closure(){}//求ε閉包move(){ }//求集合的x弧轉(zhuǎn)換determined(){}//確定化主要函數(shù)的實(shí)現(xiàn)偽代碼具有簡明扼要的特點(diǎn)，利用偽代碼子來表示程序流程有利于理解和后續(xù)實(shí)現(xiàn)。子集法偽代碼：s0s0←NFA的開始狀態(tài)集合T←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加入到子集簇C(未標(biāo)記)有T→aU}}此外，求ε的傳遞閉包要利用棧這一數(shù)據(jù)結(jié)構(gòu)做輔助，其偽代碼如下：//求e-closure(T)的偽代碼//求e-closure(T)的偽代碼將T中的所有狀態(tài)全都壓入棧S、集合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;}}returnU;//集合U即為所求的ε閉包再在偽代碼的基礎(chǔ)上來編寫這些核心函數(shù)就方便多了，具體代碼如下：set<char>e_closure(set<char>T,TriadG[],intN)set<char>e_closure(set<char>T,TriadG[],intN)//求ε的傳遞閉包{ set<char>U=T;//U用來存放T中元素的ε閉包 stack<char>S;//輔助棧 set<char>::iteratorit;//用于集合遍歷的迭代器 for(it=U.begin();it!=U.end();it++)//將U中的元素全部壓棧 S.push(*it); chart; while(!S.empty())//棧非空 { t=S.top();//棧頂元素 S.pop(); for(inti=0;i<N;i++)//查找元素的ε閉包 { if(G[i].start==t&&G[i].edge=='*')//找到元素的ε閉包 { U.insert(G[i].end);//將其放入集合U S.push(G[i].end);//將其壓棧 } } } returnU;}voiddetermined(TriadG[],intN,char*input,intn){voiddetermined(TriadG[],intN,char*input,intn){//確定化函數(shù)的實(shí)現(xiàn) cout<<endl<<"確定后的DFA:"<<endl; boolmarked[MAX_NODES];//用于標(biāo)示集合 for(inti=0;i<MAX_NODES;i++) marked[i]=false; set<char>C[MAX_NODES];//存放確定化過程中產(chǎn)生的集合 chars0=G[0].start; set<char>T0,T1; T0.insert(s0); T1=e_closure(T0,G,N);//始態(tài)的ε閉包 C[0]=T1; i=0; while(!C[i].empty()&&marked[i]==false&&i<MAX_NODES){ marked[i]=true; for(intj=0;j<n;j++){ if(input[j]!='*'){ set<char>U=e_closure(move(C[i],input[j],G,N),G,N); if(!U.empty()){ boolinC=false; intk=0; while(!C[k].empty()&&k<MAX_NODES){ if(U==C[k]){ inC=true; break; } k++; } if(!inC){ k=0; while(!C[k].empty()&&k<MAX_NODES){ k++; } C[k]=U; } cout<<i<<"→"<<input[j]<<k<<endl; } } } i++; } //下面求出確定化后的終態(tài) cout<<"終態(tài)為:"; i=0; while(!C[i].empty()){ boolis_final_state=false; set<char>::iteratorit; for(it=C[i].begin();it!=C[i].end();it++){ if(*it=='#'){ is_final_state=true; break; } } if(is_final_state)cout<<i<<","; i++; } cout<<endl;}調(diào)試分析優(yōu)點(diǎn)分析：NFA的輸入只要求輸入邊的條數(shù)即可開始輸入組成FA的基本結(jié)構(gòu)(即三元組)，而有多少引起狀態(tài)轉(zhuǎn)換的輸入都交給程序自己去完成，這一點(diǎn)就顯得很簡潔，對于用戶來說也便捷！缺點(diǎn)分析：沒有可視化，整個(gè)程序的輸入輸出是通過控制臺完成的。解決辦法：可合適的使用MFC可視化編程完成(這個(gè)有余力可以考慮一下)。用戶手冊該程序的使用十分簡單，直接按要求輸入相應(yīng)數(shù)據(jù)就是。測試數(shù)據(jù)及測試結(jié)果課本P59例4.8：總結(jié)優(yōu)點(diǎn)通過這次的實(shí)習(xí)，對編譯原理NFA、DFA及之間的等價(jià)轉(zhuǎn)換有了更加深刻的理解，也學(xué)會了利用偽代碼來設(shè)計(jì)程序，由框架到細(xì)節(jié)的實(shí)現(xiàn)，這種設(shè)計(jì)相當(dāng)便利高效。團(tuán)隊(duì)成員之間交流思想取長補(bǔ)短也讓我學(xué)到了好多思想和方法。7.源代碼#include<set>#include<stack>};set<char>e_closure(set<char>,Triad[],int);set<char>move(set<char>,char,Triad[],int);voiddetermined(Triad[],int,char*,int);constintMAX_NODES=20;intmain(){ intN; cout<<"請輸入邊數(shù):"<<endl; cin>>N; Triad*G=newTriad[N]; cout<<"請輸入正規(guī)文法(*代表ε,#代表終態(tài),約定輸入時(shí)先輸入以始態(tài)開始的三元組):"<<endl; for(inti=0;i<N;i++){ cin>>G[i].start>>G[i].edge>>G[i].end; } set<char>Edge; for(intj=0;j<N;j++){ Edge.insert(G[j].edge); } intn=Edge.size(); char*input=newchar[n]; set<char>::iteratorit; j=0; for(it=Edge.begin();it!=Edge.end();it++){ input[j]=*it; j++; } determined(G,N,input,n); return0;}set<char>e_closure(set<char>T,TriadG[],intN){ set<char>U=T; stack<char>S; set<char>::iteratorit; for(it=U.begin();it!=U.end();it++) for(inti=0;i<N;i++) { if(G[i].start==t&&G[i].edge=='*') { U.insert(G[i].end); S.push(G[i].end); } } } returnU;}set<char>move(set<char>I,chara,TriadG[],intN){ set<char>U; set<char>::iteratorit; for(it=I.begin();it!=I.end();it++) for(inti=0;i<N;i++){ if(G[i].start==*it&&G[i].edge==a) U.insert(G[i].end); } returnU;}voiddetermined(TriadG[],intN,char*input,intn){ cout<<endl<<"確定后的DFA:"<<endl; boolmarked[MAX_NODES]; for(inti=0;i<MAX_NODES;i++) marked[i]=false; set<char>C[MAX_NODES]; chars0=G[0].start; set<char>T0,T1; T0.insert(s0); T1=e_closure(T0,G,N); C[0]=T1; i=0; while(!C[i].empty()&&marked[i]==false&&i<MAX_NODES){ marked[i]=true; //下面被注釋代碼可用于輸出圖中求出來的集合 /* */ for(intj=0;j<n;j++){ if(input[j]!='*'){ set<char>U=e_closure(move(C[i],input[j],G,N),G,N); if(!U.empty()){ boolinC=false; intk=0; while(!C[k].empty()&&k<MAX_NODES){ if(U==C[k]){ inC=true; break; } k++; } if(!inC){ k=0; while(!C[k].empty()&&k<MAX_NODES){ k++; }