THOMPSON-算法的实现

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

2、A为止。规那么1.对& ,构造NFAstart这里i是新的开场状态，f是新的承受状态。很明显这个NFA识别 规那么2.对于工中的每个符号a,构造NFAstart/1同样，i是新的开场状态，f是新的承受状态。这个NFA识别a规那么3 .如果N(s)和Nt)是正规表达式s和t的NFA那么： 对于正规表达式s | t,可构造复合的NFANs|t)：对于正规表达式s*,构造复合的NFA Ns*):对于正规表达式st,可构造复合的NFA N(st):start对于括起来的正规表达式(s), 使用N ( s)本身作为它的NFA在构造过程中，每次构造的新状态都要赋予不同的名字。这样，任何NFA的两个状态都具

3、有不同的名字。即使同一符号在r中出现屡次，我们也要为该符号的每个实例创立一个独立的带有自己状态的NFA五.程序设计框架钿氐1丄盲垢入一曙 fl*rito ?() vri ta UweaC梵frf敢殳仃翻开甫立ftiA tr#B!H*iftgfi輕 E l U3C- GC话取輩词咖1沖宇摊get maxt4wa?0c-ijikrtiJT1 r:0jju kAjd(ril icAhJ5譬r&X：:- a llit*-：氏丄年荷iic-ui 苗0六.程序流程图七实验代码核心代码如下：#ifndef THOMPSON #defi ne THIMPSON_H#in elude #in clude #in

4、 clude #in clude using n amespace std;#defi ne MAX 100 /节点，定义成结构体，便于以后扩展struct statestring StateName;；/边空转换符永#表示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

5、CELL_NUM = 0;/函数声明void in put(stri ng&);int check_legal(stri ng);int check_character(stri 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 expres

6、s_2_NFA(stri ng);/处理a|bcell do_U ni te(cell,cell);/处理abcell do_Join( cell,cell);/处理a*cell 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 Regu

7、lar_Expressi on = (a|b)*abb;cell NFA_Cell;Regular_Expressi on = (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);/显

8、示Display(NFA_Cell);/*表达式转NFA处理函数，返回最终的NFA吉合*/cell express_2_NFA(stri ng expressi on)int len gth = expressi on. size();char eleme nt;cell Cell,Left,Right;stack STACK;for(i nt i=0;ile ngth;i+)eleme nt = expressi on. at(i); switch(eleme nt) case T：Right = STACK.top();STACK.pop();Left = STACK.top();STAC

9、K.pop();Cell = do_Un ite(Left,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);

10、STACK.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.StartState = StartState;Edge

11、l.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 nsSymbol = #;Edge4.StartState = Right.EdgeSe

12、tRight.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+ = Edgel;NewCell.EdgeSetNewCell.EdgeCou nt+ = Edge2;NewCe

13、ll.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，将Left返回/将Right中所有以StartState开头的边全部修改，f

14、or(i nt i=0;iRight.EdgeCou nt;i+)Right.EdgeSeti.StartState = Left.E ndState; STATE_NUM-; Right.EdgeSeti.E ndState = Left.E ndState; STATE_NUM-;Right.StartState = Left.E ndState;cell_EdgeSet_Copy(Left,Right);/将Left的完毕状态更新为Right的完毕状态Left.E ndState = Right.E ndState;return Left;/处理a*cell do_Star(cell C

15、ell)-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 nsSymbol = #;Edge2.StartState = Cell.E ndState;Edge2.E ndState = Cell.StartStat

16、e;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 = #;/构建单元/ 先将 Cell 的 EdgeSet 复制到 NewCell cell_EdgeSet_Copy(NewCell,Cell);/将新构建的四条边参加EdgeSetNewCell.EdgeSetN

17、ewCell.EdgeCou nt+ = 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;/处理acell do_Cell(char eleme nt)-cell NewCell;N

18、ewCell.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 nsSymbol = eleme nt;/构建单元NewCell.EdgeSetNewCell.EdgeCou nt+ = NewEdge;NewCell.StartState = NewCell.EdgeSetO.

19、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_co unt = Source.EdgeCo unt;for(i nt i=0;iS_co un t;i+)Dest in ati on .EdgeSetD_co un t+i = Source.EdgeSeti;Desti

20、 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_NUM+;return n ewState;/接收输入正规表达式，RegularExpression 作为回传函数void in put(stri ng &RegularExpressi on)cout RegularExpressio n;

21、此时为1az AZendl;while(!check_legal(RegularExpressi on);coutRegularExpressi onen dl;/*检测输入的正那么表达式是否合法*/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(s

22、tri ng check_stri ng)int len gth = check_stri ng.size();for(i nt i=O;ile ngth;i+)char check = 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;return true;/*先检查括号是否匹配*合法返回true,非法返回

23、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 STACK;for(i nt i=O;ile ngth;i+)if(checki=()STACK.push(i);else if(checki=)if(STACK.empty()locati oncerr有多余的右括号endl;

24、暂时不记录匹配位置cout请重新输入:endl;return false;elseSTACK.pop();if(!STACK.empty()/暂时不记录匹配位置locationcerr有多余的左括号endl; cout请重新输入:endl; return false;coutcheck=a&check=A &checka+b+b*/string add_join_symbol(string add_string) - -/*测试终止符0string check_string = abcdefgOaaa; coutcheck_stri nge ndl;int len gth = check_st

25、ri ng.size(); char * check = new char2*le ngth; strcpy(check,check_stri ng.c_str(); coutchecke ndl;char *s = ssss0 aa;coutse ndl; stri ng a(s); coutae ndl;*/int len gth = add_stri ng.size();int return_stri ng_len gth = 0;char *return_stri ng = new char2*le ngth;/做多是两倍char first,sec ond;for(i nt i=0;

26、ile ngth-1;i+)first = add_stri ng.at(i);sec ond = add_stri ng.at(i+1);retur n_stri ngretur 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!=()retur n_stri ngretur

27、 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力+后的表达式：STRINGendl;return STRING;/*优先级表:#(*isp017icp086*/in stack priority栈优先级int isp(char c)switch(c)case #: retur n 0;case (: retu

28、r n 1;case *: retur n 7;case T： return 5;case +: retur n 3;case ): retur n 8;/假设走到这一步，说明出错了cerrERROR!e ndl;return false;/in coming 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;/假设走到这一步，说明出错了cerrERROR!e

29、 ndl;return false;/*中缀表达式转后缀表达式*/string postfix(string e)s的栈底/设定e的最后一个符号式“ # ，而其“ # 一开场先放在栈 e = e+#;stack 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;coutch;ch = e.at(read_locatio n+);elsecout输出操作符：che ndl;ch1 = s.top();if(isp(ch1)icp(c