朱航宇-20112878-編譯原理合設(shè)計(jì)

1、編譯原理合設(shè)計(jì) 指導(dǎo)教師：李宏芒 專業(yè)班級：信安11-1 姓 名：朱航宇 學(xué) 號：20112878一課程設(shè)計(jì)目的編譯原理是計(jì)算機(jī)專業(yè)的一門重要的專業(yè)課程，其中包含大量軟件設(shè)計(jì)思想。大家通過課程設(shè)計(jì)，實(shí)現(xiàn)一些重要的算法，或設(shè)計(jì)一個完整的編譯程序模型，能夠進(jìn)一步加深理解和掌握所學(xué)知識，對提高自己的軟件設(shè)計(jì)水平具有十分重要的意義。二課程設(shè)計(jì)內(nèi)容（12,13題：12題 DFA 狀態(tài)最少化的程序?qū)崿F(xiàn)和13題 把NFA確定化為DFA 的算法實(shí)現(xiàn)，合并為一題，將NFA確定化為DFA，再將DFA化簡即最小化。）我在選擇課程設(shè)計(jì)題目時(shí)，只選擇了12題DFA的最小化。但由于12題工作量較小同時(shí)為了提高我的編程能力

2、我將13題NFA確定化為DFA，將這兩題合并為一題，即NFA確定化到最小化的實(shí)現(xiàn)。NFA的確定化和DFA的最小化主要是為了更好地使用狀態(tài)轉(zhuǎn)換圖構(gòu)造詞法分析程序和詞法分析程序的自動生成。設(shè)計(jì)并實(shí)現(xiàn)將NFA確定化為DFA的子集構(gòu)造算法以及DFA的最小化，從而更好地理解有限自動機(jī)之間的等價(jià)性，掌握詞法分析器自動產(chǎn)生器的構(gòu)造技術(shù)。三設(shè)計(jì)要求構(gòu)造一程序，實(shí)現(xiàn)：將給定的NFA M(其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息從鍵盤輸入)，確定化為DFA M。（要先實(shí)現(xiàn)-CLOSURE函數(shù)和Ia函數(shù)）。輸出DFA M(其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息輸出到屏幕上)。然后將由確定化后的的DFA M的有限狀態(tài)集S劃分成若干互不

3、相交的子集，使得：任何不同的兩個子集中的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個狀態(tài)都是等價(jià)的（要利用Ia函數(shù)，但并不需要構(gòu)造-CLOSURE函數(shù)，因這是DFA）。輸出化簡后的DFA M(其狀態(tài)轉(zhuǎn)換矩陣及初態(tài)、終態(tài)信息輸出到屏幕上)。四設(shè)計(jì)思路4.1 NFA確定化為DFA1非確定有限自動機(jī)NFA 一個非確定有限自動機(jī)（NFA）M是一個五元式M=（S，,S0，F(xiàn)） 其中(1)S是一個有限集，它的每一個元素稱為一個狀態(tài)； (2) 是一個有窮字母表，它的每一個元素稱為一個輸入字符；(3) 是一個從S×*到S的子集映照；(4)S0屬于，是一個非空初態(tài)集；(5)F屬于S，是一個終態(tài)集（可空）。

4、 顯然，一個含有m個狀態(tài)和n個輸入字符的NFA可表示成如下的狀態(tài)轉(zhuǎn)換圖：該圖含有m個狀態(tài)結(jié)點(diǎn)，每個節(jié)點(diǎn)可射出若干條箭弧與別的結(jié)點(diǎn)相連接，每條弧用*中的一個字（不一定要相同而且可以是空字）做標(biāo)記（稱為輸入字），整張圖至少含有一個初態(tài)結(jié)點(diǎn)以及若干個（可以是0個）終態(tài)結(jié)點(diǎn)。對于*中的任何一個字a，若存在一條從某一初態(tài)結(jié)點(diǎn)到某一終態(tài)結(jié)點(diǎn)的通路，且這條通路上所有弧的標(biāo)記字依序連接城的字（忽略那些標(biāo)記為空字的?。┑扔诎?，則稱a可為NFA M所識別。若M的某些結(jié)點(diǎn)既是初態(tài)結(jié)點(diǎn)又是終態(tài)結(jié)點(diǎn)，后者存在一條弧從某個出臺節(jié)點(diǎn)到某個終態(tài)結(jié)點(diǎn)的通路，則空字可為M所接受。 2確定有限自動機(jī)DFA的最小化 一個確定有限自動

5、機(jī)（NFA）M是一個五元式M=（S，,s0，F(xiàn)） 其中(1)S是一個有限集，它的每一個元素稱為一個狀態(tài)； (2) 是一個有窮字母表，它的每一個元素稱為一個輸入字符；(3) 是一個從S×到S的單值部分映射。(s,a)意味著：當(dāng)現(xiàn)行狀態(tài)為s、輸入字符為a時(shí)，將轉(zhuǎn)入下一個狀態(tài)s,s是s的后繼狀態(tài)；(4)s0S，是唯一的初態(tài)；(5)F屬于S，是一個終態(tài)集（可空）。 顯然，一個DFA可用一個狀態(tài)轉(zhuǎn)換矩陣表示，該矩陣的行表示狀態(tài)，列表時(shí)輸入字符，矩陣元素表示(s,a)的值。一個DFA也可以表示成一張狀態(tài)轉(zhuǎn)換圖，假設(shè)DFA M含有m個狀態(tài)和n個輸入字符，那么，該圖含有m個狀態(tài)結(jié)點(diǎn)，每個節(jié)點(diǎn)最多有n

6、條箭弧與別的結(jié)點(diǎn)相連接，每條弧用中的一個字做標(biāo)記，整張圖含有唯一的一個初態(tài)結(jié)點(diǎn)和若干個（可以是0個）終態(tài)結(jié)點(diǎn)。對于中的任何一個字a，若存在一條從某一初態(tài)結(jié)點(diǎn)到某一終態(tài)結(jié)點(diǎn)的通路，且這條通路上所有弧的標(biāo)記字依序連接城的字等于啊，則稱a可為DFA M所識別。若M的某些結(jié)點(diǎn)既是初態(tài)結(jié)點(diǎn)又是終態(tài)結(jié)點(diǎn)，后者存在一條弧從某個出臺節(jié)點(diǎn)到某個終態(tài)結(jié)點(diǎn)的通路，則空字可為M所接受。DFA M所能識別的字的全體記為L(M)。 3NFA與DFA的聯(lián)系 在非確定的有限自動機(jī)NFA中，由于某些狀態(tài)的轉(zhuǎn)移需從若干個可能的后續(xù)狀態(tài)中進(jìn)行選擇，故一個NFA對符號串的識別必然是一個試探的過程。這種不確定性識別過程帶來的反復(fù)，無疑

7、會影響到FA的工作效率。而DFA則是確定的，將NFA轉(zhuǎn)化為DFA大大提高工作效率，因此將NFA轉(zhuǎn)化為DFA是有其一定必要的。程序中采用子集法來實(shí)現(xiàn)NFA確定化為DFA。4.2 DFA的最小化 一個有限自動機(jī)M的化簡是指：尋找一個狀態(tài)數(shù)比M少的DFA M，使得L(M)=L(M).假定s和t是M的兩個不同狀態(tài)，如果分別從狀態(tài)s和t出發(fā)能讀出同樣的某個字w而停于終態(tài)，則稱s和t是等價(jià)的。如果DFA M的兩個狀態(tài)s和t不等價(jià)，則稱這兩個狀態(tài)是可區(qū)別的。一個DFA M的狀態(tài)最少化過程旨在將M的狀態(tài)集分割成一些不相交的子集，使得任何不同的兩個字集中的狀態(tài)是可區(qū)別的，而同一子集中的任何兩個狀態(tài)都是等價(jià)的。最

8、后，在每個自己中選出一個代表，同時(shí)消去其他等價(jià)狀態(tài)。又被刪除的狀態(tài)射出的弧也被刪去，但是有保留下來的狀態(tài)射出的弧是要全部保留的。五設(shè)計(jì)的基本原理 5.1總體方案設(shè)計(jì) 我的程序總共分三大模塊，一是有限自動機(jī)狀態(tài)轉(zhuǎn)換圖的結(jié)構(gòu)和有限自動機(jī)狀態(tài)信息的輸入輸出部分；二是用子集構(gòu)造算法實(shí)現(xiàn)NFA確定化為DFA，這里面又涉及到_Closure(I)和轉(zhuǎn)換函數(shù)Move(I,a)的實(shí)現(xiàn)和新生成的狀態(tài)的重命名問題以及新的狀態(tài)轉(zhuǎn)換關(guān)系的建立；三是DFA的最小化，這里面包括等價(jià)狀態(tài)的劃分，等價(jià)狀態(tài)的劃分又涉及到終態(tài)結(jié)點(diǎn)和非終態(tài)結(jié)點(diǎn)的區(qū)分，劃分之后等價(jià)狀態(tài)的重命名和新的狀態(tài)轉(zhuǎn)換關(guān)系的建立?？傮w模塊設(shè)計(jì)方案如下圖所示：子

9、集構(gòu)造算法實(shí)現(xiàn)NFA定化為DFA有限自動機(jī)的基本狀態(tài)信息DFA最小化狀態(tài)結(jié)點(diǎn)、邊和輸入終結(jié)符的結(jié)構(gòu)程序總體模塊 結(jié) 構(gòu)新生成狀態(tài)的命名和等價(jià)的狀態(tài)轉(zhuǎn)換關(guān)系的建立有限自動機(jī)狀態(tài)信息的輸入輸出等價(jià)狀態(tài)的重命名和新的狀態(tài)轉(zhuǎn)換關(guān)系的建立等價(jià)狀態(tài)的劃分區(qū)分終結(jié)狀態(tài)和非終結(jié)狀態(tài)_closure(I) 和轉(zhuǎn)換函數(shù)move(I,a)的實(shí)現(xiàn)5.2各模塊設(shè)計(jì)1有限自動機(jī)狀態(tài)轉(zhuǎn)換結(jié)構(gòu)的定義和狀態(tài)信息的輸入輸出 有限狀態(tài)機(jī)的狀態(tài)結(jié)點(diǎn)，邊和終結(jié)符（即輸入字符）均定義為字符串，利用C+標(biāo)準(zhǔn)模板庫string中的函數(shù)來實(shí)現(xiàn)定義和后續(xù)操作，以方便實(shí)現(xiàn)和簡化程序。具體如下程序片段：string NODE; /結(jié)點(diǎn)集合strin

10、g CHANGE; /終結(jié)符集合int N; /NFA邊數(shù)struct edge /狀態(tài)圖的邊，包含一條邊的起點(diǎn)，終點(diǎn)和終結(jié)符string first;string change;string last;struct chan /狀態(tài)轉(zhuǎn)換矩陣集合string ltab; /狀態(tài)子集Istring jiheMAXS; /狀態(tài)子集Ix; 有限自動機(jī)狀態(tài)信息是從鍵盤輸入有限自動機(jī)的各邊信息，包括邊的起點(diǎn)初 態(tài)結(jié)點(diǎn)，標(biāo)記字符即輸入字符，終點(diǎn)狀態(tài)結(jié)點(diǎn)；有限自動機(jī)狀態(tài)信息的輸出主要是將有限自動機(jī)的狀態(tài)轉(zhuǎn)換矩陣輸出到屏幕上，另外還包括一些提示信息，對其空格等。具體見源程序。2NFA確定化為DFA，采用子集構(gòu)

11、造算法(1) _Closure(I)的構(gòu)造假定I是NFA M的狀態(tài)子集,狀態(tài)集合I的閉包的算法_Closure(I),(a)若sI，則I_Closure(I)(b)若sI,那么從s出發(fā)經(jīng)任意條弧而能到達(dá)的任何狀態(tài)s_Closure(I) (2) 轉(zhuǎn)換函數(shù)Move(I,a)定義為：a,定義Ia=_Closure(J)，其中J是那些可從I中的某一狀態(tài)結(jié)點(diǎn)出發(fā)經(jīng)過一條a弧而到達(dá)的狀態(tài)結(jié)點(diǎn)的全體。 (3) 假定= a1 , , ak ,構(gòu)造一張表，此表的每一行含有k+1列。置該表的首行首列為_Closure(X)。一般而言，如果某一行的第一列的狀態(tài)子集已經(jīng)確定，記為I，那么置該行的i+1列為Iai(i

12、=1, ,k)。然后檢查該行上的所有狀態(tài)子集，看它們是否已在表的第一列出現(xiàn)，將未曾出現(xiàn)者填入到后面空行的第一列，為方便比較，在構(gòu)造狀態(tài)子集過程中，可對子集中的元素進(jìn)行排序。重復(fù)上述過程，直到出現(xiàn)在第i+1(i=1, ,k)列上的所有狀態(tài)子集都已經(jīng)在第一列上出現(xiàn)。因?yàn)镸的狀態(tài)子集的個數(shù)是有限的，所以上述過程必定在有限步內(nèi)終止。按照構(gòu)造此表的方法思想用程序?qū)崿F(xiàn)有限自動機(jī)M狀態(tài)子集的構(gòu)造，然后對上表中第一列的個各狀態(tài)子集重命名得到一個新的狀態(tài)轉(zhuǎn)換矩陣，該狀態(tài)裝換矩陣對應(yīng)一個與NFA M等價(jià)的DFA M。例如下圖為一個非確定有限自動機(jī)的狀態(tài)轉(zhuǎn)換圖，終態(tài)為YX512346YY 上面的狀態(tài)轉(zhuǎn)換圖按照子集法

13、生成下表的狀態(tài)轉(zhuǎn)換矩陣IIaIbX,5,15,3,15,4,15,3,15,3,1,2,6,Y5,4,15,4,15,3,15,4,1,2,6,Y5,3,1,2,6,Y5,3,1,2,6,Y5,4,1,6,Y5,4,1,6,Y5,3,1,6,Y5,4,1,2,6,Y5,4,1,2,6,Y5,3,1,6,Y5,4,1,2,6,Y5,3,1,6,Y5,3,1,2,6,Y5,4,1,6,Y 對上表中第一列的各狀態(tài)子集重命名X,5,1 = 0；5,3,1 = 1；5,4,1 = 2；5,3,1,2,6,Y = 3；5,4,1,6,Y = 4；5,4,1,2,6,Y = 5；5,3,1,6,Y = 6則

14、重命名之后上表轉(zhuǎn)化為如下表的狀態(tài)轉(zhuǎn)換矩陣，該轉(zhuǎn)換矩陣對Sab012132215334465565634該表的狀態(tài)轉(zhuǎn)換矩陣對映一個與上述NFA M等價(jià)的未化簡的DFA M，其中終態(tài)為3,4,5,6。其狀態(tài)轉(zhuǎn)換圖如下所示 01234563DFA的最小化，采用等價(jià)狀態(tài)劃分的方法 對DFA的化簡任然要用到上述的Ia函數(shù)，對DFA M的狀態(tài)集S進(jìn)行劃分的步驟是：首先把S的終態(tài)和非終態(tài)分開，分成兩個子集，形成基本劃分。假定到某個時(shí)候已含m個子集，記=I(1),I(2),I(m),并且屬于不同自己的狀態(tài)是可去別的。檢查中的每個I(i)看能否進(jìn)一步劃分。對于某個I(i)，令I(lǐng)(i)=q1,q2,qk，若存在一

15、個輸入字符a使得Ia(i)不全包含在現(xiàn)行的某一子集I(i)中，就將I(i)一分為二。假定狀態(tài)s1和s2經(jīng)a弧分別到達(dá)狀態(tài)t1和t2，而t1和t2屬于現(xiàn)行的兩個不同子集，那就將I(i)分成兩半，使得一半含有s1，另一半含有s2。由于t1和t2是可區(qū)別的，因此字aw將狀態(tài)s1和s2區(qū)別開來。一般地，若Ia(i)落入現(xiàn)行中N個不同子集，則應(yīng)將I(i)劃分成N個不相交的組，使得每個組J的Ja都落入現(xiàn)行的同一子集，這樣形成新的劃分。重復(fù)上述過程，直至劃分中所含的子集數(shù)不再增長為止。至此，中的每個子集已不可再分，也即每個字集中的狀態(tài)都是相互等價(jià)的，而不同子集的狀態(tài)則是可以相互區(qū)別的。 對于上述劃分中的子集重命名，然后刪除無用狀態(tài)（即從初態(tài)開始永遠(yuǎn)到達(dá)不了的那些狀態(tài)），則得到最簡的DFA M。上面有NFA M確定化所得的DFA M形成一個含有四個狀態(tài)子集的劃分=0，3,4,