實驗一利用子集法構造DFA

1、實驗一 利用子集法構造DFA一、實驗目的 掌握將非確定有限自動機確定化的方法和過程2、 實驗要求及內容 實驗要求：1.輸入一個NFA，輸出一個接受同一正規(guī)集的DFA；2.采用C+語言，實現該算法；3.編制測試程序；4.調試程序。 實驗步驟：1.輸入一個NFA關系圖；2.通過一個轉換算法將NFA轉換為DFA；3.顯示DFA關系圖。三、實驗環(huán)境 計算機、Windows 操作系統(tǒng)、Visual C+ 程序集成環(huán)境。4、 程序代碼#include stdafx.h#include#include#include#include#includeusing namespace std;struct edg

2、eint start,end;char c;E100,Ekong100;/E保存所有的邊，Ekong保存轉換字符為空的邊struct Stateint H100;/狀態(tài)集合int count;/狀態(tài)集合中的元素個數int flag;/是否是接受狀態(tài)int mark;/狀態(tài)編號;int n;/n:邊數int nk=0;/空字符轉換的邊數int first,accept;/開始狀態(tài)，接受狀態(tài)char alpha100;/輸入字母表,#代表空串int numof_char=0;/字母表中的字符個數int useof_char256;/該轉換字符是否用過int f200;/狀態(tài)屬性標志：0表示始態(tài)，1

3、表示接受態(tài)，-1表示中間態(tài)State DFA100;/DFA狀態(tài)集int useof_DFA100;/標志構造出來的狀態(tài)是否已存在int numof_Dtran=0;/最后得到的DFA中的狀態(tài)數char Dtran100100;/DFA狀態(tài)轉換表void input()int i,s,e;char ch;cout請輸入轉換的有向邊數n：n;cout請輸入NFA的開始狀態(tài)：first;cout請輸入NFA的接受狀態(tài)(輸入-1結束)：accept;while(accept!=-1)faccept=1;cinaccept;cout請輸入NFA，起點，終點，轉換字符(#表示空字符)：endl;int

4、k=0;for(i=0;isech;Ei.start=s;Ei.end=e;Ei.c=ch;if(ch!=#&!useof_charch)alphanumof_char+=ch;useof_charch=1;if(ch=#)Ekongnk.start=s;Ekongnk.end=e;Ekongnk.c=ch;nk+;State move(State T,char s)/c!=#State temp;temp.count=0;temp.mark=T.mark;int i,j=0,k=0;for(i=0;iT.count;i+)j=0;while(jn)if(Ej.start=T.Hi&Ej.c=

5、s) temp.Htemp.count+=Ej.end; j+;return temp;void arriveBynone(int t,int result,int& num)/搜索狀態(tài)t通過一個或多個空字符到達的狀態(tài),結果存在result中int k=0;int m=0;num=0;stack S;S.push(t);int j;while(!S.empty()j=S.top();S.pop();m=0;while(mnk) if(Ekongm.start=j) resultnum+=Ekongm.end; S.push(Ekongm.end); m+;bool check(int i,St

6、ate T)/判斷狀態(tài)i是否在T中int j;for(j=0;jT.count;j+)if(T.Hj=i)return true;return false;State closure(State T)/求閉包stack STACK;State temp;int i,j,k;for(i=0;iT.count;i+)STACK.push(T.Hi);temp.Hi=T.Hi;temp.count=T.count;temp.mark=T.mark; while(!STACK.empty() int t=STACK.top();STACK.pop();/搜索狀態(tài)t通過一個或多個空字符到達的狀態(tài)int

7、search_result100;int num;arriveBynone(t,search_result,num);for(j=0;jnum;j+) if(!check(search_resultj,temp) temp.Htemp.count+=search_resultj;STACK.push(search_resultj);for(k=0;ktemp.count;k+)if(ftemp.Hk=1) temp.flag=1; break;if(ftemp.Hk=0) temp.flag=0; break;sort(temp.H,temp.H+temp.count);for(i=0;inu

8、mof_Dtran;i+)if(temp.count!=DFAi.count) continue;sort(DFAi.H,DFAi.H+DFAi.count);for(j=0;j=DFAi.count) temp.mark=DFAi.mark;return temp;int check_inDFA()/檢查DFA中是否存在未被標記的狀態(tài),有則返回標號，否則返回-1 int i; for(i=0;inumof_Dtran;i+) if(!useof_DFAi) return i;return -1;bool check_whetherin_DFA(State T)int i,j;sort(T.H

9、,T.H+T.count);for(i=0;inumof_Dtran;i+)if(T.count!=DFAi.count) continue;sort(DFAi.H,DFAi.H+DFAi.count);for(j=0;j=DFAi.count) return true;if(i=numof_Dtran)return false;elsereturn true;void child_method()int m,n;for(m=0;m100;m+) for(n=0;n100;n+) Dtranmn=#; for(m=0;m100;m+)DFAm.flag=-1; State S0,U;S0.fl

10、ag=0;S0.count=1;S0.H0=first;State T;T=closure(S0);T.mark=0;T.flag=0;DFAnumof_Dtran+=T;memset(useof_DFA,0,sizeof(useof_DFA);int j=check_inDFA(); int k; while(j!=-1) useof_DFAj=1;for(k=0;knumof_char;k+) U=closure(move(DFAj,alphak); /if U不在DFA中 if(!check_whetherin_DFA(U) U.mark=numof_Dtran;DFAnumof_Dtr

11、an+=U; DtranDFAj.markU.mark=alphak;j=check_inDFA();void print()int i,j;for(i=0;inumof_Dtran;i+)couti:;for(j=0;jDFAi.count;j+) coutDFAi.Hj ;if(DFAi.flag=1) cout此為DFA的接受狀態(tài);if(DFAi.flag=0) cout此為DFA的開始狀態(tài);coutendl;coutendl;for(i=0;inumof_Dtran;i+)for(j=0;jnumof_Dtran;j+) if(Dtranij!=#) coutij By Dtranij

12、endl; void judge(string ch) int i,j,k;int num=ch.length(); State temp; k=0; for(i=0;inum;i+) for(j=0;jnumof_Dtran;j+) if(Dtrankj=alphai) temp=DFAj;k=j;break; if(temp.flag!=1)cout字符串 ch無法由該DFA得到endl;elsecout字符串 ch可以由該DFA得到endl;coutendl;int _tmain(int argc, _TCHAR* argv)input();child_method();couts)ju

13、dge(s);system(pause);return 0;5、 實驗結果6、 算法分析使用子集構造法對非確定有限自動機進行確定化的過程中存在大量重復計算的問題。為解決此問題,基于非確定有限自動機的特點并針對子集構造法的不足,提出了一種優(yōu)化的非確定有限自動機確定化算法。首先定義了識別符的有效引出狀態(tài)集概念并證明了-closure的并定理以保證算法的正確性,其次給出了用于避免重復計算的識別符的有效引出狀態(tài)集的構造子算法和單狀態(tài)集的-closure的求算子算法,基于這兩個子算法給出了優(yōu)化的非確定有限自動機確定化算法,最后將算法應用于實例,實驗結果表明計算量遠小于子集構造法的計算量。相比子集構造法,

14、算法能更有效地對非確定有限自動機進行確定化。七、實驗小結以前上課時有許多的問題并沒有真正的認識到，但通過這次實驗，使我掌握了許多更重要的知識點。通過實驗，我們可以知道將NFA轉換成接受同樣語言的DFA的算法稱為子集構造算法。NFA變換到DFA的基本思想是：讓DFA的每個狀態(tài)對應NFA的一個狀態(tài)集。實驗實現了NFA到DFA的轉換。實驗二 THOMPSON 算法的實現一、實驗目的 掌握將正規(guī)表達式轉換為NFA的方法和過程3、 實驗要求及內容1. 輸入一個正規(guī)表達式，輸出一個接受同一語言的NFA2. 采用C+語言，實現該算法3. 編制測試程序4. 調試程序 三、實驗環(huán)境 計算機、Windows 操作

15、系統(tǒng)、Visual C+ 程序集成環(huán)境。四、程序代碼#include Thompson.hvoid main()string Regular_Expression = (a|b)*abb;cell NFA_Cell;input(Regular_Expression);/調試需要先屏蔽Regular_Expression = add_join_symbol(Regular_Expression);Regular_Expression = postfix(Regular_Expression);NFA_Cell = express_2_NFA(Regular_Expression);Display

16、(NFA_Cell);cell express_2_NFA(string expression)int length = expression.size();char element;cell Cell,Left,Right;stack STACK;for(int i=0;ilength;i+)element = expression.at(i);switch(element)case |:Right = STACK.top();STACK.pop();Left = STACK.top();STACK.pop();Cell = do_Unite(Left,Right);STACK.push(C

17、ell);break;case *:Left = STACK.top();STACK.pop();Cell = do_Star(Left);STACK.push(Cell);break;case +:Right = STACK.top();STACK.pop();Left = STACK.top();STACK.pop();Cell = do_Join(Left,Right);STACK.push(Cell);break;default:Cell = do_Cell(element);STACK.push(Cell);cout處理完畢!endl;Cell = STACK.top();STACK

18、.pop();return Cell;cell do_Unite(cell Left,cell Right)cell NewCell;NewCell.EdgeCount=0;edge Edge1,Edge2,Edge3,Edge4; state StartState = new_StateNode();state EndState = new_StateNode();Edge1.StartState = StartState;Edge1.EndState = Left.EdgeSet0.StartState;Edge1.TransSymbol = #;Edge2.StartState = St

19、artState;Edge2.EndState = Right.EdgeSet0.StartState;Edge2.TransSymbol = #;Edge3.StartState = Left.EdgeSetLeft.EdgeCount-1.EndState;Edge3.EndState = EndState;Edge3.TransSymbol = #; Edge4.StartState = Right.EdgeSetRight.EdgeCount-1.EndState;Edge4.EndState = EndState;Edge4.TransSymbol = #;/先將Left和Right

20、的EdgeSet復制到NewCellcell_EdgeSet_Copy(NewCell,Left);cell_EdgeSet_Copy(NewCell,Right);/將新構建的四條邊加入EdgeSetNewCell.EdgeSetNewCell.EdgeCount+ = Edge1;NewCell.EdgeSetNewCell.EdgeCount+ = Edge2;NewCell.EdgeSetNewCell.EdgeCount+ = Edge3;NewCell.EdgeSetNewCell.EdgeCount+ = Edge4;/構建NewCell的啟示狀態(tài)和結束狀態(tài)NewCell.Sta

21、rtState = StartState;NewCell.EndState = EndState;return NewCell;/處理 abcell do_Join(cell Left,cell Right)for(int i=0;iRight.EdgeCount;i+)if(Right.EdgeSeti.StartState.StateNpare(Right.StartState.StateName)=0)Right.EdgeSeti.StartState = Left.EndState;STATE_NUM-;else if(Right.EdgeSeti.EndState.StateNpar

22、e(Right.StartState.StateName)=0)Right.EdgeSeti.EndState = Left.EndState;STATE_NUM-;Right.StartState = Left.EndState;cell_EdgeSet_Copy(Left,Right); Left.EndState = Right.EndState; return Left;cell do_Star(cell Cell)cell NewCell;NewCell.EdgeCount=0;edge Edge1,Edge2,Edge3,Edge4;state StartState = new_S

23、tateNode();state EndState = new_StateNode();/構建邊Edge1.StartState = StartState;Edge1.EndState = EndState;Edge1.TransSymbol = #;Edge2.StartState = Cell.EndState;Edge2.EndState = Cell.StartState;Edge2.TransSymbol = #;Edge3.StartState = StartState;Edge3.EndState = Cell.StartState;Edge3.TransSymbol = #;E

24、dge4.StartState = Cell.EndState;Edge4.EndState = EndState;Edge4.TransSymbol = #;/構建單元cell_EdgeSet_Copy(NewCell,Cell);NewCell.EdgeSetNewCell.EdgeCount+ = Edge1;NewCell.EdgeSetNewCell.EdgeCount+ = Edge2;NewCell.EdgeSetNewCell.EdgeCount+ = Edge3;NewCell.EdgeSetNewCell.EdgeCount+ = Edge4;NewCell.StartSt

25、ate = StartState;NewCell.EndState = EndState;return NewCell;cell do_Cell(char element)cell NewCell;NewCell.EdgeCount=0;edge NewEdge;state StartState = new_StateNode();state EndState = new_StateNode();NewEdge.StartState = StartState;NewEdge.EndState = EndState;NewEdge.TransSymbol = element; NewCell.E

26、dgeSetNewCell.EdgeCount+ = NewEdge;NewCell.StartState = NewCell.EdgeSet0.StartState;NewCell.EndState = NewCell.EdgeSet0.EndState;/EdgeCount此時為1return NewCell;void cell_EdgeSet_Copy(cell& Destination,cell Source)int D_count = Destination.EdgeCount;int S_count = Source.EdgeCount;for(int i=0;iS_count;i

27、+)Destination.EdgeSetD_count+i = Source.EdgeSeti;Destination.EdgeCount = D_count + S_count;state new_StateNode()state newState;newState.StateName = STATE_NUM+65;/轉換成大寫字母STATE_NUM+;return newState; void input(string &RegularExpression)cout請輸入正則表達式： （操作符：() * |;字符集：az AZ）RegularExpression;while(!check

28、_legal(RegularExpression);int check_legal(string check_string)if(check_character(check_string)&check_parenthesis(check_string)return true;return false;int check_character(string check_string)int length = check_string.size();for(int i=0;ilength;i+)char check = check_string.at(i);if(is_letter(check)/小

29、寫和大寫之間有5個字符，故不能連續(xù)判斷else if(check=(|check=)|check=*|check=|)elsecout含有不合法的字符!endl;cout請重新輸入:endl;return false;return true;int check_parenthesis(string check_string)int length = check_string.size();char * check = new charlength;strcpy(check,check_string.c_str();stack STACK;for(int i=0;ilength;i+)if(ch

30、ecki=()STACK.push(i);else if(checki=)if(STACK.empty()cerr有多余的右括號endl;/暫時不記錄匹配位置locationcout請重新輸入:endl;return false;elseSTACK.pop();if(!STACK.empty()cerr有多余的左括號endl;cout請重新輸入:=a&check=A&check=Z)return true;return false;string add_join_symbol(string add_string)string check_string = abcdefg0aaa;coutche

31、ck_stringendl;int length = check_string.size();char * check = new char2*length;strcpy(check,check_string.c_str();coutcheckendl;char *s = ssss0 aa;coutsendl;string a(s);coutaendl;int length = add_string.size();int return_string_length = 0;char *return_string = new char2*length;/做多是兩倍char first,second

32、;for(int i=0;ilength-1;i+)first = add_string.at(i);second = add_string.at(i+1);return_stringreturn_string_length+ = first; if(first!=(&first!=|&is_letter(second)return_stringreturn_string_length+ = +; else if(second=(&first!=|&first!=()return_stringreturn_string_length+ = +; return_stringreturn_stri

33、ng_length+ = second;return_stringreturn_string_length = 0;string STRING(return_string);cout加+后的表達式：STRINGendl;return STRING;int isp(char c)switch(c)case #: return 0;case (: return 1;case *: return 7;case |: return 5;case +: return 3;case ): return 8; cerrERROR!endl;return false;int icp(char c)switch

34、(c)case #: return 0;case (: return 8;case *: return 6;case |: return 4;case +: return 2;case ): return 1; cerrERROR!endl;return false;string postfix(string e) e = e+#;stack s;char ch = #,ch1,op;s.push(ch);string out_string = ;int read_location = 0;ch = e.at(read_location+);while(!s.empty()if(is_lett

35、er(ch)out_string = out_string + ch;ch = e.at(read_location+);elsech1 = s.top();if(isp(ch1)icp(ch)op = s.top();s.pop();out_string = out_string + op;elseop = s.top();s.pop();if(op=()ch = e.at(read_location+);cout后綴表達式：out_stringendl;return out_string;void Display(cell Cell)coutNFA 的邊數：Cell.EdgeCounten

36、dl;coutNFA 的起始狀態(tài)：Cell.StartState.StateNameendl;coutNFA 的結束狀態(tài)：Cell.EndState.StateNameendl;for(int i=0;iCell.EdgeCount;i+)cout第i+1條邊的起始狀態(tài)：Cell.EdgeSeti.StartState.StateName 結束狀態(tài)：Cell.EdgeSeti.EndState.StateName 轉換符：Cell.EdgeSeti.TransSymbolendl;cout結束endl;5、 算法分析Thompson算法的基本思想,提出一種利用算符優(yōu)先關系表來實現Thompso

37、n算法的方法,以實現正規(guī)式到有窮自動機的轉換.描述了算法的解決思路、算符優(yōu)先表的生成和NFA的表示.算法測試表明,該方法可以大大簡化算法的實現,提高編譯程序的工作效率.六、實驗結果7、 實驗小結通過這次試驗，我掌握了如何將正規(guī)表達式轉換為NFA的方法和過程。另外，我們要知道在構造過程中，每次構造的新狀態(tài)都要賦予不同的名字。這樣，任何NFA的兩個狀態(tài)都具有不同的名字。即使同一符號在r中出現多次，我們也要為該符號的每個實例創(chuàng)建一個獨立的帶有自己狀態(tài)的NFA。實驗三 詞法分析與語法分析程序設計一、實驗目的掌握計算機語言的詞法分析程序和語法分析程序的設計方法二、實驗要求、內容及步驟 實驗要求：1根據以

38、下的正規(guī)式，畫出狀態(tài)圖；標識符：(|)*十進制整數：0 | （1|2|3|4|5|6|7|8|9）（0|1|2|3|4|5|6|7|8|9）*運算符：+ * 2根據狀態(tài)圖，設計詞法分析函數int scan( )，實現從鍵盤讀入數據，分析出一個單詞。3對于只含有+、*運算的算術表達式的文法，編寫相應的語法分析程序，要求用LL(1)分析表實現，并以id+id*id為例進行測試。 E TE E +TE| T FT T *FT| F （E）| id實驗步驟1、根據狀態(tài)圖，設計詞法分析算法2、采用C+語言，實現該算法3、編制測試程序4、調試程序：輸入一組單詞，檢查輸出結果。5、編制給定文法的非遞歸的預測

39、分析程序，并加以測試。三、實驗環(huán)境計算機、Windows 操作系統(tǒng)、Visual C+ 程序集成環(huán)境。4、 實驗原理1. 詞法分析器讀入輸入串，將其轉換成將被語法分析器分析的詞法單元序 列。產生下述小語言的單詞序列。單詞符號種別編碼DIMIFDOSTOPEND標識符常數（整）=+*，（）1234567891011121314這個小語言的單詞符號的狀態(tài)轉換圖，如下圖：2.語法分析是決定如何使用一個文法生成一個終結符串的過程。語法分析器 能識別由加+ 減- 乘* 除/ 乘方 括號（）操作數所組成的算術表達式，其文法如下：EE+T|E-T|TTT*F|T/F|FFPF|Pp(E)|i使用的算法可以是

40、：預測分析法；遞歸下降分析法；算符優(yōu)先分析法；LR分析法等。3.中間代碼生成器 產生上述算術表達式的中間代碼（四元式序列）。id+*()$EE TEE TE EE +TEE E TT FTT FT TT T *FTT T FF idF (E)五、程序代碼（1）詞法分析程序的數據結構與算法：#include#includeusing namespace std;char prog100,token10;char ch;int syn,p,m=0,n,row,sum=0;char *rwtab20=dim,if,do,stop,end ,and,begin,bool,case,char,false

41、,for,int,not,or,set,then,true,until,while;void scaner()for(n=0;n=a&ch=A&ch=0&ch=a&ch=A&ch=Z)tokenm+=ch;ch=progp+;tokenm+=0;p-;syn=21;for(n=0;n=0&ch=0&ch32767)syn=-1;else switch(ch) case=:syn=8+15;token0=ch;break;case+:syn=9+15;token0=ch;break;case*:m=0;tokenm+=ch;ch=progp+;if(ch=*)syn=11+15; tokenm+

42、=ch;elsesyn=10+15;p-; break;case,:syn=12+15;token0=ch;break;case(:syn=13+15;token0=ch;break;case):syn=14+15;token0=ch;break;case#:syn=0;token0=ch;break;case)syn=17+15;tokenm+=ch;else if(ch=)syn=16+15;tokenm+=ch;elsesyn=15+15;p-;break;case:m=0;tokenm+=ch;ch=progp+;if(ch=)syn=19+15;tokenm+=ch;elsesyn=18+15;p-