朱航宇-20112878-编译原理合设计

编译原理合设计

指导教师：李宏芒专业班级：信安姓 名：朱航宇学 号：

11-1 20112878 - 1 -

1

一．课程设计目的

《编译原理》是计算机专业的一门重要的专业课程，其中包含大量软件设计

思想。大家通过课程设计，实现一些重要的算法，或设计一个完整的编译程序模型，能够进一步加深理解和掌握所学知识，对提高自己的软件设计水平具有十分重要的意义。

二．课程设计内容

（12,13题：12题 DFA 状态最少化的程序实现和13题 把NFA确定化为DFA 的算法实现，合并为一题，将NFA确定化为DFA，再将DFA化简即最小化。）

我在选择课程设计题目时，只选择了12题DFA的最小化。但由于12题工作

量较小同时为了提高我的编程能力我将13题NFA确定化为DFA，将这两题合并为一题，即NFA确定化到最小化的实现。NFA的确定化和DFA的最小化主要是为了更好地使用状态转换图构造词法分析程序和词法分析程序的自动生成。设计并实现将NFA确定化为DFA的子集构造算法以及DFA的最小化，从而更好地理解有限自动机之间的等价性，掌握词法分析器自动产生器的构造技术。 三．设计要求

构造一程序，实现：将给定的NFA M(其状态转换矩阵及初态、终态信息从键盘输入)，确定化为DFA M’。（要先实现ε-CLOSURE函数和Ia函数）。输出DFA M’(其状态转换矩阵及初态、终态信息输出到屏幕上)。然后将由确定化后的的DFA M的有限状态集S划分成若干互不相交的子集，使得：任何不同的两个子集中的状态都是可区别的，而同一子集中的任何两个状态都是等价的（要利用Ia函数，但并不需要构造ε-CLOSURE函数，因这是DFA）。输出化简后的DFA M’(其状态转换矩阵及初态、终态信息输出到屏幕上)。

四．设计思路

4.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个）终态结点。对于∑*

2 - 2 -

中的任何一个字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个状态结点，每个节点最多有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。

4.2 DFA的最小化

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

L(M)=L(M’).假定s和t是M的两个不同状态，如果分别从状态s和t出发能读出同样的某个字w而停于终态，则称s和t是等价的。如果DFA M的两个状态s

3 - 3 -

和t不等价，则称这两个状态是可区别的。一个DFA M的状态最少化过程旨在将M的状态集分割成一些不相交的子集，使得任何不同的两个字集中的状态是可区别的，而同一子集中的任何两个状态都是等价的。最后，在每个自己中选出一个代表，同时消去其他等价状态。又被删除的状态射出的弧也被删去，但是有保留下来的状态射出的弧是要全部保留的。

五．设计的基本原理

5.1总体方案设计

机状态信息的输入输出部分；二是用子集构造算法实现NFA确定化为DFA，这里面又涉及到ε_Closure(I)和转换函数Move(I,a)的实现和新生成的状态的重命名问题以及新的状态转换关系的建立；三是DFA的最小化，这里面包括等价状态的划分，等价状态的划分又涉及到终态结点和非终态结点的区分，划分之后等价状态的重命名和新的状态转换关系的建立。总体模块设计方案如下图所示：

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

4 - 4 -

程序 总体 模块 5.2各模块设计

DFA最小化 结 构 有限自动机的基本状态状态结点、边和输入终结符的结构 有限自动机状态信息的输入输出 ε_closure(I) 和 转换函数move(I,a)的实现 子集构造算 法实现NFA 定化为DFA 新生成状态的命名和等价的状态转换关系的建立 区分终结状态 和非终结状态 等价状态的划分 等价状态的重命名和新的状态转换关系的建立

1．有限自动机状态转换结构的定义和状态信息的输入输出

有限状态机的状态结点，边和终结符（即输入字符）均定义为字符串，利用

C++标准模板库string中的函数来实现定义和后续操作，以方便实现和简化 程序。具体如下程序片段：

string NODE; //结点集合 string CHANGE; //终结符集合 int N; //NFA边数

struct edge

5 - 5 -