第二章詞法分析

1、2.3.2 NFA的定義 NFA的必要 識別程序設(shè)計語言中所有記號的DFA遇到的問 題 典型的程序設(shè)計語言中都有許多記號，每一個 記號都能被其自己的DFA識別出來 理論上應(yīng)該能將所有的記號都合并為一個巨大 的DFA。 這不是一個DFA。如果不使用系統(tǒng)化的方法 將所有的記號都合并為一個巨大的DFA，將 非常復(fù)雜。 13 letter letter,digit 2 other 5 digit digit 4 other 7 6 = 9 10 S的子集 S0S 初始狀態(tài) 1.A S 接受狀態(tài)集合 NFA 類似于 DFA，除了 擴展 包括 NFA 可以包含 -轉(zhuǎn)換無需考慮輸入串就有可 能發(fā)生的轉(zhuǎn)換 1

2、2 擴展擴展T的定義的定義 每一個字符都可以導(dǎo)致多個狀態(tài)。因此每一個字符都可以導(dǎo)致多個狀態(tài)。因此T的值的值 是狀態(tài)的一個集合而不是單獨的狀態(tài)是狀態(tài)的一個集合而不是單獨的狀態(tài) 例 NFA M=（S，P，Z,0，1,f,S,Z） 其中 f（S，0）=P f（S，1）=S，Z f（Z，0）=P f（Z，1）=P f（P，1）=Z 矩陣表示矩陣表示: : 01 SPS,Z PZ ZPP 0 0 1 狀態(tài)圖表示狀態(tài)圖表示: : S P Z 0 0,1 1 1 1 Z L(M): 由自動機 M 所接受（識別）的語言 L(M) ：is the set of strings of character字 符c1

3、c2cn ，每一個ci 都屬于 ， 且存 在關(guān)系：s1 在T(S0,c1)中,s2在T(S1,c2) 中,Sn 在T(Sn-1,cn) 中， s0 是初始狀態(tài)， Sn 是A的元素 c1c2cn 中的任一 ci 都可能是 真正被接受的串是刪除了的串 c1c2cn 非確定性 接受特定串的轉(zhuǎn)換序列并不由狀態(tài)和下一個輸 入字符在每一步確定下來 例如 1 2 34 a ab 下面兩個轉(zhuǎn)換序列都可接受串下面兩個轉(zhuǎn)換序列都可接受串 “abb” : 12424 abb 134242 ab 4 b 2.3.3 用代碼實現(xiàn)有窮自動機 構(gòu)建掃描程序（詞法分析程序）的過程構(gòu)建掃描程序（詞法分析程序）的過程: 正則表達(dá)

4、式正則表達(dá)式DFA 掃描程序掃描程序 正則表達(dá)式表示一種模式，用來描述記號正則表達(dá)式表示一種模式，用來描述記號 DFAs 表示按照正則表達(dá)式描述的模式接受符表示按照正則表達(dá)式描述的模式接受符 號串的算法號串的算法 從正則表達(dá)式到DFA（2.4節(jié)) 有窮自動機構(gòu)造詞法分析程序 1 用代碼實現(xiàn) DFA 用代碼實現(xiàn)DFA的一般算法 用一個變量保持當(dāng)前的狀態(tài) 將轉(zhuǎn)換寫成一個雙層嵌套的case語句而不是一 個循環(huán) 第一個case語句測試當(dāng)前的狀態(tài) 嵌套著的第2層測試輸入字符及所給的狀態(tài) state:=1;start while state=1 or 2 do case state of 1:case i

5、nput character of letter:advance the input; state:=2; else state:=error or other; end case 例如例如:接受標(biāo)識符的接受標(biāo)識符的DFA 13 letter letter digit 2 other 2:case input character of letter,digit:advance the input; state:=2; else state:=3; end case; end case; end while; if state=3 then accept else error; 13 lette

6、r letter digit 2 other 2 用代碼實現(xiàn)DFA的狀態(tài)轉(zhuǎn)換表 使用轉(zhuǎn)換表，可以用代碼實現(xiàn)任一DFA 代碼圖解中用到的變量 轉(zhuǎn)換被保存在一個轉(zhuǎn)換數(shù)組 “T”中，T由狀態(tài)和 輸入字符索引； 先行輸入的轉(zhuǎn)換是由布爾數(shù)組 “Advance”給出, 它們也由狀態(tài)和輸入字符索引； 由布爾數(shù)組 “Accept”給出的接受狀態(tài)由狀態(tài)索 引 代碼圖解 state:=1; ch:=next input character; while not Acceptstate and not error(state) do newstate:=Tstate,ch; if Advancestate,ch t

7、hen ch:=next input char; state:=newstate; end while; if Acceptstate then accept; 表驅(qū)動的優(yōu)點 代碼的長度縮短了 相同的代碼可以解決許多不同的問題 代碼較易改變（維護(hù)） 缺點 表格會變得非常大，使得程序要求使用的空間也 變得非常大 3 代碼的動作 進(jìn)行轉(zhuǎn)換時發(fā)生的典型動作是：將字符從輸入 串中移到屬于單個記號累積字符的字符串中 在達(dá)到某個接受狀態(tài)時的典型動作是：將剛被 識別的記號及相關(guān)屬性返回 遇到出錯狀態(tài)的典型動作是：在輸入中備份 （回溯）或生成錯誤記號 2.4 從正則表達(dá)式到 DFAs 正則表達(dá)式與 DFA的等

8、價性 從正則表達(dá)式到DFA 從正則表達(dá)式到 NFA(2.4.1) 從 NFA 到 DFA(2.4.2) DFA的最小化(2.4.3) 2.4.1 從正則表達(dá)式到 NFA “語法制導(dǎo)”法: 按正則表達(dá)式的語法結(jié)構(gòu)指引構(gòu)造過程 正則表達(dá)式構(gòu)造NFA的基本語法結(jié)構(gòu)的構(gòu)造規(guī) 則 2對于正則表達(dá)式對于正則表達(dá)式 ,構(gòu)造的構(gòu)造的NFA為為: 3對于正則表達(dá)式對于正則表達(dá)式a, a ，構(gòu)造的構(gòu)造的NFA為為 1對于正則表達(dá)式對于正則表達(dá)式,構(gòu)造的構(gòu)造的NFA為為: y x y x y x a a 復(fù)合正則表達(dá)式e的構(gòu)造規(guī)則 2 然后按下述三種情況進(jìn)行分解，直至每條弧上然后按下述三種情況進(jìn)行分解，直至每條弧上

9、 標(biāo)記一個字符標(biāo)記一個字符 1 先構(gòu)造如下的正則表達(dá)式先構(gòu)造如下的正則表達(dá)式 “e” 的的NFA: e e 1 1 Xy e=e1|e2 e e 2 2 X1 e e 1 1y e 2 e=e1e2 X1 y e1 e=e1* y x e e 例如例如: 將正則表達(dá)式將正則表達(dá)式 (a|b)*abb 翻譯成翻譯成NFA X (a|b)*a bb Y X (a|b) * 1 a 2 bb 3 Y X 4 1 b 3 a 2 b a|b Y X 4 1 b 3 a 2 b a b Y 2.4.2 從 NFA 到 DFA 1 轉(zhuǎn)換需解決的問題 刪除-轉(zhuǎn)換（合并） 如果 ,則刪除S2 S1S2 i j

10、 k m a b a n （a ） i,j m k a a b n （b ） 狀態(tài)合并（消除在單個字符上的多重轉(zhuǎn)換） 0 1 2 3 a a b c （a ） 01,23 a b c （b ） 2 轉(zhuǎn)換方法子集法 讓DFA 的每個狀態(tài)對應(yīng)NFA 的一個狀態(tài)集合。 即DFA用它的一個狀態(tài)記錄在NFA讀入一個輸 入符號后可能達(dá)到的所有狀態(tài)。 3 對狀態(tài)集合I的有關(guān)運算 狀態(tài)集合 I 的閉包_closure( I ) 是狀態(tài)集I中的任何狀態(tài)S以及經(jīng)任意條弧 而能到達(dá)的狀態(tài)的集合。 I I S2 S2 S1S1 S3 S3 _ Close(I) 以下將_closure( I ) 簡寫為closure(

11、I) Closure(I) =I Sk | if Sj Sk, Sj Closure(I) ， Sk Closure(I) 狀態(tài)集合的空閉包_closure 總是包含狀態(tài)集 合本身 if I=0,the _closure( I )= 例如例如: NFA 10 01 2 4 5 3 6789 a b abb 74 , 2,1 , 0 , Ia子集 I 是狀態(tài)集合, a 是字母表的一個字符 Move（I，a）=t|sI,and s t Ia= _closure ( Move( I , a ) ) a Ib = _closure( 例如例如: NFA 10 01 2 45 3 6789 a b ab

12、b if I=0,1,2,4,7 thenIa = _closure( ) 3 , 8 = 3, 8, 6 , 7 , 1 , 2 , 4 5 6 , ) = 5 , 7 , 2 , 1 , 4 4 由NFA M 構(gòu)造DFA M 的算法 將M的初始狀態(tài)的空閉包作為 M的初始狀態(tài) 為這個集合，以及此后的每個后續(xù)集合為這個集合，以及此后的每個后續(xù)集合S，為每個輸，為每個輸 入入a，計算計算Sa子集子集 ，這將由轉(zhuǎn)換S Sa定義一 個新的狀態(tài) a 繼續(xù)這個過程，直到?jīng)]有新狀態(tài)或轉(zhuǎn)換生成繼續(xù)這個過程，直到?jīng)]有新狀態(tài)或轉(zhuǎn)換生成 將包含將包含M接受狀態(tài)的狀態(tài)標(biāo)記為接受狀態(tài)接受狀態(tài)的狀態(tài)標(biāo)記為接受狀態(tài) 0,

13、1, 7,2,4 5,6,7,1,2,4=T28,3,6,7,1,2,4=T110,5,6,7,1,2,4 10,5,6,7,1,2,48,3,6,7,1,2,4=T19,5,6,7,1,2,4 5,6,7, 1,2,4=T28,3,6,7,1,2,4=T15,6,7,1,2,4 9,5,6,7,1,2,48,3,6,7,1,2,4=T18,3,6,7,1,2,4 5,6,7,1,2,48,3,6,7,1,2,4 IbIaI T0 T1 T2 T3 T4 0 0 0 0 1 01 2 45 3 6789 a b abb 10 4 0 b 2 13 b b a a a b a b a 重新命名重

14、新命名 DFA的狀態(tài)集合的狀態(tài)集合,我們得到我們得到 0,1, 7,2,4 5,6,7,1,2,4=T28,3,6,7,1,2,4=T110,5,6,7,1,2,4 10,5,6,7,1,2,48,3,6,7,1,2,4=T19,5,6,7,1,2,4 5,6,7, 1,2,4=T28,3,6,7,1,2,4=T15,6,7,1,2,4 9,5,6,7,1,2,48,3,6,7,1,2,4=T18,3,6,7,1,2,4 5,6,7,1,2,48,3,6,7,1,2,4 IbIaI T0 T1 T2 T3 T4 0 0 0 0 1 2.4.3 將DFA中的狀態(tài)數(shù)最小化 它們都是正則表達(dá)式a*的

15、DFA , 但是后者是最 小的 理論 對于任何給定的DFA，都有一個含有最少量狀 態(tài)的等價的DFA,而且這個最小狀態(tài)的DFA是 唯一的 a a a 等價狀態(tài) 如果 s 和 t 是兩個狀態(tài)，它們是等價當(dāng)且僅當(dāng): s 和 t 都是接受狀態(tài)或非接受狀態(tài)。 對于任何一個字符 a, s 和 t必須轉(zhuǎn)換到等價 的狀態(tài)里 C和和F同是終態(tài)同是終態(tài), C和和F讀入讀入a都到達(dá)都到達(dá)C,讀入讀入b 都到達(dá)都到達(dá)E,所以所以 C和和F等價等價 S和和C不等價，因為不等價，因為C是終態(tài)，而是終態(tài)，而S不是終不是終 態(tài)態(tài) 例如例如 a C DB AE F Sb a a a a a b b b b b a b 最小化算

16、法分割法 把一個DFA的狀態(tài)分成一些不相交的子集，使得 任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一 子集中的任何兩個狀態(tài)都是等價的. 首先, 分割為兩個狀態(tài)集合，一個包含所有接受 狀態(tài)，一個包含所有非接受狀態(tài)。 考慮每個子集中狀態(tài)針對字母表中每個字符 a 的轉(zhuǎn)換，來決定子集中的所有狀態(tài)是等價的還 是應(yīng)該分割的。 如果一個子集中的兩個狀態(tài)s 和 t 在 a 上有轉(zhuǎn)換 且位于不同的集合，則我們稱 a 區(qū)分了狀態(tài) s 和 t 必須根據(jù)考慮中狀態(tài)集合的 a-轉(zhuǎn)換的位置將它們 分隔開 繼續(xù)這個過程直到每個集合僅包含一個元素 （原始DFA最?。┗蛞恢笔堑皆贈]有集合可以 分隔了 DB A S a a a b b b ba, C DB AE F Sb a a a a a a b b b b b b a 1