正规式、NFA、DFA、MFA的转换.doc

《正规式、NFA、DFA、MFA的转换.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机专业软件类课程实验报告课程名称：编译原理实验题目：正规式、NFA、DFA、MFA的转换实验小组成员：实验小组组长：任课教师：专业名称：计算机科学与技术班级名称：计科1班实验起止时间：2014-5-19~2014-5-29一、实验目的1、理解什么是正规式2、理解NFA、DFA、MFA的概念；3、掌握正规式和NFA之间的等价变换；4、掌握NFA和DFA之间的等价变换；5、掌握DFA和MFA之间的等价变换；6、了解程序设计语言Java的语言机制。二、实验内容程序的流程图如下所示：1、根据用户输入的表达式，验

2、证是否为合法的正规式2、根据正规式，将其转换为NFA3、根据NFA，将其转换为DFA4、根据DFA，将其转换为MFA三、实验需求1、正规式验证对输入的表达式能够做出正确的判断，如果是合法的正规式，则激活正规式转为NFA的功能；如果不是合法的正规式，则会弹出消息框进行提示2、正规式转为NFA对经过验证的正规式，根据算法，将其转换为NFA，得出开始符号集、终结符号集以及符号集，并激活NFA转为DFA的功能；也可以点击打开按钮，选择一个格式符合规范的NFA文件，同时激活NFA转为DFA的功能；也可以对得到的NFA

3、进行保存3、NFA转为DFA对第一个文本框中的NFA，根据算法，将其转换为DFA，得出开始符号集、终结符号集以及符号集，并激活DFA转为MFA的功能；也可以点击打开按钮，选择一个格式符合规范的DFA文件，同时激活DFA转为MFA的功能；也可以对得到的DFA进行保存4、DFA转为MFA对第二个文本框中的DFA，根据算法，将其转换为MFA，得出开始符号集、终结符号集以及符号集；也可以点击打开按钮，选择一个格式符合规范MFA文件；也可以对得到的MFA进行保存四、主要数据结构介绍1、自定义一个JavaBean，这个

4、类里只有三个属性，节点的开始符号，接受符号，终结符号，并有他们的get()、set()方法，将类名定义为Node2、整个程序涉及到的NFA、DFA、MFA都存放在ArrayList中，每次通过迭代器Iterator进行迭代3、在正规式转为NFA时，将创建一个开始符号栈和一个终结符号栈，分别用来存储开始符号和终结符号4、在NFA转换为DFA时，创建一个对象数组Object[][2]，每个数组单元第一列为ArrayList，存放的是节点号，第二列是一个Boolean，标记

5、该状态T是否被访问过5、在DFA转换为MFA时，创建一个对象数组Object[]，每个数组单元为ArrayList，存放的是每次划分的节点信息五、主要模块算法介绍1、正规式验证将输入的正规式使用toCharArray()转换成一个一个字符，然后对字符进行处理，主要是验证左右括号是否匹配正确，以及”

6、”，”.”，”*”等符号位置是否合法，输入的表达式中是否含有非法字符2、正规式转为NFA对经过验证的正规式进行一个字符一个字符的判断，其中”*”的优先级最高，其次是”.”，最后是”

7、”。在转换过程

8、中，构造两个栈，一个栈是开始符号栈，用来存放创建的开始符号，一个是终结符号栈，用来存放创建的终结符号。通过对”

9、”，”.”，”*”优先级的的不同，对两个栈进行不同的处理，将产生的结点存入ArrayList中3、NFA转为DFA将从第一个文本框中读出的NFA节点信息存入ArrayList，由迭代器进行迭代，算法的流程如下图所示：开始求开始状态闭包标记Ｆ令它为集合C中的唯一成员集合C中存在尚未被标记子集标记Ｔ对子集Ｔ中的每个输入字母求Ｕ＝Ｉa子集将Ｕ加入Ｃ中结束语是否4、DFA转为MFA

10、化简DFA的基本思想是指导它的状态分成一些互不相交的子集，每一个子集中的状态都不是等价的，不同子集中的状态可以由某个输入串来区别，最后将不能区别的每个子集用一个状态来做代表，这种方法称为“分割法”。具体过程是：（1）将M的所有状态分成两个子集——终态集和非终态集；（2）考察每一个子集，若发现某子集中的状态不等价，将其划分为两个集合；（3）重复第（2）步，继续考察已得到的每一个子集，直到没有任何一个子集需要继续划分为止。这时DFA的状态被分成若干个互不相交的子集。（4）从每个子集中选出一个状态做代表即可得到最

11、简的DFA。六、程序实现环境及使用说明本次实验采用Eclipse进行代码的编写、编译及运行；编写语言为java语言；程序的运行环境为jdk1.8；系统为windows 8.1七、实验测试用例设计说明1、正规式验证（1）输入””，这是一个错误的输入（2）输入”ab

12、b”，这是一个正确的输入2、正规式转为NFA（1）输入”ab

13、b”，这是一个不含闭包的例子（2）输入”(a*

14、b)*”，这是一个含有闭包的例子3、NF