正规式转换和最小dfa毕业设计.doc
约35页DOC格式手机打开展开
正规式转换和最小dfa毕业设计,正规式转换和最小dfa毕业设计本文共计34页，8336字；正规式转换和最小dfa摘要 编译程序的工作过程通常是词法分析、语法分析、语义分析、代码生成、代码优化。编译程序的这些过程的执行先后就构成了编译程序的逻辑结构，但是这些逻辑结构不一定是按照某一个固定顺序的，也有可能是按照平行或者互锁的方式执行的。本文主要介绍基于编...
内容介绍
此文档由会员 霜天盈月 发布
正规式转换和最小DFA毕业设计
本文共计34页，8336字；
正规式转换和最小DFA
摘 要
编译程序的工作过程通常是词法分析、语法分析、语义分析、代码生成、代码优化。编译程序的这些过程的执行先后就构成了编译程序的逻辑结构，但是这些逻辑结构不一定是按照某一个固定顺序的，也有可能是按照平行或者互锁的方式执行的。
本文主要介绍基于编译器构造技术中的由正规表达式到最小化DFA的算法设计和实现技术；把NFA转化为与其等价的DFA所使用的子集构造算法最后实现词法分析。NFA转化为与其等价的DFA需分两步进行：a、构造NFA N的状态K的子集的算法；b、计算e-closure。c、用分割法对DFA实现最小化。完成这些子模块的设计后，再通过某一中间模块的总控程序对其调用，最后再由主程序合并调用。在算法实现过程中，主要使用visual C++进行编程，并且用到了STL（标准模板库）技术来对边集、状态集进行定义和处理。正规表达式与自动机理论在词法构造乃至整个编译器构造过程中起着至关重要的作用，同时它们被广泛应用于计算机科学的各个领域，它们与计算机其它学科之间也有着很大的联系。
关键词：正则表达式，NFA，DFA，Thompson构造法，子集构造算法， 分割法
目 录
摘要 ………………………………………………………………………………1
第1章 绪论 ………………………………………………………………………
1.1 实验环境与开发工具 ……………………………………………………5
1.2 有穷动机简介 ……………………………………………………………6
1.3 基本概念 ……………………………………………………………………6
1.4 NFA向DFA转换 ……………………………………………………………6
1.5 DFA 的矩阵表示 ……………………………………………………………7
1.6正规式、正规表达式、有限自动机之间的关系…………………………….7
第2章 设计任务的组织和分工 …………………………………………………
2.1小组任务分工…………………………………………………………………
2.2 本人主要任务…………………………………………………………………
第3章 需求分析
3.1 总体功能需求 …………………………………………………………………9
3.2 系统主要功能…………………………………………………………………10
3.3 数据流图………………………………………………………………………11
3.4 数据字典………………………………………………………………………
3.5 数据项………………………………………………………………………
3.6 数据结构………………………………………………………………………
第4章 详细设计
4.1功能模块设计………………………………………………………………………13
4.2 算法设计………………………………………………………………………13
4.2.1 将正则表达式转换为有限自动机………………………………………
4.2.2 实现从NFA构造DFA的算法---子集构造法…………………………………
4.2.3 确定有限自动机的化简…………………………………………………………
4.3 主函数说明………………………………………………………………………
4.4 流程图………………………………………………………………………
4.4.1 用Thompson构造法构造NFA……………………………………………
4.4.2 用子集构造法构造DFA…………………………………………………
4.4.3 DFA化简………………………………………………………………………
第5章 界面设计……………………………………………………………………16
5.1界面用途………………………………………………………………………
5.2界面的建设………………………………………………………………………
5.3界面的优点与不足…………………………………………………………………
第六章结论
参考文献 ……………………………………………………………………………19
总结 …………………………………………………………………………………20
附录
源程序 ……………………………………………………………………………21
参考资料
1、软件工程导论（第三版） 清华大学出版社 张海潘著
2、编译原理（第二版） 西北工业大学出版社 蒋立源等著（方法全）
3、程序设计语言编译原理 国防工业大学出版社 陈火旺著（原理强）
4、编译程序设计 北京大学出版社 王永宁著（实现佳）
5、Visual C++6.0开发使用手册 机械工业出版社 Brian Siler等著
6、编译原理（第2版）清华大学出版社 张素琴 吕映之 等著
本文共计34页，8336字；
正规式转换和最小DFA
摘 要
编译程序的工作过程通常是词法分析、语法分析、语义分析、代码生成、代码优化。编译程序的这些过程的执行先后就构成了编译程序的逻辑结构，但是这些逻辑结构不一定是按照某一个固定顺序的，也有可能是按照平行或者互锁的方式执行的。
本文主要介绍基于编译器构造技术中的由正规表达式到最小化DFA的算法设计和实现技术；把NFA转化为与其等价的DFA所使用的子集构造算法最后实现词法分析。NFA转化为与其等价的DFA需分两步进行：a、构造NFA N的状态K的子集的算法；b、计算e-closure。c、用分割法对DFA实现最小化。完成这些子模块的设计后，再通过某一中间模块的总控程序对其调用，最后再由主程序合并调用。在算法实现过程中，主要使用visual C++进行编程，并且用到了STL（标准模板库）技术来对边集、状态集进行定义和处理。正规表达式与自动机理论在词法构造乃至整个编译器构造过程中起着至关重要的作用，同时它们被广泛应用于计算机科学的各个领域，它们与计算机其它学科之间也有着很大的联系。
关键词：正则表达式，NFA，DFA，Thompson构造法，子集构造算法， 分割法
目 录
摘要 ………………………………………………………………………………1
第1章 绪论 ………………………………………………………………………
1.1 实验环境与开发工具 ……………………………………………………5
1.2 有穷动机简介 ……………………………………………………………6
1.3 基本概念 ……………………………………………………………………6
1.4 NFA向DFA转换 ……………………………………………………………6
1.5 DFA 的矩阵表示 ……………………………………………………………7
1.6正规式、正规表达式、有限自动机之间的关系…………………………….7
第2章 设计任务的组织和分工 …………………………………………………
2.1小组任务分工…………………………………………………………………
2.2 本人主要任务…………………………………………………………………
第3章 需求分析
3.1 总体功能需求 …………………………………………………………………9
3.2 系统主要功能…………………………………………………………………10
3.3 数据流图………………………………………………………………………11
3.4 数据字典………………………………………………………………………
3.5 数据项………………………………………………………………………
3.6 数据结构………………………………………………………………………
第4章 详细设计
4.1功能模块设计………………………………………………………………………13
4.2 算法设计………………………………………………………………………13
4.2.1 将正则表达式转换为有限自动机………………………………………
4.2.2 实现从NFA构造DFA的算法---子集构造法…………………………………
4.2.3 确定有限自动机的化简…………………………………………………………
4.3 主函数说明………………………………………………………………………
4.4 流程图………………………………………………………………………
4.4.1 用Thompson构造法构造NFA……………………………………………
4.4.2 用子集构造法构造DFA…………………………………………………
4.4.3 DFA化简………………………………………………………………………
第5章 界面设计……………………………………………………………………16
5.1界面用途………………………………………………………………………
5.2界面的建设………………………………………………………………………
5.3界面的优点与不足…………………………………………………………………
第六章结论
参考文献 ……………………………………………………………………………19
总结 …………………………………………………………………………………20
附录
源程序 ……………………………………………………………………………21
参考资料
1、软件工程导论（第三版） 清华大学出版社 张海潘著
2、编译原理（第二版） 西北工业大学出版社 蒋立源等著（方法全）
3、程序设计语言编译原理 国防工业大学出版社 陈火旺著（原理强）
4、编译程序设计 北京大学出版社 王永宁著（实现佳）
5、Visual C++6.0开发使用手册 机械工业出版社 Brian Siler等著
6、编译原理（第2版）清华大学出版社 张素琴 吕映之 等著
