實(shí)驗(yàn)一利用子集法構(gòu)造DFA

1、實(shí)驗(yàn)一 利用子集法構(gòu)造DFA一、實(shí)驗(yàn)?zāi)康?掌握將非確定有限自動(dòng)機(jī)確定化的方法和過(guò)程2、 實(shí)驗(yàn)要求及內(nèi)容 實(shí)驗(yàn)要求：1.輸入一個(gè)NFA，輸出一個(gè)接受同一正規(guī)集的DFA；2.采用C+語(yǔ)言，實(shí)現(xiàn)該算法；3.編制測(cè)試程序；4.調(diào)試程序。 實(shí)驗(yàn)步驟：1.輸入一個(gè)NFA關(guān)系圖；2.通過(guò)一個(gè)轉(zhuǎn)換算法將NFA轉(zhuǎn)換為DFA；3.顯示DFA關(guān)系圖。三、實(shí)驗(yàn)環(huán)境 計(jì)算機(jī)、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保存轉(zhuǎn)換字符為空的邊struct Stateint H100;/狀態(tài)集合int count;/狀態(tài)集合中的元素個(gè)數(shù)int flag;/是否是接受狀態(tài)int mark;/狀態(tài)編號(hào);int n;/n:邊數(shù)int nk=0;/空字符轉(zhuǎn)換的邊數(shù)int first,accept;/開(kāi)始狀態(tài)，接受狀態(tài)char alpha100;/輸入字母表,#代表空串int numof_char=0;/字母表中的字符個(gè)數(shù)int useof_char256;/該轉(zhuǎn)換字符是否用過(guò)int f200;/狀態(tài)屬性標(biāo)志：0表示始態(tài)，1

3、表示接受態(tài)，-1表示中間態(tài)State DFA100;/DFA狀態(tài)集int useof_DFA100;/標(biāo)志構(gòu)造出來(lái)的狀態(tài)是否已存在int numof_Dtran=0;/最后得到的DFA中的狀態(tài)數(shù)char Dtran100100;/DFA狀態(tài)轉(zhuǎn)換表void input()int i,s,e;char ch;cout請(qǐng)輸入轉(zhuǎn)換的有向邊數(shù)n：n;cout請(qǐng)輸入NFA的開(kāi)始狀態(tài)：first;cout請(qǐng)輸入NFA的接受狀態(tài)(輸入-1結(jié)束)：accept;while(accept!=-1)faccept=1;cinaccept;cout請(qǐng)輸入NFA，起點(diǎn)，終點(diǎn)，轉(zhuǎn)換字符(#表示空字符)：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通過(guò)一個(gè)或多個(gè)空字符到達(dá)的狀態(tài),結(jié)果存在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通過(guò)一個(gè)或多個(gè)空字符到達(dá)的狀態(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中是否存在未被標(biāo)記的狀態(tài),有則返回標(biāo)號(hào)，否則返回-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的開(kāi)始狀態(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無(wú)法由該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、 實(shí)驗(yàn)結(jié)果6、 算法分析使用子集構(gòu)造法對(duì)非確定有限自動(dòng)機(jī)進(jìn)行確定化的過(guò)程中存在大量重復(fù)計(jì)算的問(wèn)題。為解決此問(wèn)題,基于非確定有限自動(dòng)機(jī)的特點(diǎn)并針對(duì)子集構(gòu)造法的不足,提出了一種優(yōu)化的非確定有限自動(dòng)機(jī)確定化算法。首先定義了識(shí)別符的有效引出狀態(tài)集概念并證明了-closure的并定理以保證算法的正確性,其次給出了用于避免重復(fù)計(jì)算的識(shí)別符的有效引出狀態(tài)集的構(gòu)造子算法和單狀態(tài)集的-closure的求算子算法,基于這兩個(gè)子算法給出了優(yōu)化的非確定有限自動(dòng)機(jī)確定化算法,最后將算法應(yīng)用于實(shí)例,實(shí)驗(yàn)結(jié)果表明計(jì)算量遠(yuǎn)小于子集構(gòu)造法的計(jì)算量。相比子集構(gòu)造法,

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

15、系統(tǒng)、Visual C+ 程序集成環(huán)境。四、程序代碼#include Thompson.hvoid main()string Regular_Expression = (a|b)*abb;cell NFA_Cell;input(Regular_Expression);/調(diào)試需要先屏蔽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復(fù)制到NewCellcell_EdgeSet_Copy(NewCell,Left);cell_EdgeSet_Copy(NewCell,Right);/將新構(gòu)建的四條邊加入EdgeSetNewCell.EdgeSetNewCell.EdgeCount+ = Edge1;NewCell.EdgeSetNewCell.EdgeCount+ = Edge2;NewCell.EdgeSetNewCell.EdgeCount+ = Edge3;NewCell.EdgeSetNewCell.EdgeCount+ = Edge4;/構(gòu)建NewCell的啟示狀態(tài)和結(jié)束狀態(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();/構(gòu)建邊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 = #;/構(gòu)建單元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此時(shí)為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;/轉(zhuǎn)換成大寫(xiě)字母STATE_NUM+;return newState; void input(string &RegularExpression)cout請(qǐng)輸入正則表達(dá)式： （操作符：() * |;字符集：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、寫(xiě)和大寫(xiě)之間有5個(gè)字符，故不能連續(xù)判斷else if(check=(|check=)|check=*|check=|)elsecout含有不合法的字符!endl;cout請(qǐng)重新輸入: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有多余的右括號(hào)endl;/暫時(shí)不記錄匹配位置locationcout請(qǐng)重新輸入:endl;return false;elseSTACK.pop();if(!STACK.empty()cerr有多余的左括號(hào)endl;cout請(qǐng)重新輸入:=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加+后的表達(dá)式：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后綴表達(dá)式：out_stringendl;return out_string;void Display(cell Cell)coutNFA 的邊數(shù)：Cell.EdgeCounten

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

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

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

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

40、：預(yù)測(cè)分析法；遞歸下降分析法；算符優(yōu)先分析法；LR分析法等。3.中間代碼生成器 產(chǎn)生上述算術(shù)表達(dá)式的中間代碼（四元式序列）。id+*()$EE TEE TE EE +TEE E TT FTT FT TT T *FTT T FF idF (E)五、程序代碼（1）詞法分析程序的數(shù)據(jù)結(jié)構(gòu)與算法：#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-