编译原理报告:NFA转DFA(详解-附源代码).doc

编译原理报告:NFA转DFA(详解-附源代码).doc

ID:52901741

大小:158.50 KB

页数:11页

时间:2020-03-31

编译原理报告:NFA转DFA(详解-附源代码).doc_第1页
编译原理报告:NFA转DFA(详解-附源代码).doc_第2页
编译原理报告:NFA转DFA(详解-附源代码).doc_第3页
编译原理报告:NFA转DFA(详解-附源代码).doc_第4页
编译原理报告:NFA转DFA(详解-附源代码).doc_第5页
资源描述:

《编译原理报告:NFA转DFA(详解-附源代码).doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、112015编译原理实习报告____________________________________________________________________________________________编译原理实习报告学号:******班级:******姓名:******日期:2015112015编译原理实习报告____________________________________________________________________________________________目录1.题目及需求分析……………………………………………32.设计分析………………

2、……………………………………33.调试分析……………………………………………………74.用户手册……………………………………………………75.测试结果……………………………………………………76.总结…………………………………………………………77.源代码………………………………………………………8112015编译原理实习报告____________________________________________________________________________________________题目:NFA转换为等价的DFA实习时间:2015.10.12【问题描述】以定理

3、“设L为一个由不确定的有穷自动机接受的集合,则存在一个接受L的确定的有穷自动机”为理论基础,设计算法实现将不确定的有穷自动机(NFA)转换为与之等价的确定的有穷自动机(DFA)。【基本要求】① 确定能够表示FA的合适的结构,以便FA的输入和输出② 设计的算法既要成功实现题目要求的功能,又要高效、鲁棒③ 程序中的函数、变量等命名要规则,可读性要强(易懂)1.需求分析(1)要将以状态转换图表示的NFA转换为DFA,首先应设计一个结构来表示FA,以便图形式的FA便于输入和输出。(2)设计合适的算法来实现NFA的确定化,这里用子集法来构造等价的DFA。(3)测试数据:课本P59例4.8转换前

4、的NFA转换后的DFA2.设计(1)数据结构设计由于FA是一个图,可想到用图的存储结构来存储FA,但是,FA中两个结点之间的路径可以不只一条,这让想考虑用邻接矩阵来存储的FA处理起来有点复杂,我采用的是“结点-边-结点”式的三元组来表示FA。FA有多少条边就应该有多少个这样的三元组,以一个数组来存放这些三元组,那么一个FA就可以表示出来了。此外,由子集法的步骤可见,集合(set)这一结构应该使用,,set结构符合我们数学的集合要求,不含相同元素,并且两个集合间还可以进行比较是否相等,十分有利于我们的程序实现。表示FA的结构://Triad(三元组):S→aB即(S,a,B)struc

5、tTriad{charstart;charedge;charend;};集合与栈使用库里面的标准集合、栈。即包含头文件set、stack112015编译原理实习报告____________________________________________________________________________________________(1)文件结构程序不是很复杂,加之使用到的数据结构是标准库里的,文件只有一个N2D.cpp,其中有#include和#include。(2)程序基本框架概览structTriad{};//FA的基本组成结构intma

6、in(){初始化工作;determined();//确定化}e_closure(){}//求ε闭包move(){}//求集合的x弧转换determined(){}//确定化(3)主要函数的实现伪代码具有简明扼要的特点,利用伪代码子来表示程序流程有利于理解和后续实现。子集法伪代码:s0←NFA的开始状态集合T←e-closure(s0)把T加入到子集簇C(未标记)while(集合U←在C中找到一个未标记的集合){标记U;for(对于每一种输入即a、b......){U←e-closure(move(T,a))if(U不是C的子集)把U加入到子集簇C(未标记)有T→aU}}此外,求ε的传

7、递闭包要利用栈这一数据结构做辅助,其伪代码如下:112015编译原理实习报告____________________________________________________________________________________________//求e-closure(T)的伪代码将T中的所有状态全都压入栈S、集合Uwhile(S非空){t←取栈顶元素;for(每个从t状态能通过空串转换得到的状态s)if(s不在U中){把状态s加入U;把状

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。