編譯原理 第二章詞法分析-2.ppt

1、2.3.2 NFA的定義,NFA的必要 識(shí)別程序設(shè)計(jì)語(yǔ)言中所有記號(hào)的DFA遇到的問(wèn)題 典型的程序設(shè)計(jì)語(yǔ)言中都有許多記號(hào)，每一個(gè)記號(hào)都能被其自己的DFA識(shí)別出來(lái) 理論上應(yīng)該能將所有的記號(hào)都合并為一個(gè)巨大的DFA。,這不是一個(gè)DFA。如果不使用系統(tǒng)化的方法將所有的記號(hào)都合并為一個(gè)巨大的DFA，將非常復(fù)雜。,解決這個(gè)問(wèn)題的方法 將DFA擴(kuò)展到NFA (對(duì)于當(dāng)前的輸入，當(dāng)前的狀態(tài)將轉(zhuǎn)換為多個(gè)狀態(tài)) NFA 轉(zhuǎn)換為 DFA的算法,不確定的有窮自動(dòng)機(jī)（NFA) NFA M=(S,T,S0,A), 其中 S 是狀態(tài)的集合 是字母表 T是轉(zhuǎn)換函數(shù): S X ()- S的子集 S0S 初始狀態(tài) A S 接受狀態(tài)

2、集合,NFA 類似于 DFA，除了 擴(kuò)展 包括 NFA 可以包含 -轉(zhuǎn)換無(wú)需考慮輸入串就有可能發(fā)生的轉(zhuǎn)換,擴(kuò)展T的定義 每一個(gè)字符都可以導(dǎo)致多個(gè)狀態(tài)。因此T的值是狀態(tài)的一個(gè)集合而不是單獨(dú)的狀態(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,矩陣表示:,狀態(tài)圖表示:,L(M): 由自動(dòng)機(jī) M 所接受（識(shí)別）的語(yǔ)言 L(M) ：is the set of strings of character字符c1c2cn ，每一個(gè)ci 都屬于 ， 且存在關(guān)系：s1 在T(S0,c1)中,s2在T(S1,

3、c2)中,Sn 在T(Sn-1,cn) 中， s0 是初始狀態(tài)， Sn 是A的元素 c1c2cn 中的任一 ci 都可能是 真正被接受的串是刪除了的串 c1c2cn,非確定性 接受特定串的轉(zhuǎn)換序列并不由狀態(tài)和下一個(gè)輸入字符在每一步確定下來(lái),例如,下面兩個(gè)轉(zhuǎn)換序列都可接受串 “abb” :,2.3.3 用代碼實(shí)現(xiàn)有窮自動(dòng)機(jī),構(gòu)建掃描程序（詞法分析程序）的過(guò)程:,正則表達(dá)式表示一種模式，用來(lái)描述記號(hào) DFAs 表示按照正則表達(dá)式描述的模式接受符號(hào)串的算法,從正則表達(dá)式到DFA（2.4節(jié)) 有窮自動(dòng)機(jī)構(gòu)造詞法分析程序,1 用代碼實(shí)現(xiàn) DFA,用代碼實(shí)現(xiàn)DFA的一般算法 用一個(gè)變量保持當(dāng)前的狀態(tài) 將轉(zhuǎn)

4、換寫成一個(gè)雙層嵌套的case語(yǔ)句而不是一個(gè)循環(huán) 第一個(gè)case語(yǔ)句測(cè)試當(dāng)前的狀態(tài) 嵌套著的第2層測(cè)試輸入字符及所給的狀態(tài),state:=1;start while state=1 or 2 do case state of 1:case input character of letter:advance the input; state:=2; else state:=error or other; end case,例如:接受標(biāo)識(shí)符的DFA,2:case input character of letter,digit:advance the input; state:=2; else sta

5、te:=3; end case; end case; end while; if state=3 then accept else error;,2 用代碼實(shí)現(xiàn)DFA的狀態(tài)轉(zhuǎn)換表,使用轉(zhuǎn)換表，可以用代碼實(shí)現(xiàn)任一DFA,代碼圖解中用到的變量 轉(zhuǎn)換被保存在一個(gè)轉(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(sta

6、te) do newstate:=Tstate,ch; if Advancestate,ch then ch:=next input char; state:=newstate; end while; if Acceptstate then accept;,表驅(qū)動(dòng)的優(yōu)點(diǎn) 代碼的長(zhǎng)度縮短了 相同的代碼可以解決許多不同的問(wèn)題 代碼較易改變（維護(hù)） 缺點(diǎn) 表格會(huì)變得非常大，使得程序要求使用的空間也變得非常大,3 代碼的動(dòng)作,進(jìn)行轉(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)作是：在輸入

7、中備份（回溯）或生成錯(cuò)誤記號(hào),2.4 從正則表達(dá)式到 DFAs,正則表達(dá)式與 DFA的等價(jià)性 從正則表達(dá)式到DFA 從正則表達(dá)式到 NFA(2.4.1) 從 NFA 到 DFA(2.4.2) DFA的最小化(2.4.3),2.4.1 從正則表達(dá)式到 NFA,“語(yǔ)法制導(dǎo)”法: 按正則表達(dá)式的語(yǔ)法結(jié)構(gòu)指引構(gòu)造過(guò)程,正則表達(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為:,x,復(fù)合正則表達(dá)式e的構(gòu)造規(guī)則,2 然后按下述三種情況進(jìn)行分解，直至每條弧上標(biāo)記一個(gè)字符,1 先構(gòu)造如下的正則表達(dá)式 “e”

8、 的NFA:,例如: 將正則表達(dá)式 (a|b)*abb 翻譯成NFA,2.4.2 從 NFA 到 DFA,1 轉(zhuǎn)換需解決的問(wèn)題 刪除-轉(zhuǎn)換（合并） 如果 ,則刪除S2,狀態(tài)合并（消除在單個(gè)字符上的多重轉(zhuǎn)換）,2 轉(zhuǎn)換方法子集法,讓DFA 的每個(gè)狀態(tài)對(duì)應(yīng)NFA 的一個(gè)狀態(tài)集合。 即DFA用它的一個(gè)狀態(tài)記錄在NFA讀入一個(gè)輸入符號(hào)后可能達(dá)到的所有狀態(tài)。,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)的集合。,以下將_closure( I ) 簡(jiǎn)寫為closure(I) Closure(I) =I Sk | if Sj

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

10、= _closure( , ),= ,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ù)這個(gè)過(guò)程，直到?jīng)]有新狀態(tài)或轉(zhuǎn)換生成,將包含M接受狀態(tài)的狀態(tài)標(biāo)記為接受狀態(tài),0,1, 7,2,4,10,5,6,7,1,2,4,9,5,6,7,1,2,4,5,6,7,1,2,4,8,3,6,7,1,2,4,Ib,Ia,I,T0,T1,T2,T3,T4,重新命名 DFA的狀態(tài)集合,我們得到,2.4.3 將DFA中的狀態(tài)數(shù)最小化,它們都是正則表達(dá)式a*的DFA , 但是后者是最小的 理論 對(duì)于任何給定的D

11、FA，都有一個(gè)含有最少量狀態(tài)的等價(jià)的DFA,而且這個(gè)最小狀態(tài)的DFA是唯一的,等價(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)里,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),例如,最小化算法分割法 把一個(gè)DFA的狀態(tài)分成一些不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個(gè)狀態(tài)都是等價(jià)的.,首先, 分割為兩個(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)換且位于不同的集合，則我們稱 a 區(qū)分了狀態(tài) s 和 t,必須根據(jù)考慮中狀態(tài)集合的 a-轉(zhuǎn)換的位置將它們分隔開 繼續(xù)這個(gè)過(guò)程直到每個(gè)集合僅包含一個(gè)元素（原始DFA最?。┗蛞恢笔堑皆?zèng)]有集合可以分隔了,a,1.將狀態(tài)分為接受狀態(tài)和非接受狀態(tài) S,A,B C,D,E,F 2 繼續(xù)分割（尋找子集中不等價(jià)狀態(tài)） S,A,B=S,BA=SAB C,D,E,F 3 讓 D 表示 C,D,E,F,P=S,A,B,D,考慮非接受的錯(cuò)誤狀態(tài)的錯(cuò)誤轉(zhuǎn)換 有兩個(gè)狀