【正文】 國防科技大學(xué)計算機(jī)系 602教研室 0 1 2 3 5 4 6 a a b b b a b a a b a b a b I(1)={0, 1, 2} I(2)={3, 4, 5, 6} Ia(1) ={1, 3} I(11) ={0, 2} I(12) ={1} I(2)={3, 4, 5, 6} I(11) ={0, 2} Ia(11) ={1} Ib(11) ={2, 5} I(111) ={0} I(112) ={2} I(12) ={1} I(2)={3, 4, 5, 6} Ia(2) ={3, 6} Ia(2) ={4, 5} 國防科技大學(xué)計算機(jī)系 602教研室 0 1 2 3 5 4 6 a a b b b a b a a b a b a b 0 1 2 3 a a b b b a a b 國防科技大學(xué)計算機(jī)系 602教研室 詞法分析器的自動產(chǎn)生 LEX 詞法分析程序自動產(chǎn)生器 詞法分析程序 L LEX源程序 詞法分析程序 L 單詞符號 輸入串 狀態(tài)轉(zhuǎn)換矩陣 控制執(zhí)行程序 國防科技大學(xué)計算機(jī)系 602教研室 AUXILIARY DEFINITION letter?A|B|...|Z digit ?0|1|...|9 RECOGNITION RULES 1 DIM { RETURN (1,) } 2 IF { RETURN (2,) } 3 DO { RETURN (3,) } 4 STOP { RETURN (4,) } 5 END { RETURN (5,) } 6 letter(letter|digit) * { RETURN (6, TOKEN) } 7 digit(digit)* { RETURN (7, DTB) } 8 = { RETURN (8, ) } 9 + { RETURN (9,) } 10 * { RETURN (10,) } 11 ** { RETURN (11,) } 12 , { RETURN (12,) } 13 ( { RETURN (13,) } 14 ) { RETURN (14,) } 國防科技大學(xué)計算機(jī)系 602教研室 ? LEX的工作過程： ?首先，對每條識別規(guī)則 Pi構(gòu)造一個相應(yīng)的非確定有限自動機(jī) Mi； ?然后，引進(jìn)一個新初態(tài) X，通過 ?弧，將這些自動機(jī)連接成一個新的 NFA； ?最后，把 M確定化、最小化，生成該 DFA的狀態(tài)轉(zhuǎn)換表和控制執(zhí)行程序 國防科技大學(xué)計算機(jī)系 602教研室 X ? P2 ? ? ? M1 Mm M2 P1 Pm ? ? 國防科技大學(xué)計算機(jī)系 602教研室 作業(yè) ? P647， 8， 12， 14 國防科技大學(xué)計算機(jī)系 602教研室 例 : 對下圖 NFA M構(gòu)造其 DFA. a a b b b X Y 解 : 用子集法構(gòu)造轉(zhuǎn)換矩陣 I I a I b{ x } { x , y } { y }{ y } { x , y }{ x , y } { x , y } { x , y } 字符狀態(tài)a b0 2 11 22 2 2不可識別 ba ! 國防科技大學(xué)計算機(jī)系 602教研室 {1, 2} {0} a b a,b a b 0 2 1 DFA M’ a a,b a b 0 1 化簡后的 DFA M’ ba ?。?！ 。 ? 對于上述最后劃分 ?中的每個子集，我們選取每個子集 I中的一個狀態(tài)代表其他狀態(tài)，則可得到化簡后的 DFA M?。這樣構(gòu)成新的劃分。 國防科技大學(xué)計算機(jī)系 602教研室 ? 例如，假定狀態(tài) s1和 s2經(jīng) a弧分別到達(dá) t1和t2，而 t1和 t2屬于現(xiàn)行 ?中的兩個不同子集，說明有一個字 ?， t1讀出 ?后到達(dá)終態(tài)，而t2讀出 ?后不能到達(dá)終態(tài)，或者反之，那么對于字 a? ， s1讀出 a?后到達(dá)終態(tài)，而s2讀出 a?不能到達(dá)終態(tài)，或者反之，所以s1和 s2不等價。 國防科技大學(xué)計算機(jī)系 602教研室 ? 具體做法 : 對 M的狀態(tài)集進(jìn)行劃分 ?首先，把 S劃分為終態(tài)和非終態(tài)兩個子集，形成基本劃分 ?。 國防科技大學(xué)計算機(jī)系 602教研室 ? 對一個 DFA M最少化的基本思想 : 把 M的狀態(tài)集劃分為一些不相交的子集，使得任何兩個不同子集的狀態(tài)是可區(qū)別的，而同一子集的任何兩個狀態(tài)是等價的。 國防科技大學(xué)計算機(jī)系 602教研室 代之為 i j V1 V2 k i k V1V2 代之為 i j V1|V2 i j V2 V1 代之為 i k V1* i j ? ? k V1 然后 ， 按下面的三條規(guī)則對 V進(jìn)行分裂 國防科技大學(xué)計算機(jī)系 602教研室 ? 逐步把這個圖轉(zhuǎn)變?yōu)槊織l弧只標(biāo)記為 ?上的一個字符或 ?，最后得到一個 NFA M?，顯然L(M?)=L(V) 國防科技大學(xué)計算機(jī)系 602教研室 ? (a|b)*(aa|bb)(a|b)* X Y (a|b)*(aa|bb)(a|b)* X Y ? 5 1 4 2 3 6 a b ? ? ? a b a b a b 國防科技大學(xué)計算機(jī)系 602教研室 I Ia Ib {X,5,1} {5,3,1} {5,4,1} {5,3,1} {5,2,3,1,6,Y} {5,4,1} {5,4,1} {5,3,1} {5,2,4,1,6,Y} {5,2,3,1,6,Y} {5,2,3,1,6,Y} {5,4,6,1,Y} {5,4,6,1,Y} {5,3,6,1,Y} {5,2,4,1,6,Y} {5,2,4,1,6,Y} {5,3,6,1,Y} {5,2,4,1,6,Y} {5,3,6,1,Y} {5,2,3,1,6,Y} {5,4,6,1,Y} X Y ? 5 1 4 2 3 6 a b ? ? ? a b a b a b 國防科技大學(xué)計算機(jī)系 602教研室 I a b 0 1 2 1 3 2 2 1 4 3 3 4 4 6 5 5 6 5 6 3 4 0 1 2 3 5 4 6 a a b b b a b a a b a b a b 國防科技大學(xué)計算機(jī)系 602教研室 確定有限自動機(jī)的化簡 ? 對 DFA M的化簡 :尋找一個狀態(tài)數(shù)比 M少的 DFA M?，使得 L(M)=L(M?) ? 假設(shè) s和 t為 M的兩個狀態(tài)，稱 s和 t等價 :如果從狀態(tài) s出發(fā)能讀出某個字 ?而停止于終態(tài)，那么同樣，從 t出發(fā)也能讀出 ?而停止于終態(tài)；反之亦然。 L(M) = L(M1)* = L(r1)* = L(r) 至此，結(jié)論 2獲證。 令 M=S1∪ {q0, f0}, ?1, ?, q0, {f0}，其中 q0, f0?S1， ?定義如下： (a) ?(q0,?)=?(f1,?)={q1, f0} (b) ?(q,a)= ?1(q, a), 當(dāng) q?S1{f1}, a??1∪ {?}。 ? M1 q1 f1 M2 q2 f2 國防科技大學(xué)計算機(jī)系 602教研室 ? 情形 3： r=r1*。 令 M=S1∪ S2, ?1∪ ?2, ?, q1, {f2}，其中 ?定義如下： (a) ?(q,a)= ?1(q,a), 當(dāng) q?S1{f1}, a??1∪ {?} (b) ?(q,a)= ?2(q,a), 當(dāng) q?S2, a??2∪ {?}