（毕业论文 字数：8836 页数：34）摘 要：编译程序的工作过程通常是词法分析、语法分析、语义分析、代码生成、代码优化。编译程序的这些过程的执行先后就构成了编译程序的逻辑结构，但是这些逻辑结构不一定是按照某一个固定顺序的，也有可能是按照平行或者互锁的方式执行的。
本文主要介绍基于编译器构造技术中的由正规表达式到最小化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章 绪 论
1.1 实验环境与开发工具
硬件环境：处理器AMD 2600+ 内存 512M 硬盘 80G
显示器 美格770XC+
软件环境：VC++6.0
1.2 有穷动机简介
有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。 有穷自动机分为两类：确定的有穷自动机(Deterministic Finite Automata)和不确定的有穷自动机(Nondeterministic Finite Automata) 。有限自动机是是描述特定类型算法的数学方法。在这里有穷自动机可用作描述在输入串中识别模式的过程，常用于构造扫描程序。有限自动机(简称自动机)分为确定有限自动机DFA和非确定有限自动机NFA，其中DFA是NFA的特例。
1.3基本概念
1.确定有限自动机DFA (Deterministic Finite Automata)
一个确定的有限自动机 M(记作DFA M)是一个五元组
Ｍ＝(Σ，q，q0，F，δ)，其中
(a)q是一个有限状态集合。
(b)Σ是一个字母表，它的每个元素称为一个输入符号。
(C)q0∈q，q0 称为初始状态。
(D)F∈q，F称为终结状态集合。
(e)δ是一个从q× Σ到q的单值映射
δ(q，a)＝q’(q,q’∈q，a∈Σ)表示当前状态为q,输入符号为a时，自动机将转换到下一个状态q’，q’称为q的一个后继状态。
2.非确定的有限自动机NFA (Nondeterministic Finite Automata)
一个非确定的有限自动机 M(记作NFA M)是一个五元组
Ｍ＝(Σ，q，q0，F，δ)，其中
(a)q是一个有限状态集合。
(b)Σ是一个字母表，它的每个元素称为一个输入符号。
(c)q0∈q，q0 称为初始状态。
(d)F∈q，F称为终结状态集合。
(e)δ是一个从qＸΣ∪{ε}到q的子集的映射，即δ：qＸＳ→2q
表示当前状态为q,输入符号为a时，自动机将转换到下一个状态q’，q’称为q的一个后继状态。非确定有限自动机的主要特点是：一个状态的不同输出边可标有相同的符号。这时在给定状态和符号的情况下，不能确定下一个状态，因此称之为非确定的。
1.4 NFA向DFA的转换
从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是： DFA的每一个状态对应NFA的一组状态.DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态.
1.5 DFA 的矩阵表示
一个DFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即k行a列为f(k,a)的值。用双箭头“=>”标明初态；否则第一行即是初态，相应终态行在表的右端标以1，非终态标以0。
第2章 设计任务的组织和分工
第3章 需求分析
3.1 总体功能需求
正规式转换和最小DFA 的实现，首先是将正规式转化为不确定的有穷自动机(NFA),然后将NFA转化为DFA,最后实现DFA最小化，也即DFA的确定化。
3.2 系统主要功能
本系统的主要功能包括以下几个部分：
将正则式转为逆波兰式
用Thompson构造法构造NFA
构造NFA
输出NFA状态表
用子集构造法构造DFA
构造DStates表
输出Dtran表
输出DFA
构造最小DFA
输出最小DFA
3.3 数据流图
第4章 详细设计
4.2 算法设计
4.2.1 将正则表达式转换为有限自动机
1. 有穷自动机和正规表达式之间的等价性：(1).对于∑上的一个NFA M，可以构造一个∑上的正规式R,使得L(R)=L(M)。(2).对于∑上的一个正规式R，可以构造一个∑上的NFA M，使得L(M)=L(R)。
2. 转换步骤：a. 首先把正规表达式分解成一系列的子表达式。对子表达式应用规则构造相应的NFA。
| 