正则表达式转化为DFA程序的设计与实现3

《正则表达式转化为DFA程序的设计与实现3》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、学号:哈尔滨师范大学学士学位论文题目正则表达式转化为DFA程序的设计与实现学生指导教师年级专业计算机科学与技术系别计算机科学与技术学院计算机科学与信息工程哈尔滨师范大学学士学位论文开题报告论文题目正则表达式转化为DFA程序的设计与实现学生姓名指导教师年级2004级专业计算机科学与技术2008年3月1日课题来源：学院分配，教师指定。课题研究的目的和意义：正则表达式转化为DFA,主要是解决给定一个正则表达式自动转化为DFAo其Fl的在于了解和掌握正则表达式自动转化为DFA的过程，理解和掌握编译中的技术方法，对编译原理的教学研究有着积极的意义。通过研究可加强对学生应

2、用能力的培养，使学生不仅具备理论知识，更耍具备应用能力，使所学能为所用。在编译的教学过程中，把正则表达式转化为DFA是编译原理中的基本方法,在转换过程中，多数是采用手工运算，运算量大而且有时不是很准确。就算是准确的话，时间也浪费太多。这个课题主要就是解决这个问题。本课题就是讨论正则表达式转化为DFA程序的设计与实现这个问题采用计算机来实现，这样既准确又方便，更利于对编译原理的理解与掌握。国内外同类课题研究现状及发展趋势：通过对国内外有关的学术刊物（如《MFC编程》、《编译原理》、《COMPUTERTechnology》等）、教育网站和国际内有关学术会议（GCC

3、CE、ICCE、CBE等）的论文集进行分析，编译教学的设计研究主要是关于语法分析设计等方面，缺乏系统的研究。可以说，编译教学的设计理论的研究还处于初级阶段，还有很多问题需耍去研究和探索。当然，在美国，日本，英国等发达国家，在这一方面的研究比中国进步得多。我们在学习外国的技术中应该进一步提高自己。现在大的发展趋势是编程方向。首先，同类课题包括了更加复杂算法的应用程序，它用于推断或简化程序中的信息；这又与更为复杂的程序设计语言的发展结合在一起。其中典型的有用于函数语言编译Milner类型检查的统一算法。其次，同类课题已越来越成为基于窗口的交互开发环境（Intera

4、ctiveDevelopmentEnvironment,IDE）的一部分，它包括了编辑器、连接程序、调试程序以及项目管理程序。这样的IDE标准并没有多少，但是对标准的窗口环境进行开发已成为方向。另一方面，尽管近年来在编译原理领域进行了大量的研究，但是基本的设计原理在近20年中都没有多大的改变。AlfredV.Ullman是美国AT&T贝尔实验室计算机原理研究员的负责人。他在多伦多大学获得工程物理专业应用科学学士学位，在普林斯顿大学获得博士学位。JohnBackus是美国一位在编译方面的专家，他们都是这个同类课题方面的专家。课题研究的主要内容和方法，研究过程中的

5、主要问题和解决办法：木文主要介绍基于编译器构造技术中的由正规表达式到最小化DFA的算法设计和实现技术；主要包括由正则表达式构造NFA所用到的Thompson构造法、把NFA转化为与其等价的DFA所使用的子集构造算法以及把DFA最小化的算法，最后实现词法分析。Thompson构造法根据读入的正规表达式的不同字符进入相应的转换处理。NFA转化为与其等价的DFA需分两步进行：a、构造NFAN的状态K的子集的算法；b、计算“closure。完成这些子模块的设计后，再通过某一中间模块的总控程序对其调用，最后再由主程序合并调用。在算法实现过程中，主要使用C++进行编程，并

6、且用到了STL（标准模板库）技术来对边集、状态集进行定义和处理。正则表达式与自动机理论在词法构造乃至整个编译器构造过程中起着至关重要的作用，同时它们被广泛应用于计算机科学的各个领域，它们与计算机其它学科Z间也有着很大的联系。主要问题：正则表达式转化为NFA所用到的Thompson构造法NFA转化为DFA的子集构造法确定有限自动机DFA的化简解决办法：通过查找资料，进行实验，老师指导等方法逐一解决。课题研究起止时间和进度安排：2008-1-15——2008-3-12008-3-2——2008-3-202008-3-21——2008-4-102008-4-11——

7、2008-4-302008-5-1——2008-5-10确定论文题目，查找资料，撰写开题报告查找资料，进一步分析题目研究内容撰写论文并送老师第一次审查论文第二次修改，老师第二次审查论文第三次审查、修改并作毕业答辩前准备交论文，答辩课题研究所需主要设备、仪器及药品：硬件需要：计算机软件需要：安装C++系统计算机要求：WindowsXP（较好）、Windows2000>Windows98可选外出调研主要单位，访问学者姓名:兰州交通大学，李敬文指导教师审查意见:指导教师（签字）2008年3月教研室（研究室）评审意见：教研室（研究室）主任（签字）2008年3月系（部）

8、主任审查意见：系（部）主任（签字）20