实验一利用子集法构造DFA

1、实验一 利用子集法构造DFA一、实验目的 掌握将非确定有限自动机确定化的方法和过程2、 实验要求及内容 实验要求：1.输入一个NFA，输出一个接受同一正规集的DFA；2.采用C+语言，实现该算法；3.编制测试程序；4.调试程序。 实验步骤：1.输入一个NFA关系图；2.通过一个转换算法将NFA转换为DFA；3.显示DFA关系图。三、实验环境 计算机、Windows 操作系统、Visual C+ 程序集成环境。4、 程序代码#include stdafx.h#include#include#include#include#includeusing namespace std;struct edg

2、eint start,end;char c;E100,Ekong100;/E保存所有的边，Ekong保存转换字符为空的边struct Stateint H100;/状态集合int count;/状态集合中的元素个数int flag;/是否是接受状态int mark;/状态编号;int n;/n:边数int nk=0;/空字符转换的边数int first,accept;/开始状态，接受状态char alpha100;/输入字母表,#代表空串int numof_char=0;/字母表中的字符个数int useof_char256;/该转换字符是否用过int f200;/状态属性标志：0表示始态，1

3、表示接受态，-1表示中间态State DFA100;/DFA状态集int useof_DFA100;/标志构造出来的状态是否已存在int numof_Dtran=0;/最后得到的DFA中的状态数char Dtran100100;/DFA状态转换表void input()int i,s,e;char ch;cout请输入转换的有向边数n：n;cout请输入NFA的开始状态：first;cout请输入NFA的接受状态(输入-1结束)：accept;while(accept!=-1)faccept=1;cinaccept;cout请输入NFA，起点，终点，转换字符(#表示空字符)：endl;int

4、k=0;for(i=0;isech;Ei.start=s;Ei.end=e;Ei.c=ch;if(ch!=#&!useof_charch)alphanumof_char+=ch;useof_charch=1;if(ch=#)Ekongnk.start=s;Ekongnk.end=e;Ekongnk.c=ch;nk+;State move(State T,char s)/c!=#State temp;temp.count=0;temp.mark=T.mark;int i,j=0,k=0;for(i=0;iT.count;i+)j=0;while(jn)if(Ej.start=T.Hi&Ej.c=

5、s) temp.Htemp.count+=Ej.end; j+;return temp;void arriveBynone(int t,int result,int& num)/搜索状态t通过一个或多个空字符到达的状态,结果存在result中int k=0;int m=0;num=0;stack S;S.push(t);int j;while(!S.empty()j=S.top();S.pop();m=0;while(mnk) if(Ekongm.start=j) resultnum+=Ekongm.end; S.push(Ekongm.end); m+;bool check(int i,St

6、ate T)/判断状态i是否在T中int j;for(j=0;jT.count;j+)if(T.Hj=i)return true;return false;State closure(State T)/求闭包stack STACK;State temp;int i,j,k;for(i=0;iT.count;i+)STACK.push(T.Hi);temp.Hi=T.Hi;temp.count=T.count;temp.mark=T.mark; while(!STACK.empty() int t=STACK.top();STACK.pop();/搜索状态t通过一个或多个空字符到达的状态int

7、search_result100;int num;arriveBynone(t,search_result,num);for(j=0;jnum;j+) if(!check(search_resultj,temp) temp.Htemp.count+=search_resultj;STACK.push(search_resultj);for(k=0;ktemp.count;k+)if(ftemp.Hk=1) temp.flag=1; break;if(ftemp.Hk=0) temp.flag=0; break;sort(temp.H,temp.H+temp.count);for(i=0;inu

8、mof_Dtran;i+)if(temp.count!=DFAi.count) continue;sort(DFAi.H,DFAi.H+DFAi.count);for(j=0;j=DFAi.count) temp.mark=DFAi.mark;return temp;int check_inDFA()/检查DFA中是否存在未被标记的状态,有则返回标号，否则返回-1 int i; for(i=0;inumof_Dtran;i+) if(!useof_DFAi) return i;return -1;bool check_whetherin_DFA(State T)int i,j;sort(T.H

9、,T.H+T.count);for(i=0;inumof_Dtran;i+)if(T.count!=DFAi.count) continue;sort(DFAi.H,DFAi.H+DFAi.count);for(j=0;j=DFAi.count) return true;if(i=numof_Dtran)return false;elsereturn true;void child_method()int m,n;for(m=0;m100;m+) for(n=0;n100;n+) Dtranmn=#; for(m=0;m100;m+)DFAm.flag=-1; State S0,U;S0.fl

10、ag=0;S0.count=1;S0.H0=first;State T;T=closure(S0);T.mark=0;T.flag=0;DFAnumof_Dtran+=T;memset(useof_DFA,0,sizeof(useof_DFA);int j=check_inDFA(); int k; while(j!=-1) useof_DFAj=1;for(k=0;knumof_char;k+) U=closure(move(DFAj,alphak); /if U不在DFA中 if(!check_whetherin_DFA(U) U.mark=numof_Dtran;DFAnumof_Dtr

11、an+=U; DtranDFAj.markU.mark=alphak;j=check_inDFA();void print()int i,j;for(i=0;inumof_Dtran;i+)couti:;for(j=0;jDFAi.count;j+) coutDFAi.Hj ;if(DFAi.flag=1) cout此为DFA的接受状态;if(DFAi.flag=0) cout此为DFA的开始状态;coutendl;coutendl;for(i=0;inumof_Dtran;i+)for(j=0;jnumof_Dtran;j+) if(Dtranij!=#) coutij By Dtranij

12、endl; void judge(string ch) int i,j,k;int num=ch.length(); State temp; k=0; for(i=0;inum;i+) for(j=0;jnumof_Dtran;j+) if(Dtrankj=alphai) temp=DFAj;k=j;break; if(temp.flag!=1)cout字符串 ch无法由该DFA得到endl;elsecout字符串 ch可以由该DFA得到endl;coutendl;int _tmain(int argc, _TCHAR* argv)input();child_method();couts)ju

13、dge(s);system(pause);return 0;5、 实验结果6、 算法分析使用子集构造法对非确定有限自动机进行确定化的过程中存在大量重复计算的问题。为解决此问题,基于非确定有限自动机的特点并针对子集构造法的不足,提出了一种优化的非确定有限自动机确定化算法。首先定义了识别符的有效引出状态集概念并证明了-closure的并定理以保证算法的正确性,其次给出了用于避免重复计算的识别符的有效引出状态集的构造子算法和单状态集的-closure的求算子算法,基于这两个子算法给出了优化的非确定有限自动机确定化算法,最后将算法应用于实例,实验结果表明计算量远小于子集构造法的计算量。相比子集构造法,

14、算法能更有效地对非确定有限自动机进行确定化。七、实验小结以前上课时有许多的问题并没有真正的认识到，但通过这次实验，使我掌握了许多更重要的知识点。通过实验，我们可以知道将NFA转换成接受同样语言的DFA的算法称为子集构造算法。NFA变换到DFA的基本思想是：让DFA的每个状态对应NFA的一个状态集。实验实现了NFA到DFA的转换。实验二 THOMPSON 算法的实现一、实验目的 掌握将正规表达式转换为NFA的方法和过程3、 实验要求及内容1. 输入一个正规表达式，输出一个接受同一语言的NFA2. 采用C+语言，实现该算法3. 编制测试程序4. 调试程序 三、实验环境 计算机、Windows 操作

15、系统、Visual C+ 程序集成环境。四、程序代码#include Thompson.hvoid main()string Regular_Expression = (a|b)*abb;cell NFA_Cell;input(Regular_Expression);/调试需要先屏蔽Regular_Expression = add_join_symbol(Regular_Expression);Regular_Expression = postfix(Regular_Expression);NFA_Cell = express_2_NFA(Regular_Expression);Display

16、(NFA_Cell);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 = expression.at(i);switch(element)case |:Right = STACK.top();STACK.pop();Left = STACK.top();STACK.pop();Cell = do_Unite(Left,Right);STACK.push(C

17、ell);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();Cell = do_Join(Left,Right);STACK.push(Cell);break;default:Cell = do_Cell(element);STACK.push(Cell);cout处理完毕!endl;Cell = STACK.top();STACK

18、.pop();return Cell;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 = #;Edge2.StartState = St

19、artState;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.TransSymbol = #;/先将Left和Right

20、的EdgeSet复制到NewCellcell_EdgeSet_Copy(NewCell,Left);cell_EdgeSet_Copy(NewCell,Right);/将新构建的四条边加入EdgeSetNewCell.EdgeSetNewCell.EdgeCount+ = Edge1;NewCell.EdgeSetNewCell.EdgeCount+ = Edge2;NewCell.EdgeSetNewCell.EdgeCount+ = Edge3;NewCell.EdgeSetNewCell.EdgeCount+ = Edge4;/构建NewCell的启示状态和结束状态NewCell.Sta

21、rtState = StartState;NewCell.EndState = EndState;return NewCell;/处理 abcell do_Join(cell Left,cell Right)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.StateNpar

22、e(Right.StartState.StateName)=0)Right.EdgeSeti.EndState = Left.EndState;STATE_NUM-;Right.StartState = Left.EndState;cell_EdgeSet_Copy(Left,Right); Left.EndState = Right.EndState; return Left;cell do_Star(cell Cell)cell NewCell;NewCell.EdgeCount=0;edge Edge1,Edge2,Edge3,Edge4;state StartState = new_S

23、tateNode();state EndState = 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 = #;E

24、dge4.StartState = Cell.EndState;Edge4.EndState = EndState;Edge4.TransSymbol = #;/构建单元cell_EdgeSet_Copy(NewCell,Cell);NewCell.EdgeSetNewCell.EdgeCount+ = Edge1;NewCell.EdgeSetNewCell.EdgeCount+ = Edge2;NewCell.EdgeSetNewCell.EdgeCount+ = Edge3;NewCell.EdgeSetNewCell.EdgeCount+ = Edge4;NewCell.StartSt

25、ate = StartState;NewCell.EndState = EndState;return NewCell;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; NewCell.E

26、dgeSetNewCell.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.EdgeCount;int S_count = Source.EdgeCount;for(int i=0;iS_count;i

27、+)Destination.EdgeSetD_count+i = Source.EdgeSeti;Destination.EdgeCount = D_count + S_count;state new_StateNode()state newState;newState.StateName = STATE_NUM+65;/转换成大写字母STATE_NUM+;return newState; void input(string &RegularExpression)cout请输入正则表达式： （操作符：() * |;字符集：az AZ）RegularExpression;while(!check

28、_legal(RegularExpression);int check_legal(string check_string)if(check_character(check_string)&check_parenthesis(check_string)return true;return 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)/小

29、写和大写之间有5个字符，故不能连续判断else if(check=(|check=)|check=*|check=|)elsecout含有不合法的字符!endl;cout请重新输入:endl;return false;return true;int check_parenthesis(string check_string)int length = check_string.size();char * check = new charlength;strcpy(check,check_string.c_str();stack STACK;for(int i=0;ilength;i+)if(ch

30、ecki=()STACK.push(i);else if(checki=)if(STACK.empty()cerr有多余的右括号endl;/暂时不记录匹配位置locationcout请重新输入:endl;return false;elseSTACK.pop();if(!STACK.empty()cerr有多余的左括号endl;cout请重新输入:=a&check=A&check=Z)return true;return false;string add_join_symbol(string add_string)string check_string = abcdefg0aaa;coutche

31、ck_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 *return_string = new char2*length;/做多是两倍char first,second

32、;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 if(second=(&first!=|&first!=()return_stringreturn_string_length+ = +; return_stringreturn_stri

33、ng_length+ = second;return_stringreturn_string_length = 0;string STRING(return_string);cout加+后的表达式：STRINGendl;return STRING;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;int icp(char c)switch

34、(c)case #: return 0;case (: return 8;case *: return 6;case |: return 4;case +: return 2;case ): return 1; cerrERROR!endl;return false;string postfix(string e) 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_lett

35、er(ch)out_string = out_string + ch;ch = e.at(read_location+);elsech1 = s.top();if(isp(ch1)icp(ch)op = s.top();s.pop();out_string = out_string + op;elseop = s.top();s.pop();if(op=()ch = e.at(read_location+);cout后缀表达式：out_stringendl;return out_string;void Display(cell Cell)coutNFA 的边数：Cell.EdgeCounten

36、dl;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;5、 算法分析Thompson算法的基本思想,提出一种利用算符优先关系表来实现Thompso

37、n算法的方法,以实现正规式到有穷自动机的转换.描述了算法的解决思路、算符优先表的生成和NFA的表示.算法测试表明,该方法可以大大简化算法的实现,提高编译程序的工作效率.六、实验结果7、 实验小结通过这次试验，我掌握了如何将正规表达式转换为NFA的方法和过程。另外，我们要知道在构造过程中，每次构造的新状态都要赋予不同的名字。这样，任何NFA的两个状态都具有不同的名字。即使同一符号在r中出现多次，我们也要为该符号的每个实例创建一个独立的带有自己状态的NFA。实验三 词法分析与语法分析程序设计一、实验目的掌握计算机语言的词法分析程序和语法分析程序的设计方法二、实验要求、内容及步骤 实验要求：1根据以

38、下的正规式，画出状态图；标识符：(|)*十进制整数：0 | （1|2|3|4|5|6|7|8|9）（0|1|2|3|4|5|6|7|8|9）*运算符：+ * 2根据状态图，设计词法分析函数int scan( )，实现从键盘读入数据，分析出一个单词。3对于只含有+、*运算的算术表达式的文法，编写相应的语法分析程序，要求用LL(1)分析表实现，并以id+id*id为例进行测试。 E TE E +TE| T FT T *FT| F （E）| id实验步骤1、根据状态图，设计词法分析算法2、采用C+语言，实现该算法3、编制测试程序4、调试程序：输入一组单词，检查输出结果。5、编制给定文法的非递归的预测

39、分析程序，并加以测试。三、实验环境计算机、Windows 操作系统、Visual C+ 程序集成环境。4、 实验原理1. 词法分析器读入输入串，将其转换成将被语法分析器分析的词法单元序 列。产生下述小语言的单词序列。单词符号种别编码DIMIFDOSTOPEND标识符常数（整）=+*，（）1234567891011121314这个小语言的单词符号的状态转换图，如下图：2.语法分析是决定如何使用一个文法生成一个终结符串的过程。语法分析器 能识别由加+ 减- 乘* 除/ 乘方 括号（）操作数所组成的算术表达式，其文法如下：EE+T|E-T|TTT*F|T/F|FFPF|Pp(E)|i使用的算法可以是

40、：预测分析法；递归下降分析法；算符优先分析法；LR分析法等。3.中间代码生成器 产生上述算术表达式的中间代码（四元式序列）。id+*()$EE TEE TE EE +TEE E TT FTT FT TT T *FTT T FF idF (E)五、程序代码（1）词法分析程序的数据结构与算法：#include#includeusing namespace std;char prog100,token10;char ch;int syn,p,m=0,n,row,sum=0;char *rwtab20=dim,if,do,stop,end ,and,begin,bool,case,char,false

41、,for,int,not,or,set,then,true,until,while;void scaner()for(n=0;n=a&ch=A&ch=0&ch=a&ch=A&ch=Z)tokenm+=ch;ch=progp+;tokenm+=0;p-;syn=21;for(n=0;n=0&ch=0&ch32767)syn=-1;else switch(ch) case=:syn=8+15;token0=ch;break;case+:syn=9+15;token0=ch;break;case*:m=0;tokenm+=ch;ch=progp+;if(ch=*)syn=11+15; tokenm+

42、=ch;elsesyn=10+15;p-; break;case,:syn=12+15;token0=ch;break;case(:syn=13+15;token0=ch;break;case):syn=14+15;token0=ch;break;case#:syn=0;token0=ch;break;case)syn=17+15;tokenm+=ch;else if(ch=)syn=16+15;tokenm+=ch;elsesyn=15+15;p-;break;case:m=0;tokenm+=ch;ch=progp+;if(ch=)syn=19+15;tokenm+=ch;elsesyn=18+15;p-