利用子集法构造DFA.docx
《利用子集法构造DFA.docx》由会员分享，可在线阅读，更多相关《利用子集法构造DFA.docx（17页珍藏版）》请在冰点文库上搜索。
利用子集法构造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每个输入符号adobegin
U:
=ε-closure（move（T,a））;
ifU没在Dstates中then
将U作为一个未被标记的状态添加到Dstates.
Dtran[T,a]:
=U
end
end
3.ε-closure的计算：
将T中所有状态压入栈stack;
将ε-closure（T）初始化为T;
whilestack不空dobegin
将栈顶元素t弹出栈;
for每个这样的状态u：
从t到u有一条标记为ε的边do
ifu不在ε-closure（T）中dobegin
将u添加到ε-closure（T）;
将u压入栈stack中
end
end
五．程序设计
1.总体设计
2.子程序设计
识别模块
六．程序中的结构说明
1.结构体
Symbolrecord结构体
结构体成员名
成员属性
Symbol[10]
用于存储关键字编码名
id
用于存储关键字对应的编码
entrytype结构体
结构体成员名
成员属性
idname[10]
用于存储识别后标识符名
address
用于存储标识符的地址
type
用于存储标识符的类型
digittype结构体
结构体成员名
成员属性
num
用于存储识别后的数字
address
用于存储标识符数字的地址
tokentype结构体
结构体成员名
成员属性
id
用于存储被识别的类型名
entry
用于存储标识符的地址
idname[10]
用于存储被识别的标识符名
2.符号编码表
符号编码表
符号名
代码
符号名
代码
Begin
0
}
14
End
1
（
15
If
2
）
16
Then
3
<
17
Else
4
<=
18
for
5
=
19
do
6
!
=
20
while
7
>
21
+
8
>=
22
-
9
:
=
23
*
10
‘’
24
/
11
Id
25
;
12
Const
26
{
13
3.重要函数介绍
tokentyperecogid（charch）//识别标识符算法
tokentyperecogdig（charch）///识别数字函数
tokentyperecogdel（charch）//识别算符和界符函数
tokentypehandlecom（charch）//handlecom函数，识别注释函数
voidsort（charch）//sort函数，读取文件内容，并根据读入内容调用不同的识别函数
voidscanner（）//scanner函数，打开文件
七.函数代码
#include
#include
#include
#include
//定义单词编码表的数据结构
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;j<9;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）;//int>>char
returntokenid;
}
//识别算符和界符函数
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）;
else
tokenword=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=getc（fp）;
while（ch!
=EOF）
{if（!
isspace（ch））
{sort（ch）;}
ch=fgetc（fp）;
}
fclose（fp）;
}
intmain（）
{inti;
printf（"输出token字如下:
\n"）;
printf（"idname\ttype\taddress\n"）;
scanner（）;
printf（"************************************\n"）;
printf（"输出符号表如下：
\n"）;
printf（"%s\t%s\t%s\n","idname","address","type"）;
for（i=0;i<=k-1;i++）
printf（"%s\t%d\t%d\n",a[i].idname,a[i].address,a[i].type）;
printf（"************************************\n"）;
printf（"输出常数表如下：
\n"）;
printf（"%s\t%s\n","num","address"）;
for（i=0;i<=t-1;i++）
printf（"%d\t%d\n",d[i].num,d[i].address）;
printf（"\n\n"）;
system（"pause"）;
}
八．程序测试
Source源文件
程序截图
main（）
{
Ifa!
=35
end;
dowhile
end;
36
}
九．实验小结
子集构造法的基本思想是构造得到的DFA的每个状态对应于NFA的一个状态集合。
DFA的状态数可能是NFA状态数的指数，但对于一种真实的语言，他的NFA和DFA的状态数量大致相同，状态数量呈现指数关系的情形尚未在实验中出现过。
以前上课时有许多的问题并没有真正的认识到，但通过这次实验的制作，使我掌握了许多更重要的知识点。
我学到了怎么根据文法规则写出正规式，再有正规式一步步得到DFA,NFA，再由DFA画出流程图，这为后续的编程建立了雏形。
除此之外还把过去学习的知识再重新拾起来。
以前总是模模糊糊的，现在心里清楚了许多。
实验实现了NFA到DFA的转换。
升级会员 