《DFA的编程实现(含源代码、实验报告)要点.pdf》由会员分享,可在线阅读,更多相关《DFA的编程实现(含源代码、实验报告)要点.pdf(14页珍藏版)》请在三一文库上搜索。
1、实验一(一)程序设计语言及其编译器实现概览(2 小时) 实验目的:学习一门简单的程序设计语言的定义及其编译器实现 实验任务:针对一门简单的程序设计语言,阅读其定义文档,初步了解其编译器的源代码。 实验内容: (1)选择一门语言:TINY 或其它语言也可(需自备其编译器的源代码)。 (2)阅读其定义文档,了解语言定义的方法,包括:词法、语法、语义、运行时环境、目 标机器、目标语言等内容。 (3)了解其编译器源代码。 对 TINY 语言编译器, 其源代码由多个文件组成,请弄清楚每个文件的作用是什么。 详情请见编译原理及实践第1.7 节。请做一个C+工程文件(Win32 Console Applic
2、ation, 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 的“字符集” 、 “状态集”、 “开始状态” 、
4、“接受状态集” 、 “状态转换表” 等内容,并保存在设定的变量中。 (2)DFA 的存储与读写: 将上述 DFA 的五元组保存在一个文本文件中,扩展名指定为 .dfa。请自行设计DFA 文 件的存储格式, 并说明其含义。 能将保存在内存变量中的DFA 写入 DFA 文件,也能将 DFA 文件读入内存中。 (思考:对稀疏DFA(转换表中为空的地方较多)或用“或”表达转换的 DFA (如下的测试用例三) ,如何改进DFA 转换表的表达。 ) (3)DFA 的正确性检查: 检查所有集合的元素的唯一性。 检查“开始状态”是否唯一,并是否包含在“状态集”中。 检查“接受状态集”是否为空,并是否包含在“状
5、态集”中。 检查“状态转换表”是否满足DFA 的要求。 检查“状态转换表”并非填满时的处理是否得当 (4)DFA 的语言集列表显示: 输入待显示的字符串的最大长度N, 输出以上定义的DFA 的语言集中长度N 的所有 规则字符串。 (提示:注意算法中while 循环的次数) (5)DFA 的规则字符串判定: 输入(或用字符集随机生成)一个字符串, 模拟 DFA 识别字符串的过程判定该字符串 是否是规则字符串(属于DFA 的语言集)。 测试用例: DFA (一) DFA (二) DFA (三) 实验要求: 按照编译原理及实践参考书第二章中描述的“while 循环 +双层 case选择”的算法 编程
6、实现一般的DFA。 要求能通过以上三个测试用例的测试。 完成内容中(1) (5)部分,可得C。 完成内容中(1) (2) (5)部分,可得B。 完成内容中(1) (2) (4) (5)部分,可得A。 完成全部内容,可得奖励。 判定算法概要: 准备:开始状态s0, 接受状态集 F, 状态转换表T(s, c), sS, c c = getchar(); s = 开始状态s0; while ( c != EOF ) / 输入未结束则循环 s = T(s, c); if (s = NULL) error(); c = getchar(); if (s 接受状态集F) accept (); else e
7、rror (); 通用 DFA 存储格式的建议: (用以上的第三个测试DFA 为例) 3 / 字符集中的字符个数(以下两行也可合并成一行) / * o / 以空格分隔的字符集。O 代表任意非 /和 *的字符 5 / 状态个数(以下两行也可合并成一行) 1 2 3 4 5 / 状态编号。若约定总是用从1 开始的连续数字表示,则此行可省略 1 / 开始状态的编号。若约定为1,则此行可省略 1 / 结束状态个数。若约定为1,则此行可省略 5 / 结束状态的编号 2 -1 -1 / 状态 1 的所有出去的转换。按字符集中的字符顺序给出。-1 表示出错状态 -1 3 -1 3 4 3 5 4 3 -1
8、-1 -1 实验报告: 同时上交纸质报告与电子版报告。纸质报告以实验分析、实验中遇到的问题及解决方 法、实验测试(含屏幕截图)、实验心得等为主,不得大量引用源程序(引用源程序总行数 不得超过100 行) 。电子版报告以源程序、测试用例、输出文件等为主,包括纸质报告的电 子版, 须确保提并的源程序能编译运行,否则不要上交。 电子版请发送到, 邮件标题请写明学号、姓名与实验编号,形如: 。不得抄袭实验报 告与源程序,否则后果自负! 提高内容: (1)图形化的用户界面; (2)任意 DFA 的状态转换图、状态转换表的图形绘制; 附实验报告源码 实验一 DFA 的编程实现 实验目的: 通过本次实验,加
9、深对DFA及其识别的语言的理解,学习对一般的DFA的表 达方法与编程实现方法。 实验任务: 编写一个 C语言程序,模拟实现DFA 识别字符串的过程。 实验内容: (1)DFA 的输入; (2)DFA的存储与读写;(3)DFA 的正确性检查;(4) DFA的语言集列表显示;(5)DFA的规则字符串判定; 实验分析: DFA 的初始化 一个 DFA的基本信息状态集、字符集、开始状态、结束状态集、状态转换 表; 在程序中状态集、 字符集、开始状态、结束状态集都用 string类型来表示, 即可不用考虑用户输入内容的长度。 但缺点是字符集只能是字符而不可以是字符 串。 状态转换表:为三个字符的字符串,
10、 第一个为当前状态, 第二个为输入字符, 第三个为下一状态。用 vector容器存放转换函数的内容 字符串判断 初始化一个 DFA,后可以通过一下算法判断一个字符串是否符合该DFA。 判定算法概要: 准备:开始状态s0, 接受状态集F, 状态转换表T(s, c), sS, c c = getchar(); s = 开始状态s0; while ( c != EOF ) / 输入未结束则循环 s = T(s, c); if (s = NULL) error(); c = getchar(); if (s 接受状态集F) accept (); else error (); 在实际编写代码中的体现为
11、void identify() / 判断字符串 coutstr; int i=0; char present=StartStates; while(i容器 存储即可; 实验用例: 实验结果: DFA的初始化 判断字符串: 显示小于 N的语言集: 读取 DFA文件: 实验总结: 在这次实验中,学习对一般的DFA 的表达方法与编程实现方法。对课本提 供的算法有了更深刻的认识。 在编写和调试代码的过程中对自身的编程能力也有 了很大的提高。 对自动机和其识别语言有了更透彻的理解。在动手编程之前一定 要好好明确实验的理论准备和思路的理清,能帮助我们在实验过程中少走更多的 弯路。总之在这次实验中收获很多,
12、提高了动手能力和分析问题的能力。 源代码: /构造一个 DFA #include #include #include #include using namespace std; class TransitionTable public: char present; /当前状态 char next; /下一状态 char input; /输入字符 TransitionTable(char P,char I,char D) present=P; next=D; input=I; ; class DFA public: DFA() coutselect; if(select=1) inti(); i
13、f(select=2) read(); string States; /状态集 char StartStates; /开始状态 string FinalStates; /结束状态集 string Alphabet; /字符集 vector Trans; / 转换函数 void inti() /初始化自动机 coutStates; coutAlphabet; coutinput; if(strcmp(input,“#“)=0) break; TransitionTable Temp(input0,input1,input2); Trans.push_back(Temp); coutStartStates; coutFinalStates; void identify() / 识别字符串 coutstr; int i=0; char present=StartStates; while(iN; example.Traversal(example.StartStates,N); example.write(); system(“pause“); return 0; /*测试用例 输入状态转换表 0a1 0b2 1b2 2a1 1a3 2b3 3a3 3b3 # 0a1 0b2 2a1 1b2 1a3 2b5 3a3 5b5 3b4 5a6 6b4 4a6 6a3 4b5 */
链接地址:https://www.31doc.com/p-5196687.html