THOMPSON-算法的实现

第1页实验二：THOMPSON算法的实现一．实验目的掌握THOMPSON算法原理和方法。二．实验要求、内容及步骤1.输入字母表上的正规式r，输出一个接受L（r）的NFA；2.采用C++语言，实现该算法；3.编制测试程序4.调试程序；三．实验设备计算机、Windows操作系统、VisualC++程序集成环境。四．实验原理Thompson构造法：从正规表达式构造NFA输入：字母表Σ上的一个正规表达式r输出：接受L(r)的NFAN方法：将r分解成最基本的子表达式，使用下面的规则1和2为r的每个基本符号（ε或Σ中的符号）构造NFA。用规则3逐步组合前面构造的NFA，直到获得整个正规表达式的NFA为止。规则1.对ε,构造NFA第2页这里i是新的开始状态，f是新的接受状态。很明显这个NFA识别{ε}。规则2.对于Σ中的每个符号a，构造NFA同样，i是新的开始状态，f是新的接受状态。这个NFA识别{a}。规则3.如果N(s)和N(t)是正规表达式s和t的NFA，则：①对于正规表达式s|t,可构造复合的NFAN(s|t):②对于正规表达式st,可构造复合的NFAN(st)：③对于正规表达式s*,构造复合的NFAN(s*):第3页④对于括起来的正规表达式(s),使用N(s)本身作为它的NFA。在构造过程中，每次构造的新状态都要赋予不同的名字。这样，任何NFA的两个状态都具有不同的名字。即使同一符号在r中出现多次，我们也要为该符号的每个实例创建一个独立的带有自己状态的NFA。第4页五.程序设计框架第5页六.程序流程图七.实验代码核心代码如下：#ifndefTHOMPSON_H#defineTHIMPSON_H#includeiostream#includestdio.h#includestack#includestringusingnamespacestd;第6页#defineMAX100//节点，定义成结构体，便于以后扩展structstate{stringStateName;};//边空转换符永'#'表示structedge{stateStartState;stateEndState;charTransSymbol;};//单元structcell{edgeEdgeSet[MAX];intEdgeCount;stateStartState;stateEndState;};//全局变量声明//intEDGE_NUM=0;intSTATE_NUM=0;//intCELL_NUM=0;//函数声明voidinput(string&);intcheck_legal(string);intcheck_character(string);intcheck_parenthesis(string);intis_letter(char);stringadd_join_symbol(string);//中缀转后缀stringpostfix(string);//优先级instackpriorityintisp(char);//优先级incomingpriorityintscp(char);//表达式转NFAcellexpress_2_NFA(string);//处理a|bcelldo_Unite(cell,cell);//处理abcelldo_Join(cell,cell);//处理a*celldo_Star(cell);第7页//处理acelldo_Cell(char);//将一个单元的边的集合复制到另一个单元voidcell_EdgeSet_Copy(cell&,cell);//产生一个新的状态节点，便于管理statenew_StateNode();//显示voidDisplay(cell);#endif#includeThompson.h//主函数，voidmain(){stringRegular_Expression=(a|b)*abb;cellNFA_Cell;Regular_Expression=(a|b)*abb;//接受输入input(Regular_Expression);//调试需要先屏蔽//添加“+”，便于转后缀表达式Regular_Expression=add_join_symbol(Regular_Expression);//中缀转后缀Regular_Expression=postfix(Regular_Expression);//表达式转NFANFA_Cell=express_2_NFA(Regular_Expression);//显示Display(NFA_Cell);}/**表达式转NFA处理函数,返回最终的NFA结合*/cellexpress_2_NFA(stringexpression){intlength=expression.size();charelement;cellCell,Left,Right;stackcellSTACK;for(inti=0;ilength;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;第8页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_Join(Left,Right);STACK.push(Cell);break;default:Cell=do_Cell(element);STACK.push(Cell);}}cout处理完毕!endl;Cell=STACK.top();STACK.pop();returnCell;}//处理a|bcelldo_Unite(cellLeft,cellRight){cellNewCell;NewCell.EdgeCount=0;edgeEdge1,Edge2,Edge3,Edge4;//获得新的新状态节点stateStartState=new_StateNode();stateEndState=new_StateNode();//构建边Edge1.StartState=StartState;Edge1.EndState=Left.EdgeSet[0].StartState;Edge1.TransSymbol='#';Edge2.StartState=StartState;Edge2.EndState=Right.EdgeSet[0].StartState;Edge2.TransSymbol='#';Edge3.StartState=Left.EdgeSet[Left.EdgeCount-1].EndState;Edge3.EndState=EndState;Edge3.TransSymbol='#';Edge4.StartState=Right.EdgeSet[Right.EdgeCount-1].EndState;Edge4.EndState=EndState;Edge4.TransSymbol='#';//构建单元//先将Left和Right的EdgeSet复制到NewCell第9页cell_EdgeSet_Copy(NewCell,Left);cell_EdgeSet_Copy(NewCell,Right);//将新构建的四条边加入EdgeSetNewCell.EdgeSet[NewCell.EdgeCount++]=Edge1;NewCell.EdgeSet[NewCell.EdgeCount++]=Edge2;NewCell.EdgeSet[NewCell.EdgeCount++]=Edge3;NewCell.EdgeSet[NewCell.EdgeCount++]=Edge4;//构建NewCell的启示状态和结束状态NewCell.StartState=StartState;NewCell.EndState=EndState;returnNewCell;}//处理abcelldo_Join(cellLeft,cellRight){//将Left的结束状态和Right的开始状态合并，将Right的边复制给Left，将Left返回//将Right中所有以StartState开头的边全部修改，for(inti=0;iRight.EdgeCount;i++){if(Right.EdgeSet[i].StartState.StateName.compare(Right.StartState.StateName)==0){Right.EdgeSet[i].StartState=Left.EndState;STATE_NUM--;}elseif(Right.EdgeSet[i].EndState.StateName.compare(Right.StartState.StateName)==0){Right.EdgeSet[i].EndState=Left.EndState;STATE_NUM--;}}Right.StartState=Left.EndState;cell_EdgeSet_Copy(Left,Right);//将Left的结束状态更新为Right的结束状态Left.EndState=Right.EndState;returnLeft;}//处理a*celldo_Star(cellCell){cellNewCell;NewCell.EdgeCount=0;edgeEdge1,Edge2,Edge3,Edge4;//获得新的新状态节点stateStartState=new_StateNode();stateEndState=new_StateNode();//构建边Edge1.StartState=StartState;Edge1.EndState=EndState;第10页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.TransSymbol='#';//构建单元//先将Cell的EdgeSet复制到NewCellcell_EdgeSet_Copy(NewCell,Cell);//将新构建的四条边加入EdgeSetNewCell.EdgeSet[NewCell.EdgeCount++]=Edge1;NewCell.EdgeSet[NewCell.EdgeCount++]=Edge2;NewCell.EdgeSet[NewCell.EdgeCount++]=Edge3;NewCell.EdgeSet[NewCell.EdgeCount++]=Edge4;//构建NewCell的启示状态和结束状态NewCell.StartState=StartState;NewCell.EndState=EndState;returnNewCell;}//处理acelldo_Cell(charelement){cellNewCell;NewCell.EdgeCount=0;edgeNewEdge;//获得新的新状态节点stateStartState=ne