DFA的構(gòu)造與運(yùn)行實(shí)驗(yàn)源碼實(shí)驗(yàn)報(bào)告

西北師范大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院學(xué)生實(shí)驗(yàn)報(bào)告學(xué)號：7107年9月14日系別計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院專業(yè)軟件工程班級級軟件一班姓名王尚課程名稱計(jì)算機(jī)編譯原理課程類型專業(yè)必修學(xué)時(shí)數(shù)實(shí)驗(yàn)名稱DFA的構(gòu)造與運(yùn)行實(shí)驗(yàn)實(shí)驗(yàn)?zāi)康暮鸵?guī)定：通過本次實(shí)驗(yàn)，加深對DFA及其識別的語言的理解，學(xué)習(xí)對普通的DFA的體現(xiàn)辦法與編程實(shí)現(xiàn)辦法。編寫一種C語言程序，模擬實(shí)現(xiàn)DFA識別字符串的過程。（1）DFA的輸入；（2）DFA的存儲與讀寫；（3）DFA的對的性檢查；（4）DFA的語言集列表顯示；（5）DFA的規(guī)則字符串鑒定；。實(shí)驗(yàn)內(nèi)容//構(gòu)造一種DFA#include<iostream>#include<string>#include<vector>#include<fstream>usingnamespacestd;classTransitionTable{public: charpresent; //現(xiàn)在狀態(tài) charnext; //下一狀態(tài) charinput; //輸入字符 TransitionTable(charP,charI,charD) { present=P; next=D; input=I; }};classDFA{public: DFA() { cout<<"1、手動輸入，2、讀取txt文獻(xiàn)"<<endl; intselect; cin>>select; if(select==1) inti(); if(select==2) read(); } stringStates; //狀態(tài)集 charStartStates; //開始狀態(tài) stringFinalStates; //結(jié)束狀態(tài)集 stringAlphabet; //字符集 vector<TransitionTable>Trans;//轉(zhuǎn)換函數(shù) voidinti() //初始化自動機(jī) { cout<<"請輸入有限狀態(tài)集S："<<endl; cin>>States; cout<<"請輸入字符集A："<<endl; cin>>Alphabet; cout<<"請輸入轉(zhuǎn)換函數(shù)MOVE--格式為：現(xiàn)在狀態(tài)-輸入字符-下一狀態(tài)：(輸入#結(jié)束輸入)"<<endl; intj=0; while(true) { charinput[4]; cin>>input; if(strcmp(input,"#")==0) break; TransitionTableTemp(input[0],input[1],input[2]); Trans.push_back(Temp); } cout<<"請輸入開始狀態(tài)集S0："<<endl; cin>>StartStates; cout<<"請輸入結(jié)束狀態(tài)集F："<<endl; cin>>FinalStates; } voididentify() //識別字符串 { cout<<"請輸入字符串："<<endl; stringstr; cin>>str; inti=0; charpresent=StartStates; while(i<str.length()) { present=move(present,str[i]);//move函數(shù)即去遍歷轉(zhuǎn)換表，返回下個(gè)狀態(tài) if(present=='N')//N即為move返回錯誤的狀態(tài)， { break; } i++; } if(FinalStates.find(present)!=FinalStates.npos)//如果返回的狀態(tài)用find函數(shù)屬于最后狀態(tài)集則表達(dá)識別 cout<<"該自動機(jī)識別此字符串"<<endl; else cout<<"該自動機(jī)不識別此字符串"<<endl;; } charmove(charP,charI) //move轉(zhuǎn)換函數(shù) { for(inti=0;i<Trans.size();i++) { if(Trans[i].present==P&&Trans[i].input==I) returnTrans[i].next; } return'N'; } voidread() //從txt文獻(xiàn)中讀取DNF的信息 { chartemp[10]; fstreamff("DNF.txt",ios::in); ff.getline(temp,10); Alphabet=temp; ff.getline(temp,10); States=temp; ff.getline(temp,10); StartStates=temp[0]; ff.getline(temp,10); FinalStates=temp[0]; while(!ff.eof()) { ff.getline(temp,10); TransitionTableTemp(temp[0],temp[1],temp[2]); Trans.push_back(Temp); } } /*將DNF的信息寫入文獻(xiàn)中， 第一行：字符集； 第二行：狀態(tài)集; 第三行：開始狀態(tài)； 第四行：結(jié)束狀態(tài)集； 下列行寫入狀態(tài)轉(zhuǎn)換表*/ voidwrite() { fstreamff("DNF.txt",ios::out); ff<<Alphabet<<endl; ff<<States<<endl; ff<<StartStates<<endl; ff<<FinalStates<<endl; for(inti=0;i<Trans.size();i++) ff<<Trans[i].present<<Trans[i].input<<Trans[i].next<<endl; ff.close(); } voidTraversal(charpresent,intN,stringstrass="") //遍歷DFA的語言集列表顯示 { if(present=='N'||N<0) return; N--; if(FinalStates.find(present)!=FinalStates.npos) { cout<<"該自動機(jī)識別字符串:"<<strass<<endl; } elseif(FinalStates.find(present)==FinalStates.npos&&N<0) return; for(inti=0;i<Alphabet.length();i++) { stringtemp; temp=strass; strass+=Alphabet[i]; Traversal(move(present,Alphabet[i]),N,strass); strass=temp; } }};intmain(){ DFAexample; example.identify(); intN; cout<<"請輸入N"<<endl; cin>>N; example.Traversal(example.StartStates,N); example.write(); system("pause"); return0;}/*測試用例輸入狀態(tài)轉(zhuǎn)換表0a10b21b22a11a32b33a33b3#0a10b22a11b21a32b53a35b53b45a66b44a66a34b5*/錯誤分析：對于遞歸的終止條件寫得不夠明確。遞歸前對字符串賦值strass賦值，遞歸后應(yīng)當(dāng)還原，這一點(diǎn)沒有想到。調(diào)試了很久。總結(jié)，對遞歸的具體編寫還是不熟悉?，F(xiàn)在的代碼，字符集和狀態(tài)只能是一種字符，若要優(yōu)化能夠用vector<string>容器存儲即可。實(shí)驗(yàn)總結(jié)：在這次實(shí)驗(yàn)