THOMPSON算法地实现

1、实用文案实验二：THOMPSON法的实现一. 实验目的掌握THOMPSON法原理和方法。二. 实验要求、内容及步骤1. 输入字母表上的正规式r，输出一个接受L（ r ）的NFA2. 采用C+语言，实现该算法；3. 编制测试程序4. 调试程序；三. 实验设备计算机、Windows操作系统、Visual C+程序集成环境。四. 实验原理Thompsor构造法：从正规表达式构造 NFA输入：字母表工上的一个正规表达式 r输出：接受L（r）的NFA N方法：将r分解成最基本的子表达式，使用下面的规则 1和2为r的每个 基本符号（&或工中的符号）构造NFA用规则3逐步组合前面构造的NFA 直到获

2、得整个正规表达式的 NFA为止。规则1.对& ,构造NFAstart这里i是新的开始状态，f是新的接受状态。很明显这个NFA识别 £ 规则2.对于工中的每个符号a,构造NFA标准文档是新的接受状态。这个NFA识别a。同样，i是新的开始状态，规则3 .如果N(s)和N(t) 是正规表达式s和t的NFA则: 对于正规表达式s | t,可构造复合的NFA N(s|t):CCD z Ci 对于正规表达式st,可构造复合的NFA N(st): 对于正规表达式 s*,构造复合的NFA Ns*): 对于括起来的正规表达式(s), 使用N ( s)本身作为它的NFA在构造过程中，每次构造的新

3、状态都要赋予不同的名字。这样，任何NFA的两个状态都具有不同的名字。即使同一符号在r中出现多次，我们也要为该符号的每个实例创建一个独立的带有自己状态的NFA五. 程序设计框架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;标准文档实用文案#defi ne MAX 100/节点，定义成结构体，便于以后扩展struct statestring S

5、tateName;；/边空转换符永#表示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;/函数声明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);/中缀转后缀string postfix(string);/ 优先级 in stack priorityint isp(char);/ 优先级 in coming priorityint scp(char);/表达式转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);/将二个单元的边的集合复制到另一个单元void cell_EdgeSet_Copy(cell & ,cell);/产生一个新的状态节点，便于管理state new_StateNode();/显示void Display(cell);#en dif#in clude "Thomps on .h"/主函数，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);/调试需要先屏蔽/添加"+”，便于转后缀表达式Regular_Expressi on = addoin_symbol(Regular_Expressi on);/中缀转后缀Regular_Expressi on = postfix(Regular_Expressi on);/表达式转NFANFA_Cell = express_2_NFA(Regular_Expressio n);/显示Display(NFA_Cell);/*表达式转NFA处理函数，返回最终的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)标准文档 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;/获得新的新状态节点state StartState = n ew_StateNode(); state En dState = n ew_StateNode();/构建边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 = '#'/构建单元/ 先将 Left 和 Right 的 EdgeSet 复制到 NewCell cell_EdgeSet_Copy(NewCell,Left);cell_EdgeSet_Copy(NewCell,Right);/将新构建的四条边加入EdgeSetNewCell.EdgeSetNewCell.EdgeCou nt

14、+ = Edgel;NewCell.EdgeSetNewCell.EdgeCou nt+ = Edge2;NewCell.EdgeSetNewCell.EdgeCou nt+ = Edge3;NewCell.EdgeSetNewCell.EdgeCou nt+ = Edge4;/构建NewCell的启示状态和结束状态NewCell.StartState = StartState;NewCell.E ndState = En dState;return NewCell;/处理abcell do_Joi n( cell Left,cell Right)-/将Left的结束状态和 Right的开始状

15、态合并，将Right的边复制给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的结束状态更新为Right的结束状态

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;/获得新的新状态节点state StartState = n ew_StateNode(); state En dState = n ew_StateNode();/构建边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、'/构建单元/ 先将 Cell 的 EdgeSet 复制到 NewCell cell_EdgeSet_Copy(NewCell,Cell);/将新构建的四条边加入EdgeSetNewCell.EdgeSetNewCell.EdgeCou nt+ = Edgel;NewCell.EdgeSetNewCell.EdgeCou nt+ = Edge2;NewCell.EdgeSetNewCell.EdgeCou nt+ = Edge3;NewCell.EdgeSetNewCell.EdgeCou nt+ = Edge4; /构建NewCell的启示状态和结束状态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;/获得新的新状态节点state StartState = n ew_StateNode();state En dState = n ew_StateNode();/构建边NewEdge.StartState = StartState;NewEdge.E ndState = En dState;NewEdge.Tra

20、nsSymbol = eleme nt;/构建单元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; - -/*获得新的状态节点，统一产生，便于管理，不能产生重复的状态并添加到state_set 数组中*/state new_StateNode()state n ewState;n ewState.StateName = STATE_NUM+65; 转换成大写字母 STATE_N

22、UM+;return n ewState;/接收输入正规表达式，RegularExpression 作为回传函数void in put(stri ng &RegularExpressi on)cout<<"请输入正则表达式：(操作符：()* |;字符集：此时为1az AZ) "<<endl;docin> >RegularExpressio n;while(!check_legal(RegularExpressi on); cout<<RegularExpressi on<<en dl;/*检测输入的正则表达

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个字符，故不能连续判断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; /*添加交操作符"+”，便于中缀转后缀表达式 例如 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<<"力+'后的表达式："<<STRING<<endl;return STRING;/*优先级表：# ( * | + )isp 0

32、17538icp 086421*/in stack priority栈内优先级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栈外优先级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;/*中缀表达式转后缀表达式*/string postfix(strin

34、g e)s的栈底/设定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