THOMPSON算法的实现

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

2、止。规则1.对£ ,构造NFA这里i是新的开始状态，f是新的接受状态。很明显这个NFA识别汀。 规则2.对于2中的每个符号a,构造NFA同样，i是新的开始状态，f是新的接受状态。这个NFA识别a 0规则3 .如果N(s)和对于正规表达式S*,构造复合的NFA Ns*):N(t)是正规表达式S和t的NFA则：对于括起来的正规表达式(S), 使用N ( S)本身作为它的NFA在构造过程中，每次构造的新状态都要赋予不同的名字。这样，任何NFA的两个状态都具有不同的名字。即使同一符号在 r中出现多次，我们也要为该 符号的每个实例创建一个独立的带有自己状态的 NFA五. 程序设计框架六. 程序

3、流程图七.实验代码核心代码如下:#ifndef THO MP SON_H #defi ne THI MP SON_H #in elude <iostream> #in clude <stdio.h> #in clude <stack> #in clude <stri ng> using n ames pace std;#defi ne MAX 100节点，定义成结构体，便于以后扩展struct statestri ng StateName;边空转换符永#'表示struct edgestate StartState;state En dSt

4、ate; 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 inpu t(stri ng&);int check_legal(stri ng);int check_character(stri ng);int check_ paren thesis(stri ng);int is_letter(char

5、);stri ng add_j oin _symbol(stri ng);中缀转后缀-stri ng po stfix(stri ng);优先级 in stack p riorityint isp( char);优先级 in coming p riorityint scp( char);表达式转NFAcell exp ress_2_NFA(stri ng);处理a|bcell do_U ni te(cell,cell);处理abcell do_Jo in( cell,cell);处理a*cell do_Star(cell);处理acell do_Cell(char);将一个单元的边的集合复制到

6、另一个单元void cell_EdgeSet_Co py(cell & ,cell);产生一个新的状态节点，便于管理state new_StateNode();显示void Dis play(cell);#e ndif#in clude "Tho mpson .h"主函数，void mai n()stri ng Regular_Ex pressi on = "(a|b)*abb"cell NFA_Cel|-Regular_Ex pressi on = "(a|b)*abb"接受输入input(Regular_Expressio

7、n);/ 调试需要先屏蔽/添加“ + ”屜于转后缀表达式Regular_Ex pressi on = add_join_symbol(Regular_Ex pressi on);中缀转后缀Regular_Ex pressi on = po stfix(Regular_Ex pressi on);/表达式转NFA-NFA_Cell = ex press_2_NFA(Regular_Ex pressio n);/显示Dis play(NFA_Cell);/*表达式转NFA处理函数，返回最终的NFA结合*/cell exp ress_2_NFA(stri ng exp ressi on) "

8、;"int len gth = exp ressi on. size();char eleme nt;cell Cell,Left,Right;stack<cell> STACK;for(i nt i=0;i<le ngth;i+)eleme nt = exp ressi on. at(i);switch(eleme nt)case T：Right = STACK.to p();STACK .pop();Left = STACK.to p();STACK .pop();Cell = do_U nite(Left,Right);STACK. push(Cell);br

9、eak;case '*':Left = STACK.to p();STACK .pop();Cell = do_Star(Left);STACK. push(Cell);break;case '+':Right = STACK.to p();STACK .pop();Left = STACK.to p();STACK .pop();Cell = do_Joi n(Left,Right);STACK. push(Cell); break;default:Cell = do_Cell(eleme nt);STACK.push(Cell);cout<<&q

10、uot;处理完毕!"<<endl;Cell = STACK.t op();STACK .pop(); return Cell;处理a|bcell do_Un ite(cell Left,cell Right)"cell NewCell;NewCell.EdgeCou nt=O; edge Edge1,Edge2,Edge3,Edge4;/获得新的新状态节点state StartState = n ew_StateNode();state En dState = new_StateNode();/构建边Edge1.StartState = StartState;E

11、dge1.E ndState = Left.EdgeSet0.StartState;Edge1.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 nsSymbol = '#'E

12、dge4.StartState = Right.EdgeSetRight.EdgeCou nt-1.E ndState;Edge4.E ndState = En dState;Edge4.Tra nsSymbol = '#'/构建单元/先将 Left 和 Right 的 EdgeSet 复制到 NewCell cell_EdgeSet_Co py(NewCell,Left);cell_EdgeSet_C op y(NewCell,Right);将新构建的四条边加入EdgeSetNewCell.EdgeSetNewCell.EdgeCou nt+ = Edge1;NewCell.

13、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的开始状态合并，将Right的边复制给Left

14、，将Left返回将Right中所有以StartState开头的边全部修改，for(i nt i=0;i<Right.EdgeCou nt;i+)if(Right.EdgeSeti.StartState.StateN pare(Right.StartState.StateName)=O) Right.EdgeSeti.StartState = Left.E ndState;STATE_NUM-;elseif(Right.EdgeSe ti.E ndState.StateName.co mp are(Right.StartState.StateName)=O)Right.EdgeSeti.E

15、 ndState = Left.E ndState; STATE_NUM-;Right.StartState = Left.E ndState;cell_EdgeSet_Co py(Left,Right);将Left的结束状态更新为 Right的结束状态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_St

16、ateNode(); state En dState = n ew_StateNode();/构建边Edge1.StartState = StartState;Edge1.E ndState = En dState;Edge1.Tra nsSymbol = '#'Edge2.StartState = Cell.E ndState;Edge2.E ndState = Cell.StartState;Edge2.Tra nsSymbol = '#'Edge3.StartState = StartState;Edge3.E ndState = Cell.StartSt

17、ate;Edge3.Tra nsSymbol = '#'Edge4.StartState = Cell.E ndState;Edge4.E ndState = En dState;Edge4.Tra nsSymbol = '#'/构建单元/先将 Cell 的 EdgeSet 复制到 NewCellcell_EdgeSet_Co py(NewCell,Cell);将新构建的四条边加入EdgeSetNewCell.EdgeSetNewCell.EdgeCou nt+ = Edge1;NewCell.EdgeSetNewCell.EdgeCou nt+ = Edge2

18、;NewCell.EdgeSetNewCell.EdgeCou nt+ = Edge3;NewCell.EdgeSetNewCell.EdgeCou nt+ = Edge4;/构建NewCell的启示状态和结束状态NewCell.StartState = 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 e

19、w_StateNode();state En dState = new_StateNode();/构建边NewEdge.StartState = StartState;NewEdge.E ndState = En dState;NewEdge.Tra nsSymbol = eleme nt;/构建单元NewCell.EdgeSetNewCell.EdgeCou nt+ = NewEdge;NewCell.StartState = NewCell.EdgeSet0.StartState;NewCell.E ndState = NewCell.EdgeSet0.E ndState;/EdgeCou

20、 nt 此时为 1 return NewCell;void cell_EdgeSet_C opy( cell& Desti nati on, cell Source)" "int D_co unt = Dest in ati on .EdgeCo unt; int S_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

21、_co unt;/*获得新的状态节点，统一产生，便于管理，不能产生重复的状态并添加到state_set数组中*/state new_StateNode() "state n ewState;newState.StateName = STATE_NUM+65;/ 转换成大写字母 STATE_NUM+;return n ewState;接收输入正规表达式，RegularExpression作为回传函数 void inpu t(stri ng &RegularEx pressi on)（操作符：（）* |;字符集：az AZ） "<<endl; cout<

22、;<"请输入正则表达式： docin> >RegularEx pressio n; while(!check_legal(RegularEx pressi on); /coutvvRegularEx pressi on<<en dl;/*检测输入的正则表达式是否合法*/int check_legal(stri ng check_stri ng)" "if(check_character(check_stri ng)&&check_ paren thesis(check_stri ng) " "一 &

23、quot;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 check = check_stri ng.at(i);if(is_letter(check)/小写和大写之间有5个字符，故不能连续判断/cout<<"字母合法"else

24、if(check='('|check=')'|check='*'|check=T)/cout<<"操作符 合法"elsecout<<"含有不合法的字符!"<<endl;cout<<"请重新输入:"<<endl;return false;return true;/*先检查括号是否匹配*合法返回true,非法返回false*/int check_ paren thesis(stri ng check_stri ng) "

25、"int len gth = check_stri ng.size(); char * check = new charle ngth; strc py (check,check_stri ng.c_str(); /char a = check_stri ng.at(1); stack <in t> STACK;for(i nt i=0;i<le ngth;i+) if(checki='(')STACK. push(i); else if(checki=')') if(STACK.e mp ty()cerr<<"

26、有多余的右括号"<<endl;/暂时不记录匹配位置locationcout<<"请重新输入:"<<endl;return false; elseSTACK. pop();if(!STACK.e mp ty()/暂时不记录匹配位置locationcerr<<"有多余的左括号"<<endl; cout<<"请重新输入:"<<endl; return false;/cout<<check<<e ndl; return tru

27、e;/*检测是否是字母是返回true,否则false*/int is_letter(char check)if(check>='a '&&check<='z'|check>='A '&&check<='Z') return true;return false;/*添加交操作符“ + ”，便于中缀转后缀表达式 例如 abb->a+b+b*/stri ng add_j oin _symbol(stri ng add_stri ng) " "/* 测试终止

28、符0stri ng check_stn ng = "abcdefg'Oaaa" cout<<check_stn ng<<e ndl;int len gth = check_stri ng.size();char * check = new char2*le ngth; strc py (check,check_stn ng.c_str(); cout<<check<<e ndl;char *s = "ssssO aa"cout<<s<<e ndl;stri ng a(s);c

29、out<<a<<e ndl;*/int len gth = add_stri ng.size();int return_stri ng_len gth = 0;char *return_string = new char2*length;/ 做多是两倍 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_stn ngretur n_stn ng_le ngth+ = first;/若第二个是字母、

30、第一个不是('、I'都要添加if(first!='('&&first!=T&&is_letter(seco nd)retur n_stri ngretur n_stri ng_le ngth+ = '+' " ""/若第二个是'(',第一个不是T、(',也要加else if(seco nd='('&&first!='|'&&first!='(')retur n_stri ngretu

31、r 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' stri ng STRING(return_stri ng);cout<<"加'+'后的表达式："<<STRING<<endl; return STRING;/*优先级表：#0isp icp *

32、/in stack p riority int isp( char c) switch(c)case '#': retur n 0;栈内优先级0case '(': retur n 1;case '*': return 7;case T： return 5;case '+': retur n 3;case ')': retur n 8;/若走到这一步，说明出错了 cerr<<"ERROR!"<<e ndl;return false;/in coming p riority

33、栈外优先级 int icp( char c)switch(c)case '#': return 0;case '(': retur n 8;case '*': return 6;case T： return 4;case '+': retur n 2;case ')': retur n 1;/若走到这一步，说明出错了cerr<<"ERROR!"<<e ndl; return false;/*中缀表达式转后缀表达式*/stri ng po stfix(stri ng e)/

34、设定e的最后一个符号式“ #”，而其“ #”一开始先放在栈s的栈底 e = e+"#"stack<char> s;char ch = '#',ch1, op;s.pu sh(ch);/读一个字符stri ng out_stri ng =""int read_locati on = 0;ch = e.at(read_locati on+); while(!s.e mp ty()if(is_letter(ch)out_stri ng = out_stri ng + ch; /cout<<ch;ch = e.at(rea

35、d_locatio n+);else/cout<<"输出操作符："<<ch<<endl;ch1 = s.t op();if(is p(ch1)<ic p( ch)s.pu sh(ch);/cout<<"压栈"<<ch<<"读取下一个"<<endl; ch = e.at(read_locati on+); "else if(is p(ch1)>ic p(ch)op = s.to p();s.popO;/cout<<"退栈"<<op<<"添加到输出字符串 "<<endl; out_stri ng = out_stri ng + op;/cout< <op; elseop = s.to p();s.popO；/cout<<"退栈"<<op<<"但不添加到输入字符串"<<endl;if(op='(')ch = e.at(read_locati on+);/cout<<e ndl;cout<<"