DFA的構(gòu)造與運行實驗源碼實驗報告

西北師范大學計算機科學與工程學院學生實驗報告學號：7107年9月14日系別計算機科學與技術(shù)學院專業(yè)軟件工程班級級軟件一班姓名王尚課程名稱計算機編譯原理課程類型專業(yè)必修學時數(shù)實驗名稱DFA的構(gòu)造與運行實驗實驗目的和規(guī)定：通過本次實驗，加深對DFA及其識別的語言的理解，學習對普通的DFA的體現(xiàn)辦法與編程實現(xiàn)辦法。編寫一種C語言程序，模擬實現(xiàn)DFA識別字符串的過程。（1）DFA的輸入；（2）DFA的存儲與讀寫；（3）DFA的對的性檢查；（4）DFA的語言集列表顯示；（5）DFA的規(guī)則字符串鑒定；。實驗內(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文獻"<<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() //初始化自動機 { 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)換表，返回下個狀態(tài) if(present=='N')//N即為move返回錯誤的狀態(tài)， { break; } i++; } if(FinalStates.find(present)!=FinalStates.npos)//如果返回的狀態(tài)用find函數(shù)屬于最后狀態(tài)集則表達識別 cout<<"該自動機識別此字符串"<<endl; else cout<<"該自動機不識別此字符串"<<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文獻中讀取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的信息寫入文獻中， 第一行：字符集； 第二行：狀態(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<<"該自動機識別字符串:"<<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賦值，遞歸后應當還原，這一點沒有想到。調(diào)試了很久?？偨Y(jié)，對遞歸的具體編寫還是不熟悉?，F(xiàn)在的代碼，字符集和狀態(tài)只能是一種字符，若要優(yōu)化能夠用vector<string>容器存儲即可。實驗總結(jié)：在這次實驗