《THOMPSON算法的实现》由会员分享，可在线阅读，更多相关《THOMPSON算法的实现（19页珍藏版）》请在金锄头文库上搜索。
1、THOMPSON-算法的实现 作者： 日期：实验二：THOMPSON 算法的实现一实验目的掌握THOMPSON 算法原理和方法。二实验要求、内容及步骤1.输入字母表上的正规式r，输出一个接受L（r）的NFA；2.采用C+语言，实现该算法；3.编制测试程序4.调试程序；三实验设备计算机、Windows 操作系统、Visual C+ 程序集成环境。四实验原理Thompson构造法：从正规表达式构造NFA输入：字母表上的一个正规表达式r输出：接受L(r)的NFA N方法：将r分解成最基本的子表达式，使用下面的规则1和2为r的每个基本符号（ 或中的符号）构造NFA。用规则3逐步组合前面构造的NFA，直
2、到获得整个正规表达式的NFA为止。规则1. 对, 构造NFA 这里 i 是新的开始状态，f是新的接受状态。很明显这个NFA识别。 规则2. 对于中的每个符号a，构造NFA同样，i 是新的开始状态， f 是新的接受状态。 这个NFA识别 a。规则3 . 如果N(s) 和 N(t) 是正规表达式s和t的NFA，则：对于正规表达式 s | t, 可构造复合的NFA N(s|t): 对于正规表达式 st, 可构造复合的NFA N(st)：对于正规表达式 s*, 构造复合的NFA N(s*):对于括起来的正规表达式 (s), 使用N (s) 本身作为它的NFA。在构造过程中，每次构造的新状态都要赋予不同
3、的名字。这样，任何NFA的两个状态都具有不同的名字。即使同一符号在r中出现多次，我们也要为该符号的每个实例创建一个独立的带有自己状态的NFA。五.程序设计框架六.程序流程图七.实验代码核心代码如下：#ifndef THOMPSON_H#define THIMPSON_H#include #include #include #include using namespace std;#define MAX 100/节点，定义成结构体，便于以后扩展struct statestring StateName;/边 空转换符永#表示struct edgestate StartState;state End
4、State;char TransSymbol;/单元struct celledge EdgeSetMAX;int EdgeCount;state StartState;state EndState;/全局变量声明/int EDGE_NUM = 0;int STATE_NUM = 0;/int CELL_NUM = 0;/函数声明void input(string&);int check_legal(string);int check_character(string);int check_parenthesis(string);int is_letter(char);string add_jo
5、in_symbol(string);/中缀转后缀string postfix(string);/优先级 in stack priorityint isp(char);/优先级 in coming priorityint scp(char);/表达式转NFAcell express_2_NFA(string);/处理 a|bcell do_Unite(cell,cell);/处理 abcell do_Join(cell,cell);/处理 a*cell do_Star(cell);/处理 acell do_Cell(char);/将一个单元的边的集合复制到另一个单元void cell_EdgeS
6、et_Copy(cell&,cell);/产生一个新的状态节点，便于管理state new_StateNode();/显示void Display(cell);#endif#include Thompson.h/主函数，void main()string Regular_Expression = (a|b)*abb;cell NFA_Cell;Regular_Expression = (a|b)*abb;/接受输入input(Regular_Expression);/调试需要先屏蔽/添加“+”，便于转后缀表达式Regular_Expression = add_join_symbol(Regul
7、ar_Expression);/中缀转后缀Regular_Expression = postfix(Regular_Expression);/表达式转NFANFA_Cell = express_2_NFA(Regular_Expression);/显示Display(NFA_Cell);/*表达式转NFA处理函数,返回最终的NFA结合*/cell express_2_NFA(string expression)int length = expression.size();char element;cell Cell,Left,Right;stack STACK;for(int i=0;ilen
8、gth;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;case *:Left = STACK.top();STACK.pop();Cell = do_Star(Left);STACK.push(Cell);break;case +:Right = STACK.top();STACK.pop();Left = ST
9、ACK.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();return Cell;/处理 a|bcell do_Unite(cell Left,cell Right)cell NewCell;NewCell.EdgeCount=0;edge Edge1,Edge2,Edge3,Edge4;/获得新的新状态节点state St
10、artState = new_StateNode();state EndState = new_StateNode();/构建边Edge1.StartState = StartState;Edge1.EndState = Left.EdgeSet0.StartState;Edge1.TransSymbol = #;Edge2.StartState = StartState;Edge2.EndState = Right.EdgeSet0.StartState;Edge2.TransSymbol = #;Edge3.StartState = Left.EdgeSetLeft.EdgeCount-1
11、.EndState;Edge3.EndState = EndState;Edge3.TransSymbol = #;Edge4.StartState = Right.EdgeSetRight.EdgeCount-1.EndState;Edge4.EndState = EndState;Edge4.TransSymbol = #;/构建单元/先将Left和Right的EdgeSet复制到NewCellcell_EdgeSet_Copy(NewCell,Left);cell_EdgeSet_Copy(NewCell,Right);/将新构建的四条边加入EdgeSetNewCell.EdgeSetN
12、ewCell.EdgeCount+ = Edge1;NewCell.EdgeSetNewCell.EdgeCount+ = Edge2;NewCell.EdgeSetNewCell.EdgeCount+ = Edge3;NewCell.EdgeSetNewCell.EdgeCount+ = Edge4;/构建NewCell的启示状态和结束状态NewCell.StartState = StartState;NewCell.EndState = EndState;return NewCell;/处理 abcell do_Join(cell Left,cell Right)/将Left的结束状态和R
13、ight的开始状态合并，将Right的边复制给Left，将Left返回/将Right中所有以StartState开头的边全部修改，for(int i=0;iRight.EdgeCount;i+)if(Right.EdgeSeti.StartState.StateNpare(Right.StartState.StateName)=0)Right.EdgeSeti.StartState = Left.EndState;STATE_NUM-;else if(Right.EdgeSeti.EndState.StateNpare(Right.StartState.StateName)=0)Right.EdgeSeti.EndState = Left.EndState;STATE_NUM-;Right.StartState = Left.EndState;cell_EdgeSet_Copy(Left,Right);
