第四章詞法分析-wenkub
2022-08-29 13:36:28 本頁(yè)面
【正文】 在一個(gè) ?上的確定有窮自動(dòng)機(jī) M，使得 V=L(M) ?DFA的確定性表現(xiàn)在轉(zhuǎn)換函數(shù) f:K ∑→K 是一個(gè)單值 函數(shù)，也就是說(shuō) ,對(duì)任何狀態(tài) k∈ K和輸入符號(hào) a ∈ ∑， f(k,a)唯一地確定了下一個(gè)狀態(tài) 37 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 二 .丌確定的有窮自動(dòng)機(jī) NFA ?一個(gè) NFA： M=（ K， ?， f， S， Z） ?K是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài) ??是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào) ?f是一個(gè)從 K? ?* 到 K的子集的映像，即： K* ?* → 2 K ?S?K是一個(gè)非空初態(tài)集 ?Z?K是一個(gè)終態(tài)集 38 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?例 ：一個(gè) NFA M=（ {0， 1， 2， 3， 4}， {a， b}， f， {0}， {2,4}）其中 ?f(0,a)={0,3} f(2,b)={2} ?f(0,b)={0,1} f(3,a)={4} ?f(1,b)={2} f(4,a)={4} ?f(2,a)={2} f(4,b)={4} ?它的狀態(tài)圖表示如圖 ： 39 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 40 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?一個(gè) NFA也可以用一個(gè)矩陣表示 ... ?∑*上的符 號(hào) 串 t在 NFA N上運(yùn)行 ... ?∑*上的符 號(hào) 串 t被 NFA N識(shí)別（讀出、接受） ... ?DFA是 NFA的特例 ?對(duì)每個(gè) NFA N存在一個(gè) DFA Ｍ ,使得 L(M)=L(N) ?對(duì)于任何兩個(gè)有窮自動(dòng)機(jī) M和 N，如果 L(M)=L(N)，則稱 M與 N是等價(jià)的 41 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 三 .NFA轉(zhuǎn)換為等價(jià)的 DFA ?定理： 設(shè) L為一個(gè)由不確定的有窮自動(dòng)機(jī)接受的集合，則 存在一個(gè)接受 L的確定的有窮自動(dòng)機(jī) ?將 NFA轉(zhuǎn)換成接受同樣語(yǔ)言的 DFA，這種算法稱為 子集法 42 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?定義對(duì)狀態(tài)集合 I的幾個(gè)有關(guān)運(yùn)算： ? I的 ?閉包，表示為 ?closure(I)，定義為一狀態(tài) 集，是狀態(tài)集 I中的任何狀態(tài) S經(jīng)任意條 ?弧而能到達(dá)的狀 態(tài)的集合。} ?構(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)記。 ? closure(move(T3,b))={1,2,4,5,6,7,10},令其為 T4，在入 C中， T4未被標(biāo)記 T4： ?closure(move(T4,a))={1,2,3,4,6,7,8}，即 T1。形成 一個(gè)與 M等價(jià)的 M`, M`只有一個(gè)初態(tài) x和一個(gè)終態(tài) y ?第二步，逐步消去 M`中的所有結(jié)點(diǎn)，直至只剩下 x和 y 結(jié)點(diǎn)。 其實(shí)，分解 R的方式很多，用圖 (a)(b)(c)(d)分別表明另一種分解方式和所構(gòu)造的 NFA。它用于構(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。 } /*adjustcc to tab position*/ ? ＼ n { cc=0。} ? { cc++。} 80 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ? { cc++。 } ? . { cc++。} ? ) { cc++。return LE。} ? ∶ = { cc++。 { cc++。 ? sscanf(yytext,%d, amp。 ? } 81 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ? {IDENT} { ? Symbol *s。 ? else /*it39。 圖 LEX程序例子 識(shí)別 PL/0單詞的 LEX程序 82 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 167。} (a|b)*c {printf( `4%s\n`,yytext)。 詞法分析程序的設(shè)計(jì)技術(shù)可應(yīng)用于其它領(lǐng)域，比如查詢語(yǔ)言以及信息檢索系統(tǒng)等，這種應(yīng)用領(lǐng)域的程序設(shè)計(jì)特點(diǎn)是，通過(guò)字符串模式的匹配來(lái)引發(fā)動(dòng)作，回想 LEX，說(shuō)明詞法分析程序的語(yǔ)言，可以看成是一個(gè)模式動(dòng)作語(yǔ)言。 90 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 第 4章 作業(yè)題 P72： 1.(2)(3) 2. 4. 6. 7. 9. 。 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直接跟在右邊。 本章講述了詞法分析程序設(shè)計(jì)原則，并介紹了正規(guī)式和有窮動(dòng)機(jī)分別作為正規(guī)集描述和識(shí)別機(jī)制。} (ab)+c? {printf( `2%s\n`,yytext)。 ? return s〉 type。 ? if((s=lookup(yytext))==0) /*new identifier*
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1