NFA轉(zhuǎn)化為DFA的轉(zhuǎn)換算法及實(shí)現(xiàn)

1、編譯原理課程實(shí)踐報(bào)告編譯原理課程實(shí)踐報(bào)告 設(shè)計(jì)名稱：NFANFA 轉(zhuǎn)化為轉(zhuǎn)化為 DFADFA 的轉(zhuǎn)換算法及實(shí)現(xiàn)的轉(zhuǎn)換算法及實(shí)現(xiàn) 二級學(xué)院： 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院 專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) 班 級： 計(jì)科本 091 班 姓 名： 學(xué) 號： 指導(dǎo)老師： 日 期： 2012 年 6 月 28 日 摘要 有窮自動(dòng)機(jī)分為確定的有窮自動(dòng)機(jī)（DFA）和不確定的有窮自動(dòng)機(jī)（NFA） 兩類。兩者各有特點(diǎn)、作用于不同的地方，因此需要進(jìn)行轉(zhuǎn)化。NFA轉(zhuǎn)化為DFA 的理論在詞法構(gòu)造乃至整個(gè)編譯器構(gòu)造過程中起著至關(guān)重要的作用，同時(shí)它們 被廣泛應(yīng)用于計(jì)算機(jī)科學(xué)的各個(gè)領(lǐng)域，它們與計(jì)算機(jī)其它學(xué)科之間也有著很密 切的關(guān)系。

2、本文主要介紹基于編譯器構(gòu)造技術(shù)中的由NFA轉(zhuǎn)化為DFA的算法設(shè)計(jì)和實(shí)現(xiàn) 技術(shù)：主要包括NFA轉(zhuǎn)化為與其等價(jià)的DFA所使用的子集構(gòu)造算法以及把DFA化簡 的算法，實(shí)現(xiàn)詞法分析，最后使用Visual C+語言加以實(shí)現(xiàn)。 NFA轉(zhuǎn)化為與其等價(jià)的DFA需分兩步進(jìn)行：1、構(gòu)造NFA的狀態(tài)的子集的算 法；2、計(jì)算-closure。完成這些子模塊的設(shè)計(jì)后，再通過某一中間模塊的總 控程序?qū)ζ湔{(diào)用，最后再由主程序總調(diào)用，也就實(shí)現(xiàn)了NFA轉(zhuǎn)化為其等價(jià)的 DFA，接下來就是以分割法的思想為指導(dǎo)實(shí)現(xiàn)DFA的化簡，最后并以實(shí)例加以說 明。 關(guān)鍵詞關(guān)鍵詞：有窮自動(dòng)機(jī)；NFA ；DFA； 轉(zhuǎn)化 ； 化簡 目錄目錄 1 1

3、前言前言 .3 1.1 選題的依據(jù)和必要性選題的依據(jù)和必要性.3 1.2 課題意義課題意義.3 2 NFANFA 轉(zhuǎn)化為轉(zhuǎn)化為 DFADFA 的算法及實(shí)現(xiàn)的算法及實(shí)現(xiàn) .4 2.1 基本定義基本定義.4 2.1.2 DFA的概念的概念.5 2.1.3 NFA與與DFA的矩陣表示的矩陣表示.5 2.1.4 NFA向向DFA的轉(zhuǎn)換的思路的轉(zhuǎn)換的思路.6 3 DFA 的化簡的化簡.7 3.1 化簡的理論基礎(chǔ).7 3.23.2 化簡的基本思想化簡的基本思想.7 3.3 化簡的代碼實(shí)現(xiàn)化簡的代碼實(shí)現(xiàn).7 4 4 程序設(shè)計(jì)程序設(shè)計(jì) .14 4.14.1 程序分析程序分析.14 4.1.14.1.1 流程圖

4、流程圖.14 4.1.24.1.2 子集構(gòu)造法子集構(gòu)造法.16 4.24.2 具體的轉(zhuǎn)換過程具體的轉(zhuǎn)換過程.18 1 1 前言前言 1.1 選題的依據(jù)和必要性選題的依據(jù)和必要性 由于很多計(jì)算機(jī)系統(tǒng)都配有多個(gè)高級語言的編譯程序，對有些高級語言甚 至配置了幾個(gè)不同性質(zhì)的編譯程序。從功能上看，一個(gè)編譯程序就是一個(gè)語言 翻譯程序。語言翻譯程序把源語言書寫的程序翻譯成目標(biāo)語言的等價(jià)程序。經(jīng) 過編譯程序的設(shè)計(jì)可以大大提高學(xué)生的編程能力。 編譯程序的工作過程通常是詞法分析、語法分析、語義分析、代碼生成、 代碼優(yōu)化1。由于現(xiàn)在有很多詞法分析程序工具都是基于有窮自動(dòng)機(jī)的，而詞 法分析又是語法分析的基礎(chǔ)2，所以我

5、們有必要進(jìn)行有窮自動(dòng)機(jī)的確定化和最 小化。 1.2 課題意義課題意義 編譯程序的這些過程的執(zhí)行先后構(gòu)成了編譯程序的邏輯結(jié)構(gòu)3。有窮自動(dòng)機(jī) （也稱有限自動(dòng)機(jī)）作為一種識別裝置，它能準(zhǔn)確地識別正規(guī)集，即識別正規(guī) 文法所定義的語言和正規(guī)式所表示的集合，引入有窮自動(dòng)機(jī)這個(gè)理論，正是為 詞法分析程序的自動(dòng)構(gòu)造尋找特殊的方法和工具4。NFA轉(zhuǎn)化為DFA的理論在詞 法構(gòu)造至整個(gè)編譯器構(gòu)造過程中起著至關(guān)重要的作用，同時(shí)它們被廣泛應(yīng)用于 計(jì)算機(jī)科學(xué)的各個(gè)領(lǐng)域，它們與計(jì)算機(jī)其它學(xué)科也有著密切的聯(lián)系。 2 NFANFA轉(zhuǎn)化為轉(zhuǎn)化為DFADFA的算法及實(shí)現(xiàn)的算法及實(shí)現(xiàn) 編譯原理是計(jì)算機(jī)專業(yè)的一門重要專業(yè)課，旨在介紹編

6、譯程序構(gòu)造的一般 原理和基本方法。內(nèi)容包括語言和文法、詞法分析、語法分析、語法制導(dǎo)翻譯、 中間代碼生成、存儲管理、代碼優(yōu)化和目標(biāo)代碼生成。進(jìn)行NFA轉(zhuǎn)換為DFA的詞 法分析和語法分析，首先要對目標(biāo)對象有有所了解，這就需要對NFA、DFA進(jìn)一 步了解。 2.1 基本定義基本定義 NFA，也稱不確定的有窮自動(dòng)機(jī)，是由一個(gè)五元式定義的數(shù)學(xué)模型，特點(diǎn)是 它的不確定性，即在當(dāng)前狀態(tài)下，讀入同一個(gè)字符，可能有多個(gè)下一狀態(tài)。 DFA，也稱確定的有窮自動(dòng)機(jī)，也是由一個(gè)五元式定義的數(shù)學(xué)模型，相對的 特點(diǎn)是它的確定性，即在當(dāng)前狀態(tài)下，讀入同一個(gè)字符，最多有一個(gè)后繼狀態(tài)。 2.1.1NFA 的概念的概念 NFA(n

7、ondeterministic finite-state automata)即非確定有限自動(dòng)機(jī), 一個(gè)非確定的有限自動(dòng)機(jī) NFA M是一個(gè)五元式: NFA M=(S, , , S0, F) 其中 S有限狀態(tài)集 輸入符號加上 ,即自動(dòng)機(jī)的每個(gè)結(jié)點(diǎn)所射出的弧可以 是 中一個(gè)字符或是 . S0初態(tài)集 F終態(tài)集 轉(zhuǎn)換函數(shù) S 2S (2S -S 的冪集S 的子集構(gòu)成的集合） 狀態(tài)轉(zhuǎn)換圖如圖2.1.1： 1 1 0 1 0，1 圖圖2.1.1 NFA狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖 2.1.2 DFA的概念的概念 DFA(deterministic finite-state automata)即確定有限自動(dòng)機(jī)，一個(gè)

8、確 定的有限自動(dòng)機(jī) DFA M 是一個(gè)五元式: M=(S, ，, S0, Z) 其中: S 有限狀態(tài)集 輸入字母表 映射函數(shù)(也稱狀態(tài)轉(zhuǎn)換函數(shù)) SS (s,a)=S , S, S S, a S0 初始狀態(tài) S0 S Z終止?fàn)顟B(tài)集 ZS Z S P P Z P P aa ba b b a， b 圖圖2.1.2 DFA狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖 2.1.3 NFA與與DFA的矩陣表示的矩陣表示 一個(gè)NFA或者DFA還可以用一個(gè)矩陣5表示，矩陣也可以說是狀態(tài)轉(zhuǎn)換表， 它的優(yōu)點(diǎn)是可以快速訪問給定的狀態(tài)在給定的輸入字符時(shí)能轉(zhuǎn)換到的狀態(tài)集。 矩陣，每個(gè)狀態(tài)一行，每個(gè)輸入符號和（如果有需要的）各占一列，表的第i

9、 行中與輸入符號a對應(yīng)的表項(xiàng)是一個(gè)狀態(tài)集合，表示NFA或者DFA在狀態(tài)i輸入a 時(shí)所能到達(dá)的狀態(tài)集合（DFA的集合唯一） ，即（i，a）6。 （7） 如圖2.1.1可用表2.3.1.表示： 表表2.3.12.3.1 NFANFA狀態(tài)轉(zhuǎn)換表狀態(tài)轉(zhuǎn)換表 輸入 狀態(tài) 01 SPS，Z P Z ZPP 如圖2.1.2可用表2.3.2表示： 表表2.3.22.3.2 DFADFA狀態(tài)轉(zhuǎn)換表狀態(tài)轉(zhuǎn)換表 輸入 狀態(tài) ab 012 13 2 213 333 2.1.4 NFA向向DFA的轉(zhuǎn)換的思路的轉(zhuǎn)換的思路 從NFA的矩陣表示中可以看出，表項(xiàng)通常是一狀態(tài)的集合，而在DFA的矩 陣表示中，表項(xiàng)是一個(gè)狀態(tài)，NF

10、A到相應(yīng)的DFA的構(gòu)造的基本思路是：DFA的 每一個(gè)狀態(tài)對應(yīng)NFA的一組狀態(tài)DFA使用它的狀態(tài)記錄在NFA讀入一個(gè)輸入符 號后可能達(dá)到的所有狀態(tài)4。 2.2 NFA 和和 DFA 之間的聯(lián)系之間的聯(lián)系 在非確定的有限自動(dòng)機(jī) NFA 中,由于某些狀態(tài)的轉(zhuǎn)移需從若干個(gè)可能的后續(xù) 狀態(tài)中進(jìn)行選擇，故一個(gè) NFA 對符號串的識別就必然是一個(gè)試探的過程。這種 不確定性給識別過程帶來的反復(fù)，無疑會(huì)影響到 FA 的工作效率。而 DFA 則是確 定的,將 NFA 轉(zhuǎn)化為 DFA 將大大提高工作效率,因此將 NFA 轉(zhuǎn)化為 DFA 是有其一 定必要的。 3 DFA的化簡的化簡 得到新的DFA之后，并沒有完成任務(wù)

11、，因?yàn)橥ㄟ^NFA轉(zhuǎn)化成DFA不一定是最簡 的，也就是說，有多余的狀態(tài)可以被刪除，而我們需要的是得到一個(gè)唯一的最 簡的DFA12，也就是說，NFA轉(zhuǎn)化為DFA之后，還需要化簡，也就是最小化。 3.13.1 化簡的理論基礎(chǔ)化簡的理論基礎(chǔ) DFA的化簡是指：尋找一個(gè)狀態(tài)數(shù)最少的DFA M，使得L（M）=L（M） 。 化簡的方法是消去DFA M中的多余狀態(tài)（或無用狀態(tài)） ，合并等價(jià)狀態(tài)。 DFA中的多余狀態(tài)是指這樣的狀態(tài)：從開始狀態(tài)出發(fā)，讀入任何輸入串都 不能到達(dá)的那個(gè)狀態(tài)；或者從這個(gè)狀態(tài)沒有通路到達(dá)終態(tài)。 兩個(gè)狀態(tài)S 和T等價(jià)是指：如果從狀態(tài)S出發(fā)能讀出某個(gè)字W而停于終態(tài)， 從T出發(fā)也能讀出同樣的字

12、W而停于終態(tài)；反之，從T出發(fā)能讀出同樣的字W而 停于終態(tài)，從S出發(fā)也能讀出某個(gè)字W而停于終態(tài)。 3.23.2 化簡的基本思想化簡的基本思想 化簡DFA的基本思想是指導(dǎo)它的狀態(tài)分成一些互不相交的子集，每一個(gè)子 集中的狀態(tài)都不是等價(jià)的，不同子集中的狀態(tài)可以由某個(gè)輸入串來區(qū)別，最后 將不能區(qū)別的每個(gè)子集用一個(gè)狀態(tài)來做代表13-15，這種方法稱為“分割法”。具 體過程是： （1）將M的所有狀態(tài)分成兩個(gè)子集終態(tài)集和非終態(tài)集； （2）考察每一個(gè)子集，若發(fā)現(xiàn)某子集中的狀態(tài)不等價(jià)，將其劃分為兩個(gè)集合； （3）重復(fù)第（2）步，繼續(xù)考察已得到的每一個(gè)子集，直到?jīng)]有任何一個(gè)子集 需要繼續(xù)劃分為止。這時(shí)DFA的狀態(tài)被

13、分成若干個(gè)互不相交的子集。 （4）從每個(gè)子集中選出一個(gè)狀態(tài)做代表即可得到最簡的DFA。 3.3 化簡的代碼實(shí)現(xiàn)化簡的代碼實(shí)現(xiàn) #include #include #define MAXS 100 using namespace std; string NODE; /結(jié)點(diǎn)集合 string CHANGE; /終結(jié)符集合 int N; /NFA 邊數(shù) struct edge string first; string change; string last; ; struct chan string ltab; string jiheMAXS; ; void kong(int a) int i; f

14、or(i=0;ia;i+) cout ; /排序 void paixu(string char b; for(j=0;ja.length();j+) for(i=0;iNODE.find(ai+1) b=ai; ai=ai+1; ai+1=b; void eclouse(char c,string for(k=0;khe.length() he+=bk.last; eclouse(bk.last0,he,b); void move(chan k=he.ltab.length(); l=he.jihem.length(); for(i=0;ik;i+) for(j=0;jhe.jihem.len

15、gth() he.jihem+=bj.last0; for(i=0;il;i+) for(j=0;jhe.jihem.length() he.jihem+=bj.last0; /輸出 void outputfa(int len,int h,chan *t) int i,j,m; cout I ; for(i=0;ilen;i+) coutICHANGEi ; coutendl-endl; for(i=0;ih;i+) cout ti.ltab; m=ti.ltab.length(); for(j=0;jlen;j+) kong(8-m); m=ti.jihej.length(); coutti

16、.jihej; coutendl; void main() edge *b=new edgeMAXS; int i,j,k,m,n,h,x,y,len; bool flag; string jhMAXS,endnode,ednode,sta; cout請輸入 NFA 各邊信息（起點(diǎn) 條件空為* 終點(diǎn)） ，以#結(jié)束：endl; for(i=0;ibi.first; if(bi.first=#) break; cinbi.changebi.last; N=i; /*for(j=0;jN;j+) coutbj.firstbj.changebj.lastendl;*/ for(i=0;iNODE.le

17、ngth() NODE+=bi.first; if(NODE.find(bi.last)NODE.length() NODE+=bi.last; if(CHANGE.find(bi.change)CHANGE.length() len=CHANGE.length(); cout結(jié)點(diǎn)中屬于終態(tài)的是：endnode; for(i=0;iNODE.length() cout所輸終態(tài)不在集合中，錯(cuò)誤！endl; return; /coutendnode=endnodeendl; chan *t=new chanMAXS; t0.ltab=b0.first; h=1; eclouse(b0.first0

18、,t0.ltab,b); /求 e-clouse /coutt0.ltabendl; for(i=0;ih;i+) for(j=0;jti.ltab.length();j+) for(m=0;mlen;m+) eclouse(ti.ltabj,ti.jihem,b); /求 e-clouse for(k=0;klen;k+) /coutti.jihek; move(ti,k,b); /求 move(I,a) /coutti.jihekendl; for(j=0;jti.jihek.length();j+) eclouse(ti.jihekj,ti.jihek,b); /求 e-clouse f

19、or(j=0;jlen;j+) paixu(ti.jihej); /對集合排序以便比較 for(k=0;kh;k+) flag=operator=(tk.ltab,ti.jihej); if(flag) break; if(!flag coutendl狀態(tài)轉(zhuǎn)換矩陣如下：endl; outputfa(len,h,t); /輸出狀態(tài)轉(zhuǎn)換矩陣 /狀態(tài)重新命名 string *d=new stringh; NODE.erase(); coutendl重命名：endl; for(i=0;ih;i+) sta=ti.ltab; ti.ltab.erase(); ti.ltab=A+i; NODE+=ti.

20、ltab; coutsta=ti.ltabendl; for(j=0;jendnode.length();j+) if(sta.find(endnodej)sta.length() d1=ednode+=ti.ltab; for(k=0;kh;k+) for(m=0;mlen;m+) if(sta=tk.jihem) tk.jihem=ti.ltab; for(i=0;iednode.length() d0+=NODEi; endnode=ednode; coutendlDFA 如下：endl; outputfa(len,h,t); /輸出 DFA cout其中終態(tài)為：endnodeendl;

21、 /DFA 最小化 m=2; sta.erase(); flag=0; for(i=0;im;i+) /coutdi=diendl; for(k=0;klen;k+) /coutICHANGEkendl; y=m; for(j=0;jdi.length();j+) for(n=0;ny;n+) if(dn.find(tNODE.find(dij).jihek)dn.length()|tNODE.find(dij).jihek.length()=0) if(tNODE.find(dij).jihek.length()=0) x=m; else x=n; if(!sta.length() sta+

22、=x+48; else if(sta0!=x+48) dm+=dij; flag=1; di.erase(j,1); /coutdiendl; j-; break; /跳出 n /n /j if(flag) m+; flag=0; /coutsta=staendl; sta.erase(); /k /i coutendl集合劃分：; for(i=0;im;i+) coutdi ; coutendl; /狀態(tài)重新命名 chan *md=new chanm; NODE.erase(); coutendl重命名：endl; for(i=0;im;i+) mdi.ltab=A+i; NODE+=mdi

23、.ltab; coutdi=mdi.ltabendl; for(i=0;im;i+) for(k=0;klen;k+) for(j=0;jh;j+) if(di0=tj.ltab0) for(n=0;nm;n+) if(!tj.jihek.length() break; else if(dn.find(tj.jihek)dn.length() mdi.jihek=mdn.ltab; break; break; ednode.erase(); for(i=0;im;i+) for(j=0;jendnode.length();j+) if(di.find(endnodej)di.length()

24、endnode=ednode; coutendl最小化 DFA 如下：endl; outputfa(len,m,md); cout其中終態(tài)為：endnodeendl; 4 4 程序設(shè)計(jì)程序設(shè)計(jì) 通過本設(shè)計(jì)所要求達(dá)到的目的是：充分理解和掌握NFA，DFA以及NFA確定化 過程的相關(guān)概念和知識，理解和掌握子集法的相關(guān)知識和應(yīng)用，現(xiàn)在需要編程 16-18實(shí)現(xiàn)對輸入NFA轉(zhuǎn)換成DFA輸出的功能。 4.14.1 程序分析程序分析 4.1.14.1.1 流程圖流程圖 程序總框圖如圖4.1所示： 總模塊 NFA 圖結(jié)構(gòu) 狀態(tài)轉(zhuǎn)換表 DFA 圖結(jié)構(gòu) 初始化狀態(tài) 轉(zhuǎn)換矩陣 狀態(tài)轉(zhuǎn)換操 作 圖圖4.1 .1 程序

25、總框圖程序總框圖 開始 輸入 NFA，初始化 NFA 初步轉(zhuǎn)化為 DFA 結(jié)束 重命名化簡 圖圖4.1.2 功能圖功能圖 4.1.24.1.2 子集構(gòu)造法子集構(gòu)造法 已證明：非確定的有限自動(dòng)機(jī)與確定的有限自動(dòng)機(jī)從功能上來說是等價(jià)的， 也就是說，我們能夠從： NFA M DFA M 使得 L(M)=L(M) 為了使得 NFA 確定化，我們首先給出兩個(gè)定義： 定義 1:集合 I 的 -閉包： 令 I 是一個(gè)狀態(tài)集的子集，定義 -closure（I）為： 1）若 sI，則 s-closure（I） ； 2）若 sI，則從 s 出發(fā)經(jīng)過任意條 弧能夠到達(dá)的任何 狀態(tài)都屬于 -closure（I） 。 狀態(tài)集 -closure（I）稱為 I 的 -閉包 定義 2:令 I 是 NFA M的狀態(tài)集的一個(gè)子集, a 定義: Ia=-closure(J) 其中 J = (s,a) J 是從狀態(tài)子集 I 中的每個(gè)狀態(tài)出發(fā),經(jīng)過標(biāo)記為 a 的弧而達(dá)到的狀態(tài) 集合。 Ia 是狀態(tài)子集,其元素為 J 中的狀態(tài),加上從 J 中每一個(gè)狀態(tài)出發(fā)通過 弧到達(dá)的狀態(tài)。 給定如圖 2 所示的 NFA: b b a a b 0 12 3 4 圖 4.1.3 與之等價(jià)的 DFA 如圖 3： b a b 0，1 2，4 4 3 a 圖 4.1.4 開