2022年正则式转换成最小DFA终稿 .pdf

《2022年正则式转换成最小DFA终稿 .pdf》由会员分享，可在线阅读，更多相关《2022年正则式转换成最小DFA终稿 .pdf（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、#include #include #include #include #define MAXLENGTH 50 char tokenMAXLENGTH=;/输入字符串char buffMAXLENGTH=;/ 缓冲区char stackMAXLENGTH=;/逆波兰式所用栈char stringMAXLENGTH=;/存逆波兰式char letterMAXLENGTH=;/输入字母集int len_letter;/ 字母的种类数int nfa_gMAXLENGTH2;/nfa状态存储数组char nfa_sMAXLENGTH;/nfa变量int len_nfa;/nfa 状态数组长度int

2、headMAXLENGTH;/nfa中间状态头结点int tailMAXLENGTH;/nfa中间状态头结点int buff_dfaMAXLENGTH;/dfa中间缓冲区int bufdMAXLENGTH;/dfa第二缓冲区int closureMAXLENGTHMAXLENGTH;/closure集合存储数组int len_closureMAXLENGTH;/closure数组长度int buff_jiMAXLENGTH;/寻找 closure 集合缓冲区int dfa1MAXLENGTHMAXLENGTHMAXLENGTH;/dfa1简化前存储数组int dfa2MAXLENGTHMAXL

3、ENGTH;/dfa简化后存储数组int stack_jiMAXLENGTH;/寻找 closure 集合所用栈int q_head,q_tail;/closure 集合所用队列头尾指针int min_dfaMAXLENGTHMAXLENGTH; int buff_mdfaMAXLENGTH; int xulieMAXLENGTH; int min_dfa_num; int flag_min; / void init(void);/ 初始化一些全局变量void start_token(void);/ 开始int letter_found(char *);/ 将正则式中的字母和种类数找出来int

4、 ismistake(void);/ 正规式是否错误int have_letter(int);/ 在正规式字符串该点以前是否有字母/ void jiadian(char *);/ 在正则式中加入点作为连接运算符名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 22 页 - - - - - - - - - int pre(char);/nfa 运算符优先级char nibolan(char *);/ 改写成逆波兰式void NFA_create(void);/ 构造 nfa

5、/ int found_ji(int);/寻找 closure 集合/void paixu(int *,int);/排序数组int insert(int *,int,int);/closure集合插入新元素int same_clo(int);/ 查看是否已有相同的closure void DFA_create(void);/ 构造 dfa / void min_DFA(void);/ 构造最小 dfa int found_z(void);/ 寻找终态集合int same_contain(int,int);/ 查看两个状态是否在一个集合里int contain(int,int);/ 查看两个状态

6、中同一个变量下的两个状态是否相同int min_f(int);/ 输入 dfa 的状态，返回其在最小dfa 中的状态int main() int n,i,t,k; char y; int j; do init(); printf(n 请输入正规式(只能用小写字母，以#开始，以 #结束 ):); scanf(%s,token); getchar(); if(ismistake()=1) printf(n 正则式错误！ ！ ！n); else start_token(); printf(n 是否继续？ Y/Nn); /scanf(%c,&y); y=getchar(); while(y=y); e

7、xit(0); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 22 页 - - - - - - - - - void start_token() int n=0,i,t,k,i1; int j; len_letter=t=letter_found(token); jiadian(token); nibolan(buff); NFA_create(); printf(n 逆波兰式为：%s,string); printf(n 字母集为： %s,letter); printf

8、( 代表空 ):n); for(i=0;i%d,nfa_si,nfa_gi0,nfa_gi1); printf(nhead:%dttail:%dn,head0,tail0); DFA_create(); n( 代表为空 ); printf(n 状态 t); if(t=0) printf(n); printf(%d,dfa1001); for(i=0;it;i+) printf(%ct,letteri); for(i=0;iq_head;i+) printf(n); for(j=0;jt+1;j+) if(dfa1ij1=9&dfa1ij2=9&dfa1ij3=9) printf( ); els

9、e for(k=1;kdfa1ij0+1;k+) printf(%d,dfa1ijk); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 22 页 - - - - - - - - - printf(t); printf(nn 确定 DFA(代表为空 )：n); printf( 状态 t); for(i=0;it;i+) printf(%ct,letteri); for(i=0;iq_head;i+) printf(n); for(j=0;jt+1;j+) if(dfa2i

10、j=999) printf( );printf(t); else printf(%d,dfa2ij); printf(t); min_DFA(); printf(nn 确定最小DFA(代表为空 )：n); /*printf( 状态 t); printf(n); for(i=0;imin_dfa_num;i+) for(i1=0;min_dfaii1!=999;i1+) printf(%d,min_dfaii1); printf(t); printf(n);*/ printf( 状态 t); if(t=0) printf(n); printf(%dt,dfa1001); printf( 终态 )

11、; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 22 页 - - - - - - - - - else for(i=0;it;i+) printf(%ct,letteri); / printf(%dt,min_dfa_num); for(i=0,i1=0;imin_dfa_num;i1+) if(i=min_f(i1) printf(n); printf(%dt,i); for(j=1;jt+1;j+) if(dfa2i1j=999) printf( );printf

12、(t); else printf(%d,min_f(dfa2i1j); printf(t); i+; printf( 终态 ); printf(nnn); void init(void) int i=0,j,k; len_letter=0; len_nfa=0; q_head=0; q_tail=0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 22 页 - - - - - - - - - head1=0; head2=0; tail1=0; tail2=0; for

13、(i=0;iMAXLENGTH;i+) tokeni=0;/ 输入字符串buffi=0;/ stacki=0;/ stringi=0;/ letteri=0; buff_mdfai=999; xuliei=999; nfa_gi0=0; nfa_gi1=0; buff_dfai=0; bufdi=0; len_closurei=0; buff_jii=0;/ stack_jii=0;/ for(j=0;jMAXLENGTH;j+) closureij=0; dfa2ij=999; min_dfaij=999; for(k=0;kMAXLENGTH;k+) dfa1ijk=0; int init

14、_mdfa() int i; for(i=0;iMAXLENGTH;i+) buff_mdfai=999; int ismistake() int i,t=1; int k=0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 22 页 - - - - - - - - - for(k=0;kMAXLENGTH;k+) if(tokenk=() t+; if(t1) return 1; else if(tokenk=) t-; if(t1) return 1; if(t!=

15、1)return 1; if(token0!=#)return 1; for(i=1;i=a&tokeni=z); else switch(tokeni) case #: if(tokeni+1!=0) return 1; break; case |: if(tokeni+1=|tokeni+1=)|have_letter(i)=0) return 1; break; case (: if(tokeni+1=)|tokeni+1=|tokeni+1=*) return 1; break; case ): 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - -

16、- - - - - - 名师精心整理 - - - - - - - 第 7 页，共 22 页 - - - - - - - - - if(have_letter(i)=0) return 1; break; case *: if(tokeni+1=*|have_letter(i)=0) return 1; break; case 0: if(tokeni-1!=#) return 1; return 0; break; default :return 1;break; return 0; int have_letter(int i) int j; for(j=0;j=a&tokenj=a&toke

17、ni=z) for(j=0;j=pre(b) stringk+=b; -j; b=stackj-1; stackj+=a; else stringk+=a; a=buff+i; a=stack-j; while(a=|a=*|a=.) stringk+=a; a=stack-j; stringk=0; void jiadian(char * token) int i=1,j=1; buff0=#; while(tokeni!=#) if(tokeni+1=a&tokeni+1=a&stringi=z) flag_head_tail+; headflag_head_tail=h; tailfla

18、g_head_tail=t; nfa_glen_nfa0=h; nfa_glen_nfa1=t; nfa_slen_nfa=stringi; len_nfa+; t=t+2; h=h+2; else if(stringi=.) nfa_glen_nfa0=tailflag_head_tail-1; nfa_glen_nfa1=headflag_head_tail; nfa_slen_nfa=; tailflag_head_tail-1=tailflag_head_tail; tailflag_head_tail=0; headflag_head_tail=0; p=1; len_nfa+; f

19、lag_head_tail-; else if(stringi=*) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 22 页 - - - - - - - - - nfa_glen_nfa0=tailflag_head_tail; nfa_glen_nfa1=headflag_head_tail; nfa_slen_nfa=; tailflag_head_tail=nfa_glen_nfa1;/这是一种简化算法，下面注释的是实际算法/*nfa_glen_nfa0=h;

20、nfa_glen_nfa1=headflag_head_tail; nfa_slen_nfa=; len_nfa+; nfa_glen_nfa0=tailflag_head_tail; nfa_glen_nfa1=t; nfa_slen_nfa=; len_nfa+; headflag_head_tail=h; tailflag_head_tail=t; nfa_glen_nfa0=h; nfa_glen_nfa1=t; nfa_slen_nfa=; len_nfa+; t=t+2; h=h+2;*/ len_nfa+; else if(stringi=|) nfa_glen_nfa0=h;

21、nfa_glen_nfa1=headflag_head_tail-1; nfa_slen_nfa=; len_nfa+; nfa_glen_nfa0=h; nfa_glen_nfa1=headflag_head_tail; nfa_slen_nfa=; len_nfa+; headflag_head_tail-1=h; h=h+2; nfa_glen_nfa0=tailflag_head_tail-1; nfa_glen_nfa1=t; nfa_slen_nfa=; len_nfa+; nfa_glen_nfa0=tailflag_head_tail; nfa_glen_nfa1=t; nfa

22、_slen_nfa=; len_nfa+; tailflag_head_tail-1=t; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 22 页 - - - - - - - - - t=t+2; tailflag_head_tail=0; headflag_head_tail=0; flag_head_tail-; nfa_g00=0; nfa_g01=head0; nfa_s0=; head0=0; int found_ji(i) int m=0; int k0=

23、0; int k1,k2,k3; int i1,j,q,q1; int p=0; stack_jip=i; buff_jik0=stack_jip; p+; k0+; while(p!=0) k1=stack_jip-1; stack_jip-1=0; p-; m=0; while(mlen_nfa) if(nfa_sm=&nfa_gm0=k1) stack_jip=nfa_gm1; buff_jik0=stack_jip; k0+; p+; m+; q1=k0; for(i1=0;i1q1;i1+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - -

24、 - - - - - 名师精心整理 - - - - - - - 第 13 页，共 22 页 - - - - - - - - - for(j=i1+1;jbuff_jij) q=buff_jii1; buff_jii1=buff_jij; buff_jij=q; else if(buff_jii1=buff_jij) buff_jij=999; k0-; return k0; /*void paixu(int *buff_ji,int t) int i,j,p; for(i=0;it;i+) for(j=i+1;jbuff_jij) p=buff_jii; buff_jii=buff_jij;

25、buff_jij=p; */ int insert(int *buff_dfa,int length,int k) int i,j=0,flag=1; if(length=0) buff_dfa0=k; return 1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 22 页 - - - - - - - - - else if(buff_dfalength-1=0;i-) if(buff_dfai=k) j=i; if(buff_dfaj!=k) for(i=len

26、gth-1;i=j;i-) buff_dfai+1=buff_dfai; buff_dfaj=k; length+; return length; else return length; int same_clo(int t) int i,j,m=0; for(i=0;it;i+) m=0; if(len_closurei=len_closuret) for(j=0;jlen_closuret;j+) if(closureij!=closuretj) m=1; if(m=0) return i; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - -

27、- - - - 名师精心整理 - - - - - - - 第 15 页，共 22 页 - - - - - - - - - return 999; void DFA_create() int i=0,m,n=0,j; int t,k,len; int i1,i2,i3; int p; q_head=0; q_tail=0; k=len_letter; if(k=0) dfa1001=0; t=len_closure0=found_ji(nfa_g00); /paixu(buff_ji,t); for(i=0;ilen_closure0;i+) closure0i=buff_jii; dfa100

28、0=len_closure0; dfa200=0; for(i=0;ilen_closure0;i+) dfa100i+1=closure0i; q_head=0; q_tail+; while(q_head!=q_tail) dfa1q_head00=len_closureq_head; for(i2=0;i2len_closureq_head;i2+) dfa1q_head0i2+1=closureq_headi2; dfa2q_head0=q_head; for(i=0;ik;i+) len=0; for(j=0;jlen_closureq_head;j+) for(m=0;mlen_n

29、fa;m+) if(nfa_sm=letteri&nfa_gm0=closureq_headj) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 22 页 - - - - - - - - - len=insert(buff_dfa,len,nfa_gm1); for(i1=0;i1len;i1+) bufdi1=buff_dfai1; if(len!=0) p=len; for(i1=0;i1p;i1+) t=found_ji(bufdi1); for(i2=0;i2t

30、;i2+) len=insert(buff_dfa,len,buff_jii2); len_closureq_tail=len; for(i1=0;i1len;i1+) closureq_taili1=buff_dfai1; dfa1q_headi+10=len_closureq_tail; for(i2=0;i2len_closureq_tail;i2+) dfa1q_headi+1i2+1=closureq_taili2; if(same_clo(q_tail)=999) dfa2q_headi+1=q_tail; q_tail+; else dfa2q_headi+1=same_clo(

31、q_tail); else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 22 页 - - - - - - - - - len=3; dfa1q_headi+10=len; for(i1=0;i1len;i1+) dfa1q_headi+1i1+1=9; dfa2q_headi+1=999; q_head+; int found_z() int i,j,k=0; for(i=0;iq_head;i+) for(j=1;jdfa1i00+1;j+) if(dfa1i0j

32、=tail0) min_dfa0k=i; k+; return k; int contain(int i,int j) int m,n; if(j=999|i=999) if(i=999&j!=999)return 0; else if(j=999&i!=999) return 0; else if(i=999&j=999) return 1; for(m=0;mMAXLENGTH;m+) for(n=0;nMAXLENGTH;n+) if(min_dfamn=i) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理

33、- - - - - - - 第 18 页，共 22 页 - - - - - - - - - for(n=0;nMAXLENGTH;n+) if(min_dfamn=j) return 1; return 0; int same_contain(int i,int j) int m,n,k,p,flag=0; for(p=0;plen_letter;p+) if(contain(dfa2ip+1,dfa2jp+1)=0) return 0; return 1; void min_DFA() int i,j,k,i1=0; int m,n1,n2,n3,n4; int p0,p1,p2; int

34、s0,s1,s2; k=found_z(); m=0; for(i=0;iq_head;i+) for(j=0;jk;j+) if(i=min_dfa0j) i1=1; if(i1=0) min_dfa1m=i; m+; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 22 页 - - - - - - - - - if(min_dfa10!=999) min_dfa_num=2; for(s0=0;s0q_head;s0+) for(s1=1;s1min_dfa_num

35、;s1+) init_mdfa(); n2=0; buff_mdfan2=min_dfas10; n2+; for(n1=1;min_dfas1n1!=999;n1+) if(same_contain(min_dfas10,min_dfas1n1)=1) buff_mdfan2=min_dfas1n1; n2+; p0=0; p1=0; for(n3=0;min_dfas1n3!=999;n3+) if(min_dfas1n3!=buff_mdfan3-p0) min_dfamin_dfa_nump1=min_dfas1n3; p1+; p0+; for(n1=0;n1MAXLENGTH;n1

36、+) min_dfas1n1=buff_mdfan1; if(min_dfamin_dfa_num0!=999) min_dfa_num+; else min_dfa_num=1; int min_f(int k) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 22 页 - - - - - - - - - int i,j,p; for(i=1;imin_dfa_num;i+) xuliei=i; for(i=1;imin_dfa_num;i+) for(j=i+1;j

37、min_dfaj0) p=xuliei; xuliei=xuliej; xuliej=p; for(i=0;imin_dfa_num;i+) for(j=0;min_dfaij!=999;j+) if(k=min_dfaij&i=0) return min_dfa_num-1; else if(k=min_dfaij) return xuliei-1; return 999; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 22 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 22 页 - - - - - - - - -