利用子集法构造DFA

1、实验一：利用子集法构造DFA 一实验目的掌握将非确定有限自动机确定化的方法和过程。二实验要求、内容及步骤实验要求：1.输入一个NFA，输出一个接受同一正规集的DFA；2.采用C+语言，实现该算法；3.编制测试程序；4.调试程序。实验步骤：1.输入一个NFA关系图；2.通过一个转换算法将NFA转换为DFA；3.显示DFA关系图。三实验设备计算机、Windows 操作系统、Visual C+ 程序集成环境。四实验原理1.NFA-DFA转换原理：从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是：DFA的每一个状态对应

2、NFA的一组状态。 DFA使用它的状态去记录在NFA读入一个输入符号后可能到达的所有状态。输入：一个NFA N输出：一个接受同样语言的DFA D方法：为D构造转换表Dtran，DFA的每个状态是NFA的状态集。D的状态集合用Dstates表示。D的开始状态为-closure(s0)，s0是N的开始状态。使用下列算法构造D的状态集合Dstates和转换表Dtran。如果D的某个状态是至少包含一个N的接受状态的NFA状态集，那么它是D的一个接受状态。2.子集构造法：初始时, -closure(S0) 是 Dstates 中唯一的状态且未被标记;while Dstates 中存在一个未标记的状态T

3、do begin标记T; for 每个输入符号 a do beginU := -closure ( move (T, a) );if U 没在Dstates中 then将U作为一个未被标记的状态添加到 Dstates.Dtran T, a := Uendend3.-closure的计算：将T中所有状态压入栈stack;将-closure (T) 初始化为T;while stack不空 do begin将栈顶元素t弹出栈; for 每个这样的状态u：从t到u有一条标记为 的边do if u 不在-closure ( T )中 do begin 将u 添加到-closure ( T ); 将u压入

4、栈stack中 endend五程序设计1.总体设计读入字符识别模块识别标识符识别分界符、运算符识别常数输出2.子程序设计 识别模块读取字符字母识别标识符数字识别数字/识别注释打印并结束FTFTFT六程序中的结构说明1.结构体Symbolrecord结构体结构体成员名成员属性Symbol10用于存储关键字编码名id用于存储关键字对应的编码entrytype结构体结构体成员名成员属性idname10用于存储识别后标识符名address用于存储标识符的地址type用于存储标识符的类型digittype结构体结构体成员名成员属性num用于存储识别后的数字address用于存储标识符数字的地址token

5、type结构体结构体成员名成员属性id用于存储被识别的类型名entry用于存储标识符的地址idname10用于存储被识别的标识符名2.符号编码表符号编码表符号名代码符号名代码Begin014End1(15If2)16Then317Else421+8=22-9:=23*10 24/11Id25;12Const26133.重要函数介绍tokentype recogid(char ch) /识别标识符算法tokentype recogdig(char ch) /识别数字函数tokentype recogdel(char ch) /识别算符和界符函数tokentype handlecom(char c

6、h) /handlecom函数，识别注释函数void sort(char ch) /sort函数，读取文件内容，并根据读入内容调用不同的识别函数void scanner()/scanner函数，打开文件七.函数代码#include #include #include #include /定义单词编码表的数据结构struct symbolrecord char symbol10; int id; ;/定义符号表的数据结构struct entrytype char idname10; int address; int type;/定义常数表的数据结构struct digittype int num

7、; int address;/Token字的数据结构struct tokentype int id; int entry; char idname10;FILE *fp; /源文件指针struct digittype d10; /定义常数表，个数指针struct entrytype a40;int k=0,t=0;/单词编码表初始化struct symbolrecord s26= 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

8、, ,17, ,21, =,22, :=,23, ,24, const,26;/识别标识符算法tokentype recogid(char ch) tokentype tokenid; FILE *fs; int flag,fflag; char word10=0; int i,j; i=0; while(isalpha(ch)|isdigit(ch) wordi=ch; ch=fgetc(fp); i=i+1; ungetc(ch,fp); wordi=0; for(j=0;j=8;j+) flag=strcmp(word, sj.symbol); if(flag=0) /是关键字 toke

9、nid.id=j; tokenid.entry=-1; break; if(flag!=0) for(j=0;j=k;j+)fflag=strcmp(aj.idname,word); if(fflag=0) /在符号表中可以找到 tokenid.id=25; tokenid.entry=aj.address; break; if(fflag!=0) fs=fopen(symbol.txt,a); /符号表中不存在的标识符 strcpy(ak.idname, word); ak.address=k; ak.type=25; tokenid.id=25; tokenid.entry=k; for(

10、j=0;j9;j+) fprintf(fs,%c,wordj); fprintf(fs,%c,t); fprintf(fs,%d,ak.address); fprintf(fs,%c,t); fprintf(fs,%d,ak.type); fprintf(fs,%c,n); fclose(fs); k=k+1; strcpy(tokenid.idname, word);/自行添加的 return tokenid;/识别数字函数tokentype recogdig(char ch) int flag; int i=0,j; int num=0; tokentype tokenid; while(

11、isdigit(ch) num=(ch-48)+num*10; ch=fgetc(fp); i=i+1; for(j=0;jchar return tokenid;/识别算符和界符函数tokentype recogdel(char ch) tokentype tokenid; switch(ch) case: tokenid.id=13; strcpy(tokenid.idname, );/自行添加的break; case: tokenid.id=14; strcpy(tokenid.idname, );break; case;: tokenid.id=12; strcpy(tokenid.i

12、dname, ;);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(tok

13、enid.idname, :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

14、, (); break; case): tokenid.id=16; strcpy(tokenid.idname, ); break; tokenid.entry=-1; return tokenid; /handlecom函数/tokentype handlecom(char ch) tokentype tokenid; char ch1; int flag=0; if(ch!=* ) tokenid.id=25; tokenid.entry=-1; else while(flag=0) ch1=ch; ch=fgetc(fp); if(ch1=*)&(ch=/) flag=1; retur

15、n tokenid;/sort函数/void sort(char ch) struct tokentype tokenword; FILE * fq = fopen(tokenfile.txt,a);if(isalpha(ch) tokenword=recogid(ch); /字母else if(isdigit(ch) tokenword=recogdig(ch); /数字 else if(ch=/) tokenword=handlecom(ch); elsetokenword=recogdel(ch);printf(%st%dt%dn,tokenword.idname,tokenword.i

16、d,tokenword.entry); fprintf(fq,%d,tokenword.id); fprintf(fq,%c,t); fprintf(fq,%d,tokenword.entry); fprintf(fq,%c,n); fclose(fq);/scanner函数/void scanner() char ch; fp=fopen(source.txt,r); ch=getc(fp); while(ch!=EOF) if(!isspace(ch) sort(ch); ch=fgetc(fp); fclose(fp);int main() int i; printf(输出token字如

17、下:n); printf(idnamettypetaddressn); scanner(); printf(*n); printf(输出符号表如下：n); printf(%st%st%sn,idname,address,type); for(i=0;i=k-1;i+) printf(%st%dt%dn,ai.idname,ai.address,ai.type); printf(*n); printf(输出常数表如下：n); printf(%st%sn,num,address); for(i=0;i=t-1;i+) printf(%dt%dn,di.num,di.address); printf(nn); system(pause);八程序测试Source源文件程序截图main() If a!=35end;do while end;36九实验小结子集