NFA轉(zhuǎn)化為DFA編譯原理實(shí)驗(yàn)報(bào)告(共10頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱 正則表達(dá)式與有限自動(dòng)機(jī)院 系 信息工程學(xué)院 班 級(jí) 計(jì)算機(jī)科學(xué)與技術(shù)1班 學(xué) 號(hào) 姓 名 朱義 1、 實(shí)驗(yàn)?zāi)康耐ㄟ^本次實(shí)驗(yàn)，加深對(duì)正則表達(dá)式，NFA，DFA及其識(shí)別的語言的理解二、實(shí)驗(yàn)題目編程實(shí)現(xiàn)NFA確定化為NFA的過程3、 算法思想1. 一個(gè)自動(dòng)機(jī)是一個(gè)五元組，分別是<狀態(tài)集，符號(hào)集，f函數(shù)，起始狀態(tài)，終止?fàn)顟B(tài)>2. 使用子集法的步驟是：1) 將起始狀態(tài)求閉包，得到S0。2) 從0開始直到totss對(duì)每個(gè)子集求各個(gè)字符所能到達(dá)的新子集將其加入tot+1子集中。3) 檢查tot+1子集是否與之前的子集重合或者為空,如果重合或?yàn)榭?/p>

2、則子集不增加。4) 記錄新的狀態(tài)轉(zhuǎn)換函數(shù)。3. 根據(jù)NFA轉(zhuǎn)化為DFA的過程一步步模擬進(jìn)行操作。4、 數(shù)據(jù)結(jié)構(gòu)介紹程序里將NFA五元組分別儲(chǔ)存在以下數(shù)據(jù)結(jié)構(gòu)里初態(tài)集儲(chǔ)存在 int數(shù)組 sta_statumaxs里 maxs為元素的最大數(shù)終態(tài)集儲(chǔ)存在 int數(shù)組 end_statumaxs里字符集儲(chǔ)存在 char數(shù)組 chamaxs里狀態(tài)儲(chǔ)存為0n-1（n個(gè)狀態(tài)情況）狀態(tài)轉(zhuǎn)換函數(shù)儲(chǔ)存于結(jié)構(gòu) stuct statu里struct Edge /轉(zhuǎn)化邊 char cost; /消耗 int dest; /指向的終點(diǎn);struct statu Edge node50; / 終點(diǎn) int cnt;/邊的數(shù)

3、量 statu() cnt=0; for(int i=0;i<50;i+) nodei.cost='#' nodei.dest=0; sta50;/起點(diǎn)5、 具體實(shí)現(xiàn)使用子集法實(shí)現(xiàn)：函數(shù)接口解釋： void creat_subset(void); 構(gòu)造子集函數(shù) Ins(int a,int ss) 用深搜（dfs）求狀態(tài)ss的閉包，并將閉包里的所有元素加入到子集closurea里。void ins_subset(int a,int ss,char target) 求狀態(tài)ss通過字符target所能到達(dá)的所有狀態(tài)，并將這些狀態(tài)加入到子集closurea里。int check(

4、int tt) 檢查子集closurett是否與之前的子集重合，為空則返回-2，不重合返回-1，重合則返回重合的子集下標(biāo)。void print(void) 輸出DFA的五元組信息。 1.將起始狀態(tài)求閉包，得到S0。 將初狀態(tài)里所有的元素及其能通過e空路所到的狀態(tài)加入closure0作為初始子集 for(int i=0;i<ct_sta_statu;i+) / 求起始狀態(tài)求閉包，得到S0 closure0.members.insert(sta_statui); ins(0,sta_statui); / e_closure(s0)2.從0開始直到totss對(duì)每個(gè)子集求各個(gè)字符所能到達(dá)的新子集

5、將其加入tot+1子集中。for(tempss=0;tempss<=totss;tempss+)/tempss 表示當(dāng)前運(yùn)算的狀態(tài)下表 totss表示總共的狀態(tài)數(shù) 新生產(chǎn)的狀態(tài)子集加入到 closurtot+1中 for(int j=0;j<ct_cha;j+) for(it=closuretempss.members.begin();it!=closuretempss.members.end();it+) ins_subset(totss+1,*it,chaj); void ins_subset(int a,int beg,char target)/ 求狀態(tài)ss通過字符targe

6、t所能到達(dá)的所有狀態(tài)，并將這些狀態(tài)加入到子集closurea里。 for(int i=0;i<t;i+) if(stabeg.nodei.cost = target) closurea.members.insert(stabeg.nodei.dest); ins(a,stabeg.nodei.dest);/求出這些狀態(tài)后用dfs求其能經(jīng)過空路所到達(dá)的狀態(tài)也加入closurea return ; void ins(int a,int beg)/求集合的 閉包 for(int i=0;i<t;i+) if(stabeg.nodei.cost='

7、;#') closurea.members.insert(stabeg.nodei.dest); ins(a,stabeg.nodei.dest); 3.檢查tot+1子集是否與之前的子集重合或者為空,如果重合或?yàn)榭談t子集不增加int check(int tt) if(closurett.members.empty() return -2; /為空則返回-2 set<int>:iterator isa,isb; for(int i=0;i<tt;i+) isb=closurett.members.begin(); if(closurett.members.size()

8、=closurei.members.size() for(isa=closurei.members.begin();isa!=closurei.members.end();isa+) if(*isa!=*isb) break; else isb+; if(isb=closurett.members.end() return i; /重合則返回之前相同的子集的下標(biāo) return -1;/不重合返回-14.記錄新的狀態(tài)轉(zhuǎn)換函數(shù) if(ok=-2)/新子集為空 ; else if(ok=-1) /與之前的子集不重合，記錄新狀態(tài)轉(zhuǎn)換函數(shù) totss+; newstatempss.nodenewstat

9、t.cost=chaj; t+.dest=totss; else/與之前的子集重合，記錄新狀態(tài)轉(zhuǎn)換函數(shù) closuretotss+1.members.clear(); t.cost=chaj; t+.dest=ok; 5.輸出DFA信息六、設(shè)計(jì)過程中的問題與對(duì)策NFA轉(zhuǎn)化為DFA的過程中最難解決的是如何儲(chǔ)存狀態(tài)轉(zhuǎn)換函數(shù)以及記錄新的狀態(tài)轉(zhuǎn)換函數(shù)的問題，我開始設(shè)計(jì)為一個(gè)二維數(shù)組，實(shí)際應(yīng)用時(shí)發(fā)現(xiàn)當(dāng)NFA中一個(gè)字符對(duì)應(yīng)兩個(gè)目標(biāo)時(shí)前一個(gè)目標(biāo)會(huì)被覆蓋。于是再仔細(xì)觀察NFA的特點(diǎn)，多個(gè)初態(tài)，多個(gè)終態(tài)，一個(gè)狀態(tài)經(jīng)一個(gè)字符可對(duì)應(yīng)多個(gè)狀態(tài)。設(shè)計(jì)了一種新的儲(chǔ)存結(jié)構(gòu)，因?yàn)槊總€(gè)NFA相當(dāng)于一個(gè)有向圖。用一個(gè)結(jié)構(gòu)體儲(chǔ)存