THOMPSON 算法的实现.docx

《THOMPSON 算法的实现.docx》由会员分享，可在线阅读，更多相关《THOMPSON 算法的实现.docx（13页珍藏版）》请在三一办公上搜索。

1、THOMPSON 算法的实现实验二：THOMPSON 算法的实现 一实验目的 掌握THOMPSON 算法原理和方法。 二实验要求、内容及步骤 1.输入字母表上的正规式r，输出一个接受L的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 第 1 页 这里 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*): 第 2 页 对于括起来的正规表达式 (s), 使用N (s) 本身作为它的NFA。 在构造过程中，每

3、次构造的新状态都要赋予不同的名字。这样，任何NFA的两个状态都具有不同的名字。即使同一符号在r中出现多次，我们也要为该符号的每个实例创建一个独立的带有自己状态的NFA。 第 3 页 五.程序设计框架 第 4 页 六.程序流程图 七.实验代码 核心代码如下： #ifndef THOMPSON_H #define THIMPSON_H #include #include #include #include using namespace std; 第 5 页 #define MAX 100 /节点，定义成结构体，便于以后扩展 struct state string StateName; ; /边

4、空转换符永#表示 struct edge state StartState; state EndState; char TransSymbol; ; /单元 struct cell edge 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(stri

5、ng); int check_parenthesis(string); int is_letter(char); string add_join_symbol(string); /中缀转后缀 string postfix(string); /优先级 in stack priority int isp(char); /优先级 in coming priority int scp(char); /表达式转NFA cell express_2_NFA(string); /处理 a|b cell do_Unite(cell,cell); /处理 ab cell do_Join(cell,cell);

6、/处理 a* cell do_Star(cell); 第 6 页 /处理 a cell do_Cell(char); /将一个单元的边的集合复制到另一个单元 void cell_EdgeSet_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)

7、*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结合 */ cell express_2_N

8、FA(string expression) int length = expression.size; char element; cell Cell,Left,Right; stack STACK; for(int i=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; 第 7 页 case

9、 *: 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; retu

10、rn Cell; /处理 a|b cell do_Unite(cell Left,cell Right) cell NewCell; NewCell.EdgeCount=0; edge Edge1,Edge2,Edge3,Edge4; /获得新的新状态节点 state StartState = new_StateNode; state EndState = new_StateNode; /构建边 Edge1.StartState = StartState; Edge1.EndState = Left.EdgeSet0.StartState; Edge1.TransSymbol = #; Edg

11、e2.StartState = StartState; Edge2.EndState = Right.EdgeSet0.StartState; Edge2.TransSymbol = #; Edge3.StartState = Left.EdgeSetLeft.EdgeCount-1.EndState; Edge3.EndState = EndState; Edge3.TransSymbol = #; Edge4.StartState = Right.EdgeSetRight.EdgeCount-1.EndState; Edge4.EndState = EndState; Edge4.Tran

12、sSymbol = #; /构建单元 /先将Left和Right的EdgeSet复制到NewCell 第 8 页 cell_EdgeSet_Copy(NewCell,Left); cell_EdgeSet_Copy(NewCell,Right); /将新构建的四条边加入EdgeSet NewCell.EdgeSetNewCell.EdgeCount+ = Edge1; NewCell.EdgeSetNewCell.EdgeCount+ = Edge2; NewCell.EdgeSetNewCell.EdgeCount+ = Edge3; NewCell.EdgeSetNewCell.EdgeC

13、ount+ = Edge4; /构建NewCell的启示状态和结束状态 NewCell.StartState = StartState; NewCell.EndState = EndState; return NewCell; /处理 ab cell do_Join(cell Left,cell Right) /将Left的结束状态和Right的开始状态合并，将Right的边复制给Left，将Left返回 /将Right中所有以StartState开头的边全部修改， for(int i=0;iRight.EdgeCount;i+) if(Right.EdgeSeti.StartState.St

14、ateNpare(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); /将Left的结束状态更新

15、为Right的结束状态 Left.EndState = Right.EndState; return Left; /处理 a* cell do_Star(cell Cell) cell NewCell; NewCell.EdgeCount=0; edge Edge1,Edge2,Edge3,Edge4; /获得新的新状态节点 state StartState = new_StateNode; state EndState = new_StateNode; /构建边 Edge1.StartState = StartState; Edge1.EndState = EndState; 第 9 页 E

16、dge1.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的E

17、dgeSet复制到NewCell cell_EdgeSet_Copy(NewCell,Cell); /将新构建的四条边加入EdgeSet NewCell.EdgeSetNewCell.EdgeCount+ = Edge1; NewCell.EdgeSetNewCell.EdgeCount+ = Edge2; NewCell.EdgeSetNewCell.EdgeCount+ = Edge3; NewCell.EdgeSetNewCell.EdgeCount+ = Edge4; /构建NewCell的启示状态和结束状态 NewCell.StartState = StartState; NewCe

18、ll.EndState = EndState; return NewCell; /处理 a cell do_Cell(char element) cell NewCell; NewCell.EdgeCount=0; edge NewEdge; /获得新的新状态节点 state StartState = new_StateNode; state EndState = new_StateNode; /构建边 NewEdge.StartState = StartState; NewEdge.EndState = EndState; NewEdge.TransSymbol = element; /构建

19、单元 NewCell.EdgeSetNewCell.EdgeCount+ = NewEdge; NewCell.StartState = NewCell.EdgeSet0.StartState; NewCell.EndState = NewCell.EdgeSet0.EndState;/EdgeCount此时为1 return NewCell; void cell_EdgeSet_Copy(cell& Destination,cell Source) int D_count = Destination.EdgeCount; int S_count = Source.EdgeCount; for

20、(int i=0;iS_count;i+) Destination.EdgeSetD_count+i = Source.EdgeSeti; 第 10 页 Destination.EdgeCount = D_count + S_count; /* 获得新的状态节点，统一产生，便于管理，不能产生重复的状态 并添加到state_set数组中 */ state new_StateNode state newState; newState.StateName = STATE_NUM+65;/转换成大写字母 STATE_NUM+; return newState; /接收输入正规表达式，RegularEx

21、pression作为回传函数 void input(string &RegularExpression) cout请输入正则表达式： RegularExpression; while(!check_legal(RegularExpression); /coutRegularExpressionendl; /*检测输入的正则表达式是否合法 */ int check_legal(string check_string) if(check_character(check_string)&check_parenthesis(check_string) return true; return false

22、; /* 检查输入的字符是否合适 * | az AZ 合法返回true,非法返回false */ int check_character(string check_string) int length = check_string.size; for(int i=0;ilength;i+) char check = check_string.at(i); if(is_letter(check)/小写和大写之间有5个字符，故不能连续判断 /cout字母 合法; else if(check=(|check=)|check=*|check=|) 第 11 页 /cout操作符 合法; else co

23、ut含有不合法的字符!endl; cout请重新输入:endl; return false; return true; /*先检查括号是否匹配 *合法返回true,非法返回false */ int check_parenthesis(string check_string) int length = check_string.size; char * check = new charlength; strcpy(check,check_string.c_str); /char a = check_string.at(1); stack STACK; for(int i=0;ilength;i+

24、) if(checki=() STACK.push(i); else if(checki=) if(STACK.empty) cerr有多余的右括号endl;/暂时不记录匹配位置location cout请重新输入:endl; return false; else STACK.pop; if(!STACK.empty) /暂时不记录匹配位置location cerr有多余的左括号endl; cout请重新输入:endl; return false; /coutcheck=a&check=A&checka+b+b */ string add_join_symbol(string add_stri

25、ng) /* 测试终止符0 string check_string = abcdefg0aaa; coutcheck_stringendl; int length = check_string.size; char * check = new char2*length; strcpy(check,check_string.c_str); coutcheckendl; char *s = ssss0 aa; coutsendl; string a(s); coutaendl; */ int length = add_string.size; int return_string_length =

26、0; char *return_string = new char2*length;/做多是两倍 char first,second; for(int i=0;ilength-1;i+) first = add_string.at(i); second = add_string.at(i+1); return_stringreturn_string_length+ = first; /若第二个是字母、第一个不是(、|都要添加 if(first!=(&first!=|&is_letter(second) return_stringreturn_string_length+ = +; /若第二个是

27、(,第一个不是|、(,也要加 else if(second=(&first!=|&first!=() return_stringreturn_string_length+ = +; /将最后一个字符写入 return_stringreturn_string_length+ = second; return_stringreturn_string_length = 0; string STRING(return_string); cout加+后的表达式：STRINGendl; 第 13 页 return STRING; /* 优先级表： # ( * | + ) isp 0 1 7 5 3 8 i

28、cp 0 8 6 4 2 1 */ /in stack priority 栈内优先级 int isp(char c) switch(c) case #: return 0; case (: return 1; case *: return 7; case |: return 5; case +: return 3; case ): return 8; /若走到这一步，说明出错了 cerrERROR!endl; return false; /in coming priority 栈外优先级 int icp(char c) switch(c) case #: return 0; case (: r

29、eturn 8; case *: return 6; case |: return 4; case +: return 2; case ): return 1; /若走到这一步，说明出错了 cerrERROR!endl; return false; /*中缀表达式转后缀表达式 */ string postfix(string e) /设定e的最后一个符号式“#”，而其“#”一开始先放在栈s的栈底 e = e+#; stack s; char ch = #,ch1,op; s.push(ch); 第 14 页 /读一个字符 string out_string = ; int read_locat

30、ion = 0; ch = e.at(read_location+); while(!s.empty) if(is_letter(ch) out_string = out_string + ch; /coutch; ch = e.at(read_location+); else /cout输出操作符：chendl; ch1 = s.top; if(isp(ch1)icp(ch) s.push(ch); /cout压栈ch 读取下一个icp(ch) op = s.top; s.pop; /cout退栈op 添加到输出字符串endl; out_string = out_string + op; /

31、coutop; else op = s.top; s.pop; /cout退栈op 但不添加到输入字符串endl; if(op=() ch = e.at(read_location+); /coutendl; cout后缀表达式：out_stringendl; return out_string; /*显示DFA */ void Display(cell Cell) coutNFA 的边数：Cell.EdgeCountendl; 第 15 页 coutNFA 的起始状态：Cell.StartState.StateNameendl; coutNFA 的结束状态：Cell.EndState.Sta

32、teNameendl; for(int i=0;iCell.EdgeCount;i+) cout第i+1条边的起始状态：Cell.EdgeSeti.StartState.StateName 结束状态：Cell.EdgeSeti.EndState.StateName 转换符：Cell.EdgeSeti.TransSymbolendl; cout结束endl; 八.实验结果 九.实验小结 通过实验记录可知，程序输出的NFA是输入的正则表达式构造NFA的正确结果，程序的输出结果与实际的结果一致，程序能正确实现THOMPSON 算法。 第 16 页 通过本次试验，我初步掌握THOMPSON 算法原理和方法，并且对正则表达式和NFA有了更深入的理解，更能理解它们之间的联系，这对于以后我将他们应用于更多地方有很多帮助。同时通过上机编程锻炼了我的动手能力。 第 17 页