【正文】 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?例 為 r=(a|b)*abb構(gòu)造 NFA N,使得 L(N)=L(r) ?從左到右分解 r,令 r1=a,第 1個(gè) a,則有 令 r2=b,則有 令 r3=r1|r2,則有 令 r4=r339。} ? = { cc++。cc++。 ? if((s=lookup(yytext))==0) /*new identifier*/ ? s=install(yytext,VARIABLE,level,0)。 86 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 第 4章習(xí)題 第 1題：構(gòu)造正規(guī)式 1(0|1) *101相應(yīng)的 DFA 87 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 第 2題：將下圖確定化： 88 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 第 3題：將下圖的（ a）和（ b）分別確定化和最小化： 89 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 第 4題： 構(gòu)造一個(gè) DFA，它接收 Σ={0,1}上所有滿足如下條件的字符串：每個(gè) 1都有 0直接跟在右邊。 圖 LEX程序例子 識(shí)別 PL/0單詞的 LEX程序 82 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 167。 { cc++。 } ? . { cc++。它用于構(gòu)造各種各樣語(yǔ)言的詞法分析程序 圖 77 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 圖 使用 LEX生成詞法分析器 78 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?LEX程序由三部分組成： ?說(shuō)明部分：變量說(shuō)明、常量說(shuō)明、正規(guī)定義 ?%% ?轉(zhuǎn)換規(guī)則： Pn {action n} ?%% ?輔助過(guò)程： 容納的是 action所需要的輔助過(guò)程 79 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?圖 PL/O單詞的 LEX程序片斷： ? IDENT[azAZ] [azAZ09]* ? NUMBER[09] [09]* ? %( ? include 〈 〉 ? include “ ? include “ ? include “ ? extern int level。} ?構(gòu)造 NFA N的狀態(tài) K的子集的算法，見(jiàn)圖 ： ?假定所構(gòu)造的子集族為 C，即 C= (T1, T2,... Ti),其中 T1, T2,... Ti為狀態(tài) K的子集 47 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 48 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?例 應(yīng)用圖 NFA N構(gòu)造子集 步驟如下： ?closure(0)：令 T0=?closure(0)={0,1,2,4,7}， T0未 被標(biāo)記，它現(xiàn)在是子集族 C的唯一成員 T0：令 T1=?closure(move(T0,a))={1,2,3,4,6,7,8}，將 T1 加入 C中， T1未被標(biāo)記。1 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 第四章 詞法分析 ?第一節(jié) 詞法分析程序的設(shè)計(jì) ?第二節(jié) 單詞的描述工具 ?第三節(jié) 有窮自動(dòng)機(jī) ?第四節(jié) 正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)性 ?第五節(jié) 正規(guī)文法和有窮自動(dòng)機(jī)的等價(jià)性 ?第六節(jié) 詞法分析程序的自動(dòng)構(gòu)造工具 ?第七節(jié) 典型例題及解答 2 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 知識(shí)結(jié)構(gòu) 3 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 詞法分析 自動(dòng)構(gòu)造工具 {正規(guī)集 } 正規(guī)式 有窮自動(dòng)機(jī)（ NFA DFA) 正規(guī)文法 知識(shí)結(jié)構(gòu) ① ⑤ ⑥ ② ③ ④ 4 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 第四章 詞法分析 167。并且約定，狀態(tài) S1, S2,... Sj是按某種規(guī)則排列的，即對(duì)于子集 {S1, S2}={ S2, S1,}來(lái)說(shuō)， S的狀態(tài)就是 [S1 S2] ?M和 N的輸入字母表是相同的，即是 ? ?轉(zhuǎn)換函數(shù)是這樣定義的： D([S1 S2,... Sj],a)= [R1R2... Ri] 其中 {R1,R2,... , Ri} = ?closure(move({S1, S2,... Sj},a)) 46 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ? S0=?closure(K0)為 M的開(kāi)始狀態(tài) ? St={[Sj Sk... Se]，其中 [Sj Sk... Se]?S且 {Sj , Sk,... Se} ∩Kt?216。 詞法分析程序的自動(dòng)構(gòu)造工具 ?以 LEX為例介紹如何從正規(guī)式產(chǎn)生識(shí)別該正規(guī)式所描述的 單詞的詞法分析程序 ?LEX是一個(gè)廣泛使用的工具， UNIX系統(tǒng)中使用 lex命令調(diào) 用。 return colon。} ? 。 ? } ? %% ? yywrap( ) { ? }。并給出該語(yǔ)言的正規(guī)式。 /* install symbol*/ ? if (s→type==C) ? =s〉 adr。return GE。 return EQ。則有： 69 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 令 r5=a， 令 r6=b， 令 r7=b， 令 r8=r5r6， 令 r9=r8r7，則有： 令 r10=r4r9，則最終得到圖 NFA N即為所求。 有窮自動(dòng)機(jī) 一 .確定的有窮自動(dòng)機(jī)（ DFA）（有限自動(dòng)機(jī)） ?DFA：能準(zhǔn)確地識(shí)別正規(guī)集 ?一個(gè)確定的 DFA： M=（ K， Σ， f， S， Z） ?K是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài) ?Σ 是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符 號(hào)，所以也稱 Σ 為輸入符號(hào)字母表 28 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?f是轉(zhuǎn)換函數(shù)，是在 K Σ→K 上的映射，即，如 f（ ki， a） =kj，（ ki∈ K， kj∈ K） 就意味著，當(dāng)前狀 態(tài)為 ki，輸入符為 a時(shí)，將轉(zhuǎn)換為下一個(gè)狀態(tài) kj，我們 把 kj稱作 ki的一個(gè)后繼狀態(tài) ?S∈ K是唯一的一個(gè)初態(tài) ?Z? K是一個(gè)終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài) 29 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?例 ： DFA M=（ {S， U,V， Q}， {a， b}， f， S， {Q}） 其中 f定義為： ?f（ S， a） =U f（ V， a） =U ?f（ S， b） =V f（ v， b） =Q ?f（ U， a） =Q f（ Q， a） =Q ?f（ U， b） =V f（ Q， b） =Q 30 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?一個(gè) DFA可以表示成一個(gè) 狀態(tài)圖 （狀態(tài)轉(zhuǎn)換圖） ?假定