【正文】 1 ，常數(shù)為 2，關(guān)鍵字為 3，運(yùn)算符為 4，界符為 5 10 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?if i=5 then x:=y ?關(guān)鍵字 if (3, ? if?) ?標(biāo)識(shí)符 i （ 1，指向 i的符號(hào)表入口） ?等號(hào) ＝ （ 4, ?= ?） ?常數(shù) 5 （ 2, ?5? ） ?關(guān)鍵字 then （ 3, ?then ? ） ?標(biāo)識(shí)符 x （ 4,指向 x的符號(hào)表入口） ?賦值號(hào) := （ 4, ?： = ? ） ?標(biāo)識(shí)符 y （ 1, 指向 y的符號(hào)表入口 ） ?分號(hào) 。 單詞的描述工具 一 .正規(guī)文法 ?程序設(shè)計(jì)語言中的幾類單詞可用下述規(guī)則描述： ?標(biāo)識(shí)符 l|l字母數(shù)字 ?字母數(shù)字 l|d|l字母數(shù)字 |d字母數(shù)字 ?無符號(hào)整數(shù) d|d無符號(hào)整數(shù) ?運(yùn)算符 +||*|/|=|等號(hào) |等號(hào) …… ?等號(hào) = ?界符 ,|。 狀態(tài)集合 I的任何狀態(tài) S都屬于 ?closure(I) ? I的 a弧轉(zhuǎn)換，表示為 move(I,a)定義為狀態(tài)集合 J ，其中 J是所有那些可從 I的某一狀態(tài)經(jīng)過一條 a弧而到達(dá) 的狀態(tài)的全體 43 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?使用圖 NFA N的狀態(tài)集合來理解上述兩個(gè)運(yùn)算： ??closure(0)={0,1,2,4,7} ?令 A={0,1,2,4,7}, move(A,a)={3,8} ??closure({3,8})={1,2,3,4,6,7,8} 圖 NFA N 44 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?對(duì)于一個(gè) NFA N=（ K， ?， f， K0， Kt）來說，若 I是 K 的一個(gè)子集，設(shè) I＝ {s1,s2,?,s j}， a是 ∑中的一個(gè)元素，則 move(I,a)=f(s1,a) ∪ f(s2,a) ∪ ? ∪ f(sj,a) 45 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?假設(shè) NFA N=(K, ?,f,K0,Kt)按如下辦法構(gòu)造一個(gè) DFA M=(S, ?,d,S0,St)，使得 L(M)=L(N)： ? M的狀態(tài)集 S由 K的一些子集組成。 ?closure(move(T4,b))={1,2,4,5,6,7}，即 T2 50 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ? a b 0 01247 T0=01247 38 5 38 1234678 5 124567 T1=1234678 38 59 59 1245679 T2=124567 38 5 T3=1245679 38 5 10 5 10 12456710 T4=12456710 38 5 51 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?至此，算法終止共構(gòu)造了 5個(gè)子集： ?T0={0,1,2,4,7} ?T1={1,2,3,4,6,7,8} ?T2={1,2,4,5,6,7} ?T3={1,2,4,5,6,7,9} ?T4={1,2,4,5,6,7,10} ?那么圖 NFA N構(gòu)造的 DFA M為： ={ [T0], [T1], [T2], [T3], [T4] } 2. ∑={a,b} 52 盛威網(wǎng)：專業(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] ?為便于書寫，將 [T0]、 [T1]、 [T2]、 [T3]、 [T4]重新命名為 A、 B、 C、 D、 E或用 0、 4分別表示，若采用后 者，該 DFA M的狀態(tài)轉(zhuǎn)換圖如圖 ： 53 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 圖 DFA M 54 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 四 . DFA的化簡(jiǎn) ?最小狀態(tài) DFA： ?沒有多余狀態(tài) (死狀態(tài) ) ?沒有兩個(gè)狀態(tài)是互相等價(jià)（ 不可區(qū)別 ） ?一個(gè)有窮自動(dòng)機(jī)可以通過消除無用狀態(tài)和合并等價(jià)狀態(tài) 而轉(zhuǎn)換成一個(gè)最小的與之等價(jià)的有窮自動(dòng)機(jī) ?有窮自動(dòng)機(jī)的無用狀態(tài)：從該自動(dòng)機(jī)的開始狀態(tài)出發(fā)， 任何輸入串也 不能到達(dá) 的那個(gè)狀態(tài)或者從這個(gè)狀態(tài) 沒有 通路到達(dá) 終態(tài) ?例如圖 M中的狀態(tài) s4便是無用狀態(tài) 55 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 圖 消除多余狀態(tài) 56 盛威網(wǎng)：專業(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)：專業(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)：專業(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)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 圖 DFA M和 DFA M` 60 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 167。 70 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 圖 從正規(guī)式 r構(gòu)造 NFA 71 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 167。 line copy()。 return NE。 return Rparen。 cc++。n)。s a VARIABLE or PROC*/ ? =s。} 85 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 【 本章小結(jié) 】 詞法分析程序是編譯第一階段的工作，它讀入字符流的源程序，按照詞法規(guī)則識(shí)別單詞 ,交由語法分析程