欢迎来到天天文库
浏览记录
ID:29197991
大小:260.00 KB
页数:14页
时间:2018-12-17
《dfa地编程实现(含源代码、实验报告材料)》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、实用标准文案实验一(一)程序设计语言及其编译器实现概览(2小时)实验目的:学习一门简单的程序设计语言的定义及其编译器实现实验任务:针对一门简单的程序设计语言,阅读其定义文档,初步了解其编译器的源代码。实验内容:(1)选择一门语言:TINY或其它语言也可(需自备其编译器的源代码)。(2)阅读其定义文档,了解语言定义的方法,包括:词法、语法、语义、运行时环境、目标机器、目标语言等内容。(3)了解其编译器源代码。·对TINY语言编译器,其源代码由多个文件组成,请弄清楚每个文件的作用是什么。详情请见《编译原理及实践》第1.7节。请做一个C++工程文件(Win32ConsoleApplication
2、,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等文件,三人一组进行讨论,给每一行加上注释,总结你们各自对程序的理解和阅读程序的收获,每组提
3、交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的五元组保存在
4、一个文本文件中,扩展名指定为.dfa。请自行设计DFA文件的存储格式,并说明其含义。能将保存在内存变量中的DFA写入DFA文件,也能将DFA文件读入内存中。(思考:对稀疏DFA(转换表中为空的地方较多)或用“或”表达转换的DFA(如下的测试用例三),如何改进DFA转换表的表达。)(3)DFA的正确性检查:检查所有集合的元素的唯一性。检查“开始状态”是否唯一,并是否包含在“状态集”中。检查“接受状态集”是否为空,并是否包含在“状态集”中。精彩文档实用标准文案检查“状态转换表”是否满足DFA的要求。检查“状态转换表”并非填满时的处理是否得当…(4)DFA的语言集列表显示:输入待显示的字符串的最
5、大长度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。完
6、成全部内容,可得奖励。判定算法概要:准备:开始状态s0,接受状态集F,状态转换表T(s,c),sÎS,cÎSc=getchar();s=开始状态s0;while(c!=EOF)//输入未结束则循环…{s=T(s,c);if(s==NULL)error();c=getchar();}if(sÎ接受状态集F)accept();elseerror();通用DFA存储格式的建议:(用以上的第三个测试DFA为例)3//字符集中的字符个数(以下两行也可合并成一行)/*o//以空格分隔的字符集。O代表任意非/和*的字符5//状态个数(以下两行也可合并成一行)12345//状态编号。若约定总是用从1开始的
7、连续数字表示,则此行可省略1//开始状态的编号。若约定为1,则此行可省略1//结束状态个数。若约定为1,则此行可省略5//结束状态的编号2-1-1//状态1的所有出去的转换。按字符集中的字符顺序给出。-1表示出错状态-13-1343543-1-1-1实验报告:同时上交纸质报告与电子版报告。纸质报告以实验分析、实验中遇到的问题及解决方法、实验测试(含屏幕截图)、实验心得等为主,不得大量引用源程序(引用源程序总行数不得超过1
此文档下载收益归作者所有