第04章、詞法分析

第4章詞法分析S.PO.P表格管理程序錯(cuò)誤處理程序

本章將討論詞法分析程序的設(shè)計(jì)原則，單詞的描述技術(shù)，識(shí)別機(jī)制及詞法分析程序的自動(dòng)構(gòu)造原理。4.1詞法分析程序4.2正規(guī)表達(dá)式與正規(guī)集（正規(guī)語言）4.3有限自動(dòng)機(jī)4.4正規(guī)文法和有限自動(dòng)機(jī)的轉(zhuǎn)換4.5正規(guī)式和有限自動(dòng)機(jī)的等價(jià)性2本章重點(diǎn)單詞的描述工具單詞的識(shí)別系統(tǒng)設(shè)計(jì)和實(shí)現(xiàn)詞法分析程序首先需要描述和刻畫程序設(shè)計(jì)語言中的原子單位——單詞，其次需要識(shí)別單詞和執(zhí)行某些相關(guān)的動(dòng)作。描述程序設(shè)計(jì)語言的詞法的機(jī)制是正規(guī)表達(dá)式，識(shí)別機(jī)制是有窮狀態(tài)自動(dòng)機(jī)。34.1詞法分析程序?qū)崿F(xiàn)詞法分析（lexicalanalysis）的程序逐個(gè)讀入源程序字符并按照構(gòu)詞規(guī)則切分成一系列單詞。單詞是語言中具有獨(dú)立意義的最小單位，包括關(guān)鍵字(保留字)、標(biāo)識(shí)符、常數(shù)、運(yùn)算符、界符等。詞法分析是編譯過程中的一個(gè)階段，在語法分析前進(jìn)行，也可以和語法分析結(jié)合在一起作為一遍，由語法分析程序調(diào)用詞法分析程序來獲得當(dāng)前單詞供語法分析使用。4詞法分析的任務(wù)：主要任務(wù)：讀源程序，產(chǎn)生單詞符號(hào)其他任務(wù)：濾掉空格，跳過注釋、換行符刪除注釋進(jìn)行詞法檢查，報(bào)告所發(fā)現(xiàn)的錯(cuò)誤建立符號(hào)表5單詞的分類（1）關(guān)鍵字：或稱為保留字，是特定的字母序列，在相應(yīng)的程序設(shè)計(jì)語言中表示特殊含義。（2）標(biāo)識(shí)符：由用戶定義的串，在程序中常用做常量名、變量名、過程名等。（3）常數(shù)：各種類型的常數(shù)，包括整型、實(shí)型、布爾型、文字型等，如100，10.12，TRUE，“ABC”等。（4）運(yùn)算符：包括算術(shù)運(yùn)算符和邏輯運(yùn)算符號(hào)，如+、*、<等。（5）界符：如逗號(hào)、分號(hào)等。6詞法分析程序的輸出詞法分析程序所輸出的單詞符號(hào)，常采用以下二元式表示：

（單詞種類，單詞自身值）其中，單詞種類是語法分析所需要的信息，而單詞自身值則是編譯的其他階段需要的信息。單詞種類，可以用整數(shù)編碼表示，例如：1-標(biāo)識(shí)符，2-常數(shù)，3-關(guān)鍵字，4-運(yùn)算符，5-界符語句例：if(a>0)b=b+1;

(1)關(guān)鍵字if(3,’if’)(2)左括號(hào)((4,’(’)(3)標(biāo)識(shí)符a(1,指向a的符號(hào)表入口)(4)運(yùn)算符>(4,’>’)(5)常數(shù)0(2,’0’)……(12)界符;(5,’;’)7不同分類方法的例子：

下述C++代碼段：while(i>=j)i--;經(jīng)詞法分析器處理以后，它將被轉(zhuǎn)換為如下的單詞符號(hào)串。(while,_)((,_)(id,指向i的符號(hào)表指針)(>=,_)(id,指向j的符號(hào)表指針)(),_)(id,指向i的符號(hào)表指針)(--,_)(;,_)8詞法分析程序的實(shí)現(xiàn)方式詞法分析單獨(dú)作為一遍優(yōu)點(diǎn)：結(jié)構(gòu)簡(jiǎn)單、各遍功能單一缺點(diǎn)：效率低9源程序詞法分析程序語法分析程序Tokengettoken….詞法分析程序作為單獨(dú)的子程序優(yōu)點(diǎn)：無須在外存中保留整個(gè)源程序的內(nèi)碼形式。10將詞法分析工作分離的原因簡(jiǎn)化設(shè)計(jì)改進(jìn)編譯效率增加編譯系統(tǒng)的可移植性114.2正規(guī)表達(dá)式與正規(guī)集（正規(guī)語言）程序設(shè)計(jì)語言中的單詞是基本語法成分,單詞符號(hào)的語法可以用有效的工具加以描述，并且基于這類描述工具，實(shí)現(xiàn)詞法分析程序的自動(dòng)構(gòu)造。12正規(guī)式正規(guī)式也稱正則表達(dá)式，正規(guī)表達(dá)式（regularexpression），是說明單詞的模式(pattern)的一種重要的表示法（記號(hào)），是定義正規(guī)集的數(shù)學(xué)工具。我們用以描述單詞符號(hào)。下面是正規(guī)式和它所表示的正規(guī)集的遞歸定義。13定義（正規(guī)式和它所表示的正規(guī)集）：設(shè)字母表為，輔助字母表’={，，，，，，}。1.和都是上的正規(guī)式，它們所表示的正規(guī)集分別為{}和{}；2.任何a，a是上的一個(gè)正規(guī)式，它所表示的正規(guī)集為{a}；143.假定e1和e2都是上的正規(guī)式，它們所表示的正規(guī)集分別為L(zhǎng)(e1)和L(e2)，那么，(e1),e1e2,e1e2,e1也都是正規(guī)式，它們所表示的正規(guī)集分別為L(zhǎng)(e1),L(e1)L(e2),L(e1)L(e2)和(L(e1))。4.僅由有限次使用上述三步驟而定義的表達(dá)式才是上的正規(guī)式，僅由這些正規(guī)式所表示的集合才是上的正規(guī)集。15

正規(guī)式中的符號(hào)

其中的“”讀為“或”（也有使用“+”代替“”的）；“

”讀為“連接”；“”讀為“閉包”（即，任意有限次的自重復(fù)連接）。在不致混淆時(shí)，括號(hào)可省去，但規(guī)定算符的優(yōu)先順序?yàn)椤啊?、“”、“”。連接符“”一般可省略不寫?！啊?、“”和“”都是左結(jié)合的。16例令={a，b}，上的正規(guī)式和相應(yīng)的正規(guī)集的例子有：正規(guī)式 正規(guī)集a {a}ab {a,b}ab {ab}(ab)(ab) {aa,ab,ba,bb}a {,a,a,……任意個(gè)a的串}17

正規(guī)式 正規(guī)集

(ab) {,a,b,aa,ab……所有由a 和b組成的串}(ab)(aabb)(ab){上所有含有兩個(gè)相繼 的a或兩個(gè)相繼的b組成的串}18

討論下面兩個(gè)例子例4.1令={l，d}，則上的正規(guī)式r=l(ld)定義的正規(guī)集為:{l,ll,ld,ldd,……},其中l(wèi)代表字母,d代表數(shù)字,正規(guī)式即是字母(字母|數(shù)字)

,它表示的正規(guī)集中的每個(gè)元素的模式是“字母打頭的字母數(shù)字串”,就是Pascal和多數(shù)程序設(shè)計(jì)語言允許的的標(biāo)識(shí)符的詞法規(guī)則.例4.2={d，，e，+，-},則上的正規(guī)式d(dd)(e(+-)dd)表示的是無符號(hào)數(shù)的集合，其中d為09的數(shù)字。比如2、21.59、3.6e2、471.88e-1等都是該正規(guī)集中的元素。

程序設(shè)計(jì)語言的單詞都能用正規(guī)式來定義19正規(guī)式的等價(jià)若兩個(gè)正規(guī)式e1和e2所表示的正規(guī)集相同,則說e1和e2等價(jià),寫作e1=e2。例如：e1=(ab)，e2=ba又如：e1=b(ab),e2=(ba)b

e1=(ab),e2

=(ab)20正規(guī)式服從的代數(shù)規(guī)律設(shè)r,s,t為正規(guī)式，正規(guī)式服從的代數(shù)規(guī)律有：1.rs=sr “或”服從交換律2.r(st)=(rs)t “或”的可結(jié)合律3.(rs)t=r(st) “連接”的可結(jié)合律4.r(st)=rsrt (st)r=srtr 分配律5.r=r,r=r 是“連接”的恒等元素 零一律6.rr=r r=rrr… “或”的抽取律

214.3有限自動(dòng)機(jī)

有限自動(dòng)機(jī)(也稱有窮自動(dòng)機(jī))作為一種識(shí)別裝置，它能準(zhǔn)確地識(shí)別正規(guī)集，即識(shí)別正規(guī)文法所定義的語言和正規(guī)式所表示的集合，引入有限自動(dòng)機(jī)這個(gè)理論，正是為詞法分析程序的自動(dòng)構(gòu)造尋找特殊的方法和工具。

有限自動(dòng)機(jī)分為兩類：確定的有限自動(dòng)機(jī)(DeterministicFiniteAutomata)不確定的有限自動(dòng)機(jī)(NondeterministicFiniteAutomata)22關(guān)于有限自動(dòng)機(jī)我們將討論如下題目確定的有限自動(dòng)機(jī)DFA不確定的有限自動(dòng)機(jī)NFANFA的確定化DFA的最小化23確定的有限自動(dòng)機(jī)DFADFA定義：一個(gè)確定的有限自動(dòng)機(jī)（DFA）M是一個(gè)五元組：M=（K，Σ，f，S，Z）其中1.K是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)；2.Σ是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào)，所以也稱Σ為輸入符號(hào)表；24DFA定義(續(xù)）3.f是轉(zhuǎn)換函數(shù)，是在K×Σ→K上的映射，即，如f（ki，a）=kj，（ki∈K，kj∈K）就意味著，當(dāng)前狀態(tài)為ki，輸入符為a時(shí)，將轉(zhuǎn)換為下一個(gè)狀態(tài)kj，我們把kj稱作ki的一個(gè)后繼狀態(tài)；4.S∈K是唯一的一個(gè)初態(tài)；5.ZK是一個(gè)終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。25一個(gè)DFA的例子：DFAM=（{S，U，V，Q}，{a，b}，f，S，{Q}）其中f定義為：f（S，a）=U f（V，a）=Uf（S，b）=V f（V，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=Q26DFA可以表示成一個(gè)狀態(tài)圖一個(gè)DFA可以表示成一個(gè)狀態(tài)圖(或稱狀態(tài)轉(zhuǎn)換圖)。假定DFAM含有m個(gè)狀態(tài)，n個(gè)輸入字符，那么這個(gè)狀態(tài)圖含有m個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)最多有n個(gè)弧射出，整個(gè)圖含有唯一一個(gè)初態(tài)結(jié)點(diǎn)和若干個(gè)終態(tài)結(jié)點(diǎn)，初態(tài)結(jié)點(diǎn)冠以雙箭頭“=>”或標(biāo)以“-”，終態(tài)結(jié)點(diǎn)用雙圈表示或標(biāo)以“+”，若f(ki,a)=kj，則從狀態(tài)結(jié)點(diǎn)ki到狀態(tài)結(jié)點(diǎn)kj畫標(biāo)記為a的??；27

DFA的狀態(tài)圖表示bSUVQaaaba，bb28DFA還可以用一個(gè)矩陣表示一個(gè)DFA還可以用一個(gè)矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示相應(yīng)狀態(tài)行和輸入字符列下的新狀態(tài)，即k行a列為f(k,a)的值。用雙箭頭“=>”標(biāo)明初態(tài)；否則第一行即是初態(tài)，相應(yīng)終態(tài)行在表的右端標(biāo)以1，非終態(tài)標(biāo)以0。29DFA的矩陣表示字符狀態(tài)0001以后我們用*表示終態(tài)書上：用0表示非終態(tài)用1表示終態(tài)30

為了說明DFA如何作為一種識(shí)別機(jī)制，我們還要理解下面的定義

∑*上的符號(hào)串t在DFA

M上運(yùn)行一個(gè)輸入符號(hào)串t，（將它表示成Tt1的形式，其中T∈∑，t1∈∑*）在DFAM=（K，Σ，f，S，Z）上運(yùn)行的定義為：f（Q，Tt1）=f（f（Q，T），t1）其中Q∈K擴(kuò)充轉(zhuǎn)換函數(shù)f為K×Σ*→K上的映射，且：

f（ki，）=ki31∑*上的符號(hào)串t被DFA

M接受M=（K，Σ，f，S，Z）若t∑*，f(S，t)=P，其中S為

M的開始狀態(tài)，PZ，Z為終態(tài)集。則稱t為DFAM所接受（識(shí)別）.32例：證明t=baab被下圖的DFA所接受。bSUVQabba,baaf（S，baab）=f（f（S，b），aab）=f（V，aab）=f（f（V，a），ab）=f（U，ab）=f（f（U，a），b）=f（Q，b）=QQ屬于終態(tài)。得證。33

DFAM所能接受的符號(hào)串的全體記為L(zhǎng)(M)，對(duì)于任何兩個(gè)有限自動(dòng)機(jī)M和M′，如果L(M)=L(M′)，則稱M與M′是等價(jià)的。

結(jié)論：

上一個(gè)符號(hào)串集V是正規(guī)的，當(dāng)且僅當(dāng)存在一個(gè)上的確定有限自動(dòng)機(jī)M，使得V=L(M)。34DFA的確定性表現(xiàn)在：轉(zhuǎn)換函數(shù)f:K×Σ→K是一個(gè)單值函數(shù)，也就是說，對(duì)任何狀態(tài)k∈K，和輸入符號(hào)a∈Σ，f(k,a)唯一地確定了下一個(gè)狀態(tài)。從狀態(tài)轉(zhuǎn)換圖來看，若字母表Σ含有n個(gè)輸入字符，那末任何一個(gè)狀態(tài)結(jié)點(diǎn)最多有n條弧射出，而且每條弧以一個(gè)不同的輸入字符標(biāo)記。35例：DFAM=({0,1,2,3},{a,b},f,0,{3})其中：f（0,a)=1;f（0,b)=2f（1,a)=3;f（1,b)=2f（2,a)=1;f（2,b)=3f（3,a)=3;f（3,b)=3問：有幾個(gè)狀態(tài),幾個(gè)輸入字符？并畫出其轉(zhuǎn)換圖。該自動(dòng)機(jī)可識(shí)別符號(hào)串a(chǎn)baab和abab嗎？36解：有0，1，2，3共四個(gè)狀態(tài)。輸入字符為a,b兩個(gè)。其狀態(tài)轉(zhuǎn)換圖如下：012abababa,b3對(duì)于符號(hào)串a(chǎn)baab，可被識(shí)別。對(duì)于符號(hào)串a(chǎn)bab，不能被識(shí)別。37不確定的有限自動(dòng)機(jī)NFA定義NFAM=K，，f，S，Z，其中K為狀態(tài)的有窮非空集，為有窮輸入字母表，f為K*到K的子集（2K）的一種映射（即K×*2k），SK是非空初始狀態(tài)集，ZK為終止?fàn)顟B(tài)集.顯然，NFA也可以表示成一張狀態(tài)轉(zhuǎn)換圖。假定NFA含有m個(gè)狀態(tài)、n個(gè)輸入字符，那么，這張圖含有m個(gè)狀態(tài)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)可以射出若干條箭弧和別的結(jié)點(diǎn)相連接，每條箭弧用*上的一個(gè)字（不一定要不同的字而且可以是空字）作標(biāo)記（稱為輸入字），整張圖至少含有一個(gè)初態(tài)和若干個(gè)（可以是0個(gè)）終態(tài)結(jié)點(diǎn)。某些結(jié)點(diǎn)既可以是初態(tài)也可以是終態(tài)結(jié)點(diǎn)。38例子NFAM=（{S，P，Z}，{0，1}，f，{S，P}，{Z}），其中：

f（S，0）={P}f（Z，0）={P}f（P，1）={Z}f（Z，1）={P}f（S，1）={S，Z}SPZ00111139矩陣表示01S{P}{S,Z}P{}{Z}*Z{P}{P}40f為K*到K的子集（2K）的一種映射具有轉(zhuǎn)移的不確定的有限自動(dòng)機(jī)

123abc41有如下定理:對(duì)任何一個(gè)具有轉(zhuǎn)移的不確定的有限自動(dòng)機(jī)NFAN，一定存在一個(gè)不具有轉(zhuǎn)移的不確定的有限自動(dòng)機(jī)NFAＭ，使得L(M)=L(N)。

與上例等價(jià)的一個(gè)NFA:2acbb31acacbb123abc42類似DFA,對(duì)NFAM=K，，f，S，Z也有如下定義:∑*上的符號(hào)串t在NFA

M上運(yùn)行一個(gè)輸入符號(hào)串t，（我們將它表示成Tt1的形式，其中T∈∑，t1∈∑*）在NFAM上運(yùn)行的定義為：f(Q，Tt1)=f(f(Q，T)，t1)其中Q∈K，∑*上的符號(hào)串t被NFA

M接受若t∑*，f(S0，t)=P，其中S0∈S，P∈

Z，則稱t為NFAM所接受（識(shí)別）43

∑*上的符號(hào)串t被NFA

M接受也可以這樣理解

對(duì)于Σ﹡中的任何一個(gè)串t，若存在一條從某一初態(tài)結(jié)點(diǎn)到某一終態(tài)結(jié)點(diǎn)的道路，且這條道路上所有弧的標(biāo)記字依序連接成的串(不理采那些標(biāo)記為ε的弧)等于t，則稱t可為NFAM所識(shí)別(讀出或接受)。若M的某些結(jié)既是初態(tài)結(jié)點(diǎn)又是終態(tài)結(jié)點(diǎn)，或者存在一條從某個(gè)初態(tài)結(jié)點(diǎn)到某個(gè)終態(tài)結(jié)點(diǎn)的道路，其上所有弧的標(biāo)記均為ε，那么空字可為M所接受。44舉例0001111010001110000001不能識(shí)別：000110045

NFAM所能接受的符號(hào)串的全體記為L(zhǎng)(M)結(jié)論：

上一個(gè)符號(hào)串集V是正規(guī)的，當(dāng)且僅當(dāng)存在一個(gè)上的不確定的有限自動(dòng)機(jī)M，使得V=L(M)。46例：(0|1)*(000|111)(0|1)*47定理：DFA是NFA的特例，對(duì)每個(gè)NFAN一定存在一個(gè)DFAＭ，使得L(M)=L(N)。對(duì)每個(gè)NFAN存在著與之等價(jià)的DFAM。有一種算法，將NFA轉(zhuǎn)換成接受同樣語言的DFA，這種算法稱為子集法。

與某一NFA等價(jià)的DFA不唯一。48從NFA的矩陣表示中可以看出，表項(xiàng)通常是一狀態(tài)的集合，而在DFA的矩陣表示中，表項(xiàng)是一個(gè)狀態(tài)，NFA到相應(yīng)的DFA的構(gòu)造的基本思路是：DFA的每一個(gè)狀態(tài)對(duì)應(yīng)NFA的一組狀態(tài).DFA使用它的狀態(tài)去記錄在NFA讀入一個(gè)輸入符號(hào)后可能達(dá)到的所有狀態(tài)。49定義對(duì)狀態(tài)集合I的幾個(gè)有關(guān)運(yùn)算：1.狀態(tài)集合I的ε-閉包：表示為ε-closure(I)，定義為一狀態(tài)集，是狀態(tài)集I中的任何狀態(tài)S經(jīng)任意條ε弧而能到達(dá)的狀態(tài)的集合。狀態(tài)集合I的任何狀態(tài)S都屬于ε-closure(I)。2.Ia：從I中的狀態(tài)經(jīng)過一條a弧(前后可跳過任意條ε弧)而到達(dá)的狀態(tài)的全體。50狀態(tài)集合I的有關(guān)運(yùn)算的例子若I={1},則

-closure(I)={1,2}；若I={5},則

-closure(I)={5,6,2}；若I={1,2},則Ia={2,3,4,5,6,7,8}；(備注：不需要掌握書上講的move集合)12534678aaa51NFA轉(zhuǎn)換為DFA的思想：將從狀態(tài)S出發(fā)經(jīng)過任意條弧所能到達(dá)的狀態(tài)作為DFA的初態(tài)S'；從S'出發(fā)，把遇到輸入符號(hào)a所轉(zhuǎn)移到的后繼狀態(tài)集作為DFA的新狀態(tài)；如此重復(fù)，直到不再有新的狀態(tài)出現(xiàn)為止。52

NFA確定化算法:

假設(shè)NFAN=(K,,f,K0,Kt)，按如下辦法構(gòu)造一個(gè)DFAM=(S,,d,S0,St)，使得L(M)=L(N)：531.M的狀態(tài)集S由K的一些子集組成。用[S1S2...

Sj]表示S的元素，其中S1,S2,,...

Sj是K的狀態(tài)。并且約定，狀態(tài)S1,S2,,...

Sj是按某種規(guī)則排列的，即對(duì)于子集{S1,S2}={S2,S1,}來說，S的狀態(tài)就是[S1S2]；

2.M和N的輸入字母表是相同的，即是；3.

轉(zhuǎn)換函數(shù)是這樣定義的：d([S1S2,...

Sj],a)=[R1R2...

Rt]

其中{R1,R2,...,Rt}

=

{S1,S2,,...

Sj}a4.

S0=-closure(K0)為M的開始狀態(tài)；5.St={[SiSk...

Se]，其中[Si

Sk...

Se]S且{Si

,Sk,,...

Se}Kt}54

NFA的確定化例子47356210aaaabbbb55若要將上圖的NFA轉(zhuǎn)換為DFA，步驟如下：（1）構(gòu)造一張表，它共有｜Σ｜+1列；（2）第一行第一列為-closure({0})；（3）求Ia、Ib并檢查，未在第一列出現(xiàn)過者，填入下行首列；（4）重復(fù)步驟（3）；（5）將狀態(tài)子集重新命名。5647356210aaaabbbb-closure(0)I

S

A

B

A

C

B

B

A

D

*C

C

E

*D

F

D

*E

F

D

*F

C

E

57等價(jià)的DFAaCDBAEFSbaaaaabbbbbabF58確定有限自動(dòng)機(jī)的化簡(jiǎn)說一個(gè)有限自動(dòng)機(jī)是化簡(jiǎn)了的，即是說，它沒有多余狀態(tài)并且它的狀態(tài)中沒有兩個(gè)是互相等價(jià)的。一個(gè)有限自動(dòng)機(jī)可以通過消除多余狀態(tài)和合并等價(jià)狀態(tài)而轉(zhuǎn)換成一個(gè)最小的與之等價(jià)的有限自動(dòng)機(jī)。所謂有限自動(dòng)機(jī)的多余狀態(tài)，是指這樣的狀態(tài)：從自動(dòng)機(jī)的開始狀態(tài)出發(fā)，任何輸入串也不能到達(dá)的那個(gè)狀態(tài)；或者從這個(gè)狀態(tài)沒有通路到達(dá)終態(tài)。59

DFA的最小化就是尋求最小狀態(tài)DFA最小狀態(tài)DFA的含義:沒有多余狀態(tài)(死狀態(tài))沒有兩個(gè)狀態(tài)是互相等價(jià)（不可區(qū)別）兩個(gè)狀態(tài)s和t等價(jià)，滿足：(或可區(qū)別：不滿足）一致性(或兼容性)——同是終態(tài)或同是非終態(tài)；蔓延性(或傳播性)——從s出發(fā)讀入某個(gè)aa和從 t出發(fā)讀入某個(gè)a到達(dá)的狀態(tài)等價(jià)。60

例：C和F是等價(jià)的。因?yàn)镃和F同是終態(tài),C和F讀入a都到達(dá)C,讀入b都到達(dá)E，所以C和F等價(jià)。aCDBAEFSbaaaaabbbbbabF61最小狀態(tài)DFA對(duì)于一個(gè)DFAM=（K,∑,f,

k0,kt)，存在一個(gè)最小狀態(tài)DFAM’=（K’,∑,f’,

k0’,,kt’)，使L(M’)=L(M).62“分割法”DFA的最小化算法的核心把一個(gè)DFA的狀態(tài)分成一些不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個(gè)狀態(tài)都是等價(jià)的。結(jié)論：終態(tài)和非終態(tài)是可區(qū)別的（不等價(jià)），因?yàn)閺慕K態(tài)可以識(shí)別到達(dá)終態(tài)，而從非終態(tài)則不能識(shí)別到達(dá)終態(tài)。

63

DFA的最小化算法

DFAM=（K,∑,f,k0,,kt）,最小狀態(tài)DFAM’

1.構(gòu)造狀態(tài)的一初始劃分：終態(tài)kt和非終態(tài)K-kt兩組(group)

2.對(duì)∏根據(jù)最小化原則，構(gòu)造新劃分∏new

3.如∏new=∏,則令∏final=∏并繼續(xù)步驟4，否則∏:=∏new重復(fù)2.

4.

為∏final中的每一組選一代表，這些代表構(gòu)成M’的狀態(tài)。若k是一代表且f(k,a)=t,令r是t組的代表，則M’中有一轉(zhuǎn)換f’(k,a)=r，M’的開始狀態(tài)是含有S0的那組的代表，M’的終態(tài)是含有F的那組的代表5.去掉M’中的死狀態(tài).64DFA最小化算法的核心——分割法。步驟如下：（1）將所有狀態(tài)分成兩個(gè)子集：終態(tài)集和非終態(tài)集；（2）把等價(jià)的狀態(tài)構(gòu)成一個(gè)子集，若不等價(jià)繼續(xù)劃分；（3）結(jié)束后，重新標(biāo)號(hào)或從每個(gè)子集中選一個(gè)狀態(tài)做代表。65IIaIbSABACBBAD*CCE*DFD*EFD*FCEDFA的最小化—例子M={S,A,B}∪{C,D,E,F}∵{S,A,B}a={A,C}不包含于第1次劃分出的任意集合∴{S,A,B}不等價(jià)，繼續(xù)得到第2次劃分為：{S,B}∪{A}∵{S,B}b={B,D}不包含于第2次劃分出的任意集合∴{S,B}不等價(jià)，繼續(xù)得到第3次劃分為：{S}∪{A}∪{B}∵{C,D,E,F}a={C,F}{C,D,E,F}b={D,E}∴{C,D,E,F}等價(jià)故最后結(jié)果為：M={S}∪{A}∪{B}{C,D,E,F}aCDBAEFSbaaaaabbbbbabF66IIaIbSABACBBAC*CCCDFA的最小化—例子(續(xù))因{C,D,E,F}等價(jià)，故從{C,D,E,F}中選C作為代表，出現(xiàn)D,E,F的地方一律用C代替，如下：aCDBAEFSbaaaaabbbbbabF最小化后DFA的為：CBASaaabbbba67例子畫出能夠識(shí)別C語言注釋/**/的DFA狀態(tài)1：注釋開始狀態(tài)。狀態(tài)2：進(jìn)入注釋體前的中間狀態(tài)。狀態(tài)3：表明目前正在注釋體中的狀態(tài)。狀態(tài)4：離開注釋前的中間狀態(tài)。狀態(tài)5：注釋結(jié)束狀態(tài)，即接受狀態(tài)。1/2534/**othersothers有限自動(dòng)機(jī)的一些應(yīng)用用于某些重要軟件的設(shè)計(jì)和構(gòu)造設(shè)計(jì)和檢查數(shù)字電路行為的軟件;掃描如網(wǎng)頁族等大規(guī)模文本以發(fā)現(xiàn)字、詞或其它結(jié)構(gòu)的出現(xiàn)頻率的軟件;驗(yàn)證所有只有有限多個(gè)不同狀態(tài)的系統(tǒng)的軟件，這類系統(tǒng)包括通信協(xié)議和信息安全交換協(xié)議。文獻(xiàn)舉例：基于協(xié)議分析狀態(tài)機(jī)的入侵檢測(cè)系統(tǒng)有限自動(dòng)機(jī)在BBS信息監(jiān)測(cè)系統(tǒng)中的運(yùn)用定理：

由任意正規(guī)文法G定義的語言必然能被一個(gè)NFAM所接受。即L（G）＝L（M）

4.4正規(guī)文法和有限自動(dòng)機(jī)的轉(zhuǎn)換70定理：由任意正規(guī)文法G定義的語言必然能被一個(gè)NFAM所接受。即L（G）＝L（M）構(gòu)造方法：

設(shè)正規(guī)文法G＝（VN，VT，P，S），構(gòu)造一個(gè)與G等價(jià)的有限自動(dòng)機(jī)NFA

M＝（K，∑，f，S，Z），其中：(1)K＝VNU{Z}，Z為一個(gè)新增加的終態(tài)；(2)∑=VT(即字母表與G的終結(jié)符集相同)；(3)開始符號(hào)S作為開始狀態(tài)S；f的定義為：當(dāng)AaBP，則構(gòu)造：f（A，a）=B當(dāng)AaP,則構(gòu)造：f（A，a）=Z當(dāng)A

P,則構(gòu)造：f（A，）=Z一、正規(guī)文法＝>有限自動(dòng)機(jī)71正規(guī)文法＝>有限自動(dòng)機(jī)（例）例：設(shè)有正規(guī)文法G=({S,A},{a,b},P,S)，其中 P：SaAAaA|bS|a

試構(gòu)造與G等價(jià)的有限自動(dòng)機(jī)M。解：

設(shè)NFAM=(K,∑,f,S,Z)K={S,A,Z}∑={a,b}S

=SZ={Z}轉(zhuǎn)換函數(shù)：對(duì)于產(chǎn)生式SaA，有f(S,a)={A}對(duì)于產(chǎn)生式AaA，有f(A,a)={A}對(duì)于產(chǎn)生式AbS，有f(A,b)={S}對(duì)于產(chǎn)生式Aa，有f(A,a)={Z}SAZ開始aaab72課堂練習(xí)

設(shè)正規(guī)文法G＝({S，A，B}，{a，b}，P，S)P： S

aA|bB|a AaA|aS|bB BbB|b|a 構(gòu)造相應(yīng)的NFAM。73二、有限自動(dòng)機(jī)＝>正規(guī)文法定理：設(shè)有限自動(dòng)機(jī)M接受的語言為L(zhǎng)(M)則存在正規(guī)文法G，它產(chǎn)生的語言L(G)＝L(M)。證明思路：構(gòu)造一個(gè)正規(guī)文法G，使它接受由NFAM定義的語言。構(gòu)造方法：

設(shè)M＝（K，∑，f，S，Z），構(gòu)造一個(gè)正規(guī)文法G＝（VN，VT，P，S），其中VN＝K，S＝SP定義為：若f（A，a）＝B，則AaB在P中

對(duì)終態(tài)Z，增加一產(chǎn)生式：

Z

74有限自動(dòng)機(jī)＝>正規(guī)文法（例）例：設(shè)有DFAM=({A,B,C,D},{a,b},f,A,{D})

其中轉(zhuǎn)換函數(shù)如圖所示，

試構(gòu)造與之等價(jià)的正規(guī)文法G。解：構(gòu)造正規(guī)文法G=(VN,VT,P,S)VN={A,B,C,D}VT={a,b}S=A產(chǎn)生式集合Pf(A,a)=B，AaBf(A,b)=C，AbCf(B,a)=D，BaDf(B,b)=B，BbBf(C,a)=C，CaCf(C,b)=D，CbDDZ，DABCDaaabbb開始構(gòu)造的文法G:G[A]:AaB|bCBaD|bBCaC|bDD75課堂練習(xí)構(gòu)造同NFAM等價(jià)的正規(guī)文法G。解：bAaBbCDabbaG[A]：A→aB|bDB→bCC→aA|bD|εD→aB|bD|ε764.5正規(guī)式和有限自動(dòng)機(jī)的等價(jià)性

詞法分析程序的自動(dòng)構(gòu)造方法，基于有限自動(dòng)機(jī)和正規(guī)表達(dá)式的等價(jià)性，即：1.對(duì)于∑上的一個(gè)NFAM，可以構(gòu)造一個(gè)∑上的正規(guī)式R,使得L(R)=L(M)。2.對(duì)于∑上的一個(gè)正規(guī)式R，可以構(gòu)造一個(gè)∑上的NFAM，使的L(M)=L(R)。771、在M上加兩個(gè)結(jié)點(diǎn)S、Z，從S結(jié)點(diǎn)用ε弧到M的所有初態(tài)，從M的所有終態(tài)用ε到Z結(jié)成與M等價(jià)的M’，M’只有一個(gè)初態(tài)S和一個(gè)終態(tài)Z。03214a,ba,ba,bbbaaS03412Zεεεaa,ba,ba,babb一、自動(dòng)機(jī)＝>正規(guī)式（狀態(tài)消去法）2、逐步消去M’中的所有結(jié)點(diǎn)，直至剩下S和Z結(jié)點(diǎn)，在消去過程中，逐步用正規(guī)式來標(biāo)記弧，消去規(guī)則如下：R1R2123R1R21312R1R2R1|R2121R1R323R2R1R2*R313繼續(xù)消去S03412Zεεεaa,ba,ba,babbS042Zεεεaaa|b