nfa编译原理课程设计_键盘输入nfa资源-CSDN文库

共2个文件

cpp：1个

doc：1个

编译原理课程设计

4星 · 超过85%的资源需积分: 17 79 浏览量 2011-11-22 11:18:40 上传评论 7 收藏 56KB RAR 举报

资源详情

资源评论

收起资源包目录

nfa编译原理课程设计.rar （2个子文件）

nfa编译原理课程设计

课程设计论文.doc 180KB

nfa.cpp 6KB

引言...............................................................2

第一章概述.....................................................3

1.1 设计内容.................................................3

1.2 设计要求.................................................3

第二章设计的基本原理...........................................3

2.1NFA 确定化为 DFA．........................................3

2.2DFA 的最小化..............................................4

第三章程序设计.................................................5

3.1 总体方案设计.............................................5

3.2 各模块设计...............................................6

第四章程序测试.................................................9

第五章结论.....................................................10

参考文献..........................................................10

附录程序清单.................................................11

- 1 -

引　言

编译原理系统地向学生介绍编译程序的结构、工作流程及编译程序各组成部分

的设计原理和实现技术。由于该课程理论性和实践性都比较强，内容较为抽象复杂，

涉及到大量的软件设计算法，因此，一直是一门比较难学的课程。为了更好地理解

和掌握编译技术的基本概念、基本原理和实现方法，实践环节非常重要，只有通过

上机进行程序设计，才能对比较抽象的教学内容产生具体的感性认识，增强综合分

析问题、解决问题的能力，并提高软件设计水平。编译原理课程设计是对自己学习

编译原理课程效果的一次检验，也是为在大四能够顺利完成毕业设计的一次基本功

训练。

我在选择课程设计题目时，选择了 12 题 DFA 的最小化和 13 题 NFA 确定化为

DFA，将这两题合并为一题，即 NFA 确定化到最小化的实现。NFA 的确定化和 DFA

的最小化主要是为了更好地使用状态转换图构造词法分析程序和词法分析程序的自

动生成。设计并实现将 NFA 确定化为 DFA 的子集构造算法以及 DFA 的最小化，从

而更好地理解有限自动机之间的等价性，掌握词法分析器自动产生器的构造技术。

　　我做课程设计时，首先认真复习了课本上有限自动机的相关内容，然后从图书

馆借了一些相关的辅导书，如编译原理学习指导和编译原理实验指导等，同时也复

习了Ｃ＋＋程序设计的相关内容和Ｃ＋＋标准模板库的应用等。做好相关准备后，

开始具体着手做课程设计，了解相关的设计内容和要求，分析思考，分模块设计和

整合。正确实现之后，开始写课程设计报告。由于这是编译原理的课程设计，而不

是Ｃ＋＋程序设计的课程设计，重点在于编译原理算法思想的实现，因此为了方便

实现和调试，我将题目中将其状态转换矩阵及初态、终态信息保存在指定文件中改

为输出到屏幕上。

第一章概述

1.1 设计内容

12 题 DFA 状态最少化的程序实现和 13 题把 NFA 确定化为 DFA 的算法实现，

合并为一题，将 NFA 确定化为 DFA，再将 DFA 化简即最小化。

- 2 -

1.2 设计要求

构造一程序，实现：将给定的 NFA M(其状态转换矩阵及初态、终态信息从键盘

输入)，确定化为 DFA M’。（要先实现 ε-CLOSURE 函数和 Ia 函数）。输出

DFA M’(其状态转换矩阵及初态、终态信息输出到屏幕上)。然后将由确定化后

的的 DFA M 的有限状态集 S 划分成若干互不相交的子集，使得：任何不同的两

个子集中的状态都是可区别的，而同一子集中的任何两个状态都是等价的（要利

用 Ia 函数，但并不需要构造 ε-CLOSURE 函数，因这是 DFA）。输出化简后的

DFA M’(其状态转换矩阵及初态、终态信息输出到屏幕上)。

第二章设计的基本原理

2.1 NFA 确定化为 DFA

　　1．非确定有限自动机 NFA

一个非确定有限自动机（NFA）M 是一个五元式 M=（S，∑，δ,S0，F）

其中(1)S 是一个有限集，它的每一个元素称为一个状态；

(2) ∑是一个有穷字母表，它的每一个元素称为一个输入字符；

(3) δ 是一个从 S×∑*到 S 的子集映照；

(4)S0 属于∑，是一个非空初态集；

(5)F 属于 S，是一个终态集（可空）。

显然，一个含有 m 个状态和 n 个输入字符的 NFA 可表示成如下的状态转换图

该图含有 m 个状态结点，每个节点可射出若干条箭弧与别的结点相连接，

每条弧用∑*中的一个字（不一定要相同而且可以是空字）做标记（称为输

入字），整张图至少含有一个初态结点以及若干个（可以是 0 个）终态结点。

对于∑*中的任何一个字 a，若存在一条从某一初态结点到某一终态结点的通

路，且这条通路上所有弧的标记字依序连接城的字（忽略那些标记为空字 ε

的弧）等于啊，则称 a 可为 NFA M 所识别。若 M 的某些结点既是初态结点

又是终态结点，后者存在一条弧从某个出台节点到某个终态结点的 ε 通路，

则空字 ε 可为 M 所接受。

2．确定有限自动机 DFA 的最小化

一个确定有限自动机（NFA）M 是一个五元式 M=（S，∑，δ,s0，F）

其中(1)S 是一个有限集，它的每一个元素称为一个状态；

(2) ∑是一个有穷字母表，它的每一个元素称为一个输入字符；

(3) δ 是一个从 S×∑到 S 的单值部分映射。δ(s,a)意味着：当现行状态

为 s、输入字符为 a 时，将转入下一个状态 s’,s’是 s 的后继状态；

(4)s0∈S，是唯一的初态；

(5)F 属于 S，是一个终态集（可空）。

显然，一个 DFA 可用一个状态转换矩阵表示，该矩阵的行表示状态，列表时输

入字符，矩阵元素表示 δ(s,a)的值。一个 DFA 也可以表示成一张状态转换

图，假设 DFA M 含有 m 个状态和 n 个输入字符，那么，该图含有 m 个状

- 3 -

态结点，每个节点最多有 n 条箭弧与别的结点相连接，每条弧用∑中的一个

字做标记，整张图含有唯一的一个初态结点和若干个（可以是 0 个）终态结

点。对于∑中的任何一个字 a，若存在一条从某一初态结点到某一终态结点

的通路，且这条通路上所有弧的标记字依序连接城的字等于啊，则称 a 可为

DFA M 所识别。若 M 的某些结点既是初态结点又是终态结点，后者存在一

条弧从某个出台节点到某个终态结点的 ε 通路，则空字 ε 可为 M 所接受。

DFA M 所能识别的字的全体记为 L(M)。

3．NFA 与 DFA 的联系

在非确定的有限自动机 NFA 中，由于某些状态的转移需从若干个可能的后续

状态中进行选择，故一个 NFA 对符号串的识别必然是一个试探的过程。这

种

不确定性识别过程带来的反复，无疑会影响到 FA 的工作效率。而 DFA 则是

确

定的，将 NFA 转化为 DFA 大大提高工作效率，因此将 NFA 转化为 DFA 是

有其

一定必要的。程序中采用子集法来实现 NFA 确定化为 DFA。

2.2 DFA 的最小化

一个有限自动机 M 的化简是指：寻找一个状态数比 M 少的 DFA M’，使得

L(M)=L(M’).假定 s 和 t 是 M 的两个不同状态，如果分别从状态 s 和 t 出发能读

出同样的某个字 w 而停于终态，则称 s 和 t 是等价的。如果 DFA M 的两个状态

s 和 t 不等价，则称这两个状态是可区别的。一个 DFA M 的状态最少化过程旨

在将 M 的状态集分割成一些不相交的子集，使得任何不同的两个字集中的状态

是可区别的，而同一子集中的任何两个状态都是等价的。最后，在每个自己中

选出一个代表，同时消去其他等价状态。又被删除的状态射出的弧也被删去，

但是有保留下来的状态射出的弧是要全部保留的。

第三章程序设计

3.1 总体方案设计

我的程序总共分三大模块，一是有限自动机状态转换图的结构和有限自动机状

态信息的输入输出部分；二是用子集构造算法实现 NFA 确定化为 DFA，这里

面又涉及到 ε_Closure(I)和转换函数 Move(I,a)的实现和新生成的状态的重命

名问题以及新的状态转换关系的建立；三是 DFA 的最小化，这里面包括等价

状态的划分，等价状态的划分又涉及到终态结点和非终态结点的区分，划分之

后等价状态的重命名和新的状态转换关系的建立。总体模块设计方案如下图所

示：

- 4 -

- 5 -

评论收藏

内容反馈

zhang_mao

2013-05-28

文档包括原代码和完整的报告

nfa编译原理课程设计

评论5

最新资源

nfa编译原理课程设计

评论5

最新资源

相关推荐

编译原理课程设计重庆理工大学

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

编译原理（由正则表达式到NFA到DFA到最小化DFA），python，graphiviz实现可视化）

DFA的最小化 （完整可运行代码）

DFA化简的程序设计

DFA最小化算法实现

编译原理实验 DFA的最小化 c++代码

compiler:编译原理课程设计，包括词法分析器（nfa转dfa）和语法分析器（LR1实现）

编译原理课程设计nfa转为dfa

nfa-dfa.rar_Dfa Nfa_NFA DFA_nfa转dfa代码_有助于学写编译原理的基本思路_编译原理中nfa转df

nfa mfa dfa.rar_dfa转mfa_nfa-dfa_编译原理mfa_词法分析器

编译原理中正规式转化为nfa

NFA转化为DFA编译原理课程设计

编译原理课程设计（含报告和可运行源代码）

编译原理课程设计（NFA转DFA）

编译原理课程设计NFA和DFA

NFA确定化为DFA

编译原理nfa与dfa求解

编译原理课程设计报告

编译原理课程设计3(1).ppt

编译原理课程总结

(重庆理工大学计算机学院)编译原理课程设计报告.pdf

有穷自动机 编译原理课程设计

基于VC++的编译原理课程设计

编译原理课程设计实验报告.doc

编译原理课程设计实验报告

编译原理课程设计

编译原理课程设计1(1).ppt

DFA的最小化（完整可运行代码）

有穷自动机编译原理课程设计