利用子集法构造dfa.doc

实验一: 掌握将非确定有限自动机确定化的方法和过程。、内容及步骤实验要求:,输出一个接受同一正规集的DFA;++语言,实现该算法;;。实验步骤:;;。、Windows操作系统、VisualC++程序集成环境。-DFA转换原理:从NFA的矩阵表示中可以看出,表项通常是一状态的集合,而在DFA的矩阵表示中,表项是一个状态,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的一个接受状态。:初始时,ε-closure(S0)是Dstates中唯一的状态且未被标记;whileDstates中存在一个未标记的状态Tdobegin标记T;for每个输入符号adobeginU:=ε-closure(move(T,a));[T,a]:=-closure的计算:将T中所有状态压入栈stack;将ε-closure(T)初始化为T;whilestack不空dobegin将栈顶元素t弹出栈; for每个这样的状态u:从t到u有一条标记为ε的边doifu不在ε-closure(T)中dobegin将u添加到ε-closure(T);、.结构体Symbolrecord结构体结构体成员名成员属性Symbol[10]用于存储关键字编码名id用于存储关键字对应的编码entrytype结构体结构体成员名成员属性idname[10]用于存储识别后标识符名address用于存储标识符的地址type用于存储标识符的类型digittype结构体结构体成员名成员属性num用于存储识别后的数字address用于存储标识符数字的地址tokentype结构体结构体成员名成员属性id用于存储被识别的类型名entry用于存储标识符的地址idname[10]}14End1(15If2)16Then3<17Else4<=18for5=19do6!=20while7>21+8>=22-9:=23*10‘’24/11Id25;12Const26{(charch)//识别标识符算法tokentyperecogdig(charch)///识别数字函数tokentyperecogdel(charch)//(charch)//函数,识别注释函数voidsort(charch)//sort函数,读取文件内容,并根据读入内容调用不同的识别函数voidscanner()//scanner函数,#include<>#include<>#include<>#include<>//定义单词编码表的数据结构structsymbolrecord{charsymbol[10];intid;};//定义符号表的数据结构structentrytype{charidname[10];intaddress;inttype;};//定义常数表的数据结构structdigittype{intnum;intaddress;};//Token字的数据结构structtokentype{intid;intentry;charidname[10];};FILE*fp;//源文件指针structdigittyped[10];//定义常数表,个数指针structentrytypea[40];intk=0,t=0;//单词编码表初始化structsymbolrecords[26]={"Begin",0,"End",1,"If",2,"T