logo资料库

编译原理ε-closure（I）的程序实现（Java实现）课程设计报告.docx

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.17M 资料格式：docx 举报 版权申诉
第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
资料共10页，剩余部分请下载后查看
    North China Institute of Water Conservancy and H
    华北水利水电学院 North China Institute of Water Conservancy and Hydroelectric Power 课 程 设 计 题目 ε-closure（I）的程序实现 院 系 信息工程学院 专 业 计算机科学与技术 姓 名 学 号 指 导 教 师 2019 年 12 月 13 日
    目 录 1 需求分析……………………………………………………………………（2） 2 概要设计……………………………………………………………………（2） 3 详细设计……………………………………………………………………（2） 4 测试与分析……………………………………………………………………（3） 5 用户使用说明…………………………………………………………………（6） 6 总结………………………………………………………………………………（6） 参考文献 …………………………………………………………………………（7） 附录：程序源代码 …………………………………………………………………（7） 1
    ε-closure（I）的程序实现 1、需求分析 1.1、问题描述 输入任意给定的有限自动机，对该自动机的任意状态子集 I,输出它的空闭包 ε-closure（I）。 1.2、基本要求 （1） 输入 NFA，保存文件中； （2） 输出所有的状态子集的空闭包； （3） 输出给定状态子集的空闭包； （4） 以状态转换图方式输出用户输入的有限自动机，要求状态结点大小位 置布局合理，具有通用性。 1.3、问题分析 本次程序主要是对于输入任意给定的有限自动机 NFA，对该自动机的任意状 态子集 I,输出它的空闭包ε-closure（I）。并以状态转换图方式输出用户输入的有 限自动机，该程序主要就是输入一个任意的 NFA，通过读取该 NFA，通过对应 算法逐渐生成其状态子集，然后再对状态子集进行读空即可得到对应状态子集的 空闭包。状态装换图则是根据状态转移函数进行逐步构造得到其对应的状态转换 图即可。 2、概要设计 说明本系统中用到的所有数据类型的定义及存储结构，主程序的流程以及各 程序模块之间的调用关系。 （1） 数据结构 本程序主要用到的数据结构主要是数组，图以及哈希表。 （2） 程序模块 程序模块主要是（1）前端数据传入，（2）后台数据处理与分析，（3）对新 引入初态节点 X 的读空函数，（4）对状态子集进行读空函数，（5）对状态子集 进行读字母表函数，（5）根据已得到的状态子集求出剩下的状态子集直到不再出 现新的状态子集为止的函数。 （3） 各模块之间的调用关系以及算法设计 后台各个函数传入从前端页面提交过来并且处理后的数据。求状态子集的函 数调用对状态子集进行读空的函数以及对状态子集进行读字母表的函数 3、详细设计 该程序在设计时，要想得到它的状态子集，首先需要对该 NFA 引入新的初 态节点 X 和新的终态节点 Y。然后对该初态节点引入一条空弧到非空初态集的 任意一个状态节点，对终态集的任意节点连一条空弧到 Y。因为我们能力有限， 实在想不出如何处理 X 到任意状态节点以及任意状态节点到 Y 的情况，所以写 的时候我们就让 X 和 Y 都固定连接到那一个节点，并将其作为状态转移函数写 2
    到自动机的状态转移函数里。 我写的主要有三个函数，一个是求初态节点 X 的空闭包得到第一个状态子集， 第二个是对状态子集读空得到的结果，第三个是对状态子集读字母表得到的结果。 首先是求 NFA 的状态子集，求的时候，因为引入了一个新的状态节点 X， 所以首先就是读 X，因为 X 只有一条空弧，所以对于 X 只需要读空就可以了， 所以在这里我就写了一个对 X 读空的函数，得到 X 的空闭包，因为 X 是新加的 肯定不会经过字母表的字母，所以 X 的空闭包即为该 NFA 的第一个状态子集。 在写该函数时，因为该函数每次只能处理一条产生式，而且因为空闭包的概念是 首先先把其本身即 X 添加进去，然后对 X 出发经过任意条空弧所到达的状态都 属于 X 的空闭包，所以，该函数需要用到递归，就是假设先传入一个‘X’，然 后得到的结果为 5，那就再将本次函数调用的结果 5 作为该函数的参数传入，再 次得到一个结果，一直递归直到得不到结果为止。因为该结果每次递归调用都需 要累加而不能清空，所以我是定义了一个静态变量字符串来接收它，每次递归得 到的结果都添加到该字符串中即可得到最终结果。 然后是因为求状态子集需要对原来得到的状态子集分别求 Ia（a 属于字母表 ∑）。求 Ia 还要考虑经过空弧的情况,才能最终得到状态子集,所以这里就需要一 个专门读字母表的函数。该函数我传进去参数有三个，第一个参数是在主函数循 环得到的每一个字母，第二个参数是一个状态子集，第三个参数是所有的产生式， 产生式这里是以 String 数组的形式传入的，数组中的每一个字符串都由(1,a)→3 这样的字符串形式传入的。首先定义一个空字符串 result。然后对传入的状态子 集进行循环，然后再嵌套循环产生式，当状态子集的状态所表示的字符与产生式 的第二个字符即“1”相同时，就再判断传入的字母，当传入的字母与产生式的 第 4 个字符即“a”相同，此时就将产生式的第七个字符添加 result 中。最终的 返回值就是想要的结果。 最后一个函数也是读空的，不过这个和上面的读空是不一样的。因为这个读 空的方法是需要给求状态子集的方法进行调用的，而且求每一个状态子集的 Ia 的时候不仅需要看状态节点经过的 a 弧，还要看它经过 a 弧所能到达的状态是否 还能经过空弧到达其它状态，如果能，就把该经过空弧所到达的状态也添加进去。 所以该函数传入的参数不再是状态子集而是状态子集读 a 产生的结果，即将我写 的上一个函数的结果作为该函数的参数。他会对状态子集读 a 的结果进行遍历， 看他们读空是否还能不能到达其他状态。 在主函数中我还写了对所有的状态子集求它的空闭包，求空闭包我就用的我 写的第一个读空的函数，就是先对存放状态子集的集合 map 进行循环，取出每 一个状态子集，然后对每一个状态子集再循环，取出状态子集的每一个状态，然 后将该状态作为一个参数调用第一个读空的函数，每次循环完一个状态子集都将 其输出，并对应输出其对应的空闭包，这样输出的每一个状态子集都对应一个空 闭包了。 4、测试与分析 进行系统测试，输出测试结果。测试数据应该全面、完整，并对测试结果进行分析。 例子一： X,1,2,3,4,5,6,Y a,b (X,ε)→5 (5,a)→5 (5,b)→5 (5,ε)→1 (1,a)→3 (1,b)→4 (3,a)→2 (4,b)→2 (2,ε)→6 (6,a)→6 3
    (6,b)→6 (6,ε)→Y X Y 结果如下： 运行结果为先求所有的状态子集，然后再对所有的状态子集求空闭包，每一 个状态子集都对应一个空闭包。 例子二： 0,1,X,Y a,b (X,ε)→0 (0,ε)→Y (0,a)→1 (0,b)→1 (1,a)→0 X Y 4
    运行结果： 空代表状态子集为空的情况 例子三： X,1,2,3,Y a,b (X,ε)→1 (1,a)→1 (1,b)→1 (1,ε)→2 (2,b)→3 (3,a)→Y X Y 5
    5、用户使用说明 该程序界面简单明了，使用起来简单易上手。 6、总结 本次课程设计，我学到了很多东西，知道了对于一个 NFA，如何设计算法去 求它的状态子集以及状态子集的空闭包：因为读字母如 a 时，还要考虑其读空的 情况，所以这里在读 a 的同时还需要分别在读 a 的前后分别调用读空的函数，这 样就可以将那种经过 a 又经过空的或者经过空又经过 a 的或者 a 的前后都经过空 的情况也考虑进去了。 我写的每一个函数的具体实现过程已在上面详细设计中说明，这里不再多说。 主要说一下写的过程中也遇到了很多问题。在写读空的函数时，其中有一个是对 新加入的初态节点‘X’，是引一条空弧到 NFA 的非空初态集的任意一个状态节点， 而当时写的时候感觉太过麻烦，当时本来准备这样写的，但是写完再往下进行的 时候就进行不下去了，而且最后想想其实也没啥必要，所以最后也没那样写，然 后就把初态节点‘X’经过一条空弧到达的状态作为一个产生式放在了条件里， 这样就直接用这个条件就行了。还有就是返回结果的时候，因为每次调用函数只 能返回一个状态节点，而我们需要的是一个状态子集的集合，所以这里也试了很 多方法最后才想到用静态变量的。 在写求 Ia 的时候，因为状态节点不仅要读子母 a，还要考虑前后读空的情况， 这个当时想了好一会才想到现在的这种写法。当时就是一直在考虑如何让一个状 态子集不仅要考虑读 a 的情况，还要考虑读空的情况，当时在这个问题上纠结了 好一阵，当时也没想到可以这样写。最后在网上找到求状态子集的算法，没想到 可以先写两个函数，分别是读字母表和读空的函数，而求状态子集的时候就可以 直接按照读空读 a 再读空这个逻辑来写了，所以我就直接写了一个专门读字母的 函数，就是这个函数是只读字母的，这样逻辑就简单多了。因为读字母前面的读 空传进来的是状态子集，所以再来一个对状态子集读空的函数就行了。 其他的也就没什么太大的问题了。关于此次课程设计，我学到了很多东西。 在写的时候，才知道这次课程设计虽然写的程序不多，但是逻辑很强，特别是其 中的算法，不知道用算法写的时候感觉特别难，不知道该怎么去实现，当知道了 算法该怎么去实现的时候，才发现原来也没想象中的那么难。当一个功能比较难 6
    以实现的时候可以把它再分成几个模块来写，就会发现会变得好理解很多。 附录：程序源代码 下面只粘贴我自己主要负责的部分的主要代码 对新加入的初态节点 X 读空： public static String RestltList(String string, String[] strings) { // 读 第一个 for (int i = 0; i < strings.length; i++) { // System.out.println(i + "," + string); if (String.valueOf(string.charAt(string.length() - 1)).equals(String.valueOf(strings[i].charAt(1)))) { if (" ε ".equals(String.valueOf(strings[i].charAt(3)))) { string += String.valueOf(strings[i].charAt(6)); RestltList(string, strings); } } } return string; } 单独读字母表： public static String RestltListA(String string, String s, String[] strings) { // 传进来的是识别的状态集合，第二个是识别的字母，第三个是映 射函数 String resultA = ""; for (int i = 0; i < strings.length; i++) { if (string.equals(String.valueOf(strings[i].charAt(1)))) if (s.equals(String.valueOf(strings[i].charAt(3)))) resultA += String.valueOf(strings[i].charAt(6)); { { } } } return resultA; } 对所有状态子集读空： public static String DuKong(String result, String[] strings) { for (int i = 0; i < result.length(); i++) { 7
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料