利用子集法构造DFA

实验一：利用子集法构造DFA一．实验目的掌握将非确定有限自动机确定化的方法和过程。二．实验要求、内容及步骤实验要求：1.输入一个NFA，输出一个接受同一正规集的DFA；2.采用C++语言，实现该算法；3.编制测试程序；4.调试程序。实验步骤：1.输入一个NFA关系图；2.通过一个转换算法将NFA转换为DFA；3.显示DFA关系图。三．实验设备计算机、Windows操作系统、VisualC++程序集成环境。四．实验原理1.NFA-DFA转换原理：从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是：DFA的每一个状态对应NFA的一组状态。DFA使用它的状态去记录在NFA读入一个输入符号后可能到达的所有状态。输入：一个NFAN输出：一个接受同样语言的DFAD方法：为D构造转换表Dtran，DFA的每个状态是NFA的状态集。D的状态集合用Dstates表示。D的开始状态为ε-closure(s0)，s0是N的开始状态。使用下列算法构造D的状态集合Dstates和转换表Dtran。如果D的某个状态是至少包含一个N的接受状态的NFA状态集，那么它是D的一个接受状态。2.子集构造法：初始时,ε-closure(S0)是Dstates中唯一的状态且未被标记;whileDstates中存在一个未标记的状态Tdobegin标记T;for每个输入符号adobeginU:=ε-closure(move(T,a));ifU没在Dstates中then将U作为一个未被标记的状态添加到Dstates.Dtran[T,a]:=Uendend3.ε-closure的计算：将T中所有状态压入栈stack;将ε-closure(T)初始化为T;whilestack不空dobegin将栈顶元素t弹出栈;for每个这样的状态u：从t到u有一条标记为ε的边doifu不在ε-closure(T)中dobegin将u添加到ε-closure(T);将u压入栈stack中endend五．程序设计1.总体设计读入字符识别模块识别标识符识别分界符、运算符识别常数输出2.子程序设计识别模块读取字符字母识别标识符数字识别数字/识别注释打印并结束FTFTFT六．程序中的结构说明1.结构体Symbolrecord结构体结构体成员名成员属性Symbol[10]用于存储关键字编码名id用于存储关键字对应的编码entrytype结构体结构体成员名成员属性idname[10]用于存储识别后标识符名address用于存储标识符的地址type用于存储标识符的类型digittype结构体结构体成员名成员属性num用于存储识别后的数字address用于存储标识符数字的地址tokentype结构体结构体成员名成员属性id用于存储被识别的类型名entry用于存储标识符的地址idname[10]用于存储被识别的标识符名2.符号编码表符号编码表符号名代码符号名代码Begin0}14End1(15If2)16Then317Else4=18for5=19do6!=20while721+8=22-9:=23*10‘’24/11Id25;12Const26{133.重要函数介绍tokentyperecogid(charch)//识别标识符算法tokentyperecogdig(charch)///识别数字函数tokentyperecogdel(charch)//识别算符和界符函数tokentypehandlecom(charch)//handlecom函数，识别注释函数voidsort(charch)//sort函数，读取文件内容，并根据读入内容调用不同的识别函数voidscanner()//scanner函数，打开文件七.函数代码#includestdio.h#includestring.h#includectype.h#includestdlib.h//定义单词编码表的数据结构structsymbolrecord{charsymbol[10];intid;};//定义符号表的数据结构structentrytype{charidname[10];intaddress;inttype;};//定义常数表的数据结构structdigittype{intnum;intaddress;};//Token字的数据结构structtokentype{intid;intentry;charidname[10];};FILE*fp;//源文件指针structdigittyped[10];//定义常数表，个数指针structentrytypea[40];intk=0,t=0;//单词编码表初始化structsymbolrecords[26]={Begin,0,End,1,If,2,Then,3,Else,4,for,5,do,6,while,7,+,8,-,9,*,10,/,11,;,12,{,13,},14,(,15,),16,,17,=,18,=,19,!=,20,,21,=,22,:=,23,,24,const,26};//识别标识符算法tokentyperecogid(charch){tokentypetokenid;FILE*fs;intflag,fflag;charword[10]={0};inti,j;i=0;while(isalpha(ch)||isdigit(ch)){word[i]=ch;ch=fgetc(fp);i=i+1;}ungetc(ch,fp);word[i]='\0';for(j=0;j=8;j++){flag=strcmp(word,s[j].symbol);if(flag==0)//是关键字{tokenid.id=j;tokenid.entry=-1;break;}}if(flag!=0){for(j=0;j=k;j++){fflag=strcmp(a[j].idname,word);if(fflag==0)//在符号表中可以找到{tokenid.id=25;tokenid.entry=a[j].address;break;}}if(fflag!=0){fs=fopen(symbol.txt,a);//符号表中不存在的标识符strcpy(a[k].idname,word);a[k].address=k;a[k].type=25;tokenid.id=25;tokenid.entry=k;for(j=0;j9;j++)fprintf(fs,%c,word[j]);fprintf(fs,%c,'\t');fprintf(fs,%d,a[k].address);fprintf(fs,%c,'\t');fprintf(fs,%d,a[k].type);fprintf(fs,%c,'\n');fclose(fs);k=k+1;}}strcpy(tokenid.idname,word);//自行添加的returntokenid;}///识别数字函数tokentyperecogdig(charch){intflag;inti=0,j;intnum=0;tokentypetokenid;while(isdigit(ch)){num=(ch-48)+num*10;ch=fgetc(fp);i=i+1;}for(j=0;j=t;j++)if(d[j].num==num){flag=1;tokenid.id=26;tokenid.entry=d[j].address;break;}if(flag!=1){d[t].num=num;d[t].address=t;tokenid.id=26;tokenid.entry=t;t=t+1;}sprintf(tokenid.idname,%d,num);//intcharreturntokenid;}//识别算符和界符函数tokentyperecogdel(charch){tokentypetokenid;switch(ch){case'{':{tokenid.id=13;strcpy(tokenid.idname,{);//自行添加的}break;case'}':{tokenid.id=14;strcpy(tokenid.idname,});}break;case';':{tokenid.id=12;strcpy(tokenid.idname,;);}break;case'=':{tokenid.id=19;strcpy(tokenid.idname,=);}break;case':':ch=fgetc(fp);if(ch=='=')tokenid.id=23;break;case'!':{ch=fgetc(fp);if(ch=='=')tokenid.id=20;strcpy(tokenid.idname,!=);}break;case'':{ch=fgetc(fp);if(ch=='='){tokenid.id=18;strcpy(tokenid.idname,=);}else{tokenid.id=17;strcpy(tokenid.idname,);ungetc(ch,fp);}};break;case'':ch=fgetc(fp);if(ch=='='){tokenid.id=22;strcpy(tokenid.idname,=);}else{tokenid.id=21;strcpy(tokenid.idname,);ungetc(ch,fp);};break;case'+':{tokenid.id=8;strcpy(tokenid.idname,+);}break;case'*':{tokenid.id=10;strcpy(tokenid.idname,*);}break;case'(':{tokenid.id=15;strcpy(tokenid.idname,();}break;case')':{tokenid.id=16;strcpy(tokenid.idname,));}break;}tokenid.entry=-1;returntokenid;}/////////////////////handlecom函数////////////tokentypehandlecom(charch){tokentypetokenid;charch1;intflag=0;if(ch!='*'){tokenid.id=25;tokenid.entry=-1;}else{while(flag==0){ch1=ch;ch=fgetc(fp);if((ch1='*')&&(ch='/'))flag=1;}}returntokenid;}///////////sort函数/////////voidsort(charch){structtokentypetokenword;FILE*fq=fopen(tokenfile.txt,a);if(isalpha(ch))tokenword=recogid(ch);//字母elseif(isdigit(ch))tokenword=recogdig(ch);//数字elseif(ch=='/')tokenword=handlecom(ch);elsetokenword=recogdel(ch);printf(%s\t%d\t%d\n,tokenword.idname,tokenword.id,tokenword.entry);fprintf(fq,%d,tokenword.id);fprintf(fq,%c,'\t');fprintf(fq,%d,tokenword.entry);fprintf(fq,%c,'\n');fclose(fq);}/////////////scanner函数////////voidscanner(){charch;fp=fopen(source.txt,r);ch=g