编译原理实验报告
实验名称 正则表达式与有限自动机
院 系 奋斗的小鸟 信息工程学院
班 级 计算机科学与技术1班
学 号 2013550336
稻城亚丁红草地
姓 名 朱义
一、实验目的
通过本次实验，加深对正则表达式，NFA，DFA及其识别的语言的理解
二、实验题目
编程实现NFA确定化为NFA的过程
三、算法思想
1.一个自动机是一个五元组，分别是<状态集，符号集，f函数,起始状态，终止状态>
2.使用子集法的步骤是：
1)将起始状态求闭包，得到S0。
2)从0开始直到totss对每个子集求各个字符所能到达的新子集将其加入tot+1子集中。
3)检查tot+1子集是否与之前的子集重合或者为空,如果重合或为空则子集不增加.
4)记录新的状态转换函数。
3. 根据NFA转化为DFA的过程一步步模拟进行操作。
四、数据结构介绍
程序里将NFA五元组分别储存在以下数据结构里
初态集储存在 int数组 sta_statu［maxs］里 maxs为元素的最大数
终态集储存在 int数组 end_statu[maxs］里
字符集储存在 char数组 cha[maxs］里
状态储存为0～n-1（n个状态情况）
状态转换函数储存于结构 stuct statu里
嘴巴干燥起皮怎么办struct Edge｛ //转化边
char cost； //消耗
int dest; //指向的终点
｝；
struct statu
{
Edge node［50］； // 终点
武昌起义领导人
int cnt;//边的数量
statu(）
｛
cnt=0；
for(int i=0;i<50；i++)
{node[i].cost=’＃'；
node［i］.dest=0;｝
安居客中国网络经纪人登录 ｝
｝sta[50];//起点
五、具体实现
使用子集法实现：
函数接口解释：
void creat_subt(void）; 构造子集函数
Ins(int a，int ss) 用深搜（dfs）求状态ss的闭包，并将闭包里的所有元素加入到子集closure[a]里。
void ins_subt（int a，int ss,char target） 求状态ss通过字符target所能到达的所有状态，并将这些状态加入到子集closure[a]里。
int check（int tt） 检查子集closure［tt]是否与之前的子集重合，为空则返回—2，不重合返回—1,重合则返回重合的子集下标.
void print（void） 输出DFA的五元组信息.
1.将起始状态求闭包,得到S0.
将初状态里所有的元素及其能通过e空路所到的状态加入closure[0]作为初始子集
for(int i=0；i〈ct_sta_statu;i++） // 求起始状态求闭包，得到S0宝宝看电视
{
closure［0］.members。inrt（sta_statu[i]);
ins(0，sta_statu[i］)；
｝ // e_closure（s0）
2。从0开始直到totss对每个子集求各个字符所能到达的新子集将其加入tot+1子集中。
for(tempss=0；tempss〈=totss；tempss++）//tempss 表示当前运算的状态下表 totss表示总共的状态数 新生产的状态子集加入到 closur[tot+1］中
{计算中的上帝
for(int j=0；j〈ct_cha；j++)
zsyhfor（it=closure[tempss].members.begin(）；it!=closure［tempss］。members。end（)；it++)
