《正则表达式转化为DFA程序的设计与实现》由会员分享，可在线阅读，更多相关《正则表达式转化为DFA程序的设计与实现（47页珍藏版）》请在金锄头文库上搜索。
1、学号：哈尔滨师范大学学士学位论文题 目 正则表达式转化为 DFA 程序的设计与实现学 生 指导教师 年 级 专 业 计算机科学与技术系 别 计算机科学与技术学 院 计算机科学与信息工程哈 尔 滨 师 范 大 学学士学位论文开题报告论文题目 正则表达式转化为 DFA 程序的设计与实现学生姓名 指导教师 年 级 2004 级专 业 计算机科学与技术2008 年 3 月 1 日课题来源：学院分配，教师指定。课题研究的目的和意义：正则表达式转化为 DFA，主要是解决给定一个正则表达式自动转化为DFA。其目的在于了解和掌握正则表达式自动转化为 DFA 的过程，理解和掌握编译中的技术方法，对编译原理的教学
2、研究有着积极的意义。通过研究可加强对学生应用能力的培养，使学生不仅具备理论知识，更要具备应用能力，使所学能为所用。在编译的教学过程中，把正则表达式转化为 DFA 是编译原理中的基本方法，在转换过程中，多数是采用手工运算，运算量大而且有时不是很准确。就算是准确的话，时间也浪费太多。这个课题主要就是解决这个问题。本课题就是讨论正则表达式转化为 DFA 程序的设计与实现这个问题采用计算机来实现，这样既准确又方便，更利于对编译原理的理解与掌握。国内外同类课题研究现状及发展趋势：通过对国内外有关的学术刊物(如MFC 编程 、 编译原理 、COMPUTER Technology等)、教育网站和国际内有关学
3、术会议(GCCCE、ICCE 、CBE 等 )的论文集进行分析，编译教学的设计研究主要是关于语法分析设计等方面，缺乏系统的研究。可以说，编译教学的设计理论的研究还处于初级阶段，还有很多问题需要去研究和探索。当然，在美国，日本，英国等发达国家，在这一方面的研究比中国进步得多。我们在学习外国的技术中应该进一步提高自己。现在大的发展趋势是编程方向。首先，同类课题包括了更加复杂算法的应用程序，它用于推断或简化程序中的信息；这又与更为复杂的程序设计语言的发展结合在一起。其中典型的有用于函数语言编译 Milner 类型检查的统一算法。其次，同类课题已越来越成为基于窗口的交互开发环境（Interactive
4、 Development Environment，IDE）的一部分，它包括了编辑器、连接程序、调试程序以及项目管理程序。这样的 IDE 标准并没有多少，但是对标准的窗口环境进行开发已成为方向。另一方面，尽管近年来在编译原理领域进行了大量的研究，但是基本的设计原理在近 20 年中都没有多大的改变。AlfredV.Ullman 是美国 AT&T 贝尔实验室计算机原理研究员的负责人。他在多伦多大学获得工程物理专业应用科学学士学位，在普林斯顿大学获得博士学位。John Backus 是美国一位在编译方面的专家，他们都是这个同类课题方面的专家。课题研究的主要内容和方法，研究过程中的主要问题和解决办法：本
5、文主要介绍基于编译器构造技术中的由正规表达式到最小化 DFA 的算法设计和实现技术；主要包括由正则表达式构造 NFA 所用到的 Thompson 构造法、把 NFA 转化为与其等价的 DFA 所使用的子集构造算法以及把 DFA 最小化的算法，最后实现词法分析。Thompson 构造法根据读入的正规表达式的不同字符进入相应的转换处理。NFA 转化为与其等价的 DFA 需分两步进行：a 、构造 NFA N 的状态 K 的子集的算法；b、计算 -closure。完成这些子模块的设计后，再通过某一中间模块的总控程序对其调用，最后再由主程序合并调用。在算法实现过程中，主要使用 C+进行编程，并且用到了
6、STL（标准模板库）技术来对边集、状态集进行定义和处理。正则表达式与自动机理论在词法构造乃至整个编译器构造过程中起着至关重要的作用，同时它们被广泛应用于计算机科学的各个领域，它们与计算机其它学科之间也有着很大的联系。主要问题：正则表达式转化为 NFA 所用到的 Thompson 构造法NFA 转化为 DFA 的子集构造法确定有限自动机 DFA 的化简解决办法：通过查找资料，进行实验，老师指导等方法逐一解决。课题研究起止时间和进度安排：2008-1-152008-3-1 确定论文题目，查找资料，撰写开题报告2008-3-2 2008-3-20 查找资料，进一步分析题目研究内容2008-3-212
7、008-4-10 撰写论文并送老师第一次审查2008-4-112008-4-30 论文第二次修改，老师第二次审查2008-5-1 2008-5-10 论文第三次审查、修改并作毕业答辩前准备交论文，答辩课题研究所需主要设备、仪器及药品：硬件需要：计算机软件需要：安装 C+系统计算机要求：Windows XP（较好） 、Windows2000、Windows98 可选外出调研主要单位，访问学者姓名：兰州交通大学，李敬文指导教师审查意见：指导教师 （签字）2008 年 3 月 教研室（研究室）评审意见：_教研室（研究室）主任 （签字）2008 年 3 月系（部）主任审查意见：_系（部）主任 （签字）
8、2008 年 3 月学 士 学 位 论 文题 目 正则表达式转化为 DFA 程序的设计与实现学 生 指导教师 年 级 2004 级专 业 计算机科学与技术系 别 计算机科学与技术学 院 计算机科学与信息工程哈尔滨师范大学2008 年 5 月I摘要：计算机只能读懂 0 或者 1，而我 们用高级语言编写的程序 (原程序)是抽象的符号化了的东西，为了让计算机 读懂我们写的程序，必 须把我 们书写的程序翻译成某台机器能够读懂的(机器)语言( 目标程序) ，这就是翻译程序的作用。而“编译”则是翻译程序实现的一种方式。本文主要介绍基于编译器构造技术中的由正规表达式到最小化 DFA 的算法设计和实现技术；主
9、要包括由正规表达式构造 NFA 所用到的 Thompson 构造法、把 NFA 转化为与其等价的 DFA 所使用的子集构造算法以及把 DFA 最小化的算法，最后实现词法分析。Thompson 构造法根据读入的正规表达式的不同字符进 入相应的转换处理。NFA 转化为与其等价的 DFA 需分两步 进行：a 、构造 NFA N 的状 态 K 的子集的算法；b、 计算-closure。完成 这些子模块的设计后，再通 过某一中间模块 的总控程序对其调用，最后再由主程序合并调用。在算法实现过 程中，主要使用 visual C+进行编程，并且用到了STL（标准模板库）技术来对边 集、状 态集进行定义和处理。
10、正规表达式与自动机理论在词法构造乃至整个编译器构造过程中起着至关重要的作用，同 时它们被广泛应用于计算机科学的各个领域，它们与计 算机其它学科之间也有着很大的 联系。关键字：正规表达式；DFA；THOMPSON 构造法；词法分析II目 录第一章 绪论1.1 课题背景 .11.2 课题来源 .21.3 国内外同类课题研究现状及发展趋势 .21.4 课题研究的主要内容和方法 .21.5 课题研究的目的和意义 .3第二章 正则表达式转化为 DFA 的方法研究2.1 有限自动机的定义 .42.2 正则表达式 .52.3 转换系统 .62.4 NFA 和 DFA.62.5 正规式转化为 NFA 的方法 .82.6 NFA 转化为 DFA 的算法 .82.7 确定有限自动机 DFA 的化简 .92.8 总结 .10第三章 正则表达式转化为 NFA 的设计3.1 NFA 的设计 .113.2 将正则表达式转化为 NFA(THOMPSON 构造法) .133.3 运行 NFA.
