編譯程序原理與實現(xiàn)：第2章 詞法分析確定有限自動機(jī)

1、第2章 outline一、詞法分析概述1，詞法分析程序的功能2，詞法分析相關(guān)的一些問題二、正則表達(dá)式三、有限自動機(jī)1，確定有限自動機(jī)DFA2，非確定有限自動機(jī)NFA，NFA到DFA的轉(zhuǎn)換3，DFA的化簡4，正則表達(dá)式到NFA的轉(zhuǎn)換四、詞法分析程序構(gòu)造三、有限自動機(jī)正則表達(dá)式 - specification有限自動機(jī) Implementation什么是有限自動機(jī)？有限自動機(jī)是描述有限狀態(tài)系統(tǒng)的數(shù)學(xué)模型。有限狀態(tài)系統(tǒng)：狀態(tài)：是將事物區(qū)分開的一種標(biāo)識.具有離散狀態(tài)的系統(tǒng)：如數(shù)字電路(0,1);電燈開關(guān)(on,off);十字路口的紅綠燈；其狀態(tài)數(shù)是有限的。具有連續(xù)狀態(tài)的系統(tǒng)：水庫的水位、室內(nèi)的溫度等可

2、以連續(xù)發(fā)生變化；可以有無窮個狀態(tài).有限狀態(tài)系統(tǒng)是離散狀態(tài)系統(tǒng)。在很多領(lǐng)域，如網(wǎng)絡(luò)協(xié)議分析、形式驗證、代碼安全、排版系統(tǒng)等有重要應(yīng)用。有限自動機(jī)的例子-經(jīng)典的過河問題一個人帶著一頭狼，一頭羊，以及一棵白菜處于河的左岸。人和他的伴隨品都希望渡到河的右岸。有一條小船，每擺渡一次，只能攜帶人和其余三者之一。如果單獨(dú)留下狼和羊，狼會吃羊；如果單獨(dú)留下羊和白菜，羊會吃菜。怎樣才能渡河，而羊和白菜不會被吃掉呢？ 過河問題模型化有限自動機(jī)的模型有限自動機(jī)FA可以理解成狀態(tài)控制器FA有有限個狀態(tài)，其中有初始狀態(tài)，終止?fàn)顟B(tài)起始：處于初始狀態(tài)，讀頭位于輸入帶開頭中間：從左到右依次讀取字符，發(fā)生狀態(tài)遷移結(jié)束：讀頭到達(dá)

3、輸入帶末尾，狀態(tài)到達(dá)終態(tài)10110狀態(tài)控制器讀頭輸入帶輸出有限自動機(jī)的五要素有限狀態(tài)集 SS有限輸入符號集 轉(zhuǎn)移函數(shù) (s,a) = t 一個開始狀態(tài)s0一個終止?fàn)顟B(tài)集 TS輸入：字符串輸出：若輸入字符串結(jié)束，且到達(dá)終止?fàn)顟B(tài)，則接受，否則拒絕。例如： “101” 輸出拒絕，“1010”輸出接受。1、確定有限自動機(jī)DFA確定有限自動機(jī)DFA是一個五元組 M =(SS,S0,TS)，SS ：有限的狀態(tài)集合 S0，S1，S2， ：有限的輸入字符表 ：狀態(tài)轉(zhuǎn)換函數(shù)，SS SS 是單值全映射函數(shù)；S0 ：初始狀態(tài)， S0 SSTS ：終止?fàn)顟B(tài)集，TSSS 例1：DFA M=(0,1,2,3,4,a,b,

4、0,3)其中為： ( 0, a ) = 1 ( 0, b ) = 4 ( 1, a ) = 4 ( 1, b ) = 2 ( 2, a ) = 3 ( 2, b ) = 4 ( 3, a ) = 3 ( 3, b ) = 3 ( 4, a ) = 4 ( 4, b ) = 4DFA的兩種表示形式轉(zhuǎn)換表(transition table)易于實現(xiàn)轉(zhuǎn)換圖(transition graph)直觀，易于理解轉(zhuǎn)換表行：狀態(tài)列：字符元素：表示狀態(tài)轉(zhuǎn)換，狀態(tài)或開始狀態(tài)：默認(rèn)表的第一行表示開始狀態(tài),或者狀態(tài)加上角標(biāo)+終止?fàn)顟B(tài)：狀態(tài)加上角標(biāo)-ab0+141423-33轉(zhuǎn)換表例1：DFA M=(0,1,2,3,4

5、,a,b, ,0,3)其中為： ( 0, a ) = 1 ( 0, b ) = 4 ( 1, a ) = 4 ( 1, b ) = 2 ( 2, a ) = 3 ( 2, b ) = 4 ( 3, a ) = 3 ( 3, b ) = 3 ( 4, a ) = 4 ( 4, b ) = 4ab0+141422343-33444轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換邊 f(S1,a) = S2開始狀態(tài)終止?fàn)顟B(tài)S0SS aS1S2轉(zhuǎn)換圖ab0+141422343-334440213abababba4ab轉(zhuǎn)換圖ab0+112233-330213aabbaab0+112233-33DFA的例子例2：: a, b, c, d

6、SS: S0, S1, S2, S3開始狀態(tài): S0 終止?fàn)顟B(tài)集: S3f: (S0,a) S1, (S0,c)S2, (S0,d)S3, (S1,b)S1, (S1,d)S2, (S2,a)S3, (S3, c)S3S0aS1S2S3cddabcDFA的確定性形式定義初始狀態(tài)唯一：S0轉(zhuǎn)換函數(shù)是單值函數(shù)，即對任一狀態(tài)和輸入符號，唯一地確定了下一個狀態(tài)轉(zhuǎn)換表初始狀態(tài)唯一：第一行表元素唯一轉(zhuǎn)換圖初始狀態(tài)唯一:每個狀態(tài)最多發(fā)出n條邊，n是字母表中字母的個數(shù)，且發(fā)出的任意兩條邊上標(biāo)的字母都不同DFA的一些概念DFA接受的字符串如果M是一個DFA, a1 a2 an 是一個字符串，如果存在一個狀態(tài)序列

7、 (S0, S1 , ,Sn),滿足 S0 S1 , S1 S2 , , Sn-1 Sn其中 S0 是開始狀態(tài)，Sn 是接受狀態(tài)之一，則串a(chǎn)1 a2 an 被DFA M接受.DFA定義的串的集合(DFA接受的語言)DFA M接受的所有串的集合，稱為M定義的語言，記為 L(M)a1a2anDFA接受的語言例1中自動機(jī)接受的語言是L(aba(a|b)*)例2中自動機(jī)接受的語言是L(ab*da | ca | d)c*) 0213aabbaS0aS1S2S3cddabcDFA接受的語言若DFA M只有一個狀態(tài)，既是開始狀態(tài)又是終止?fàn)顟B(tài)，則DFA M定義的串集是L() = 若若DFA M只有一個狀態(tài)，并

8、且是開始狀態(tài)或DFA M有若干個狀態(tài)，但開始狀態(tài)到終止?fàn)顟B(tài)之間沒有通路，則DFA M定義的串集是空集SS0或S0SSS設(shè)計有限自動機(jī)自動機(jī)的設(shè)計是一個創(chuàng)造過程，沒有固定的算法和過程例1： = a,b,構(gòu)造自動機(jī)識別由所有奇數(shù)個a和奇數(shù)個b組成的字符串。S奇a,奇bS奇a,偶bS偶a,奇bS偶a,偶bbbbaabaa關(guān)鍵：不需要記住所看到的整個字符串，只需記住至此所看到的a和b的個數(shù)是奇數(shù)還是偶數(shù)設(shè)計有限自動機(jī)例2：設(shè)計有限自動機(jī)M，識別0,1上的語言 L = x000y| x,y0|1* 分析：該語言的特點是每個串都包含連續(xù)3個0的子串。 自動機(jī)的任務(wù)就是識別/檢查 000 的子串。q0q1q

9、2q300011101設(shè)計有限自動機(jī)例3：設(shè)計有限自動機(jī)M，識別0,1,2上的語言，每個字符串代表的數(shù)字能整除3。 分析: (1) 一個十進(jìn)制數(shù)除以3，余數(shù)只能是0,1,2； (2) 被3整除的十進(jìn)制數(shù)的特點：十進(jìn)制數(shù)的所有位數(shù)字的和能整除3。q0q1q2110210022DFA與程序設(shè)計語言的單詞結(jié)構(gòu)例4：使用DFA定義程序設(shè)計語言的無符號實數(shù) 0.12, 34.15 接受 00.12, 00., ., 33. 拒絕S0S30,1, , 90,1,2,9S10S2. 1,2,9S4.0,1, , 9DFA與程序設(shè)計語言的單詞結(jié)構(gòu)例5：使用DFA定義程序設(shè)計語言的標(biāo)識符x, Xy, x123,

10、 xYz 接受23x, 12_x， _x 拒絕q0q1letterletterdigitDFA與程序設(shè)計語言的單詞結(jié)構(gòu)例6：使用DFA定義程序設(shè)計語言的保留字if, else, while, forifseelilhewrofDFA的實現(xiàn)目的給定一個DFA M定義了一個串集編寫一個程序，檢查給定的串是否被DFA M所識別或接受兩種途徑基于轉(zhuǎn)換表基于轉(zhuǎn)換圖基于轉(zhuǎn)換表的DFA實現(xiàn)主要思想輸入 : 一個字符串,以#結(jié)尾.輸出 : 如果接受則輸出true 否則輸出 false數(shù)據(jù)結(jié)構(gòu)：轉(zhuǎn)換表 (二維數(shù)組 T)兩個變量State: 記錄當(dāng)前狀態(tài);CurrentChar: 記錄串中當(dāng)前正在被讀的字符;基于

11、轉(zhuǎn)換表的DFA實現(xiàn)算法主要思想1. State = InitState; 2. Read(CurrentChar); 3. while T(State, CurrentChar) error & CurrentChar # do begin State = T(State, CurrentChar); Read(CurrentChar); end; 4. if CurrentChar = # & State FinalStates， return true; otherwise, return false.S0 (c) S2 (a) S3 (b) S0 (a) S1 (b) S1 (d) S2

12、 (a) S3 (c) S3 (c) S3abcdS0+S1S2S3S1S1S2S2S3S3- S31) cab 接受 or 拒絕？2）abdacc 接受 or 拒絕？拒絕接受基于轉(zhuǎn)換圖的DFA實現(xiàn)每個狀態(tài)對應(yīng)一個帶標(biāo)號的case 語句每條邊對應(yīng)一個 goto 語句對于每個終止?fàn)顟B(tài)，增加一個分支，如果當(dāng)前字符是字符串的結(jié)束符#，則接受;ibjkaLi: case CurrentChar of a ：goto Lj b : goto Lk other : Error( )基于轉(zhuǎn)換圖的DFA實現(xiàn)每個狀態(tài)對應(yīng)一個帶標(biāo)號的case 語句每條邊對應(yīng)一個 goto 語句對于每個終止?fàn)顟B(tài)，增加一個分支，如果

13、當(dāng)前字符是字符串的結(jié)束符#，則接受;bjkaiLi: case CurrentChar of a ：goto Lj b : goto Lk # : return true; other : return false;S0aS1S2S3cddabcLS0: Read(CurrentChar); switch (CurrentChar) case a : goto LS1; case c : goto LS2: case d : goto LS3; other : return false; LS1: Read(CurrentChar); switch (CurrentChar) case b : goto LS1; case d : goto LS2: other : return false; S0aS1S2S3cddabcLS2: Read(CurrentChar); switch (CurrentChar) case a : goto LS3; other : return false; LS3: Read(CurrentChar); switch (CurrentChar) case c : goto LS3: case # : return true; other : r