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

计算机专业软件类课程实验报告
课程名称:
编译原理
实验题目:
正规式、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的语言机制。
实验内容
程序的流程图如下所示:
根据用户输入的表达式,验证是否为合法的正规式
2、根据正规式,将其转换为NFA
3、根据NFA,将其转换为DFA
4、根据DFA,将其转换为MFA
实验需求
正规式验证
对输入的表达式能够做出正确的判断,如果是合法的正规式,则激活正规式转为NFA的功能;如果不是合法的正规式,则会弹出消息框进行提示
正规式转为NFA
对经过验证的正规式,根据算法,将其转换为NFA,得出开始符号集、终结符号集以及符号集,并激活NFA转为DFA的功能;也可以点击打开按钮,选择一个格式符合规范的NFA文件,同时激活NFA转为DFA的功能;也可以对得到的NFA进行保存
NFA转为DFA
对第一个文本框中的NFA,根据算法,将其转换为DFA,得出开始符号集、终结符号集以及符号集,并激活DFA转为MFA的功能;也可以点击打开按钮,选择一个格式符合规范的DFA文件,同时激活DFA转为MFA的功能;也可以对得到的DFA进行保存
DFA转为MFA
对第二个文本框中的DFA,根据算法,将其转换为MFA,得出开始符号集、终结符号集以及符号集;也可以点击打开按钮,选择一个格式符合规范MFA文件;也可以对得到的MFA进行保存
主要数据结构介绍
自定义一个JavaBean,这个类里只有三个属性,节点的开始符号,接受符号,终结符号,并有他们的get()、set()方法,将类名定义为Node
整个程序涉及到的NFA、DFA、MFA都存放在ArrayList中,每次通过迭代器Iterator进行迭代
在正规式转为NFA时,将创建一个开始符号栈和一个终结符号栈,分别用来存储开始符号和终结符号
在NFA转换为DFA时,创建一个对象数组Object[][2],每个数组单元第一列为ArrayList,存放的是节点号,第二列是一个Boolean,标记该状态T是否被访问过
在DFA转换为MFA时,创建一个对象数组Object[],每个数组单元为ArrayList,存放的是每次划分的节点信息
主要模块算法介绍
正规式验证
将输入的正规式使用toCharArray()转换成一个一个字符,然后对字符进行处理,主要是验证左右括号是否匹配正确,以及
”|”,”.”,”*”等符号位置是否合法,输入的表达式中是否含有非法字符
2、正规式转为NFA
对经过验证的正规式进行一个字符一个字符的判断,其中”*”的优先级最高,其次是”.”,最后是”|”。在转换过程中,构造两个栈,一个栈是开始符号栈,用来存放创建的开始符号,一个是终结符号栈,用来存放创建的终结符号。通过对”|”,”.”,”*”优先级的的不同,对两个栈进行不同的处理,将产生的结点存入ArrayList中
3、NFA转为DFA
将从第一个文本框中读出的NFA节点信息存入ArrayList,由迭代器进行迭代,算法的流程如下图所示:
开始
求开始状态闭包
标记F令它为集合C中的唯一成员
集合C中存在尚未被标记子集
标记T
对子集T中的每个输入字母求U=Ia子集
将U加入C中
结束语
是
否
DFA转为MFA
化简DFA的基本思想是指导它的状态分成一些互不相交的子集,每一个子集中的状态都不是等价的,不同子集中的状态可以由某个输入串来区别,最后将不能区别的每个子集用一个状态来做代表,这种方法称为“分割法”。具体过程是:
(1)将M的所有状态分成两个子集——终态集和非终态集;
(2)考察每一个子集,若发现某子集中的状态不等价,将其划分为两个集合;
(3)重复第(2)步,继续考察已得到的每一个子集,直到没有任何一个子集需要继续划分为止。这时DFA的状态被分成若干个互不相交的子集。
(4)从每个子集中选出一个状态做代表即可得到最简的DFA。
程序实现环境及使用说明
本次实验采用Eclipse进行代码的编写、编译及运行;
编写语言为java语言;
;
系统为windows
实验测试用例设计说明
正