DFA的编程实现含源代码实验报告.docx
- 文档编号:12260021
- 上传时间:2023-06-05
- 格式:DOCX
- 页数:20
- 大小:186.55KB
DFA的编程实现含源代码实验报告.docx
《DFA的编程实现含源代码实验报告.docx》由会员分享,可在线阅读,更多相关《DFA的编程实现含源代码实验报告.docx(20页珍藏版)》请在冰点文库上搜索。
DFA的编程实现含源代码实验报告
试验一
(一)程序设计语言及其编译器实现概览(2小时)
试验目:
学习一门简单程序设计语言定义及其编译器实现
试验任务:
针对一门简单程序设计语言,阅读其定义文档,初步了解其编译器源代码。
试验内容:
(1)选择一门语言:
TINY或其它语言也可(需自备其编译器源代码)。
(2)阅读其定义文档,了解语言定义方法,包含:
词法、语法、语义、运行时环境、目标机器、目口号言等内容。
(3)了解其编译器源代码。
∙对TINY语言编译器,其源代码由多个文件组成,请搞清楚每个文件作用是什么。
详情请见《编译原理及实践》第1.7节。
请做一个C++工程文件(Win32ConsoleApplication,tiny.dsp),把它们组织起来,然后编译成可实施文件(tiny.exe),即为TINY语言编译器。
然后用它编译TINY语言示例源代码(sample.tny)。
看看编译生成目标文件(sample.tm)是怎样。
要运行目标程序,还需要一个虚拟机,名为TM机。
TM机是以软件形式存在,其源代码为tm.c,需要编译生成可实施文件tm.exe。
然后将目标程序作为TM机输入运行TM机即可得到所期待结果。
要求读懂main.c、globals.h、util.h、scan.h和util.c、scan.c等文件,三人一组进行讨论,给每一行加上注释,总结你们各自对程序了解和阅读程序收获,每组提交1份加了注释文件和心得。
有能力同学可加上tm.c。
试验一
(二)DFA编程实现(2小时)
试验目:
经过此次试验,加深对DFA及其识别语言了解,学习对通常DFA表示方法与编程实现方法。
试验任务:
编写一个C语言程序,模拟实现DFA识别字符串过程。
试验内容:
(1)DFA输入;
(2)DFA存放与读写;(3)DFA正确性检验;(4)DFA语言集列表显示;(5)DFA规则字符串判定;
内容说明:
(1)DFA输入:
分别输入DFA“字符集”、“状态集”、“开始状态”、“接收状态集”、“状态转换表”等内容,并保留在设定变量中。
(2)DFA存放与读写:
将上述DFA五元组保留在一个文本文件中,扩展名指定为.dfa。
请自行设计DFA文件存放格式,并说明其含义。
能将保留在内存变量中DFA写入DFA文件,也能将DFA文件读入内存中。
(思索:
对稀疏DFA(转换表中为空地方较多)或用“或”表示转换DFA(以下测试用例三),怎样改善DFA转换表表示。
)
(3)DFA正确性检验:
检验全部集合元素唯一性。
检验“开始状态”是否唯一,并是否包含在“状态集”中。
检验“接收状态集”是否为空,并是否包含在“状态集”中。
检验“状态转换表”是否满足DFA要求。
检验“状态转换表”并非填满时处理是否适当…
(4)DFA语言集列表显示:
输入待显示字符串最大长度N,输出以上定义DFA语言集中长度≤N全部规则字符串。
(提醒:
注意算法中while循环次数)
(5)DFA规则字符串判定:
输入(或用字符集生成)一个字符串,模拟DFA识别字符串过程判定该字符串是否是规则字符串(属于DFA语言集)。
测试用例:
DFA
(一)
DFA
(二)
DFA(三)
试验要求:
根据《编译原理及实践》参考书第二章中描述“while循环+双层case选择”算法编程实现通常DFA。
要求能经过以上三个测试用例测试。
完成内容中
(1)(5)部分,可得C。
完成内容中
(1)
(2)(5)部分,可得B。
完成内容中
(1)
(2)(4)(5)部分,可得A。
完成全部内容,可得奖励。
判定算法概要:
准备:
开始状态s0,接收状态集F,状态转换表T(s,c),s∈S,c∈∑
c=getchar();
s=开始状态s0;
while(c!
=EOF)//输入未结束则循环…
{
s=T(s,c);
if(s==NULL)
error();
c=getchar();
}
if(s∈接收状态集F)
accept();
else
error();
通用DFA存放格式提议:
(用以上第三个测试DFA为例)
3//字符集中字符个数(以下两行也可合并成一行)
/*o//以空格分隔字符集。
O代表任意非/和*字符
5//状态个数(以下两行也可合并成一行)
12345//状态编号。
若约定总是用从1开始连续数字表示,则此行可省略
1//开始状态编号。
若约定为1,则此行可省略
1//结束状态个数。
若约定为1,则此行可省略
5//结束状态编号
2-1-1//状态1全部出去转换。
按字符集中字符次序给出。
-1表示犯错状态
-13-1
343
543
-1-1-1
试验汇报:
同时上交纸质汇报与电子版汇报。
纸质汇报以试验分析、试验中碰到问题及处理方法、试验测试(含屏幕截图)、试验心得等为主,不得大量引用源程序(引用源程序总行数不得超出100行)。
电子版汇报以源程序、测试用例、输出文件等为主,包含纸质汇报电子版,须确保提并源程序能编译运行,不然不要上交。
电子版请发送到,邮件标题请写明学号、姓名与试验编号,形如:
<试验一><学号><姓名>。
不得剽窃试验汇报与源程序,不然后果自负!
提升内容:
(1)图形化用户界面;
(2)任意DFA状态转换图、状态转换表图形绘制;
附试验汇报源码
试验一DFA编程实现
试验目:
经过此次试验,加深对DFA及其识别语言了解,学习对通常DFA表示方法与编程实现方法。
试验任务:
编写一个C语言程序,模拟实现DFA识别字符串过程。
试验内容:
(1)DFA输入;
(2)DFA存放与读写;(3)DFA正确性检验;(4)DFA语言集列表显示;(5)DFA规则字符串判定;
试验分析:
DFA初始化
一个DFA基础信息状态集、字符集、开始状态、结束状态集、状态转换表;
在程序中状态集、字符集、开始状态、结束状态集都用string类型来表示,即可不用考虑用户输入内容长度。
但缺点是字符集只能是字符而不能够是字符串。
状态转换表:
为三个字符字符串,第一个为目前状态,第二个为输入字符,第三个为下一状态。
用vector容器存放转换函数内容
字符串判定
初始化一个DFA,后能够经过一下算法判定一个字符串是否符合该DFA。
判定算法概要:
准备:
开始状态s0,接收状态集F,状态转换表T(s,c),s∈S,c∈∑
c=getchar();
s=开始状态s0;
while(c!
=EOF)//输入未结束则循环…
{
s=T(s,c);
if(s==NULL)
error();
c=getchar();
}
if(s∈接收状态集F)
accept();
else
error();
在实际编写代码中表现为
voididentify()//判定字符串
{
cout<<"请输入字符串"< stringstr; cin>>str; inti=0; charpresent=StartStates; while(i { present=move(present,str[i]);//move函数即去遍历转换表,返回下个状态 if(present=='N')//N即为move返回错误状态, { break; } i++; } if(FinalStates.find(present)! =FinalStates.npos)//假如返回状态用find函数属于最终状态集则表示识别 cout<<"该自动机识别此字符串"< else cout<<"该自动机不识别此字符串"< } 对DFA存放与读写 将DNF信息写入文件中, 第一行: 字符集; 第二行: 状态集; 第三行: 开始状态; 第四行: 结束状态集; 以下行写入状态转换表 根据既定要求读取文件 中数据将其赋值,然后 初始化DFA即可; DFA语言集列表显示: 这一个模块应该是这个试验中比较难一部分了。 我并没有使用while循环这个做法。 而是用函数递归,经过全部字符集路径去遍历整个DFA。 最终将符合条件字符串输出; voidTraversal(charpresent,intN,stringstrass="")//遍历DFA语言集列表 { if(present=='N'||N<0)//若路径已经大于N或者目前状态错误,停止递归 return; N--; if(FinalStates.find(present)! =FinalStates.npos) { cout<<"该自动机识别字符串: "< } for(inti=0;i { stringtemp; temp=strass; strass+=Alphabet[i]; Traversal(move(present,Alphabet[i]),N,strass); strass=temp; } } 递归终止条件判定。 当N--时,N小于0,或者遍历到无路可走是便终止 碰到问题: 对于递归终止条件写得不够明确。 递归前对字符串赋值strass赋值,递归后应该还原,这一点没有想到。 调试了很久。 总结,对递归具体编写还是不熟悉。 现在代码,字符集和状态只能是一个字符,若要优化能够用vector 试验用例: 试验结果: DFA初始化 判定字符串: 显示小于N语言集: 读取DFA文件: 试验总结: 在这次试验中,学习对通常DFA表示方法与编程实现方法。 对书本提供算法有了更深刻认识。 在编写和调试代码过程中对本身编程能力也有了很大提升。 对自动机和其识别语言有了更透彻了解。 在动手编程之前一定要好好明确试验理论准备和思绪理清,能帮助我们在试验过程中少走更多弯路。 总而言之在这次试验中收获很多,提升了动手能力和分析问题能力。 源代码: //结构一个DFA #include #include #include #include usingnamespacestd; classTransitionTable { public: charpresent;//目前状态 charnext;//下一状态 charinput;//输入字符 TransitionTable(charP,charI,charD) { present=P; next=D; input=I; } }; classDFA { public: DFA() { cout<<"1、手动输入,2、读取txt文件"< intselect; cin>>select; if(select==1) inti(); if(select==2) read(); } stringStates;//状态集 charStartStates;//开始状态 stringFinalStates;//结束状态集 stringAlphabet;//字符集 vector voidinti()//初始化自动机 { cout<<"请输入有限状态集S: "< cin>>States; cout<<"请输入字符集A: "< cin>>Alphabet; cout<<"请输入转换函数MOVE--格式为: 目前状态-输入字符-下一状态: (输入#结束输入)"< intj=0; while(true) { charinput[4]; cin>>input; if(strcmp(input,"#")==0) break; TransitionTableTemp(input[0],input[1],input[2]); Trans.push_back(Temp); } cout<<"请输入开始状态集S0: "< cin>>StartStates; cout<<"请输入结束状态集F: "< cin>>FinalStates; } voididentify()//识别字符串 { cout<<"请输入字符串: "< stringstr; cin>>str; inti=0; charpresent=StartStates; while(i { present=move(present,str[i]);//move函数即去遍历转换表,返回下个状态 if(present=='N')//N即为move返回错误状态, { break; } i++; } if(FinalStates.find(present)! =FinalStates.npos)//假如返回状态用find函数属于最终状态集则表示识别 cout<<"该自动机识别此字符串"< else cout<<"该自动机不识别此字符串"< } charmove(charP,charI)//move转换函数 { for(inti=0;i { if(Trans[i].present==P&&Trans[i].input==I) returnTrans[i].next; } return'N'; } voidread()//从txt文件中读取DNF信息 { chartemp[10]; fstreamff("DNF.txt",ios: : in); ff.getline(temp,10); Alphabet=temp; ff.getline(temp,10); States=temp; ff.getline(temp,10); StartStates=temp[0]; ff.getline(temp,10); FinalStates=temp[0]; while(! ff.eof()) { ff.getline(temp,10); TransitionTableTemp(temp[0],temp[1],temp[2]); Trans.push_back(Temp); } } /*将DNF信息写入文件中, 第一行: 字符集; 第二行: 状态集; 第三行: 开始状态; 第四行: 结束状态集; 以下行写入状态转换表*/ voidwrite() { fstreamff("DNF.txt",ios: : out); ff< ff< ff< ff< for(inti=0;i ff< ff.close(); } voidTraversal(charpresent,intN,stringstrass="")//遍历DFA语言集列表显示 { if(present=='N'||N<0) return; N--; if(FinalStates.find(present)! =FinalStates.npos) { cout<<"该自动机识别字符串: "< } elseif(FinalStates.find(present)==FinalStates.npos&&N<0) return; for(inti=0;i { stringtemp; temp=strass; strass+=Alphabet[i]; Traversal(move(present,Alphabet[i]),N,strass); strass=temp; } } }; intmain() { DFAexample; example.identify(); intN; cout<<"请输入N"< cin>>N; example.Traversal(example.StartStates,N); example.write(); system("pause"); return0; } /*测试用例 输入状态转换表 0a1 0b2 1b2 2a1 1a3 2b3 3a3 3b3 # 0a1 0b2 2a1 1b2 1a3 2b5 3a3 5b5 3b4 5a6 6b4 4a6 6a3 4b5 */
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- DFA 编程 实现 源代码 实验 报告
![提示](https://static.bingdoc.com/images/bang_tan.gif)