编译原理报告NFA转DFA详解附源代码

编译原理实习报告学号：******班级：******姓名：******日期：2025目录1.题目及需求分析……………………………………………32.设计分析……………………………………………………33.调试分析……………………………………………………74.用户手册……………………………………………………75.测试结果……………………………………………………76.总结…………………………………………………………77.源代码………………………………………………………8题目：NFA 转换为等价的 DFA实习时间：2025.10.12【问题描述】以定理“设 L 为一个由不确定的有穷自动机接受的集合，则存在一个接受 L 的确定的有穷自动机”为理论基础，设计算法实现将不确定的有穷自动机(NFA)转换为与之等价的确定的有穷自动机(DFA)。【基本要求】① 确定能够表示 FA 的合适的结构，以便 FA 的输入和输出② 设计的算法既要成功实现题目要求的功能，又要高效、鲁棒③ 程序中的函数、变量等命名要规则，可读性要强(易懂)1．需求分析(1) 要将以状态转换图表示的 NFA 转换为 DFA，首先应设计一个结构来表示 FA，以便图形式的 FA 便于输入和输出。(2) 设计合适的算法来实现 NFA 的确定化，这里用子集法来构造等价的 DFA。(3) 测试数据:课本 P59 例 4.8 转换前的 NFA 转换后的 DFA2．设计（1）数据结构设计由于 FA 是一个图，可想到用图的存储结构来存储 FA，但是，FA 中两个结点之间的路径可以不只一条，这让想考虑用邻接矩阵来存储的 FA 处理起来有点复杂，我采纳的是“结点-边-结点”式的三元组来表示 FA。FA 有多少条边就应该有多少个这样的三元组，以一个数组来存放这些三元组，那么一个 FA 就可以表示出来了。此外，由子集法的步骤可见，集合(set)这一结构应该使用，，set 结构符合我们数学的集合要求，不含相同元素，并且两个集合间还可以进行比较是否相等，十分有利于我们的程序实现。表示 FA 的结构：集合与栈使用库里面的标准集合、栈。即包含头文件 set、stack（2）文件结构程 序 不 是 很 复 杂 ， 加 之 使 用 到 的 数 据 结 构 是 标 准 库 里 的 ， 文 件 只 有 一 个 N2D.cpp ， 其 中 有#include和#include。（3）程序基本框架概览 （4）主要函数的实现伪代码具有简明扼要的特点，利用伪代码子来表示程序流程有利于理解和后续实现。子集法伪代码：//Triad(三元...