利用子集法构造DFA.doc

《利用子集法构造DFA.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验一：利用子集法构造DFA一．实验目的掌握将非确定有限自动机确定化的方法和过程。二．实验要求、容及步骤实验要求：1.输入一个NFA，输出一个接受同一正规集的DFA；2.采用C++语言，实现该算法；3.编制测试程序；4.调试程序。实验步骤：1.输入一个NFA关系图；2.通过一个转换算法将NFA转换为DFA；3.显示DFA关系图。三．实验设备计算机、Windows操作系统、VisualC++程序集成环境。四．实验原理1.NFA-DFA转换原理：从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表

2、项是一个状态，NFA到相应的DFA的构造的基本思路是：DFA的每一个状态对应NFA的一组状态。DFA使用它的状态去记录在NFA读入一个输入符号后可能到达的所有状态。输入：一个NFAN输出：一个接受同样语言的DFAD方法：为D构造转换表Dtran，DFA的每个状态是NFA的状态集。D的状态集合用Dstates表示。D的开始状态为ε-closure(s0)，s0是N的开始状态。使用下列算法构造D的状态集合Dstates和转换表Dtran。如果D的某个状态是至少包含一个N的接受状态的NFA状态集，那么它是D的一个接受状态。2.

3、子集构造法：初始时,ε-closure(S0)是Dstates中唯一的状态且未被标记;whileDstates中存在一个未标记的状态Tdobegin标记T;for每个输入符号adobeginU:=ε-closure(move(T,a));ifU没在Dstates中then将U作为一个未被标记的状态添加到Dstates.Dtran[T,a]:=Uendend3.ε-closure的计算：将T中所有状态压入栈stack;将ε-closure(T)初始化为T;whilestack不空dobegin将栈顶元素t弹出栈;for每个

4、这样的状态u：从t到u有一条标记为ε的边doifu不在ε-closure(T)中dobegin将u添加到ε-closure(T);将u压入栈stack中endend五．程序设计1.总体设计读入字符识别模块识别标识符识别分界符、运算符识别常数输出2.子程序设计识别模块读取字符字母识别标识符数字识别数字/识别注释打印并结束FTFTFT六．程序中的结构说明1.结构体Symbolrecord结构体结构体成员名成员属性Symbol[10]用于存储关键字编码名id用于存储关键字对应的编码entrytype结构体结构体成员名成员属性i

5、dname[10]用于存储识别后标识符名address用于存储标识符的地址type用于存储标识符的类型digittype结构体结构体成员名成员属性num用于存储识别后的数字address用于存储标识符数字的地址tokentype结构体结构体成员名成员属性id用于存储被识别的类型名entry用于存储标识符的地址idname[10]用于存储被识别的标识符名2.符号编码表符号编码表符号名代码符号名代码Begin0}14End1(15If2)16Then3<17Else4<=18for5=19do6!=20while7>21+8

6、>=22-9:=23*10‘’24/11Id25;12Const26{133.重要函数介绍tokentyperecogid(charch)//识别标识符算法tokentyperecogdig(charch)///识别数字函数tokentyperecogdel(charch)//识别算符和界符函数tokentypehandlecom(charch)//handlecom函数，识别注释函数voidsort(charch)//sort函数，读取文件容，并根据读入容调用不同的识别函数voidscanner()//scanner函

7、数，打开文件七.函数代码#include#include#include#include//定义单词编码表的数据结构structsymbolrecord{charsymbol[10];intid;};//定义符号表的数据结构structentrytype{charidname[10];intaddress;inttype;};//定义常数表的数据结构structdigittype{intnum;intaddress;};//Token字的数据结构

8、structtokentype{intid;intentry;charidname[10];};FILE*fp;//源文件指针structdigittyped[10];//定义常数表，个数指针structentrytypea[40];intk=0,t=0;//单词编码表初始化structsymbolrecords[2