編譯原理第4章

1、第四章 詞法分析 本章將討論詞法分析程序的設(shè)計(jì)原則，單詞的 描述技術(shù)，識(shí)別機(jī)制及詞法分析程序的自動(dòng) 構(gòu)造原理。 4.1 詞法分析程序設(shè)計(jì) 4.2 單詞描述工具正規(guī)式與正規(guī)文法 4.3 有窮自動(dòng)機(jī) 4.4 正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)轉(zhuǎn)換 4.5 正規(guī)文法和有窮自動(dòng)機(jī)的等價(jià)轉(zhuǎn)換 本章重點(diǎn) 單詞的描述工具 單詞的識(shí)別系統(tǒng) 設(shè)計(jì)和實(shí)現(xiàn)詞法分析程序 首先需要描述和刻畫程序設(shè)計(jì)語言中的原子單 位單詞，其次需要識(shí)別單詞和執(zhí)行某些相 關(guān)的動(dòng)作。 描述程序設(shè)計(jì)語言的詞法的機(jī)制是正則表達(dá)式， 識(shí)別機(jī)制是有窮狀態(tài)自動(dòng)機(jī)。 回顧回顧 什麼是詞法分析程序 實(shí)現(xiàn)詞法分析（lexical analysis）的程 序 逐個(gè)讀入

2、源程序字符并按照構(gòu)詞規(guī)則 切分成一系列單詞。 單詞是語言中具有 獨(dú)立意義的最小單位，包括保留字、標(biāo)識(shí)符、 運(yùn)算符、標(biāo)點(diǎn)符號(hào)和常量等。 詞法分析是編譯過程中的一個(gè)階段， 在語法分析前進(jìn)行 。也可以和語法分析結(jié)合在 一起作為一遍，由語法分析程序調(diào)用詞法分析 程序來獲得當(dāng)前單詞供語法分析使用。 詞法分析程序和語法分析程序的關(guān)系 源程序詞法分析程序語法分析程序 Token get token . 詞法分析程序的主要任務(wù)： 讀源程序，產(chǎn)生單詞符號(hào) 詞法分析程序的其他任務(wù)： 濾掉空格，跳過注釋、換行符 追蹤換行標(biāo)志，復(fù)制出錯(cuò)源程序， 宏展開， 詞法分析程序的輸出 詞法分析程序的輸出可采用二元組表示： （單

3、詞種別，單詞自身值） 程序設(shè)計(jì)語言的單詞符號(hào)一般可分為5個(gè)種別： （1）標(biāo)識(shí)符，如變量名、函數(shù)名、過程名等等 （2）常量，如25、3.1416、TRUE、”abcd”等等 （3）關(guān)鍵字（有的語言稱為保留字），如if、while等 等 （4）運(yùn)算符，如+、*、=等等 （5）界符，如逗號(hào)、分號(hào)、括號(hào)等等。 例：if i=5 then x:=y； 詞法分析程序的輸出可以是： （3，if） （1，i） （4，=） （2，5） （3，then） （1，x） （4，：=） （1，y） （5，；） 詞法分析工作從語法分析 工作獨(dú)立出來的原因： 簡化設(shè)計(jì) 改進(jìn)編譯效率 增加編譯系統(tǒng)的可移植性 單詞描述工具正規(guī)

4、文法 程序設(shè)計(jì)語言中的幾類單詞均可用下述規(guī)則描述： G標(biāo)識(shí)符： l|l l|d|l|d G無符號(hào)整數(shù)： d|d G運(yùn)算符： +|-|*|/|=| = G界符： ,|;|(|) 一般程序設(shè)計(jì)語言中最復(fù)雜的單詞可能會(huì)是 無符號(hào)實(shí)數(shù)，其文法可以描述為： GW: WdY|.B|Ee YdY|.B|eE| BdC CeE|dC| EDf|sG FdF| GdF 單詞描述工具正規(guī)式 正規(guī)式也稱正則表達(dá)式,正規(guī)表 達(dá)式（regular expression）。 是說明單詞模式(pattern)的一 種重要的表示法（記號(hào)）， 是定義正規(guī)集的數(shù)學(xué)工具。 我們用以描述單詞符號(hào)。 下面是正規(guī)式和它所表示的正 規(guī)集的

5、遞歸定義。 定義（正規(guī)式和它所表示的正規(guī)集）： 設(shè)字母表為，輔助字母表=，。 1。 和都是上的正規(guī)式，它們所表示的正規(guī)集分別 為和 ； 2。任何a ，a是上的一個(gè)正規(guī)式，它所表示的正規(guī) 集為a； 3。假定e1和e2都是上的正規(guī)式，它們所表示的正規(guī)集 分別為L(e1)和L(e2)，那么，(e1), e1 e2, e1e2, e1也都是正規(guī)式,它們所表示的正規(guī)集分別為L(e1), L(e1)L(e2), L(e1)L(e2)和(L(e1)。 4。僅由有限次使用上述三步驟而定義的表達(dá)式才是 上的正規(guī)式，僅由這些正規(guī)式所表示的集合才是上 的正規(guī)集。 正規(guī)式中的符號(hào) “”讀為“或”（可以使用“+”代替

6、“” ）； “ ”讀為“連接”； “”讀為“閉包”（即，任意有限次的自重復(fù)連 接）。 在不致混淆時(shí)，括號(hào)可省去，但規(guī)定算符的優(yōu)先順序 為“”、“ ”、“” 。 連接符“ ”一般可省略不寫。 “”、“ ”和“” 都是左結(jié)合的。 例子 令=a，b， 上的正規(guī)式和相應(yīng)的正規(guī)集的例子有： 正規(guī)式 正規(guī)集 a a ab a,b ab ab (ab)(ab) aa,ab,ba,bb a ,a,a, 任意個(gè)a的串 (ab) ,a,b,aa,ab 所有由a和b組 成的串 (ab)(aabb)(ab) 上所有含有兩個(gè)相繼的a或 兩個(gè)相繼的b組成的串 討論下面兩個(gè)例子 例4.1 令=l，d，則上的正規(guī)式 r=l(

7、l d) 定義的正規(guī)集為: l,ll,ld,ldd,其中l(wèi)代表字母,d代表數(shù)字,正規(guī)式： r=字母(字母|數(shù)字) 它表示的正規(guī)集中的每個(gè)元素的模式是“字母打頭的字母數(shù)字 串”,就是Pascal和 多數(shù)程序設(shè)計(jì)語言允許的的標(biāo)識(shí)符的詞法 規(guī)則. 例4.2 =d，.，e，+，-, 則上的正規(guī)式 d(.dd )(e(+- )dd )表示的 是無符號(hào)數(shù)的集合。其中d為09的數(shù)字。 程序設(shè)計(jì)語言的單詞都能用正規(guī)式程序設(shè)計(jì)語言的單詞都能用正規(guī)式 來定義來定義. . 等價(jià)正規(guī)式 若兩個(gè)正規(guī)式e1和e2所表示的正規(guī)集相同, 則說e1和e2等價(jià),寫作e1=e2。 例如： e1= (ab)， e2 = ba 又如：

8、 e1= b(ab) , e2 =(ba)b 再如： e1= (ab) , e2 =(ab) 正規(guī)式運(yùn)算 設(shè)r,s,t為正規(guī)式，正規(guī)式服從的代數(shù)規(guī)律有： 1。rs=sr “或”服從交換律 2。r(st)=(rs)t “或”的可結(jié)合律 3。(rs)t=r(st) “連接”的可結(jié)合律 4。r(st)=rsrt (st)r=srtr 分配律 5。 r=r, r=r是“連接”的恒等元素（零一律） 6。 rr=r r=rrr “或”的抽取律 正規(guī)文法和正規(guī)式的等價(jià)性 文法產(chǎn)生式文法產(chǎn)生式正規(guī)式正規(guī)式 規(guī)則1AxB ByxB ByA=xy 規(guī)則2AxA|yxA|yA=x*y 規(guī)則3Ax Ayx AyA=x

9、|y 例4.4 將r=a(a|b)*轉(zhuǎn)換成相應(yīng)的正規(guī)文法。 解:（1） SaA, A(a|b)aA, A(a|b)* （2）SaA, A(a|b)A|aA, A(a|b)A| （3）SaA,aA, AaA|bA|AaA|bA| 例4.5 4.5 已知文法GS:GS: SaA, Sa, AaA,SaA, Sa, AaA, AdA, Aa, AdAdA, Aa, Ad 解解: :（1 1）S=aA|a, A=(aA|dA)|(a|d)S=aA|a, A=(aA|dA)|(a|d) （2 2）S=a(a|d)S=a(a|d)* *(a|d)|a(a|d)|a （3 3）S=a(a|d)S=a(a|d

10、)* *(a|d)|(a|d)| （4 4）S=a(a|d)S=a(a|d)* * 有窮自動(dòng)機(jī)(也稱有限自動(dòng)機(jī))作為一種識(shí) 別裝置，它能準(zhǔn)確地識(shí)別正規(guī)集，即識(shí)別正規(guī)文法 所定義的語言和正規(guī)式所表示的集合，引入有窮自 動(dòng)機(jī)這個(gè)理論，正是為詞法分析程序的自動(dòng)構(gòu)造尋 找特殊的方法和工具。 有窮自動(dòng)機(jī)分為兩類： （1）確定的有窮自動(dòng)機(jī) (DFA，Deterministic Finite Automata)， （2）不確定的有窮自動(dòng)機(jī) (NFA，Nondeterministic Finite Automata) 。 單詞描述工具有窮自動(dòng)機(jī) 關(guān)于有窮自動(dòng)機(jī)我們將討論如下題目 確定的有窮自動(dòng)機(jī)DFA 不確定

11、的有窮自動(dòng)機(jī)NFA NFA的確定化 DFA的最小化 確定的有窮自動(dòng)機(jī)DFA的定義： DFA M是一個(gè)五元組：M=（K，f，S，Z），其 中： 1.K是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)； 2.是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸 入符號(hào)，所以也稱為輸入符號(hào)表； 3.f是轉(zhuǎn)換函數(shù)，是在KK上的映射，即，如 f（ki，a）=kj，（kiK，kjK）就意味著，當(dāng)前 狀態(tài)為ki，輸入符為a時(shí)，將轉(zhuǎn)換為下一個(gè)狀態(tài)kj， 我們把kj稱作ki的一個(gè)后繼狀態(tài)； 4.SK是唯一的一個(gè)初態(tài)； 5.Z K是一個(gè)終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束 狀態(tài)。 一個(gè)DFA 的例子： DFA M=（S，U，V，Q，a，b

12、，f，S，Q） 其中f定義為： f（S，a）=Uf（V，a）=U f（S，b）=Vf（V，b）=Q f（U，a）=Qf（Q，a）=Q f（U，b）=Vf（Q，b）=Q 一個(gè)DFA可以表示成一個(gè)狀態(tài)圖(或稱狀態(tài)轉(zhuǎn)換圖)。 假定DFA M含有m個(gè)狀態(tài)，n個(gè)輸入字符， 那么這個(gè)狀態(tài)圖含有m個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)最多有n個(gè) 弧射出； 整個(gè)圖含有唯一一個(gè)初態(tài)結(jié)點(diǎn)和若干個(gè) 終態(tài)結(jié)點(diǎn)，初態(tài)結(jié)點(diǎn)冠以雙箭頭“=”或標(biāo)以“-”， 終態(tài)結(jié)點(diǎn)用雙圈表示或標(biāo)以“+”； 若 f(ki,a)=kj，則從狀態(tài)結(jié)點(diǎn)ki到狀態(tài)結(jié)點(diǎn)kj畫 標(biāo)記為a的?。?b S U V Q a a a b a， b 一個(gè)DFA還可以用一個(gè)矩陣表示。 該

13、矩陣的行表示狀態(tài)，列表示輸入 字符，矩陣元素表示相應(yīng)狀態(tài)行和輸入字符列 下的新狀態(tài)，即k行a列為f(k,a)的值。用雙箭 頭“=”標(biāo)明初態(tài)；否則第一行即是初態(tài)，相 應(yīng)終態(tài)行在表的右端標(biāo)以1，非終態(tài)標(biāo)以0。 ab SUV UQV VUQ QQQ 字符字符 狀態(tài)狀態(tài) 0 0 0 1 DFA M作為一種單詞識(shí)別機(jī)制,須理解以下定義 * *上的符號(hào)串上的符號(hào)串t t在在DFADFA M M上運(yùn)行上運(yùn)行 一個(gè)輸入符號(hào)串t，（可表示為Tt1的形式，其中 T，t1 *）在DFA M=（K，f，S，Z） 上運(yùn)行運(yùn)行的定義為：f（Q， Tt1）=f（f（Q，T）， t1） 其中QK擴(kuò)充轉(zhuǎn)換函數(shù)f為 K*K上的

14、映射，且： f（ki，）= ki * *上的符號(hào)串上的符號(hào)串t t被被DFADFA M M接受接受 若t *，f(S，t)=P，其中S為 M的開始狀態(tài)，P Z，Z為終態(tài)集。 則稱t為DFA M所接受接受（識(shí)別識(shí)別）. 例例：證明證明t t= =baabbaab被下圖的被下圖的DFADFA所接受所接受。 f f（S S，baabbaab）=f=f（f f（S S，b b），），aabaab） = f = f（V V，aabaab）= f= f（f f（V V，a a），），abab） =f =f（U U，abab）=f=f（f f（U U，a a），），b b） =f =f（Q Q，b b）=

15、=Q Q Q Q屬于終態(tài)。屬于終態(tài)。 得證。得證。 b S U V Q a b b a , b a a DFA M所能接受的符號(hào)串的全體記為L(M). 對(duì)于任何兩個(gè)有窮自動(dòng)機(jī)M和M，如果 L(M)=L(M)，則稱M與M是等價(jià)的. 結(jié)論： 上一個(gè)符號(hào)串集V是正規(guī)的，當(dāng)且僅當(dāng)存在 一個(gè)上的確定有窮自動(dòng)機(jī)M，使得 V=L(M)。 DFA的確定性表現(xiàn)在轉(zhuǎn)換函數(shù)f:KK是一 個(gè)單值函數(shù)，也就是說： 對(duì)任何狀態(tài)kK，和輸入符號(hào) a，f(k,a)唯一地確定了下一個(gè)狀態(tài)。 從狀態(tài)轉(zhuǎn)換圖來看，若字母表含有n個(gè)輸 入字符，那末任何一個(gè)狀態(tài)結(jié)點(diǎn)最多有n條 弧射出，而且每條弧以一個(gè)不同的輸入字 符標(biāo)記。 DFA的行為

16、很容易用程序來模擬. DFA M=（K，f，S，Z）的行為的模擬程序 K:=S； c:=getchar; while ceof do K:=f(K,c); c:=getchar; ; if K is in Z then return (yes) else return (no) ; DFA DFA = = digit,not digit 不確定的有窮自動(dòng)機(jī)NFA 定義 NFA M=K，f，S，Z，其中K為狀態(tài)的有窮非 空集， 為有窮輸入字母表，f為K * 到K 的子集（2 K）的一種映射，SK是初始狀態(tài)集， Z K為終止?fàn)顟B(tài)集. 例子 NFA M=（S，P，Z，0，1，f，S，P， Z） 其中

17、 f（S，0）=P f（Z，0）=P f（P，1）=Z f（Z，1）=P f（S，1）=S，Z S P Z 0 0,1 1 1 1 01 SPS,Z0 PZ0 ZPP1 01 SPS,Z0 P.Z0 ZPP1 簡化為 狀態(tài)圖表示狀態(tài)圖表示 矩陣表示矩陣表示 具有轉(zhuǎn)移的不確定的有窮自動(dòng)機(jī)： 12 3 a bc 對(duì)任何一個(gè)具有轉(zhuǎn)移的不確定的有窮自動(dòng)機(jī)NFA N， 一定存在一個(gè)不具有轉(zhuǎn)移的不確定的有窮自動(dòng)機(jī) NFA ，使得L(M)=L(N)。 與上例等價(jià)的一個(gè)NFA為： 2 a c b b 3 1 a c a c b b 類似DFA, 對(duì)NFA M=K，f，S，Z也有如下定義： *上的符號(hào)串t在NF

18、A M上運(yùn)行. 一個(gè)輸入符號(hào)串t，（我們將它表示成Tt1的形式， 其中T，t1 *）在NFA M上運(yùn)行運(yùn)行的定義 為： f（Q， Tt1）=f（f（Q，T），t1） 其中QK. *上的符號(hào)串t被NFA M接受 若t *，f(S0，t)=P，其中S0 S，P Z， 則稱t為NFA M所接受接受（識(shí)別識(shí)別） *上的符號(hào)串t被NFA M接受也可以這樣理解 對(duì)于中的任何一個(gè)串t，若存 在一條從某一初態(tài)結(jié)到某一終態(tài)結(jié)的道路， 且這條道路上所有弧的標(biāo)記字依序連接成 的串(不理采那些標(biāo)記為的弧)等于t，則稱 t可為NFA M所識(shí)別(讀出或接受)。 若M的某些結(jié)既是初態(tài)結(jié)又是終 態(tài)結(jié)，或者存在一條從某個(gè)初態(tài)結(jié)

19、到某個(gè) 終態(tài)結(jié)的道路,其上所有弧的標(biāo)記均為，那 么空字可為M所接受。 合法字符串： 000 111 1010001 110000001 非法字符串： 00 01100 NFA M所能接受的符號(hào)串的全體記為L(M) 結(jié)論： 上一個(gè)符號(hào)串集V是正規(guī)的，當(dāng)且僅當(dāng) 存在一個(gè)上的不確定的有窮自動(dòng)機(jī)M，使得 V=L(M)。 (0|1)*(000|111)(0|1) DFA是NFA的特例，對(duì)每個(gè)NFA N一定存在一個(gè)DFA ，使得 L(M)=L(N)。 也就是說：對(duì)每個(gè)NFA N都存 在著與之等價(jià)的DFA M。 有一種算法，將NFA轉(zhuǎn)換成接 受同樣語言的DFA。這種算法稱為子集法。子集法。 與某一與某一NF

20、ANFA等價(jià)的等價(jià)的DFADFA不唯一不唯一. 從NFA的矩陣表示中可以看出， 表項(xiàng)通常是一狀態(tài)的集合，而在DFA的矩 陣表示中，表項(xiàng)是一個(gè)狀態(tài)，NFA到相應(yīng) 的DFA的構(gòu)造的基本思路是： DFADFA的每一個(gè)狀態(tài)對(duì)應(yīng)的每一個(gè)狀態(tài)對(duì)應(yīng)NFA 的一組狀態(tài). DFA使用它的狀態(tài)去記錄在 NFA讀入一個(gè)輸入符號(hào)后可能達(dá)到的所有 狀態(tài). NFA確定化算法（子集法）: 假設(shè)NFA N=(K,f,K0,Kt)，可按如下辦法構(gòu)造一個(gè) DFA M=(S, ,d,S0,St)，使得L(M)=L(N)： 1.M的狀態(tài)集S由K K的一些子集的一些子集組成。用S1 S2. Sj 表示S的元素，其中S1, S2,. S

21、j是K的狀態(tài)。并約 定，狀態(tài)S1, S2,. Sj是按某種規(guī)則排列的，即對(duì) 于子集S1, S2= S2, S1,來說，S的狀態(tài)就是 S1 ,S2； 2 M和N的輸入字母表是相同的，即是； 3 轉(zhuǎn)換函數(shù)是這樣定義的： d(S1 S2,. Sj,a)= R1R2. Rt 其中： R1,R2,. , Rt = -closure(move(S1, S2,. Sj,a) 4 S0=-closure(K0)為M的開始狀態(tài)； 5 St=Si Sk. Se，其中Si Sk. SeS 且Si , Sk,. SeKt 定義對(duì)狀態(tài)集合I的2個(gè)有關(guān)運(yùn)算： 狀態(tài)集合狀態(tài)集合I I的的-閉包閉包，表示為： -closur

22、e(I) 定義為一狀態(tài)集，是狀態(tài)集I中的任何狀態(tài)S經(jīng)任 意條弧而能到達(dá)的狀態(tài)的集合。狀態(tài)集合I 的任何狀態(tài)S都屬于-closure(I)。 狀態(tài)集合狀態(tài)集合I I的的a a弧轉(zhuǎn)換弧轉(zhuǎn)換，表示為： move(I,a) 定義為狀態(tài)集合J，其中J是所有那些可從I中的 某一狀態(tài)經(jīng)過一條a弧而到達(dá)的狀態(tài)的全體。 狀態(tài)集合I的有關(guān)運(yùn)算的例子 I=1, -closure(I)=1,2； I=5, -closure(I)=5,6,2； move(1,2,a)=5,3,4 -closure(5,3,4)=2,3,4,5,6,7,8； 12 5 3 4 6 8 7 a a a 構(gòu)造NFA N的狀態(tài)狀態(tài)K K的子集

23、的子集的算法： 假定所構(gòu)造的子集族為C，即C= (T1, T2,. TI), 其中T1, T2,. TI為狀態(tài)K的子集。 令-closure(K0)為C中唯一成員，且是未被標(biāo)記的; while （C中存在尚未被標(biāo)記的子集T）do 標(biāo)記T； for (每個(gè)輸入字母a) do U:= -closure(move(T,a)； if (U不在C中) then 將U作為未標(biāo)記的子集加在C中 NFA的確定化 例子 4 f 3 5621i a a a a b b bb IaIb i,1,21,2,31,2,4 1,2,31,2,3,5,6,f1,2,4 1,2,41,2,31,2,4,5,6,f 1,2,3

24、,5,6,f1,2,3,5,6,f1,2,4,6,f 1,2,4,5,6,f1,2,3,6,f1,2,4,5,6,f 1,2,4,6,f1,2,3,6,f1,2,4,5,6,f 1,2,3,6,f1,2,3,5,6,f1,2,4,6,f SAB ACB BAD CCE DFD EFD FCE 4 f 3 5621i a a a a b b bb 等價(jià)的DFA a C DB AE F S b a a a a a b b b b b a b F 確定有窮自動(dòng)機(jī)的化簡 說一個(gè)有窮自動(dòng)機(jī)是化簡了的，即是 說，它沒有多余狀態(tài)并且它的狀態(tài)中沒有兩個(gè)是 互相等價(jià)的。一個(gè)有窮自動(dòng)機(jī)可以通過消除多余 狀態(tài)和合并

25、等價(jià)狀態(tài)而轉(zhuǎn)換成一個(gè)最小的與之等 價(jià)的有窮自動(dòng)機(jī)。 所謂有窮自動(dòng)機(jī)的多余狀態(tài)，是指這 樣的狀態(tài)：從自動(dòng)機(jī)的開始狀態(tài)出發(fā)，任何輸入 串也不能到達(dá)的那個(gè)狀態(tài)；或者從這個(gè)狀態(tài)沒有 通路到達(dá)終態(tài)。 DFA的最小化就是尋求最少狀態(tài)DFA 最少狀態(tài)DFA的含義: 沒有多余狀態(tài)(死狀態(tài)) 沒有兩個(gè)狀態(tài)是互相等價(jià)（不可區(qū)別） 兩個(gè)狀態(tài)s和t可區(qū)別：不滿足 兼容性同是終態(tài)或同是非終態(tài) 傳播性從s出發(fā)讀入某個(gè)aa和從 t出發(fā)讀入某個(gè)a到達(dá)的狀態(tài)等價(jià)。 C和D同是終態(tài),讀入a到達(dá)C和F, C和F同是終態(tài), C和 F讀入a都到達(dá)C,讀入b都到達(dá)E。 故而：C、D、E和F等價(jià)。 a C DB AE F S b a a

26、a a a b b b b b a b F 最小狀態(tài)DFA 對(duì)于一個(gè)DFA M =（K,f, k0,kt)，存在一 個(gè)最小狀態(tài)DFA M =（K,f, k0,kt)，,使L(M)=L(M). 結(jié)論 接受L的最小狀態(tài)有窮自動(dòng)機(jī)不計(jì)同構(gòu)是唯一的。 “分割法” DFA的最小化算法的核心 把一個(gè)DFA的狀態(tài)分成一些不相交的子集，使得任 何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子 集中的任何兩個(gè)狀態(tài)都是等價(jià)的. 算法假定每個(gè)狀態(tài)射出的弧都是完全的,否則,引 入一個(gè)新狀態(tài),叫死狀態(tài),該狀態(tài)是非狀態(tài)，將不 完全的輸入弧都射向該狀態(tài)，對(duì)所有輸入，該狀 態(tài)射出的弧還回到自己. DFA的最小化算法 DFA M =

27、（K,f, k0, kt),最小狀態(tài)DFA M 1.構(gòu)造狀態(tài)的一初始劃分：終態(tài)kt和非終態(tài)K- kt兩組(group)； 2.對(duì)施用過程過程PPPP 構(gòu)造新劃分new； 3. 如new =,則令 final= 并繼續(xù)步驟4， 否則:=new重復(fù)2。 4.為final中的每一組選一代表，這些代表構(gòu)成 M的狀態(tài)。若k是一代表且f(k,a)=t,令r是t 組的代表，則M中有一轉(zhuǎn)換f(k,a)=r，M 的開始狀態(tài)是含有S0的那組的代表M的終態(tài) 是含有F的那組的代表； 5.去掉M中的死狀態(tài)。 過程PPPP : Construction of new For each group G of do begi

28、n 1.Partiton G into subgroups such that two states s and t of G are in the same subgroups if and only if for all input symbols a, states s and t have transitions on a to states in the same group of ;/*at worst, a state will be in a subgroup by itself*/ 2.replace G in n e w by the set of all subgroup

29、s formed end DFA的最小化例子 0:S,A,B C,D,E,F 1:S,A,B C,D,E,F 2: C DB AE F Sb a a a a a a b b b b b b a A S,B b B S DB A S a a a b b b ba a #include #include char wr20; int i,error;char wr20; int i,error; int s(); int a(); int int s(); int a(); int b(); int d();b(); int d(); int s()int s() if (wri=a)if (wr

30、i=a) i+; i+;a();a(); else if (wri=b)else if (wri=b) i+; i+;b();b(); elseelse error+;error+;return 0;return 0; int a()int a()if (wri=a)if (wri=a) i+; i+;d();d(); else if (wri=b)else if (wri=b) i+; i+;b();b(); elseelse error+;error+; return 0;return 0; int b()int b()if (wri=a)if (wri=a) i+; i+;a();a()

31、; else if (wri=b)else if (wri=b) i+; i+;d();d(); elseelse error+;error+; return 0;return 0; int d()int d()if (wri=a)if (wri=a) i+; i+;d();d(); else if (wri=b)else if (wri=b) i+; i+;d();d(); elseelseif (wri=#) if (wri=#) return 1;return 1; else else error+;error+; return 0;return 0; int main()int mai

32、n() printf(Input a word:);printf(Input a word:);scanf(%s,ch);scanf(%s,ch); i=0;error=0;i=0;error=0; s();s();if (error)if (error) printf(error);printf(error); return 0;return 0; printf(right/n);printf(right/n);return 1;return 1; 例題4-8：已知NFA如圖所示，求其等價(jià)的最小DFA。 令令 -closure(K0)為為C中唯一成員，未標(biāo)中唯一成員，未標(biāo) 記記; while

33、 （C中存在未標(biāo)記的子集中存在未標(biāo)記的子集T）do 標(biāo)記標(biāo)記T； for (每個(gè)輸入字母每個(gè)輸入字母a) do U:= - closure(move(T,a)； if (U不在不在C中中) then 將將U作為未標(biāo)記的子集加在作為未標(biāo)記的子集加在C中中 p ppapapbpb 0,1,2,4,70,1,2,4,71,2,3,4,6,7,1,2,3,4,6,7, 88 1,2,4,5,6,71,2,4,5,6,7 1,2,3,4,6,7,1,2,3,4,6,7, 88 1,2,3,4,6,7,1,2,3,4,6,7, 88 1,2,4,5,6,7,1,2,4,5,6,7, 99 1,2,4,5,

34、6,71,2,4,5,6,71,2,3,4,6,7,1,2,3,4,6,7, 88 1,2,4,5,6,71,2,4,5,6,7 1,2,4,5,6,7,1,2,4,5,6,7, 99 1,2,3,4,6,7,1,2,3,4,6,7, 88 1,2,4,5,6,7,1,2,4,5,6,7, 1010 1,2,4,5,6,7,1,2,4,5,6,7, 1010 1,2,3,4,6,7,1,2,3,4,6,7, 88 1,2,4,5,6,71,2,4,5,6,7 確定化：確定化： 最小化：最小化： 正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)轉(zhuǎn)換 對(duì)有窮自動(dòng)機(jī)和正規(guī)表達(dá)式進(jìn)行了上述討論之后,我們介紹 有窮自動(dòng)機(jī)和正規(guī)

35、表達(dá)式的等價(jià)性有窮自動(dòng)機(jī)和正規(guī)表達(dá)式的等價(jià)性, ,即即： 1.對(duì)于上的一個(gè)NFA M，可以構(gòu)造一個(gè)上的正 規(guī)式R,使得L(R)=L(M)。 2.對(duì)于上的一個(gè)正規(guī)式R，可以構(gòu)造一個(gè)上的 NFA M，使的L(M)=L(R)。 從上的一個(gè)正規(guī)式R構(gòu)造上的一個(gè)NFA M， 使得L(M)=L(R)的方法。 “語法制導(dǎo)”的方法，即按正規(guī)式的語法結(jié) 構(gòu)指引構(gòu)造過程，構(gòu)造規(guī)則具體描述如下： .“對(duì)于上的一個(gè)正規(guī)式R,可以構(gòu)造一個(gè)上的NFA M， ，使得L(M)=L(R).” 說明一種構(gòu)造方法： (1)R=,構(gòu)造任一具有空終態(tài)集的NFA M。 (2） R= ，構(gòu)造的NFA M=(k0, ,f,k0.k0):f（

36、k0,a) 對(duì)于 所有a都沒定義。 (3）R=a,構(gòu)造的NFA M=(k0,k1,f,k0.k1): f(k0,a) = k1 。 (4) R =R1 | R2, 將步驟（1）（2）（3）分別應(yīng)用到 R1,R2，產(chǎn)生M1= =(K1,f1,k1,F1), M2=(K2,f2,k2,F2),其中K1,K2不相交.構(gòu)造的NFA M= (K1K2k,f,k,F):k是新增加的狀態(tài)符號(hào)，f包含 f1和f2,且f(k,a)=f1(k1,a)f2(k2,a)。若k1F1且 k2F2則 F=F1 F2，否則F=F1 F2 k (5)R=R1.R2 將步驟（1）（2）（3）分別應(yīng)用到R1,R2 產(chǎn)生 M1=(

37、K1,f1,k1,F1), M2=(K2,f2,k2,F2),其中K1,K2不 相交.構(gòu)造的NFA M= (K1K2,f,k1,F2) :f包含f1和f2,且 f(k,a)=f1(k,a),當(dāng) kF1時(shí); f(k,a)=f2(k,a),當(dāng) k K2時(shí); f(k1, )=k2, (6)R=R1* 將步驟（1）（2）（3）分別應(yīng)用到R1,產(chǎn)生 M1=(K1,f1,k1,F1), 構(gòu)造的NFA M= (K1 k0,F F0 ,f,k0,F0)其中 k0,F F0 是新 增加的兩個(gè)狀態(tài), f(k,a)=f1(k,a),當(dāng) kF1時(shí); f(k0, )=f(F1 , )= k1,F F0 , 有窮自動(dòng)機(jī)

38、正則式 對(duì)于正規(guī)式r, r= R1|R2構(gòu)造的NFA 對(duì)于正規(guī)式r, r=R1 R2構(gòu)造的NFA 對(duì)于正規(guī)式r, r=R1*構(gòu)造的NFA 例4-10 已知NFA N如下圖，求正規(guī)式R，使得L(R)=L(N) 解得解得:R=(a|b)*(aa(a|b)*)|(bb(a|b)*) =(a|b)*(aa|bb)(a|b)* 例4-11-a 已知R=(a|ab)* b b*，構(gòu)造NFA N，使得L(N)=L(R) 例4-11 已知R=(a|b)* abb，構(gòu)造NFA N，使得L(N)=L(R) 正規(guī)式用于說明(描述)單詞的結(jié)構(gòu)十分簡潔方 便。而把一個(gè)正規(guī)式編譯(或稱轉(zhuǎn)換)為一個(gè)NFA進(jìn)而 轉(zhuǎn)換為相應(yīng)的

39、DFA，這個(gè)NFA或DFA正是識(shí)別該正規(guī)式 所表示的語言的句子的識(shí)別器?；谶@種方法來構(gòu)造 詞法分析程序。 詞法分析程序的設(shè)計(jì)技術(shù)可應(yīng)用于其它 領(lǐng)域，比如查詢語言以及信息檢索系統(tǒng)等，這種應(yīng)用 領(lǐng)域的程序設(shè)計(jì)特點(diǎn)是，通過字符串模式的匹配來引 發(fā)動(dòng)作，回想LEX，說明詞法分析程序的語言，可以 看成是一個(gè)模式動(dòng)作語言。 詞法分析程序的自動(dòng)構(gòu)造工具也廣泛應(yīng) 用于許多方面，如用以生成一個(gè)程序，可識(shí)別印刷電 路板中的缺陷，又如開關(guān)線路設(shè)計(jì)和文本編輯的自動(dòng) 生成等。 正規(guī)文法G和有窮自動(dòng)機(jī)M的等價(jià)轉(zhuǎn)換 （1）M的字母表與G的終結(jié)符集相同； （2）為G中的每個(gè)非終結(jié)符生成M的一個(gè)狀 態(tài)，G的識(shí)別符就是M的開始狀態(tài)； （3）增加一個(gè)新狀態(tài)Z，作為FA的終態(tài)； （4）對(duì)G中的形如AtBtB的產(chǎn)生式，構(gòu)造的產(chǎn)生式，構(gòu)造M M 的一個(gè)轉(zhuǎn)換函數(shù)的一個(gè)轉(zhuǎn)換函數(shù)f(A,t)=B;f(A,t)=B; （5 5）對(duì)G中的形如Att的產(chǎn)生式，構(gòu)造的產(chǎn)生式，構(gòu)造M M的的 一個(gè)轉(zhuǎn)換函數(shù)一個(gè)轉(zhuǎn)換函數(shù)f(A,t)=Zf(A,t)=Z。 例4.12 已知GS： SaA; SbB; S;AaB; AbA;AaB; AbA; BaS; BbA; BBaS; BbA; B。其等價(jià)的NFA M： 習(xí)題 4.7 練習(xí) 1 （1） 2 3 4 (a) 5 8 本章小結(jié) 詞法分析