thompson算法地实现

《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逐步组合前面构造

2、的NFA，直到获得整个正规表达式的NFA为止。规则1.对ε,构造NFA标准文档实用文案这里i是新的开始状态，f是新的接受状态。很明显这个NFA识别{ε}。规则2.对于Σ中的每个符号a，构造NFA同样，i是新的开始状态，f是新的接受状态。这个NFA识别{a}。规则3.如果N(s)和N(t)是正规表达式s和t的NFA，则：①对于正规表达式s

3、t,可构造复合的NFAN(s

4、t):②对于正规表达式st,可构造复合的NFAN(st)：③对于正规表达式s*,构造复合的NFAN(s*):标准文档实用文案④对于括起来的正规表达式(s),使用N(s)本身作为它的NFA

5、。在构造过程中，每次构造的新状态都要赋予不同的名字。这样，任何NFA的两个状态都具有不同的名字。即使同一符号在r中出现多次，我们也要为该符号的每个实例创建一个独立的带有自己状态的NFA。标准文档实用文案五.程序设计框架标准文档实用文案六.程序流程图七.实验代码核心代码如下：#ifndefTHOMPSON_H#defineTHIMPSON_H#include#include#include#includeusingnamespacestd;标准文档实用文案#defineMAX100//

6、节点，定义成结构体，便于以后扩展structstate{stringStateName;};//边空转换符永'#'表示structedge{stateStartState;stateEndState;charTransSymbol;};//单元structcell{edgeEdgeSet[MAX];intEdgeCount;stateStartState;stateEndState;};//全局变量声明//intEDGE_NUM=0;intSTATE_NUM=0;//intCELL_NUM=0;//函数声明voidinput(string&);int

7、check_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

8、b标准文档实用文案celldo_

9、Unite(cell,cell);//处理abcelldo_Join(cell,cell);//处理a*celldo_Star(cell);//处理acelldo_Cell(char);//将一个单元的边的集合复制到另一个单元voidcell_EdgeSet_Copy(cell&,cell);//产生一个新的状态节点，便于管理statenew_StateNode();//显示voidDisplay(cell);#endif#include"Thompson.h"//主函数，voidmain(){stringRegular_Expression="(a

10、

11、b)*abb";cellNFA_Cell;Regular_Expression="(a

12、b)*abb";//接受输入input(Regular_Expression);//调试需要先屏蔽//添加“+”，便于转后缀表达式Regular_Expression=add_join_symbol(Regular_Expression);//中缀转后缀Regular_Expression=postfix(Regular_Expression);//表达式转NFANFA_Cell=express_2_NFA(Regular_Expression);//显示Dis

13、play(NFA_Cell);}/**表达式转NFA处理函数,返回最终的NFA结合*/cellexpress