利用子集法构造DFAWord文档下载推荐.docx
- 文档编号:7016510
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:17
- 大小:65.25KB
利用子集法构造DFAWord文档下载推荐.docx
《利用子集法构造DFAWord文档下载推荐.docx》由会员分享,可在线阅读,更多相关《利用子集法构造DFAWord文档下载推荐.docx(17页珍藏版)》请在冰点文库上搜索。
将T中所有状态压入栈stack;
将ε-closure(T)初始化为T;
whilestack不空dobegin
将栈顶元素t弹出栈;
for每个这样的状态u:
从t到u有一条标记为ε的边do
ifu不在ε-closure(T)中dobegin
将u添加到ε-closure(T);
将u压入栈stack中
end
五.程序设计
1.总体设计
2.子程序设计
识别模块
六.程序中的结构说明
1.结构体
Symbolrecord结构体
结构体成员名
成员属性
Symbol[10]
用于存储关键字编码名
id
用于存储关键字对应的编码
entrytype结构体
idname[10]
用于存储识别后标识符名
address
用于存储标识符的地址
type
用于存储标识符的类型
digittype结构体
num
用于存储识别后的数字
用于存储标识符数字的地址
tokentype结构体
用于存储被识别的类型名
entry
用于存储被识别的标识符名
2.符号编码表
符号编码表
符号名
代码
Begin
}
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<
stdio.h>
string.h>
ctype.h>
stdlib.h>
//定义单词编码表的数据结构
structsymbolrecord
{charsymbol[10];
intid;
};
//定义符号表的数据结构
structentrytype
{charidname[10];
intaddress;
inttype;
};
//定义常数表的数据结构
structdigittype
{intnum;
//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;
=k;
{fflag=strcmp(a[j].idname,word);
if(fflag==0)//在符号表中可以找到
{tokenid.id=25;
tokenid.entry=a[j].address;
break;
}}
if(fflag!
{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;
9;
fprintf(fs,"
%c"
word[j]);
fprintf(fs,"
'
\t'
%d"
a[k].address);
a[k].type);
\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;
=t;
if(d[j].num==num)
{flag=1;
tokenid.id=26;
tokenid.entry=d[j].address;
=1)
{d[t].num=num;
d[t].address=t;
tokenid.entry=t;
t=t+1;
sprintf(tokenid.idname,"
num);
//int>
char
//识别算符和界符函数
tokentyperecogdel(charch)
switch(ch)
{case'
{'
{tokenid.id=13;
strcpy(tokenid.idname,"
//自行添加的}break;
case'
}'
{tokenid.id=14;
strcpy(tokenid.idname,"
}break;
case'
'
{tokenid.id=12;
='
{tokenid.id=19;
ch=fgetc(fp);
if(ch=='
)tokenid.id=23;
{ch=fgetc(fp);
)tokenid.id=20;
strcpy(tokenid.idname,"
}break;
{ch=fgetc(fp);
{tokenid.id=18;
}
else
{tokenid.id=17;
ungetc(ch,fp);
}};
if(ch=='
){
tokenid.id=22;
else{tokenid.id=21;
ungetc(ch,fp);
};
break;
+'
{tokenid.id=8;
}break;
*'
{tokenid.id=10;
('
{tokenid.id=15;
)'
{tokenid.id=16;
/////////////////////handlecom函数////////////
tokentypehandlecom(charch)
charch1;
intflag=0;
if(ch!
)
{tokenid.id=25;
else
{while(flag==0)
{ch1=ch;
if((ch1='
)&
&
(ch='
/'
))
flag=1;
///////////sort函数/////////
voidsort(charch)
structtokentypetokenword;
FILE*fq=fopen("
tokenfile.txt"
if(isalpha(ch))
tokenword=recogid(ch);
//字母
elseif(isdigit(ch))
tokenword=recogdig(ch);
//数字
elseif(ch=='
tokenword=handlecom(ch);
tokenword=recogdel(ch);
printf("
%s\t%d\t%d\n"
tokenword.idname,tokenword.id,tokenword.entry);
fprintf(fq,"
tokenword.id);
tokenword.entry);
fclose(fq);
/////////////scanner函数////////
voidscanner()
{charch;
fp=fopen("
source.txt"
r"
ch=getc(fp);
while(ch!
=EOF)
{if(!
isspace(ch))
{sort(ch);
fclose(fp);
intmain()
{inti;
printf("
输出token字如下:
\n"
idname\ttype\taddress\n"
scanner();
************************************\n"
输出符号表如下:
%s\t%s\t%s\n"
idname"
address"
type"
for(i=0;
i<
=k-1;
i++)
a[i].idname,a[i].address,a[i].type);
输出常数表如下:
%s\t%s\n"
num"
=t-1;
%d\t%d\n"
d[i].num,d[i].address);
\n\n"
system("
pause"
八.程序测试
Source源文件
程序截图
main()
Ifa!
=35
end;
dowhile
end;
36
九.实验小结
子集构造法的基本思想是构造得到的DFA的每个状态对应于NFA的一个状态集合。
DFA的状态数可能是NFA状态数的指数,但对于一种真实的语言,他的NFA和DFA的状态数量大致相同,状态数量呈现指数关系的情形尚未在实验中出现过。
以前上课时有许多的问题并没有真正的认识到,但通过这次实验的制作,使我掌握了许多更重要的知识点。
我学到了怎么根据文法规则写出正规式,再有正规式一步步得到DFA,NFA,再由DFA画出流程图,这为后续的编程建立了雏形。
除此之外还把过去学习的知识再重新拾起来。
以前总是模模糊糊的,现在心里清楚了许多。
实验实现了NFA到DFA的转换。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 利用 子集 构造 DFA