編譯原理 第二章詞法分析

1、編譯原理 第二章詞法分析第1頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二這不是一個(gè)DFA。如果不使用系統(tǒng)化的方法將所有的記號(hào)都合并為一個(gè)巨大的DFA，將非常復(fù)雜。13letterletter,digit2other5digitdigit4other76=910 S的子集S0S 初始狀態(tài) A S 接受狀態(tài)集合第4頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二NFA 類(lèi)似于 DFA，除了擴(kuò)展 包括 NFA 可以包含 -轉(zhuǎn)換無(wú)需考慮輸入串就有可能發(fā)生的轉(zhuǎn)換12擴(kuò)展T的定義每一個(gè)字符都可以導(dǎo)致多個(gè)狀態(tài)。因此T的值是狀態(tài)的一個(gè)集合而不是單獨(dú)的狀態(tài)第5頁(yè)，共44頁(yè)，2022年，5

2、月20日，20點(diǎn)31分，星期二例 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矩陣表示:01SPS,ZPZZPP001狀態(tài)圖表示:SPZ00,1111Z第6頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二L(M): 由自動(dòng)機(jī) M 所接受（識(shí)別）的語(yǔ)言L(fǎng)(M) ：is the set of strings of character字符c1c2cn ，每一個(gè)ci 都屬于 ， 且存在關(guān)系：s1 在T(S0,c1)中,s2在T(S1,c2)中,Sn 在T(Sn-1,cn) 中， s0 是初始狀

3、態(tài)， Sn 是A的元素c1c2cn 中的任一 ci 都可能是真正被接受的串是刪除了的串 c1c2cn第7頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二非確定性接受特定串的轉(zhuǎn)換序列并不由狀態(tài)和下一個(gè)輸入字符在每一步確定下來(lái)第8頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二例如1234aab下面兩個(gè)轉(zhuǎn)換序列都可接受串 “abb” :12424abb134242ab4b第9頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二2.3.3 用代碼實(shí)現(xiàn)有窮自動(dòng)機(jī)構(gòu)建掃描程序（詞法分析程序）的過(guò)程:正則表達(dá)式DFA掃描程序正則表達(dá)式表示一種模式，用來(lái)描述記號(hào)DFAs 表示按照正

4、則表達(dá)式描述的模式接受符號(hào)串的算法第10頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二從正則表達(dá)式到DFA（2.4節(jié))有窮自動(dòng)機(jī)構(gòu)造詞法分析程序第11頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二1 用代碼實(shí)現(xiàn) DFA用代碼實(shí)現(xiàn)DFA的一般算法用一個(gè)變量保持當(dāng)前的狀態(tài)將轉(zhuǎn)換寫(xiě)成一個(gè)雙層嵌套的case語(yǔ)句而不是一個(gè)循環(huán)第一個(gè)case語(yǔ)句測(cè)試當(dāng)前的狀態(tài)嵌套著的第2層測(cè)試輸入字符及所給的狀態(tài)第12頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二state:=1;startwhile state=1 or 2 docase state of1:case input c

5、haracter of letter:advance the input; state:=2;else state:=error or other; end case例如:接受標(biāo)識(shí)符的DFA13letterletterdigit2other第13頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二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;13le

6、tterletterdigit2other第14頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二2 用代碼實(shí)現(xiàn)DFA的狀態(tài)轉(zhuǎn)換表使用轉(zhuǎn)換表，可以用代碼實(shí)現(xiàn)任一DFA第15頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二代碼圖解中用到的變量轉(zhuǎn)換被保存在一個(gè)轉(zhuǎn)換數(shù)組 “T”中，T由狀態(tài)和輸入字符索引；先行輸入的轉(zhuǎn)換是由布爾數(shù)組 “Advance”給出, 它們也由狀態(tài)和輸入字符索引；由布爾數(shù)組 “Accept”給出的接受狀態(tài)由狀態(tài)索引第16頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二代碼圖解 state:=1;ch:=next input character;whi

7、le not Acceptstate and not error(state) donewstate:=Tstate,ch;if Advancestate,ch then ch:=next input char;state:=newstate;end while;if Acceptstate then accept;第17頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二表驅(qū)動(dòng)的優(yōu)點(diǎn)代碼的長(zhǎng)度縮短了相同的代碼可以解決許多不同的問(wèn)題代碼較易改變（維護(hù)）缺點(diǎn)表格會(huì)變得非常大，使得程序要求使用的空間也變得非常大第18頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二3 代碼的動(dòng)作進(jìn)行

8、轉(zhuǎn)換時(shí)發(fā)生的典型動(dòng)作是：將字符從輸入串中移到屬于單個(gè)記號(hào)累積字符的字符串中在達(dá)到某個(gè)接受狀態(tài)時(shí)的典型動(dòng)作是：將剛被識(shí)別的記號(hào)及相關(guān)屬性返回遇到出錯(cuò)狀態(tài)的典型動(dòng)作是：在輸入中備份（回溯）或生成錯(cuò)誤記號(hào)第19頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二2.4 從正則表達(dá)式到 DFAs正則表達(dá)式與 DFA的等價(jià)性從正則表達(dá)式到DFA從正則表達(dá)式到 NFA(2.4.1)從 NFA 到 DFA(2.4.2)DFA的最小化(2.4.3)第20頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二2.4.1 從正則表達(dá)式到 NFA “語(yǔ)法制導(dǎo)”法:按正則表達(dá)式的語(yǔ)法結(jié)構(gòu)指引構(gòu)造過(guò)程第21頁(yè)

9、，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二正則表達(dá)式構(gòu)造NFA的基本語(yǔ)法結(jié)構(gòu)的構(gòu)造規(guī)則2對(duì)于正則表達(dá)式 ,構(gòu)造的NFA為:3對(duì)于正則表達(dá)式a, a ，構(gòu)造的NFA為1對(duì)于正則表達(dá)式,構(gòu)造的NFA為: yxyxyxa第22頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二復(fù)合正則表達(dá)式e的構(gòu)造規(guī)則2 然后按下述三種情況進(jìn)行分解，直至每條弧上標(biāo)記一個(gè)字符1 先構(gòu)造如下的正則表達(dá)式 “e” 的NFA:e1Xye=e1|e2e2X1e1ye2e=e1e2X1ye1e=e1*yxe第23頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二例如: 將正則表達(dá)式 (a|b)*ab

10、b 翻譯成NFAX(a|b)*abbYX (a|b)* 1a 2bb 3 YX 4 1 b 3 a 2 b a|b YX 4 1 b 3 a 2 b a b Y第24頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二2.4.2 從 NFA 到 DFA1 轉(zhuǎn)換需解決的問(wèn)題刪除-轉(zhuǎn)換（合并）如果 ,則刪除S2S1S2ijkmaban（a）i,jmkaabn（b）第25頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二狀態(tài)合并（消除在單個(gè)字符上的多重轉(zhuǎn)換）0123aabc（a）01,23abc（b）第26頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二2 轉(zhuǎn)換方法子集法讓D

11、FA 的每個(gè)狀態(tài)對(duì)應(yīng)NFA 的一個(gè)狀態(tài)集合。即DFA用它的一個(gè)狀態(tài)記錄在NFA讀入一個(gè)輸入符號(hào)后可能達(dá)到的所有狀態(tài)。第27頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二3 對(duì)狀態(tài)集合I的有關(guān)運(yùn)算狀態(tài)集合 I 的閉包_closure( I )是狀態(tài)集I中的任何狀態(tài)S以及經(jīng)任意條弧而能到達(dá)的狀態(tài)的集合。IIS2S2S1S1S3S3_ Close(I)第28頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二以下將_closure( I ) 簡(jiǎn)寫(xiě)為closure(I)Closure(I) =I Sk | if Sj Sk, Sj Closure(I) ， Sk Closure(I)

12、 狀態(tài)集合的空閉包_closure 總是包含狀態(tài)集合本身第29頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二if I=0,the _closure( I )=例如:NFA 100124536789ababb74,2,1,0,第30頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二Ia子集I 是狀態(tài)集合, a 是字母表的一個(gè)字符Move（I，a）=t|sI,and s tIa= _closure ( Move( I , a ) )a第31頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二Ib = _closure( 例如:NFA 100124536789ababbif

13、 I=0,1,2,4,7 thenIa = _closure( )3,8= 3, 8,6,7,1,2,4 5 6, ) = 5, 7, 2,1, 4第32頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二4 由NFA M 構(gòu)造DFA M 的算法將M的初始狀態(tài)的空閉包作為 M的初始狀態(tài)為這個(gè)集合，以及此后的每個(gè)后續(xù)集合S，為每個(gè)輸入a，計(jì)算Sa子集 ，這將由轉(zhuǎn)換S Sa定義一個(gè)新的狀態(tài)a繼續(xù)這個(gè)過(guò)程，直到?jīng)]有新?tīng)顟B(tài)或轉(zhuǎn)換生成將包含M接受狀態(tài)的狀態(tài)標(biāo)記為接受狀態(tài)第33頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二0,1, 7,2,45,6,7,1,2,4=T28,3,6,7,1

14、,2,4=T110,5,6,7,1,2,410,5,6,7,1,2,48,3,6,7,1,2,4=T19,5,6,7,1,2,45,6,7, 1,2,4=T28,3,6,7,1,2,4=T15,6,7,1,2,49,5,6,7,1,2,48,3,6,7,1,2,4=T18,3,6,7,1,2,45,6,7,1,2,48,3,6,7,1,2,4IbIaIT0T1T2T3T4000010124536789ababb10第34頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二40b213bbaaababa重新命名 DFA的狀態(tài)集合,我們得到0,1, 7,2,45,6,7,1,2,4=T28,

15、3,6,7,1,2,4=T110,5,6,7,1,2,410,5,6,7,1,2,48,3,6,7,1,2,4=T19,5,6,7,1,2,45,6,7, 1,2,4=T28,3,6,7,1,2,4=T15,6,7,1,2,49,5,6,7,1,2,48,3,6,7,1,2,4=T18,3,6,7,1,2,45,6,7,1,2,48,3,6,7,1,2,4IbIaIT0T1T2T3T400001第35頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二2.4.3 將DFA中的狀態(tài)數(shù)最小化它們都是正則表達(dá)式a*的DFA , 但是后者是最小的理論對(duì)于任何給定的DFA，都有一個(gè)含有最少量狀態(tài)的

16、等價(jià)的DFA,而且這個(gè)最小狀態(tài)的DFA是唯一的aaa第36頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二等價(jià)狀態(tài)如果 s 和 t 是兩個(gè)狀態(tài)，它們是等價(jià)當(dāng)且僅當(dāng):s 和 t 都是接受狀態(tài)或非接受狀態(tài)。對(duì)于任何一個(gè)字符 a, s 和 t必須轉(zhuǎn)換到等價(jià)的狀態(tài)里第37頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二C和F同是終態(tài), C和F讀入a都到達(dá)C,讀入b都到達(dá)E,所以 C和F等價(jià)S和C不等價(jià)，因?yàn)镃是終態(tài)，而S不是終態(tài)例如aCDBAEFSbaaaaabbbbbab第38頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二最小化算法分割法 把一個(gè)DFA的狀態(tài)分成一些不

17、相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個(gè)狀態(tài)都是等價(jià)的.第39頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二首先, 分割為兩個(gè)狀態(tài)集合，一個(gè)包含所有接受狀態(tài)，一個(gè)包含所有非接受狀態(tài)?？紤]每個(gè)子集中狀態(tài)針對(duì)字母表中每個(gè)字符 a 的轉(zhuǎn)換，來(lái)決定子集中的所有狀態(tài)是等價(jià)的還是應(yīng)該分割的。如果一個(gè)子集中的兩個(gè)狀態(tài)s 和 t 在 a 上有轉(zhuǎn)換且位于不同的集合，則我們稱(chēng) a 區(qū)分了狀態(tài) s 和 t 第40頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二必須根據(jù)考慮中狀態(tài)集合的 a-轉(zhuǎn)換的位置將它們分隔開(kāi)繼續(xù)這個(gè)過(guò)程直到每個(gè)集合僅包含一個(gè)元素（原始DFA最?。┗蛞恢笔堑皆?zèng)]有集合可以分隔了第41頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二DBASaaabbbba,CDBAEFSbaaaaaabbbbbba1.將狀態(tài)分為接受狀態(tài)和非接受狀態(tài)S,A,B C,D,E,F2 繼續(xù)分割（尋找子集中不等價(jià)狀態(tài)）S,A,B=S,BA=SABC,D,E,F3 讓 D 表示 C,D,E,F P=S,A,B,D第42頁(yè)，共44頁(yè)，2022年，5月20日，20點(diǎn)31分，星期二