欢迎来到天天文库
浏览记录
ID:43187190
大小:139.05 KB
页数:3页
时间:2019-09-28
《实验一DFA的编程实现》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、实验一DFA的编程实现实验目的:通过本次实验,加深对DFA及其识别的语言的理解,学习对一般的DFA的表达方法与编程实现方法。实验任务:编写一个C语言程序,模拟实现DFA识别字符串的过程。实验内容:(1)DFA的输入;(2)DFA的存储与读写;(3)DFA的正确性检查;(4)DFA的语言集列表显示;(5)DFA的规则字符串判定;内容说明:(1)DFA的输入:分别输入DFA的“字符集”、“状态集”、“开始状态”、“接受状态集”、“状态转换表”等内容,并保存在设定的变量中。(2)DFA的存储与读写:将上述DFA的五元组保存在一个文本文件屮,扩展名指定为.dfa。请自行设计DFA文件的存储格式,并说
2、明其含义。能将保存在内存变量中的DFA写入DFA文件,也能将DFA文件读入内存中。(思考:对稀疏DFA(转换表中为空的地方较多)或用“或”表达转换的DFA(如下的测试用例三),如何改进DFA转换表的表达。)(3)DFA的正确性检查:检查所有集合的元素的唯一性。检查“开始状态”是否唯一,并是否包含在“状态集”中。检查“接受状态集”是否为空,并是否包含在“状态集”中。检查“状态转换表”是否满足DFA的要求。检查“状态转换表”并非填满时的处理是否得当…(4)DFA的语言集列表显示:输入待显示的字符串的最大长度N,输出以上定义的DFA的语言集中反度WN的所有规则字符串。(提示:注意算法中while循
3、环的次数)(5)DFA的规则字符串判定:输入(或用字符集随机生成)一个字符串,模拟DFA识别字符串的过程判定该字符串是否是规则字符串(属于DFA的语言集)。测试用例:DFA(一)DFA(三)实验要求:按照《编译原理及实践》参考书第二章中描述的“while循环+双层case选择”的算法编程实现一般的DFAo要求能通过以上三个测试用例的测试。完成内容屮(1)(5)部分,可得C。完成内容中(1)(2)(5)部分,可得B。完成内容中(1)(2)(4)(5)部分,可得A。完成全部内容,可得奖励。判定算法概要:准备:开始状态s(),接受状态集F,状态转换表T(s,c),sgS,cgZc=getchar(
4、);s=开始状态So;while(c!=EOF)//输入未结束则循环…{s=T(s,c);if(s==NULL)error();c=getchar();}if(SG接受状态集F)accept();elseerror();列语言算法概要:(深度优先搜索,类似于M进制的数的进位问题)准备:开始状态so,接受状态集F,状态转换表T(s,c),sgS,C6E假设:三中的元素个数为M个,存储于charA[M]中;准备:长度N>(),存储语言元素的字符串charL[N](只存储其编号),初值全为・1;while(1){for(i=N-1;i>=0;i-)if(L[i]>=0)break;//找L串中的未
5、用字符if(i=0)//找到
6、未用完字符{L[iJ++;//用上Y中的下1个字符用判定算法判定字符串A[L[0]]〜A[L[i]]是否属于语言集中continue;}else//全部字符都已用完break;//算法至此终止}}注1:可增加存储前成经过的状态序列,从而无须调用判定算法,直接使用一步状态转换即可。注2:深度优先搜索无法实现相同长度的字符串显示在一块。若要求如此,需用宽度优先搜索。需定义一个函数用指定字符集生成长度刚好为n的字符串,然后定义主函数,让n从0循坏到N,并调用判定算法判定所有长度为n的字符串是否属于语言集即可。实验报告:同吋上交纸质报告与电子版报告。纸质报告以实验分析、实验中遇到的问题及解决方法、实
7、验测试(含屏幕截图)、实验心得等为主,不得大量引用源程序(引用源程序总行数不得超过100行)。电子版报告以源程序、测试用例、输出文件等为主,包括纸质报告的电子版,须确保提并的源程序能编译运行,否则不要上交。电子版请发送到wenjiabaol10@163.com,邮件标题请写明学号、姓名与实验编号,形如:v实验一>v学号〉v姓名不得抄袭实验报告与源程序,否则后果自负!
此文档下载收益归作者所有