【正文】 4={1,2,4,5,6,7,10} ?那么圖 NFA N構(gòu)造的 DFA M為： ={ [T0], [T1], [T2], [T3], [T4] } 2. ∑={a,b} 52 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 3. D([T0],a)=[T1] D([T3],a)=[T1] D([T0],b)=[T2] D([T3],b)=[T4] D([T1],a)=[T1] D([T4],a)=[T1] D([T1],b)=[T3] D([T4],b)=[T2] D([T2],a)=[T1] D([T2],b)=[T2] =[T0] =[T4] ?為便于書(shū)寫(xiě)，將 [T0]、 [T1]、 [T2]、 [T3]、 [T4]重新命名為 A、 B、 C、 D、 E或用 0、 4分別表示，若采用后 者，該 DFA M的狀態(tài)轉(zhuǎn)換圖如圖 ： 53 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 圖 DFA M 54 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 四 . DFA的化簡(jiǎn) ?最小狀態(tài) DFA： ?沒(méi)有多余狀態(tài) (死狀態(tài) ) ?沒(méi)有兩個(gè)狀態(tài)是互相等價(jià)（ 不可區(qū)別 ） ?一個(gè)有窮自動(dòng)機(jī)可以通過(guò)消除無(wú)用狀態(tài)和合并等價(jià)狀態(tài) 而轉(zhuǎn)換成一個(gè)最小的與之等價(jià)的有窮自動(dòng)機(jī) ?有窮自動(dòng)機(jī)的無(wú)用狀態(tài)：從該自動(dòng)機(jī)的開(kāi)始狀態(tài)出發(fā)， 任何輸入串也 不能到達(dá) 的那個(gè)狀態(tài)或者從這個(gè)狀態(tài) 沒(méi)有 通路到達(dá) 終態(tài) ?例如圖 M中的狀態(tài) s4便是無(wú)用狀態(tài) 55 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 圖 消除多余狀態(tài) 56 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?在有窮自動(dòng)機(jī)中，兩個(gè)狀態(tài) s和 t等價(jià)的條件是： ?一致性條件 ——必須同是為可接受狀態(tài)或不可接受狀態(tài) ?蔓延性條件 ——對(duì)于所有輸入符號(hào)，必須轉(zhuǎn)換到等價(jià)的 狀態(tài)里 ?分割法： 把一個(gè) DFA（不含多余狀態(tài)）的狀態(tài)分成一些 不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū) 別的，而同一子集中的任何兩個(gè)狀態(tài)都是等價(jià)的 57 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?DFA M最小化方法： ?先分成終態(tài)集合和非終態(tài)集合 ?對(duì)每個(gè)集合中的符號(hào)分別用輸出字母去查看它們到達(dá)狀 態(tài)的集合是否在同一個(gè)集合中 ?如果不在同一個(gè)集合，將它們劃分在不同的集合中 ?直到不能再劃分為止 58 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?例 將圖 DFA M最小化 ?P0=({1,2,3,4},{5,6,7}) a ?P1=({1,2},{3,4},{5,6,7}) a ?P2=({1,2},{3},{4},{5,6,7}) a ?P3=({1,2},{3},{4},{5},{6,7}) b 令 1代表 {1,2}消去 2，令 6代表 {6,7}，消去 7，得到圖 (b) 的 DFA M`，它是 (a)的 DFA M的最小化 59 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 圖 DFA M和 DFA M` 60 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 167。從 x結(jié)點(diǎn)用 ?弧連接到 M的所有初始 結(jié)點(diǎn)，從 M的所有終態(tài)結(jié)點(diǎn)用 ?弧連接到 y結(jié)點(diǎn)。在消結(jié)過(guò)程中，逐步用正規(guī)式來(lái)標(biāo)記弧 61 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?其消結(jié)的規(guī)則如下： ?最后 x和 y結(jié)點(diǎn)間的弧上的標(biāo)記則為所求的正規(guī)式 r 62 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?例 以例 NFA M為例， M的狀態(tài)圖在圖 ，求 正規(guī)式 r,使 L(r)=L(M) 63 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 64 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?對(duì)于 ∑ 上的一個(gè)正規(guī)式 R，可以構(gòu)造一個(gè) ∑ 上的 NFA M，似的 L(M)=L(R) ?語(yǔ)法制導(dǎo)方法：按正規(guī)式的語(yǔ)法結(jié)構(gòu)指引構(gòu)造過(guò)程，首先 將正規(guī)式分解成一系列子表達(dá)式，然后使用下面規(guī)則為 r 構(gòu)造 NFA，對(duì) r的各種語(yǔ)法結(jié)構(gòu)的構(gòu)造規(guī)則具體描述如下： 1. ① 對(duì)于正規(guī)式 216。則有： 69 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 令 r5=a， 令 r6=b， 令 r7=b， 令 r8=r5r6， 令 r9=r8r7，則有： 令 r10=r4r9，則最終得到圖 NFA N即為所求。 70 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 圖 從正規(guī)式 r構(gòu)造 NFA 71 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 167。 詞法分析程序的自動(dòng)構(gòu)造工具 ?以 LEX為例介紹如何從正規(guī)式產(chǎn)生識(shí)別該正規(guī)式所描述的 單詞的詞法分析程序 ?LEX是一個(gè)廣泛使用的工具， UNIX系統(tǒng)中使用 lex命令調(diào) 用。 ? int cc=0。} ? ＼ t { tablize()。 line copy()。 return LT。 return GT。 return EQ。 return NE。 return colon。 return Period。 return Lparen。 return Rparen。cc++。} ? = { cc++。return GE。 cc++。} ? 。 return Semicolon。 ? cc += yyleng。n)。 ? return NUMBER。 ? cc += yyleng。 /* install symbol*/ ? if (s→type==C) ? =s〉 adr。s a VARIABLE or PROC*/ ? =s。 ? } ? %% ? yywrap( ) { ? }。 典型例題及解答 1（ 0｜ 1） *101相應(yīng)的 DFA 83 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 DFA最小化 84 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 scanner的 LEX的源文件，請(qǐng)給 出 scanner對(duì)輸入串 ababcbacaabaababaa的輸出結(jié)果： %% a+b*a {printf( `1%s\n`,yytext)。} aa {printf( `3%s\n`,yytext)。} 85 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 【 本章小結(jié) 】 詞法分析程序是編譯第一階段的工作，它讀入字符流的源程序，按照詞法規(guī)則識(shí)別單詞 ,交由語(yǔ)法分析程序接下去。在此基礎(chǔ)上給出了詞法分析程序自動(dòng)構(gòu)造工具如 LEX的原理。 詞法分析程序的自動(dòng)構(gòu)造工具也廣泛應(yīng)用于許多方面，如用以生成一個(gè)程序，可識(shí)別印刷電路板中的缺陷，又如開(kāi)關(guān)線路設(shè)計(jì)和文本編輯的自動(dòng)生成等。并給出該語(yǔ)言