THOMPSON-算法的实现

《THOMPSON-算法的实现》由会员分享，可在线阅读，更多相关《THOMPSON-算法的实现（17页珍藏版）》请在装配图网上搜索。

1、实验二：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，直到获得整个正规表达式的NFA为止。规则1.

2、对, 构造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。在构造过程中，每次构造的新状态都要赋予不同的名字。这样，任何NFA的两个状态都具有不同

3、的名字。即使同一符号在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 EndState;char TransSymbol

4、;/单元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_join_symbol(string);/中缀转

5、后缀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_EdgeSet_Copy(cell&,cell);/产

6、生一个新的状态节点，便于管理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(Regular_Expression);/中缀转后缀R

7、egular_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;ilength;i+)element = expre

8、ssion.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 = STACK.top();STACK.pop();

9、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 StartState = new_StateNo

10、de();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.EndState;Edge3.EndSta

11、te = 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.EdgeSetNewCell.EdgeCount+ = Ed

12、ge1;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的结束状态和Right的开始状态合并，将Right的边复制

13、给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 = Lef

14、t.EndState;STATE_NUM-;Right.StartState = Left.EndState;cell_EdgeSet_Copy(Left,Right);/将Left的结束状态更新为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 EndSta

15、te = new_StateNode();/构建边Edge1.StartState = StartState;Edge1.EndState = EndState;Edge1.TransSymbol = #;Edge2.StartState = Cell.EndState;Edge2.EndState = Cell.StartState;Edge2.TransSymbol = #;Edge3.StartState = StartState;Edge3.EndState = Cell.StartState;Edge3.TransSymbol = #;Edge4.StartState = Cell.

16、EndState;Edge4.EndState = EndState;Edge4.TransSymbol = #;/构建单元/先将Cell的EdgeSet复制到NewCellcell_EdgeSet_Copy(NewCell,Cell);/将新构建的四条边加入EdgeSetNewCell.EdgeSetNewCell.EdgeCount+ = Edge1;NewCell.EdgeSetNewCell.EdgeCount+ = Edge2;NewCell.EdgeSetNewCell.EdgeCount+ = Edge3;NewCell.EdgeSetNewCell.EdgeCount+ = E

17、dge4;/构建NewCell的启示状态和结束状态NewCell.StartState = StartState;NewCell.EndState = EndState;return NewCell;/处理 acell do_Cell(char element)cell NewCell;NewCell.EdgeCount=0;edge NewEdge;/获得新的新状态节点state StartState = new_StateNode();state EndState = new_StateNode();/构建边NewEdge.StartState = StartState;NewEdge.E

18、ndState = EndState;NewEdge.TransSymbol = element;/构建单元NewCell.EdgeSetNewCell.EdgeCount+ = NewEdge;NewCell.StartState = NewCell.EdgeSet0.StartState;NewCell.EndState = NewCell.EdgeSet0.EndState;/EdgeCount此时为1return NewCell;void cell_EdgeSet_Copy(cell& Destination,cell Source)int D_count = Destination.

19、EdgeCount;int S_count = Source.EdgeCount;for(int i=0;iS_count;i+)Destination.EdgeSetD_count+i = Source.EdgeSeti;Destination.EdgeCount = D_count + S_count;/*获得新的状态节点，统一产生，便于管理，不能产生重复的状态并添加到state_set数组中*/state new_StateNode()state newState;newState.StateName = STATE_NUM+65;/转换成大写字母STATE_NUM+;return ne

20、wState;/接收输入正规表达式，RegularExpression作为回传函数void input(string &RegularExpression)cout请输入正则表达式： （操作符：() * |;字符集：az AZ）RegularExpression;while(!check_legal(RegularExpression);/coutRegularExpressionendl;/*检测输入的正则表达式是否合法*/int check_legal(string check_string)if(check_character(check_string)&check_parenthesi

21、s(check_string)return true;return false;/*检查输入的字符是否合适 () * | 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=*|che

22、ck=|)/cout操作符 合法;elsecout含有不合法的字符!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

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

24、ing)/* 测试终止符0string 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 = 0;char *

25、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+ = +;/若第二个是(,第一个不是|、(,也要加else

26、 if(second=(&first!=|&first!=()return_stringreturn_string_length+ = +;/将最后一个字符写入return_stringreturn_string_length+ = second;return_stringreturn_string_length = 0;string STRING(return_string);cout加+后的表达式：STRINGendl;return STRING;/*优先级表： #(*|+)isp 017538icp 086421*/in stack priority 栈内优先级int isp(char

27、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 (: return 8;case *: return 6;case |: return 4;case +: return 2;case ): retu

28、rn 1;/若走到这一步，说明出错了cerrERROR!endl;return false;/*中缀表达式转后缀表达式*/string postfix(string e)/设定e的最后一个符号式“#”，而其“#”一开始先放在栈s的栈底e = e+#;stack s;char ch = #,ch1,op;s.push(ch);/读一个字符string out_string = ;int read_location = 0;ch = e.at(read_location+);while(!s.empty()if(is_letter(ch)out_string = out_string + ch;/

29、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;/coutop;elseop = s.top();s.pop();/cout退栈op 但不添加到输入字符串endl;if(op=()ch = e.at(read_location+);/coutendl;cout后

30、缀表达式：out_stringendl;return out_string;/*显示DFA*/void Display(cell Cell)coutNFA 的边数：Cell.EdgeCountendl;coutNFA 的起始状态：Cell.StartState.StateNameendl;coutNFA 的结束状态：Cell.EndState.StateNameendl;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 算法。通过本次试验，我初步掌握THOMPSON 算法原理和方法，并且对正则表达式和NFA有了更深入的理解，更能理解它们之间的联系，这对于以后我将他们应用于更多地方有很多帮助。同时通过上机编程锻炼了我的动手能力。 第 17 页