【正文】 ,..., Jik； 把 J劃分成 K個(gè)不相交的組并加入到 ?中； else i = i+1。 end if。 end while。 end if。 // 試算 ?中的下一個(gè)狀態(tài)子集 end while。 // 直到 ?的每個(gè)狀態(tài)子集不可劃分為止 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 73 有限自動(dòng)機(jī) （ 2）取 ?的每組中的一個(gè)狀態(tài)作為代表，刪除其它一切等價(jià)的狀態(tài)，所有這些狀態(tài)代表就構(gòu)成了化簡(jiǎn)了的 DFA狀態(tài)集合； （ 3）每個(gè)狀態(tài)組之間的連線變成每個(gè)狀態(tài)代表之間的連線，去掉不可達(dá)狀態(tài)和無(wú)用狀態(tài)； （ 4）含有原來(lái)初態(tài)的等價(jià)狀態(tài)組就是化簡(jiǎn)了的DFA的起始狀態(tài)； （ 5）包含了原來(lái)終結(jié)狀態(tài)的等價(jià)狀態(tài)組就是化簡(jiǎn)了的 DFA的終結(jié)狀態(tài)； 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 74 有限自動(dòng)機(jī) 例 ：圖 DFA的最小化過(guò)程如下 : – 初始劃分 ? = {{0,1,2}, {3,4,5,6}}，計(jì)算 {0,1,2}a＝ {1,3}，它不包含在 ?的任何一個(gè)子集當(dāng)中，所以，可以把 {0,1,2}分解 . – 根據(jù) T(1,a)=3， T(0,a)=T(2,a)=1，把 {0,1,2}分解成兩個(gè)狀態(tài)子集{1}和 {0, 2}。這時(shí)的 ? = {{1}, {0, 2},{3,4,5,6}}。 – 繼續(xù)劃分：由于 {0, 2}b={2,5}未包含在當(dāng)前劃分的任何一個(gè)子集中，所以 {0, 2}一分為二，得到新的劃分 ? = {{0}, {1},{2},{3,4,5,6}}。 – 由于 {3,4,5,6}a={3,4,6}， {3,4,5,6}b={4,5,6}都包含在 {3,4,5,6}內(nèi)，不可再劃分。至此，整個(gè)劃分結(jié)束。 – 令狀態(tài) 3代表 {3,4,5,6}，把原來(lái)進(jìn)入狀態(tài) 5和 6的弧都導(dǎo)入 3，刪除狀態(tài) 5和 6，得到最小化的 DFA如圖 。 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 75 有限自動(dòng)機(jī) 例 a b 3 4 a 0 1 b b b a 2 5 6 b a a b b a a a b 3 b 0 1 b b a 2 b a a 最小化 圖 DFA 最小化的 DFA 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 76 有限自動(dòng)機(jī) 例 ：下圖所示的 DFA的最小化過(guò)程 a b 4 3 b 0 1 b b b a 2 b a a a 3 2 b 1 b b 0 b a a a a （ 1）因?yàn)闋顟B(tài)僅狀態(tài) 4是終結(jié)狀態(tài)，首先得劃分 {4}和 {0,1,2,3}。 （ 2）只需對(duì) {0,1,2,3}繼續(xù)劃分： {0,1,2,3}在面臨字符 a時(shí)，每個(gè)狀態(tài)都轉(zhuǎn)換到狀態(tài) 1，無(wú)法區(qū)分；而在面臨符號(hào) b時(shí)，狀態(tài) 3進(jìn)入狀態(tài) 4，狀態(tài) 0、 1和 2都轉(zhuǎn)換到 {0,1,2,3}內(nèi)得狀態(tài)，所以，可以把 {0,1,2,3}分解成 {3}和 {0,1,2}，從而得到新的劃分包括 {4}、 {3}和 {0,1,2}。 （ 3）可能再分解的是 {0,1,2}：在輸入 b時(shí)， T(0, b)＝ 2， T(1, b)=3, T(2, b)=2，據(jù)此可以把{0,1,2}分解成 {1}和 {0, 2} （ 4）繼續(xù)嘗試分解 {0, 2}：這時(shí)的 {0, 2}a＝ {1}， {0, 2}b＝ {2}，無(wú)法區(qū)分，劃分完畢。 （ 5）最小化的狀態(tài)包括 {0, 2}、 {1}、 {3}和 {4}，重新命名、整理后得到右上圖。 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 77 有限自動(dòng)機(jī) ?從正規(guī)式到有限自動(dòng)機(jī) – 基于轉(zhuǎn)換規(guī)則的算法，利用 ?－轉(zhuǎn)移把單個(gè)的正規(guī)式粘接起來(lái)，形成更復(fù)雜的 、識(shí)別正規(guī)式表示語(yǔ)言的 NFA。 定理 ： (1) 對(duì)字母表 ?上的任何一個(gè)正規(guī)表達(dá)式 e都存在一個(gè)接受 L(e)的有限自動(dòng)機(jī) M，即 L(e)＝L(M)。 (2) 對(duì)字母表 ?上的任何一個(gè)有限自動(dòng)機(jī) M都存在一個(gè)接受 L(M)正規(guī)表達(dá)式 e，即 L(M)＝ L(e) 。 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 78 有限自動(dòng)機(jī) （ 1）對(duì)應(yīng)于基本正規(guī)式 a、 ?、 ?的 NFA a ? ? 對(duì)應(yīng)于基本正規(guī)式 a的 NFA是 對(duì)應(yīng)于基本正規(guī)式 ?的 NFA是 對(duì)應(yīng)于基本正規(guī)式 ?的 NFA是 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 79 有限自動(dòng)機(jī) （ 2）選擇替換規(guī)則： e1|e2表示成 e2 e1 ? ? ? ? 構(gòu)造的有限自動(dòng)機(jī)新增加了兩個(gè)狀態(tài)，分別表示開(kāi)始狀態(tài)和終結(jié)狀態(tài)，然后把新增的起始狀態(tài)與 N(e1)和 N(e2)的起始狀態(tài)用 ?－轉(zhuǎn)移連接起來(lái)，把 N(e1)和 N(e2)的終結(jié)狀態(tài)與新增的終結(jié)狀態(tài)用 ?－轉(zhuǎn)移連接來(lái)，并且更改 N(e1)和N(e2)起始狀態(tài)和終結(jié)狀態(tài)的性質(zhì)。 N(e1)接受的任何串 s，等價(jià)于 ?s?，而它可以被 N(e1|e2)接受，即L(e1)?L(e1|e2)。同樣， L(e2)?L(e1|e2)。 反之，所有從 N(e1|e2)的開(kāi)始狀態(tài)，經(jīng)過(guò) N(e1)部分到達(dá)終結(jié)狀態(tài)，所接受的語(yǔ)言是 {?} L(e1) {?}＝ L(e1)，或者經(jīng)過(guò) N(e2)部分到達(dá)終結(jié)狀態(tài)，所接受的語(yǔ)言是 {?} L(e2) {?}＝ L(e2)，即 L(e1|e2) ? L(e1)? L(e2)。 所以 L(e1|e2)＝ L(e1)? L(e2)。 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 80 有限自動(dòng)機(jī) （ 3）連接替換規(guī)則： e1e2表示成 e2 e1 ? e1和 e2連接成 e1e2時(shí)，把 N(e1)的終結(jié)狀態(tài)改為非終結(jié)狀態(tài)，然后通過(guò)?－轉(zhuǎn)移與 N(e2)的起始狀態(tài)連接起來(lái)， N(e1)的起始狀態(tài)成為 N(e1e2)的起始狀態(tài)， N(e2)的終結(jié)狀態(tài)成為 N(e1e2)的終結(jié)狀態(tài)。 如果 N(e1)接受 s1， N(e2)接受 s2，那么，構(gòu)成 s1的路徑必須經(jīng)過(guò)標(biāo)記為 ?的唯一的一條邊后，才能與構(gòu)成 s2的路徑連接起來(lái)到達(dá)結(jié)束狀態(tài)。這樣，合成的有限自動(dòng)機(jī)接受的是 e1?e2，即 e1e2。 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 81 有限自動(dòng)機(jī) （ 4）重復(fù)替換規(guī)則： e*表示成 e ? ? ? ? 對(duì)于 e的閉包運(yùn)算 e*，新增加了分別表示開(kāi)始和結(jié)束的兩個(gè)狀態(tài)，并且更改 N(e)起始狀態(tài)和終結(jié)狀態(tài)的性質(zhì)；然后新增四條 ?－轉(zhuǎn)移 ①連接新增的的起始狀態(tài)與 N(e)的起始狀態(tài)； ②連接新增的起始狀態(tài)和終結(jié)狀態(tài)； ③連接 N(e)的終結(jié)狀態(tài)與新增的終結(jié)狀態(tài)； ④連接 N(e)的終結(jié)狀態(tài)與 N(e)的起始狀態(tài)。 新增的邊②表示 e的零次連接，等價(jià)于 (L(e))0；新增的邊④和原來(lái) N(e)構(gòu)成了回路，這樣，從 N(e)的開(kāi)始狀態(tài)到結(jié)束狀態(tài)，可以經(jīng)過(guò) N(e)一次或多次。顯然這個(gè) N(e)識(shí)別語(yǔ)言 (L(e))*。 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 82 有限自動(dòng)機(jī) ?從正規(guī)式到有限自動(dòng)機(jī)的例子 例 ：對(duì)正規(guī)式 (+|?|?)dd*構(gòu)造對(duì)應(yīng)的 NFA。 把 (+|?|?)dd*表示成 e1e2，其中 e1= +|?|?， e2= dd*，這樣，簡(jiǎn)化的構(gòu)造有三步，過(guò)程如圖： ? + ? ? ? d d ? ? + ? ? ? d d ? 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 83 有限自動(dòng)機(jī) 例 ：對(duì)正規(guī)式 ab*(ab|ba)a*構(gòu)造等價(jià)的 NFA。 首先將其改造成形式為 e1e2e3的三個(gè)子正規(guī)式的連接，其中 e1= ab*，e2= e4|e5， e3=a*，而 e4=ab， e5=ba。 ? ? ? ? ? ? ? b a b b a ? ? ? b a ab ba b* a* ab* a b b a ab|ba ? ? ? a ? ? ? a ? ? ? ? a b b a ab*(ab|ba)a* ? ? ? ? b a 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 84 有限自動(dòng)機(jī) ?有限自動(dòng)機(jī)在計(jì)算機(jī)中的表示 – 矩陣表示方法、表結(jié)構(gòu)表示和程序表示法 例 ：設(shè)一個(gè) DFA的狀態(tài)集合是 {s0, s1, s2, s3 }，其中 s0是起始狀態(tài)， s3是接受狀態(tài)；輸入符號(hào)集合是 {a,b}，映射 t(s0, a)=s1， t(s0, b)=s2， t(s1, a)=s1， t(s2, b)=s2， t(s1, b)=s3， t(s2, a)=s3，t(s3, a)=s3。 我們可以定義一個(gè)矩陣 M[4, 2]，使得 M[0, 0]=1，M[0, 1]=2， M[1, 0]=1， M[2, 1]=2， M[1, 1]=3，M[2, 0]=3， M[3, 0]=3，其中狀態(tài)就用狀態(tài)的下表代替，字母 a和 b分別用 0和 1表示。 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 85 有限自動(dòng)機(jī) – 表結(jié)構(gòu)表示 例 ： 例 DFA可以表示成如圖 。比如給定一個(gè)狀態(tài) s1和輸入符號(hào) b，首先找到 s1所在的表項(xiàng)，然后在這個(gè)表中找到輸入符號(hào) b，按照 b的指針就可以找到 s3的表項(xiàng)。 s0 2 a . b . s1 2 a . b . s2 2 a . b . s3 1 a . 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 86 詞法分析的自動(dòng)生成器 Lex ? Lex系統(tǒng)示意圖 Lex 編譯系統(tǒng) 詞法 分析器 Lex源程序 詞法分析器 輸入流 單詞記號(hào) Lex源程序是用一種面向問(wèn)題的語(yǔ)言寫(xiě)成的，這個(gè)語(yǔ)言的核心是正規(guī)表達(dá)式，用它描述輸入串的詞法結(jié)構(gòu)。在這個(gè)語(yǔ)言中用戶還可以描述當(dāng)某一個(gè)詞形被識(shí)別出來(lái)時(shí)要完成的動(dòng)作，例如在高級(jí)語(yǔ)言的詞法分析器中，當(dāng)識(shí)別出一個(gè)關(guān)鍵字時(shí)，它應(yīng)該向語(yǔ)法分析器返回該關(guān)鍵字的內(nèi)部編碼。 Lex并不是一個(gè)完整的語(yǔ)言，它只是某種高級(jí)語(yǔ)言（稱(chēng)為 Lex的宿主語(yǔ)言）的擴(kuò)充，因此 Lex沒(méi)有為描述動(dòng)作設(shè)計(jì)新的語(yǔ)言，而是借助其宿主語(yǔ)言來(lái)描述動(dòng)作，常用 C作為 Lex的宿主語(yǔ)言。 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 87 詞法分析的自動(dòng)生成器 Lex ? Lex的語(yǔ)言與實(shí)現(xiàn) Lex源程序的一般格式是： {輔助定義的部分 } %% {識(shí)別規(guī)則部分 } %% {用戶子程序部分 } 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 88 詞法分析的自動(dòng)生成器 Lex – 輔助定義的部分 ? 在 Lex源程序中，用戶為方便起見(jiàn)，需要一些輔助定義，如用一個(gè)名字代表一個(gè)復(fù)雜的正規(guī)式。輔助定義必須在第一個(gè)％％之前給出，并且從第一列開(kāi)始寫(xiě)，輔助定義的語(yǔ)法是： name translation ? 例如用名字 IDENT來(lái)代表標(biāo)識(shí)符的正規(guī)式的輔助定義為 IDENT [azAZ][azAZ09]* 輔助定義在識(shí)別規(guī)則中的使用方式是用運(yùn)算符｛ ｝將 name括起來(lái)， Lex自動(dòng)地用 translation去替換它，例如上述標(biāo)識(shí)符的輔助定義的使用為： {IDENT} 標(biāo)識(shí)符的動(dòng)作 … 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 89 詞法分析的自動(dòng)生成器 Lex – 下面我們用輔助定義的手段來(lái)寫(xiě)一段識(shí)別 FORTRAN語(yǔ)言中整數(shù)和實(shí)數(shù)的 Lex源程序： D [0?9] E [DE][?+]?{D}+ ％％ {D}+ printf(“integer”)； {D}+”.”{D}*({E})? | {D}*”.”{D}+({E})? | {D}+{E} printf(“real”)。 – 請(qǐng)注意在輔助定義部分中可以使用前面的輔助定義。例如：定義 E時(shí)使用了 D，但所用的輔助定義必須是事先已定義過(guò)的，不能出現(xiàn)循環(huán)定義。 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 90 詞法分析的自動(dòng)生成器 Lex – 識(shí)別規(guī)則部分 – 識(shí)別規(guī)則都分是 Lex源程序的核心，它是一張表：左邊一列是正規(guī)式，右邊是相應(yīng)的動(dòng)作，形式如下： R1 {A1} R2 {A2} ... Rn {An} – 其中的 Ri是正規(guī)式，稱(chēng)為詞形。 Ai是相應(yīng)的動(dòng)作，當(dāng)Lex識(shí)別出一個(gè)詞形時(shí)，要完成相應(yīng)的動(dòng)作。 青島大學(xué)信息工程學(xué)院 編譯原理與技術(shù) 91 詞法分析的自動(dòng)生成器 Lex – Lex的工作原理 – Lex程序的編譯過(guò)程 (1) 對(duì)每條識(shí)別規(guī)則構(gòu)造相應(yīng)的 NFA Mi。 (2) 然后引進(jìn)一個(gè)新的起始狀態(tài)，把它與每個(gè) Mi連接成為一個(gè) NFA