【正文】 并給出該語言的正規(guī)式。在此基礎(chǔ)上給出了詞法分析程序自動(dòng)構(gòu)造工具如 LEX的原理。} aa {printf( `3%s\n`,yytext)。 ? } ? %% ? yywrap( ) { ? }。 /* install symbol*/ ? if (s→type==C) ? =s〉 adr。 ? return NUMBER。 ? cc += yyleng。} ? 。return GE。cc++。 return Lparen。 return colon。 return EQ。 return LT。} ? ＼ t { tablize()。 詞法分析程序的自動(dòng)構(gòu)造工具 ?以 LEX為例介紹如何從正規(guī)式產(chǎn)生識(shí)別該正規(guī)式所描述的 單詞的詞法分析程序 ?LEX是一個(gè)廣泛使用的工具， UNIX系統(tǒng)中使用 lex命令調(diào) 用。則有： 69 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 令 r5=a， 令 r6=b， 令 r7=b， 令 r8=r5r6， 令 r9=r8r7，則有： 令 r10=r4r9，則最終得到圖 NFA N即為所求。從 x結(jié)點(diǎn)用 ?弧連接到 M的所有初始 結(jié)點(diǎn)，從 M的所有終態(tài)結(jié)點(diǎn)用 ?弧連接到 y結(jié)點(diǎn)。 ?closure(move(T2,b))={1,2,4,5,6,7}，即 T2， T2已在 C中 T3： ?closure(move(T3,a))={1,2,3,4,6,7,8}，即 T1。并且約定，狀態(tài) S1, S2,... Sj是按某種規(guī)則排列的，即對(duì)于子集 {S1, S2}={ S2, S1,}來說， 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的開始狀態(tài) ? St={[Sj Sk... Se]，其中 [Sj Sk... Se]?S且 {Sj , Sk,... Se} ∩Kt?216。 有窮自動(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)換圖） ?假定 DFA M含有 m個(gè)狀態(tài)， n個(gè)輸入符號(hào)，那么這個(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) (雙圈、 +)，若 f(ki,a)=kj，則從狀態(tài)結(jié)點(diǎn) ki到狀態(tài)結(jié)點(diǎn) kj畫標(biāo)記為 a的弧 31 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 圖 狀態(tài)圖表示 ?例 DFA的狀態(tài)圖表示如圖 ： 32 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?一個(gè) DFA可以表示成一個(gè) 矩陣表示 ，該矩陣的行表示狀 態(tài)，列表示輸入符號(hào)，矩陣元素表示相應(yīng)狀態(tài)和輸入符 號(hào)將轉(zhuǎn)換成的新狀態(tài)，即 k行 a列為 f(k,a)的值。在不致混淆時(shí)，括號(hào)可省去， 但規(guī)定算符的優(yōu)先順序?yàn)椤??”、“ ?”、 “ ?”、“ ? ”、 “ ?” 。 （ 5, ?。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。 ? ） 11 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 三 .將詞法分析工作分離的考慮 、清晰和條理化： ： ： 12 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 167。連接符“ ? ”一般可省略不寫。用 標(biāo)明初態(tài)；否則第一行即是初態(tài)，相應(yīng)終態(tài)行在表的右 端標(biāo)以 1，非終態(tài)標(biāo)以 0 33 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 圖 矩陣表示 ?例 DFA的矩陣表示如圖 ： 34 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?若 t? ∑*， f(S， t)=P，其中 S為 M的開始狀態(tài)， P ? Z， Z為終態(tài)集，則稱 t為 DFA M所接受 （識(shí)別） ?設(shè) Q∈ K，函數(shù) f(Q,ε)=Q，一個(gè)輸入符號(hào)串 t（ t1tx， t1 ∈ ∑,tx ∈ ∑*），在 DFA M上運(yùn)行的定義為： f(Q,t1tx)=f(f(Q,t1),tx) 35 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?例如，證明 t=baab被例 DFA所接受 ?f（ S， baab） =f（ f（ S， b）， aab） =f（ V， aab） =f（ f （ V， a）， ab） =f（ U， ab） =f（ f（ U， a）， b） =f（ Q， b） =Q ?Q屬于終態(tài) ?得證 36 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?DFA M所能接受的符 號(hào) 串的全體記為 L(M) ?結(jié)論： ?上一個(gè)符 號(hào) 串集 V???是正規(guī)的，當(dāng)且僅當(dāng)存