【正文】 90 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 第 4章 作業(yè)題 P72： 1.(2)(3) 2. 4. 6. 7. 9. 。 86 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 第 4章習題 第 1題：構造正規(guī)式 1(0|1) *101相應的 DFA 87 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 第 2題：將下圖確定化： 88 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 第 3題：將下圖的（ a）和（ b）分別確定化和最小化： 89 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 第 4題： 構造一個 DFA，它接收 Σ={0,1}上所有滿足如下條件的字符串：每個 1都有 0直接跟在右邊。 詞法分析程序的設計技術可應用于其它領域，比如查詢語言以及信息檢索系統(tǒng)等，這種應用領域的程序設計特點是，通過字符串模式的匹配來引發(fā)動作，回想 LEX，說明詞法分析程序的語言，可以看成是一個模式動作語言。 本章講述了詞法分析程序設計原則，并介紹了正規(guī)式和有窮動機分別作為正規(guī)集描述和識別機制。} (a|b)*c {printf( `4%s\n`,yytext)。} (ab)+c? {printf( `2%s\n`,yytext)。 圖 LEX程序例子 識別 PL/0單詞的 LEX程序 82 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 167。 ? return s〉 type。 ? else /*it39。 ? if((s=lookup(yytext))==0) /*new identifier*/ ? s=install(yytext,VARIABLE,level,0)。 ? } 81 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ? {IDENT} { ? Symbol *s。 ? =n。 ? sscanf(yytext,%d, amp。} ? {NUMBER} { ? intn。 { cc++。return ASGN。} ? ∶ = { cc++。cc++。return LE。} ? = { cc++。} ? ) { cc++。} ? ( { cc++。 } ? . { cc++。} ? , { cc++。} 80 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ? { cc++。} ? = { cc++。} ? { cc++。 } /*copy a line of input file*/ ? { cc++。 } /*adjustcc to tab position*/ ? ＼ n { cc=0。 ? %) ? %% ? { cc++。它用于構造各種各樣語言的詞法分析程序 圖 77 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 圖 使用 LEX生成詞法分析器 78 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?LEX程序由三部分組成： ?說明部分：變量說明、常量說明、正規(guī)定義 ?%% ?轉(zhuǎn)換規(guī)則： Pn {action n} ?%% ?輔助過程： 容納的是 action所需要的輔助過程 79 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?圖 PL/O單詞的 LEX程序片斷： ? IDENT[azAZ] [azAZ09]* ? NUMBER[09] [09]* ? %( ? include 〈 〉 ? include “ ? include “ ? include “ ? extern int level。 正規(guī)文法和有窮自動機的等價性 ?采用下面的規(guī)則可以從正規(guī)文法 G直接構造一個有窮 自動機 NFA M；使得 L（ M）＝ L（ G）： ?M的字母表與 G的終結符集相同 ?為 G中的每個非終結符生成 M的一個狀態(tài)， G的開始符 S 是開始狀態(tài) S 72 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?增加一個新狀態(tài) Z，作為 NFA的終態(tài) ?對 G中的形如 A tB的規(guī)則（其中 t為終結符或 ?， A和 B為 非終結符的產(chǎn)生式），構造 M的一個轉(zhuǎn)換函數(shù) f(A,t)=B ?對 G中形如 A t的產(chǎn)生式，構造 M的一個轉(zhuǎn)換函數(shù) f(A,t)=Z 73 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?例 ：與文法 G［ S］等價的 NFA M如圖 ?G[S]: ?S a A ?S bB ?S ε ?A aB ? A bA ?B aS ?B bA ?B ε 74 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?有窮自動機轉(zhuǎn)換成等價的正規(guī)文法： ?對轉(zhuǎn)換函數(shù) f(A,t)=B,可寫一產(chǎn)生式： A tB ?對可接受狀態(tài) Z，增加一產(chǎn)生式： Z ε ?有窮自動機的初態(tài)對應文法開始符 ?有窮自動機的字母表為文法的終結符集 75 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?例 ： 給出不圖 NFA等價的正規(guī)文法 G ?G＝（｛ A， B， C， D｝，｛ a， b}， P， A），其中 P為： ?A a B ?C ε ?A bD ?D aB ?B bC ?D bD ?C aA ?D ε ?C bD 76 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 167。 其實，分解 R的方式很多，用圖 (a)(b)(c)(d)分別表明另一種分解方式和所構造的 NFA。所構造的 NFA為： 65 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 66 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 67 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 68 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?例 為 r=(a|b)*abb構造 NFA N,使得 L(N)=L(r) ?從左到右分解 r,令 r1=a,第 1個 a,則有 令 r2=b,則有 令 r3=r1|r2,則有 令 r4=r339。形成 一個與 M等價的 M`, M`只有一個初態(tài) x和一個終態(tài) y ?第二步，逐步消去 M`中的所有結點，直至只剩下 x和 y 結點。 正規(guī)式和有窮自動機的等價性 ?對于 ∑ 上的一個 NFA M，可以構造一個 ∑ 上的正規(guī)式 R,使得 L(R)=L(M) ?第一步，在 M的狀態(tài)轉(zhuǎn)換圖上加進兩個結，一