THOMPSON-算法的实现.doc

文档介绍：--------------------------校验:_____________-----------------------日期:_____________THOMPSON-算法的实现实验二:。、,输出一个接受L(r)的NFA;++语言,实现该算法;;、Windows操作系统、VisualC++程序集成环境。:从正规表达式构造NFA输入:字母表Σ上的一个正规表达式r输出:接受L(r)的NFAN方法:将r分解成最基本的子表达式,使用下面的规则1和2为r的每个基本符号(ε或Σ中的符号)构造NFA。用规则3逐步组合前面构造的NFA,直到获得整个正规表达式的NFA为止。,构造NFA这里i是新的开始状态,f是新的接受状态。很明显这个NFA识别{ε}。,构造NFA同样,i是新的开始状态,f是新的接受状态。这个NFA识别{a}。(s)和N(t)是正规表达式s和t的NFA,则:①对于正规表达式s|t,可构造复合的NFAN(s|t):②对于正规表达式st,可构造复合的NFAN(st):③对于正规表达式s*,构造复合的NFAN(s*):④对于括起来的正规表达式(s),使用N(s)本身作为它的NFA。在构造过程中,每次构造的新状态都要赋予不同的名字。这样,任何NFA的两个状态都具有不同的名字。即使同一符号在r中出现多次,我们也要为该符号的每个实例创建一个独立的带有自己状态的NFA。:#ifndefTHOMPSON_H#HIMPSON_H#include<iostream>#include<stack>#include<string>usingnamespacestd;#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);//ingpriorityintscp(char);//表达式转NFAcellexpress_2_NFA(string);//处理a|bcelldo_Unite(cell,cell);//处理abcelldo_Join(cell,cell);//处理a*celldo_Star(cell);//处理acelldo_Cell(char);//将一个单元的边的集合复制到另一个单元voidcell_EdgeSet_Copy(cell&,cell);//产生一个新的状态节点,便于管理statenew_StateNode();//显示voidDisplay(cell);#endif//主函数,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); //表达式转NFA NFA_Cell=express_2_NFA(Regular_Expression); //显示 Display(NFA_Cell);}/**表达式转NFA处理函数,返回最终的NFA结合*