THOMPSON 算法的實現(xiàn)

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

2、對, 構(gòu)造NFA 這里 i 是新的開始狀態(tài)，f是新的接受狀態(tài)。很明顯這個NFA識別。 規(guī)則2. 對于中的每個符號a，構(gòu)造NFA同樣，i 是新的開始狀態(tài)， f 是新的接受狀態(tài)。 這個NFA識別 a。規(guī)則3 . 如果N(s) 和 N(t) 是正規(guī)表達式s和t的NFA，則：對于正規(guī)表達式 s | t, 可構(gòu)造復(fù)合的NFA N(s|t): 對于正規(guī)表達式 st, 可構(gòu)造復(fù)合的NFA N(st)：對于正規(guī)表達式 s*, 構(gòu)造復(fù)合的NFA N(s*):對于括起來的正規(guī)表達式 (s), 使用N (s) 本身作為它的NFA。在構(gòu)造過程中，每次構(gòu)造的新狀態(tài)都要賦予不同的名字。這樣，任何NFA的兩個狀態(tài)都具有不同

3、的名字。即使同一符號在r中出現(xiàn)多次，我們也要為該符號的每個實例創(chuàng)建一個獨立的帶有自己狀態(tài)的NFA。五.程序設(shè)計框架六.程序流程圖七.實驗代碼核心代碼如下：#ifndef THOMPSON_H#define THIMPSON_H#include <iostream>#include <stdio.h>#include <stack>#include <string>using namespace std;#define MAX 100/節(jié)點，定義成結(jié)構(gòu)體，便于以后擴展struct statestring StateName;/邊 空轉(zhuǎn)換符永'

4、;#'表示struct edgestate StartState;state EndState;char TransSymbol;/單元struct celledge EdgeSetMAX;int EdgeCount;state StartState;state EndState;/全局變量聲明/int EDGE_NUM = 0;int STATE_NUM = 0;/int CELL_NUM = 0;/函數(shù)聲明void input(string&);int check_legal(string);int check_character(string);int check_par

5、enthesis(string);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);/表達式轉(zhuǎn)NFAcell express_2_NFA(string);/處理 a|bcell do_Unite(cell,cell);/處理 abcell do_Join(cell,cell);/處理 a*cell do_Star(cell);/處理 acel

6、l do_Cell(char);/將一個單元的邊的集合復(fù)制到另一個單元void cell_EdgeSet_Copy(cell&,cell);/產(chǎn)生一個新的狀態(tài)節(jié)點，便于管理state new_StateNode();/顯示void Display(cell);#endif#include "Thompson.h"/主函數(shù)，void main()string Regular_Expression = "(a|b)*abb"cell NFA_Cell;Regular_Expression = "(a|b)*abb"/接受輸入inp

7、ut(Regular_Expression);/調(diào)試需要先屏蔽/添加“+”，便于轉(zhuǎn)后綴表達式Regular_Expression = add_join_symbol(Regular_Expression);/中綴轉(zhuǎn)后綴Regular_Expression = postfix(Regular_Expression);/表達式轉(zhuǎn)NFANFA_Cell = express_2_NFA(Regular_Expression);/顯示Display(NFA_Cell);/*表達式轉(zhuǎn)NFA處理函數(shù),返回最終的NFA結(jié)合*/cell express_2_NFA(string expression)int l

8、ength = expression.size();char element;cell Cell,Left,Right;stack<cell> STACK;for(int i=0;i<length;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(Cell);break;case '*'

9、: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;Cel

10、l = STACK.top();STACK.pop();return Cell;/處理 a|bcell do_Unite(cell Left,cell Right)cell NewCell;NewCell.EdgeCount=0;edge Edge1,Edge2,Edge3,Edge4;/獲得新的新狀態(tài)節(jié)點state StartState = new_StateNode();state EndState = new_StateNode();/構(gòu)建邊Edge1.StartState = StartState;Edge1.EndState = Left.EdgeSet0.StartState;Ed

11、ge1.TransSymbol = '#'Edge2.StartState = StartState;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.End

12、State;Edge4.EndState = EndState;Edge4.TransSymbol = '#'/構(gòu)建單元/先將Left和Right的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+

13、= Edge3;NewCell.EdgeSetNewCell.EdgeCount+ = Edge4;/構(gòu)建NewCell的啟示狀態(tài)和結(jié)束狀態(tài)NewCell.StartState = StartState;NewCell.EndState = EndState;return NewCell;/處理 abcell do_Join(cell Left,cell Right)/將Left的結(jié)束狀態(tài)和Right的開始狀態(tài)合并，將Right的邊復(fù)制給Left，將Left返回/將Right中所有以StartState開頭的邊全部修改，for(int i=0;i<Right.EdgeCount;i+)i

14、f(Right.EdgeSeti.StartState.StateNpare(Right.StartState.StateName)=0)Right.EdgeSeti.StartState = Left.EndState;STATE_NUM-;else if(Right.EdgeSeti.EndState.StateNpare(Right.StartState.StateName)=0)Right.EdgeSeti.EndState = Left.EndState;STATE_NUM-;Right.StartState = Left.EndState;cell_EdgeSet_Copy(Lef

15、t,Right);/將Left的結(jié)束狀態(tài)更新為Right的結(jié)束狀態(tài)Left.EndState = Right.EndState;return Left;/處理 a*cell do_Star(cell Cell)cell NewCell;NewCell.EdgeCount=0;edge Edge1,Edge2,Edge3,Edge4;/獲得新的新狀態(tài)節(jié)點state StartState = new_StateNode();state EndState = new_StateNode();/構(gòu)建邊Edge1.StartState = StartState;Edge1.EndState = EndS

16、tate;Edge1.TransSymbol = '#'Edge2.StartState = Cell.EndState;Edge2.EndState = Cell.StartState;Edge2.TransSymbol = '#'Edge3.StartState = StartState;Edge3.EndState = Cell.StartState;Edge3.TransSymbol = '#'Edge4.StartState = Cell.EndState;Edge4.EndState = EndState;Edge4.TransSym

17、bol = '#'/構(gòu)建單元/先將Cell的EdgeSet復(fù)制到NewCellcell_EdgeSet_Copy(NewCell,Cell);/將新構(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.StartSt

18、ate = StartState;NewCell.EndState = EndState;return NewCell;/處理 acell do_Cell(char element)cell NewCell;NewCell.EdgeCount=0;edge NewEdge;/獲得新的新狀態(tài)節(jié)點state StartState = new_StateNode();state EndState = new_StateNode();/構(gòu)建邊NewEdge.StartState = StartState;NewEdge.EndState = EndState;NewEdge.TransSymbol =

19、 element;/構(gòu)建單元NewCell.EdgeSetNewCell.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.EdgeC

20、ount;for(int i=0;i<S_count;i+)Destination.EdgeSetD_count+i = Source.EdgeSeti;Destination.EdgeCount = D_count + S_count;/*獲得新的狀態(tài)節(jié)點，統(tǒng)一產(chǎn)生，便于管理，不能產(chǎn)生重復(fù)的狀態(tài)并添加到state_set數(shù)組中*/state new_StateNode()state newState;newState.StateName = STATE_NUM+65;/轉(zhuǎn)換成大寫字母STATE_NUM+;return newState;/接收輸入正規(guī)表達式，RegularExpress

21、ion作為回傳函數(shù)void input(string &RegularExpression)cout<<"請輸入正則表達式： （操作符：() * |;字符集：az AZ）"<<endl;docin>>RegularExpression;while(!check_legal(RegularExpression);/cout<<RegularExpression<<endl;/*檢測輸入的正則表達式是否合法*/int check_legal(string check_string)if(check_charac

22、ter(check_string)&&check_parenthesis(check_string)return true;return false;/*檢查輸入的字符是否合適 () * | az AZ合法返回true,非法返回false*/int check_character(string check_string)int length = check_string.size();for(int i=0;i<length;i+)char check = check_string.at(i);if(is_letter(check)/小寫和大寫之間有5個字符，故不能連續(xù)判

23、斷/cout<<"字母 合法"else if(check='('|check=')'|check='*'|check='|')/cout<<"操作符 合法"elsecout<<"含有不合法的字符!"<<endl;cout<<"請重新輸入:"<<endl;return false;return true;/*先檢查括號是否匹配*合法返回true,非法返回false*/ int che

24、ck_parenthesis(string check_string)int length = check_string.size();char * check = new charlength;strcpy(check,check_string.c_str();/char a = check_string.at(1);stack<int> STACK;for(int i=0;i<length;i+)if(checki='(')STACK.push(i);else if(checki=')')if(STACK.empty()cerr<&l

25、t;"有多余的右括號"<<endl;/暫時不記錄匹配位置locationcout<<"請重新輸入:"<<endl;return false;elseSTACK.pop();if(!STACK.empty()/暫時不記錄匹配位置locationcerr<<"有多余的左括號"<<endl;cout<<"請重新輸入:"<<endl;return false;/cout<<check<<endl;return tru

26、e;/*檢測是否是字母是返回true,否則false*/int is_letter(char check)if(check>='a'&&check<='z'|check>='A'&&check<='Z')return true;return false;/*添加交操作符“+”，便于中綴轉(zhuǎn)后綴表達式例如 abb->a+b+b*/string add_join_symbol(string add_string)/* 測試終止符0string check_string = &

27、quot;abcdefg0aaa"cout<<check_string<<endl;int length = check_string.size();char * check = new char2*length;strcpy(check,check_string.c_str();cout<<check<<endl;char *s = "ssss0 aa"cout<<s<<endl;string a(s);cout<<a<<endl;*/int length = add

28、_string.size();int return_string_length = 0;char *return_string = new char2*length;/做多是兩倍char first,second;for(int i=0;i<length-1;i+)first = add_string.at(i);second = add_string.at(i+1);return_stringreturn_string_length+ = first;/若第二個是字母、第一個不是'('、'|'都要添加if(first!='('&&

29、amp;first!='|'&&is_letter(second)return_stringreturn_string_length+ = '+'/若第二個是'(',第一個不是'|'、'(',也要加else if(second='('&&first!='|'&&first!='(')return_stringreturn_string_length+ = '+'/將最后一個字符寫入return_strin

30、greturn_string_length+ = second;return_stringreturn_string_length = '0'string STRING(return_string);cout<<"加'+'后的表達式："<<STRING<<endl;return STRING;/*優(yōu)先級表： #(*|+)isp 017538icp 086421*/in stack priority 棧內(nèi)優(yōu)先級int isp(char c)switch(c)case '#': return 0

31、;case '(': return 1;case '*': return 7;case '|': return 5;case '+': return 3;case ')': return 8;/若走到這一步，說明出錯了cerr<<"ERROR!"<<endl;return false;/in coming priority 棧外優(yōu)先級int icp(char c)switch(c)case '#': return 0;case '(': r

32、eturn 8;case '*': return 6;case '|': return 4;case '+': return 2;case ')': return 1;/若走到這一步，說明出錯了cerr<<"ERROR!"<<endl;return false;/*中綴表達式轉(zhuǎn)后綴表達式*/string postfix(string e)/設(shè)定e的最后一個符號式“#”，而其“#”一開始先放在棧s的棧底e = e+"#"stack<char> s;char

33、ch = '#',ch1,op;s.push(ch);/讀一個字符string out_string = ""int read_location = 0;ch = e.at(read_location+);while(!s.empty()if(is_letter(ch)out_string = out_string + ch;/cout<<ch;ch = e.at(read_location+);else/cout<<"輸出操作符："<<ch<<endl;ch1 = s.top();if(isp(ch1)<icp(ch)s.push(ch);/cout<<"壓棧"<<ch<<" 讀取下一個"<<endl;ch = e.at(read_location+);else if(isp(ch1)>icp(ch)op = s.top();s.pop();/cout<&