THOMPSON算法地實現(xiàn)

1、實用文案實驗二：THOMPSON法的實現(xiàn)一. 實驗?zāi)康恼莆誘HOMPSON法原理和方法。二. 實驗要求、內(nèi)容及步驟1. 輸入字母表上的正規(guī)式r，輸出一個接受L（ r ）的NFA2. 采用C+語言，實現(xiàn)該算法；3. 編制測試程序4. 調(diào)試程序；三. 實驗設(shè)備計算機、Windows操作系統(tǒng)、Visual C+程序集成環(huán)境。四. 實驗原理Thompsor構(gòu)造法：從正規(guī)表達(dá)式構(gòu)造 NFA輸入：字母表工上的一個正規(guī)表達(dá)式 r輸出：接受L（r）的NFA N方法：將r分解成最基本的子表達(dá)式，使用下面的規(guī)則 1和2為r的每個 基本符號（&或工中的符號）構(gòu)造NFA用規(guī)則3逐步組合前面構(gòu)造的NFA 直到獲

2、得整個正規(guī)表達(dá)式的 NFA為止。規(guī)則1.對& ,構(gòu)造NFAstart這里i是新的開始狀態(tài)，f是新的接受狀態(tài)。很明顯這個NFA識別 £ 規(guī)則2.對于工中的每個符號a,構(gòu)造NFA標(biāo)準(zhǔn)文檔是新的接受狀態(tài)。這個NFA識別a。同樣，i是新的開始狀態(tài)，規(guī)則3 .如果N(s)和N(t) 是正規(guī)表達(dá)式s和t的NFA則: 對于正規(guī)表達(dá)式s | t,可構(gòu)造復(fù)合的NFA N(s|t):CCD z Ci 對于正規(guī)表達(dá)式st,可構(gòu)造復(fù)合的NFA N(st): 對于正規(guī)表達(dá)式 s*,構(gòu)造復(fù)合的NFA Ns*): 對于括起來的正規(guī)表達(dá)式(s), 使用N ( s)本身作為它的NFA在構(gòu)造過程中，每次構(gòu)造的新

3、狀態(tài)都要賦予不同的名字。這樣，任何NFA的兩個狀態(tài)都具有不同的名字。即使同一符號在r中出現(xiàn)多次，我們也要為該符號的每個實例創(chuàng)建一個獨立的帶有自己狀態(tài)的NFA五. 程序設(shè)計框架L也討欣耳九文 f *fit+f k>il wriiu Tiiieiii3EA-行到etfiuj中set liwO讀電草測的第I傘宇 袴 sjetjuiHtclHsrQ* fiortvLZ耳諭YN識別界FF1楸：“斗 jkl 0識別甦己品驗 raxiidigO捕入餐號我、ua sth* 血 tcikeii)1itiMd cc«iO1iii ism識則字符常載 T«ag iatrl符號表:iis.U

4、>wn;(rib lukai)實用文案六. 程序流程圖拮竹懵満給#I山罰仝處先rMFA和弁R Vt甘廠萩京*中丑示g 驗字幷豐時亍戳，七實驗代碼核心代碼如下：#ifndef THOMPSON #defi ne THIMPSON_H#in elude <iostream>#in clude <stdio.h>#in clude <stack>#in clude <stri ng> using n amespace std;標(biāo)準(zhǔn)文檔實用文案#defi ne MAX 100/節(jié)點，定義成結(jié)構(gòu)體，便于以后擴展struct statestring S

5、tateName;；/邊空轉(zhuǎn)換符永#表示struct edgestate StartState;state En dState;char Tran sSymbol;/單元struct celledge EdgeSetMAX;int EdgeCo unt;state StartState;state En dState;/全局變量聲明/int EDGE_NUM = 0;int STATE_NUM = 0;/int CELL_NUM = 0;/函數(shù)聲明void in put(stri ng&);int check_legal(stri ng);int check_character(str

6、i ng);int check_pare nthesis(stri ng);int is_letter(char);string add_join_symbol(string);/中綴轉(zhuǎn)后綴string postfix(string);/ 優(yōu)先級 in stack priorityint isp(char);/ 優(yōu)先級 in coming priorityint scp(char);/表達(dá)式轉(zhuǎn)NFAcell express_2_NFA(stri ng);/處理a|bcell do_U ni te(cell,cell);/處理abcell do_Join( cell,cell);/處理a*cel

7、l do_Star(cell);處理acell do_Cell(char);/將二個單元的邊的集合復(fù)制到另一個單元void cell_EdgeSet_Copy(cell & ,cell);/產(chǎn)生一個新的狀態(tài)節(jié)點，便于管理state new_StateNode();/顯示void Display(cell);#en dif#in clude "Thomps on .h"/主函數(shù)，void mai n()stri ng Regular_Expressi on = "(a|b)*abb"cell NFA_Cell;Regular_Expressi on

8、 = "(a|b)*abb"/接受輸入in put(Regular_Expressi on);/調(diào)試需要先屏蔽/添加"+”，便于轉(zhuǎn)后綴表達(dá)式Regular_Expressi on = addoin_symbol(Regular_Expressi on);/中綴轉(zhuǎn)后綴Regular_Expressi on = postfix(Regular_Expressi on);/表達(dá)式轉(zhuǎn)NFANFA_Cell = express_2_NFA(Regular_Expressio n);/顯示Display(NFA_Cell);/*表達(dá)式轉(zhuǎn)NFA處理函數(shù)，返回最終的NFA吉合*/

9、cell express_2_NFA(stri ng expressi on)int len gth = expressi on. size();char eleme nt;cell Cell,Left,Right;stack<cell> STACK;for(i nt i=0;i<le ngth;i+)eleme nt = expressi on. at(i);switch(eleme nt)標(biāo)準(zhǔn)文檔 case T：Right = STACK.top();STACK.pop();Left = STACK.top();STACK.pop();Cell = do_Un ite(L

10、eft,Right);STACK.push(Cell); 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_Joi n(Left,Right);STACK.push(Cell); break;default:Cell = do_Cell(eleme nt);STACK.

11、push(Cell);cout<<"處理完畢!"<<endl;Cell = STACK.top();STACK.pop();return Cell; /處理a|bcell do_Unite(cell Left,cell Right)cell NewCell;NewCell.EdgeCou nt=O; edge Edge1,Edge2,Edge3,Edge4;/獲得新的新狀態(tài)節(jié)點state StartState = n ew_StateNode(); state En dState = n ew_StateNode();/構(gòu)建邊Edge1.StartS

12、tate = StartState;Edgel.E ndState = Left.EdgeSetO.StartState;Edgel.Tra nsSymbol = '#'Edge2.StartState = StartState;Edge2.E ndState = Right.EdgeSetO.StartState;Edge2.Tra nsSymbol = '#'Edge3.StartState = Left.EdgeSetLeft.EdgeCou nt-1.E ndState;Edge3.E ndState = En dState;Edge3.Tra nsSy

13、mbol = '#'Edge4.StartState = Right.EdgeSetRight.EdgeCou nt-1.E ndState;Edge4.E ndState = En dState;Edge4.Tra nsSymbol = '#'/構(gòu)建單元/ 先將 Left 和 Right 的 EdgeSet 復(fù)制到 NewCell cell_EdgeSet_Copy(NewCell,Left);cell_EdgeSet_Copy(NewCell,Right);/將新構(gòu)建的四條邊加入EdgeSetNewCell.EdgeSetNewCell.EdgeCou nt

14、+ = Edgel;NewCell.EdgeSetNewCell.EdgeCou nt+ = Edge2;NewCell.EdgeSetNewCell.EdgeCou nt+ = Edge3;NewCell.EdgeSetNewCell.EdgeCou nt+ = Edge4;/構(gòu)建NewCell的啟示狀態(tài)和結(jié)束狀態(tài)NewCell.StartState = StartState;NewCell.E ndState = En dState;return NewCell;/處理abcell do_Joi n( cell Left,cell Right)-/將Left的結(jié)束狀態(tài)和 Right的開始狀

15、態(tài)合并，將Right的邊復(fù)制給Left，將Left返回/將Right中所有以StartState開頭的邊全部修改，for(i nt i=0;i<Right.EdgeCou nt;i+)e)=0)Right.EdgeSeti.StartState = Left.E ndState; STATE_NUM-;elseRight.EdgeSeti.E ndState = Left.E ndState;STATE_NUM-;Right.StartState = Left.E ndState;cell_EdgeSet_Copy(Left,Right);/將Left的結(jié)束狀態(tài)更新為Right的結(jié)束狀態(tài)

16、Left.E ndState = Right.E ndState; return Left;/處理a*cell do_Star(cell Cell)-cell NewCell;NewCell.EdgeCou nt=O; edge Edge1,Edge2,Edge3,Edge4;/獲得新的新狀態(tài)節(jié)點state StartState = n ew_StateNode(); state En dState = n ew_StateNode();/構(gòu)建邊Edge1.StartState = StartState;Edge1.E ndState = En dState;Edge1.Tra nsSymbo

17、l = '#'Edge2.StartState = Cell.E ndState;Edge2.E ndState = Cell.StartState;Edge2.Tra nsSymbol = '#'Edge3.StartState = StartState;Edge3.E ndState = Cell.StartState;Edge3.Tra nsSymbol = '#'Edge4.StartState = Cell.E ndState;Edge4.E ndState = En dState;Edge4.Tra nsSymbol = '#

18、'/構(gòu)建單元/ 先將 Cell 的 EdgeSet 復(fù)制到 NewCell cell_EdgeSet_Copy(NewCell,Cell);/將新構(gòu)建的四條邊加入EdgeSetNewCell.EdgeSetNewCell.EdgeCou nt+ = Edgel;NewCell.EdgeSetNewCell.EdgeCou nt+ = Edge2;NewCell.EdgeSetNewCell.EdgeCou nt+ = Edge3;NewCell.EdgeSetNewCell.EdgeCou nt+ = Edge4; /構(gòu)建NewCell的啟示狀態(tài)和結(jié)束狀態(tài)NewCell.StartSt

19、ate = StartState;NewCell.E ndState = En dState; return NewCell;/處理acell do_Cell(char eleme nt)cell NewCell;NewCell.EdgeCou nt=O;edge NewEdge;/獲得新的新狀態(tài)節(jié)點state StartState = n ew_StateNode();state En dState = n ew_StateNode();/構(gòu)建邊NewEdge.StartState = StartState;NewEdge.E ndState = En dState;NewEdge.Tra

20、nsSymbol = eleme nt;/構(gòu)建單元NewCell.EdgeSetNewCell.EdgeCou nt+ = NewEdge;NewCell.StartState = NewCell.EdgeSetO.StartState;NewCell.E ndState = NewCell.EdgeSetO.E ndState;/EdgeCou nt return NewCell;void cell_EdgeSet_Copy(cell& Desti nati on, cell Source)int D_co unt = Desti nati on .EdgeCo unt;int S_

21、co unt = Source.EdgeCo unt;for(i nt i=0;i<S_co un t;i+)Dest in ati on .EdgeSetD_co un t+i = Source.EdgeSeti;Desti nati on .EdgeCo unt = D_co unt + S_co unt; - -/*獲得新的狀態(tài)節(jié)點，統(tǒng)一產(chǎn)生，便于管理，不能產(chǎn)生重復(fù)的狀態(tài)并添加到state_set 數(shù)組中*/state new_StateNode()state n ewState;n ewState.StateName = STATE_NUM+65; 轉(zhuǎn)換成大寫字母 STATE_N

22、UM+;return n ewState;/接收輸入正規(guī)表達(dá)式，RegularExpression 作為回傳函數(shù)void in put(stri ng &RegularExpressi on)cout<<"請輸入正則表達(dá)式：(操作符：()* |;字符集：此時為1az AZ) "<<endl;docin> >RegularExpressio n;while(!check_legal(RegularExpressi on); cout<<RegularExpressi on<<en dl;/*檢測輸入的正則表達(dá)

23、式是否合法*/int check_legal(string check_string)if(check_character(check_stri ng)&&check_pare nthesis(check_stri ng) return true;return false;檢查輸入的字符是否合適()* | az AZ合法返回true,非法返回false*/int check_character(stri ng check_stri ng)int len gth = check_stri ng.size();for(i nt i=0;i<le ngth;i+)char ch

24、eck = check_stri ng.at(i);if(is_letter(check)小寫和大寫之間有5個字符，故不能連續(xù)判斷cout<<" 字母合法"else if(check='('|check=')'|check='*'|check=T)cout<<"操作符合法"elsecout<<"含有不合法的字符!"<<endl;cout<<"請重新輸入:"<<endl;return false;r

25、eturn true;/*先檢查括號是否匹配*合法返回true,非法返回false*/int check_parenthesis(string check_string)int len gth = check_stri ng.size();char * check = new charle ngth;strcpy(check,check_stri ng.c_str();/char a = check_stri ng.at(1);stack <in t> STACK;for(i nt i=O;i<le ngth;i+)if(checki='(')STACK.pu

26、sh(i);else if(checki=')')if(STACK.empty()locati oncerr<<"有多余的右括號"<<endl;暫時不記錄匹配位置cout<<"請重新輸入:"<<endl;return false;elseSTACK.pop();if(!STACK.empty()/暫時不記錄匹配位置locationcerr<<"有多余的左括號"<<endl; cout<<"請重新輸入:"<<

27、;endl; return false;cout<<check<<e ndl;return true;/*檢測是否是字母是返回true,否則false*/int is_letter(char check)if(check>='a'&&check<='z'|check>='A '&&check<='Z') return true;return false; /*添加交操作符"+”，便于中綴轉(zhuǎn)后綴表達(dá)式 例如 abb->a+b+b*/str

28、ing addoin_symbol(string add_string)/*測試終止符0string check_string = "abcdefg'Oaaa"cout<<check_stri ng<<e ndl;int len gth = check_stri ng.size();char * check = new char2*le ngth;strcpy(check,check_stri ng.c_str(); cout<<check<<e ndl;char *s = "ssss0 aa"co

29、ut<<s<<e ndl;stri ng a(s);cout<<a<<e ndl;*/int len gth = add_stri ng.size();int return_stri ngen gth = 0;char *return_stri ng = new char2*le ngth;/做多是兩倍char first,sec ond;for(i nt i=0;i<le ngth-1;i+)first = add_stri ng.at(i);sec ond = add_stri ng.at(i+1);retur n_stri ngret

30、ur n_stri ng_le ngth+ = first;/若第二個是字母、第一個不是'('、T都要添加if(first!='('&&first!=T&&is_letter(seco nd)retur n_stri ngretur n_stri ng_le ngth+ = '+' - -/若第二個是'(',第一個不是T 、('，也要加else if(seco nd='('&&first!='|'&&first!='(&

31、#39;)retur n_stri ngretur n_stri ng_le ngth+ = '+'/將最后一個字符寫入retur n_stri ngretur n_stri ng_le ngth+ = sec ond;retur n_stri ngretur n_stri ng_le ngth = '0'string STRING(return_string);cout<<"力+'后的表達(dá)式："<<STRING<<endl;return STRING;/*優(yōu)先級表：# ( * | + )isp 0

32、17538icp 086421*/in stack priority棧內(nèi)優(yōu)先級int isp(char c)switch(c)case '#': retur n 0;case '(': retur n 1;case '*': retur n 7;case T： return 5;case '+': retur n 3;case ')': retur n 8;/若走到這一步，說明出錯了cerr<<"ERROR!"<<e ndl;return false;/in coming

33、 priority棧外優(yōu)先級int icp(char c)switch(c)case '#': retur n 0;case '(': retur n 8;case '*': retur n 6;case T： return 4;case '+': retur n 2;case ')': retur n 1;/若走到這一步，說明出錯了cerr<<"ERROR!"<<e ndl;return false;/*中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式*/string postfix(strin

34、g e)s的棧底/設(shè)定e的最后一個符號式“ #”，而其“ #”一開始先放在棧e = e+"#"stack<char> s; char ch = '#',ch1,op; s.push(ch);/讀一個字符string out_string =""int read_locati on = 0;ch = e.at(read_locati on+);while(!s.empty()if(is_letter(ch)-out_stri ng = out_stri ng + ch;/cout<<ch;ch = e.at(read

35、_locatio n+); -else/cout<<"輸出操作符："<<ch<<e ndl;ch1 = s.top();if(isp(ch1)<icp(ch)s.push(ch);/cout<<"壓棧"<<ch<<"讀取下一個"<<endl;ch = e.at(read_locati on+);else if(isp(ch1)>icp(ch)op = s.top();s.pop();cout<<" 退棧"<<op<<"添加到輸出字符串"<<endl;out_stri ng = out_stri ng + op;/cout<<op;elseop = s.top();s.pop();/cout<<"退棧"<<op<<"但不添加到輸入字符串"<&l