第三章詞法分析-資料下載頁

　　

【正文】 國防科技大學計算機系 602教研室 ? 逐步把這個圖轉變為每條弧只標記為 ?上的一個字符或 ?，最后得到一個 NFA M?，顯然L(M?)=L(V) 國防科技大學計算機系 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 國防科技大學計算機系 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 國防科技大學計算機系 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 國防科技大學計算機系 602教研室 確定有限自動機的化簡 ? 對 DFA M的化簡 :尋找一個狀態數比 M少的 DFA M?，使得 L(M)=L(M?) ? 假設 s和 t為 M的兩個狀態，稱 s和 t等價 :如果從狀態 s出發能讀出某個字 ?而停止于終態，那么同樣，從 t出發也能讀出 ?而停止于終態；反之亦然。 ? 兩個狀態不等價，則稱它們是 可區別 的。 國防科技大學計算機系 602教研室 ? 對一個 DFA M最少化的基本思想 : 把 M的狀態集劃分為一些不相交的子集，使得任何兩個不同子集的狀態是可區別的，而同一子集的任何兩個狀態是等價的。最后，讓每個子集選出一個代表，同時消去其他狀態。 國防科技大學計算機系 602教研室 ? 具體做法 : 對 M的狀態集進行劃分 ?首先，把 S劃分為終態和非終態兩個子集，形成基本劃分 ?。 ?假定到某個時候， ?已含 m個子集，記為?={I(1)， I(2)， ? ， I(m)}，檢查 ?中的每個子集看是否能進一步劃分 : ?對某個 I(i)，令 I(i)={s1,s2, ? ,sk}，若存在一個輸入字符 a使得 Ia(i) 不會包含在現行 ?的某個子集 I(j)中，則至少應把 I(i)分為兩個部分。 國防科技大學計算機系 602教研室 ? 例如，假定狀態 s1和 s2經 a弧分別到達 t1和t2，而 t1和 t2屬于現行 ?中的兩個不同子集，說明有一個字 ?， t1讀出 ?后到達終態，而t2讀出 ?后不能到達終態，或者反之，那么對于字 a? ， s1讀出 a?后到達終態，而s2讀出 a?不能到達終態，或者反之，所以s1和 s2不等價。則將分成兩半，使得一半含有 s1: I(i1)={s|s?I(i)且 s經 a弧到達 t, 且 t與 t1屬于現行 ?中的同一子集 } 另一半含有 s2: I(i2)=I(i)I(i1) 國防科技大學計算機系 602教研室 ? 一般地，對某個 a和 I(i)，若 Ia(i) 落入現行 ?中 N個不同子集，則應把 I(i)劃分成 N個不相交的組，使得每個組 J的 Ja都落入的 ?同一子集。這樣構成新的劃分。 ? 重復上述過程，直到 ?所含子集數不再增長。 ? 對于上述最后劃分 ?中的每個子集，我們選取每個子集 I中的一個狀態代表其他狀態，則可得到化簡后的 DFA M?。 ? 若 I含有原來的初態，則其代表為新的初態，若 I含有原來的終態，則其代表為新的終態 。 國防科技大學計算機系 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} 國防科技大學計算機系 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 國防科技大學計算機系 602教研室 詞法分析器的自動產生 LEX 詞法分析程序自動產生器 詞法分析程序 L LEX源程序 詞法分析程序 L 單詞符號 輸入串 狀態轉換矩陣 控制執行程序 國防科技大學計算機系 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,) } 國防科技大學計算機系 602教研室 ? LEX的工作過程： ?首先，對每條識別規則 Pi構造一個相應的非確定有限自動機 Mi； ?然后，引進一個新初態 X，通過 ?弧，將這些自動機連接成一個新的 NFA； ?最后，把 M確定化、最小化，生成該 DFA的狀態轉換表和控制執行程序 國防科技大學計算機系 602教研室 X ? P2 ? ? ? M1 Mm M2 P1 Pm ? ? 國防科技大學計算機系 602教研室 作業 ? P647， 8， 12， 14 國防科技大學計算機系 602教研室 例 : 對下圖 NFA M構造其 DFA. a a b b b X Y 解 : 用子集法構造轉換矩陣 I I a I b{ x } { x , y } { y }{ y } { x , y }{ x , y } { x , y } { x , y } 字符狀態a b0 2 11 22 2 2不可識別 ba ! 國防科技大學計算機系 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 ！！！