編譯原理第三章

編譯原理電子教案第三章詞法分析（lexicalanalysis）謝強(qiáng)計算機(jī)科學(xué)與技術(shù)學(xué)ieqiang@.con2本章的主要內(nèi)容詞法分析器的設(shè)計要求狀態(tài)轉(zhuǎn)換圖正規(guī)表達(dá)式有限自動機(jī)正規(guī)式、正規(guī)文法、有限自動機(jī)的等價性確定有限自動機(jī)的化簡詞法分析器的自動產(chǎn)生（了解）3本章要求知識點：詞法分析程序的功能及構(gòu)造方法，正規(guī)表達(dá)式與正規(guī)集，正規(guī)表達(dá)式與正規(guī)文法，狀態(tài)轉(zhuǎn)換圖與基本符號的識別，有限自動機(jī)。深刻理解：正規(guī)表達(dá)式，有限自動機(jī)，正規(guī)文法以及三者之間的等價性；確定的有限自動機(jī)和非確定的有限自動機(jī)之間的等價性。熟練掌握：（1）對于某一正規(guī)集，寫出其正規(guī)表達(dá)式，構(gòu)造其非確定的有限自動機(jī)、確定的有限自動機(jī)，并將其最小化；（2）對于某一正規(guī)集，寫出正規(guī)表達(dá)式，構(gòu)造自動機(jī)，然后構(gòu)造正規(guī)文法。4本章教學(xué)線索1詞法分析程序的設(shè)計1.1詞法分析程序的功能1.2詞法分析程序作為一個獨立子程序2詞法分析器的設(shè)計3狀態(tài)轉(zhuǎn)換圖4正規(guī)表達(dá)式與有限自動機(jī)5確定有限自動機(jī)的化簡6詞法分析程序的自動構(gòu)造工具LEX簡介51.1詞法分析程序的功能

詞法分析的任務(wù)：從左到右逐個字符地對源程序進(jìn)行掃描，產(chǎn)生一個個的單詞符號，把作為字符串的源程序改造成為單詞符號串的中間程序。詞法分析器源程序單詞符號6單詞符號關(guān)鍵字、標(biāo)識符、常數(shù)、（運）算符、界符；詞法分析器輸出單詞符號的表示

（單詞種別，單詞符號的屬性值）單詞種別通常用整數(shù)編碼。詞類編碼提供給語法分析程序使用；單詞自身的屬性值提供給語義分析程序使用。具體的分類設(shè)計以方便語法分析程序使用為原則。單詞分種策略標(biāo)識符一般統(tǒng)規(guī)為一種；常數(shù)則宜按類型（整、實、布爾等）分種；關(guān)鍵字可以將全體視為一種，也可以一字一種；運算符可采用一字一種，一個將具有共性的運算符視為一種。界符一般采用一字一種。71.2詞法分析程序作為一個獨立子程序（1）語法分析程序的子程序；（2）組織成一遍掃描。（為什么？）復(fù)雜問題分解，模塊化設(shè)計，使得整個編譯程序的結(jié)構(gòu)更簡潔、清晰。由于詞法分析程序相對于語法分析程序來說要簡單得多，如果把詞法分析和語法分析合在一起將會導(dǎo)致語法分析程序變得非常復(fù)雜，并且使編譯程序的執(zhí)行效率變得很低。8詞法分析語法分析語義分析和中間代碼生成源程序中間代碼符號表管理錯誤的診查處理9whilei＜＞jdoifi＞jthen

i:＝i-jelsej:=j-i‘while’，‘i’，‘＜＞’，‘j’，‘do’，‘if’，‘i’，‘＞’，‘j’,‘then’,'i',':=’,'i',’-’,'j','else','j',':=','j','-',‘i'詞法分析器〈while，——〉〈id，指向i的符號表入口的指針〉〈relational－op，NE〉〈id，指向j的符號表入口的指針〉〈do，——〉〈if，——〉〈id，指向i的符號表入口的指針〉〈id，指向j的符號表入口的指針〉例子：10本章教學(xué)線索1詞法分析程序的設(shè)計2詞法分析器的設(shè)計2.1輸入、輸出預(yù)處理2.2單詞符號的識別（P40—41）3狀態(tài)轉(zhuǎn)換圖4正規(guī)表達(dá)式與有限自動機(jī)5確定有限自動機(jī)的化簡6詞法分析程序的自動構(gòu)造工具LEX簡介112.1輸入、輸出預(yù)處理（1）去除掉空白符、跳格符、回車符和換行符等編輯性字符；（2）去除程序中的注釋符；（3）掃描緩沖區(qū)122.2單詞符號的識別（P40—41）超前搜索問題關(guān)鍵字的識別標(biāo)識符的識別常數(shù)的識別算符和界符的識別13本章教學(xué)線索1詞法分析程序的設(shè)計2詞法分析器的設(shè)計3狀態(tài)轉(zhuǎn)換圖3.1狀態(tài)轉(zhuǎn)換圖的概念3.2構(gòu)造識別一種簡單語言的單詞符號的轉(zhuǎn)換圖4正規(guī)表達(dá)式與有限自動機(jī)5確定有限自動機(jī)的化簡6詞法分析程序的自動構(gòu)造工具LEX簡介143.1狀態(tài)轉(zhuǎn)換圖的概念狀態(tài)轉(zhuǎn)換圖是一張有限方向圖，在狀態(tài)轉(zhuǎn)換圖中，結(jié)點代表狀態(tài)，用圓圈表示。狀態(tài)之間用箭弧連結(jié)。箭弧上的標(biāo)記（字符、正規(guī)式）代表在射出結(jié)點（即箭符始結(jié)點）狀態(tài)下可能出現(xiàn)的輸入字符或字符類。一張狀態(tài)轉(zhuǎn)換圖只包含有限個狀態(tài)（即有限個結(jié)點），其中含有一個初態(tài)（用雙線箭頭指示）和若干個終態(tài)（用雙圈表示），而且實際上至少要有一個終態(tài)，初態(tài)表示分析的開始，終態(tài)表示分析的結(jié)束。一個狀態(tài)轉(zhuǎn)換圖可用于識別（或接受）一定的字符串。15012*字母其它字母或數(shù)字圖A—識別標(biāo)識符的轉(zhuǎn)換圖012*數(shù)字其它圖B—識別整數(shù)的轉(zhuǎn)換圖數(shù)字017*其它圖C—識別Fortran實型常數(shù)的轉(zhuǎn)換圖23456數(shù)字?jǐn)?shù)字?jǐn)?shù)字其它+或-E或D數(shù)字E或D··數(shù)字?jǐn)?shù)字?jǐn)?shù)字163.2構(gòu)造識別一種簡單語言的單詞符號的轉(zhuǎn)換圖限制條件：（1）所有關(guān)鍵字都是“保留字”，用戶不得使用它們作為自己定義的標(biāo)識符。（2）關(guān)鍵字作為一類特殊的標(biāo)識符來處理，不再專門設(shè)置對應(yīng)的轉(zhuǎn)換圖，把它們預(yù)先安排在一張表格中，當(dāng)轉(zhuǎn)換圖識別出一個標(biāo)識符，就去查詢這張表，確定是否為一個關(guān)鍵字。（3）如果關(guān)鍵字、標(biāo)識符和常數(shù)之間沒有確定的運算符或界符作間隔，則必須至少用一個空白符作間隔2**38*121311非*空白字母非字母與數(shù)字字母或數(shù)字?jǐn)?shù)字?jǐn)?shù)字非數(shù)字=+*...，（）其它1819本章教學(xué)線索1詞法分析程序的設(shè)計2詞法分析器的設(shè)計3狀態(tài)轉(zhuǎn)換圖4正規(guī)表達(dá)式與有限自動機(jī)4.1正規(guī)式與正規(guī)集4.2確定有限自動機(jī)（DFA）4.3非確定有限自動機(jī)NFA4.4DFAM和NFAM的等價性4.5正規(guī)文法與有限自動機(jī)的等價性4.6正規(guī)式與有限自動機(jī)的等價性5確定有限自動機(jī)的化簡6詞法分析程序的自動構(gòu)造工具LEX簡介204.1正規(guī)式與正規(guī)集4.1.1正規(guī)式與正規(guī)集的定義（概念）（1）ε、Φ都是∑上的正規(guī)式，它們所表示的正規(guī)集分別為{ε}和Φ；（2）任何a∈∑，a是∑上的一個正規(guī)式，它所表示的正規(guī)集為{a}；（3）如果U、V都是∑上的正規(guī)式，它們所表示的正規(guī)集分別記為L（U）和L（V），那么，（U|V）、（U*V）和（U）*也是正規(guī)式，它們所表示的正規(guī)集分別為L（U）∪L（V）、L（U）L（V）和（L（U））*；僅由有限次使用上述步驟而得到的表達(dá)式才是∑上的正規(guī)式；僅由這些正規(guī)式所表示的字集才是∑上的正規(guī)集。21例子：令∑={a，b}，下面是∑上的正規(guī)式和相應(yīng)的正規(guī)集正規(guī)式正規(guī)集ba*∑上所有以b為首后跟任意多個a的字a(a|b)*∑上所有以a為首的字（a|b）*

(aa|bb)(a|b)*∑上所有含有兩個相繼的a或兩個相繼的b的字224.1.2正規(guī)式的數(shù)學(xué)運算交換律：U|V=V|U；結(jié)合律：U|（V|W）=（U|V）|W、U（VM）=（UV）W；分配律：U（V|W）=UV|UW（V|W）|U=VU|WUε連接：εU=Uε=U23另外一種定義方法：定義正規(guī)表達(dá)式（regularexpression）是以下的一種：基本（basic）正規(guī)表達(dá)式由一個單字符a（其中a在字母表∑中），以及元字符ε或元字符Φ組成。在第1種情況下，L(a)={a}；在第2種情況下，L(ε)={ε}；在第3種情況下，L(Φ)={}。r|s格式的表達(dá)式：其中r和s均是正規(guī)式。在這種情況下，L（r|s）=L（r）∪L（s）。rs格式的表達(dá)式：其中r和s是正規(guī)式。在這種情況下，

L（rs）=L(r)L（s）。r*格式的表達(dá)式：其中r是正規(guī)表達(dá)式。在這種情況下，L（r*）=L（r）*。（r）格式的表達(dá)式：其中r是正規(guī)式。在這種情況下，L（（r））=L（r），因此，括號并不改變語言，它們只調(diào)整運算的優(yōu)先權(quán)。24需要注意：｜的優(yōu)先權(quán)最低，連結(jié)次之，*則最高。另外還注意到在這個定義中，5個符號|、*、*、（和）都有了元字符的含義。正規(guī)式的連接一般不滿足交換律254.2確定有限自動機(jī)（DFA）4.2.1確定有限自動機(jī)的定義

一個確定有限自動機(jī)（DFA）M是一個五元式：M=（S，∑，δ，s0，F(xiàn)），其中：S是一個有限集，它的每個元素稱為一個狀態(tài)；∑是一個有窮字母表，它的每個元素稱為一個輸入字符；δ是一個從Sx∑至S的單值部分映射。δ（s，a）=s′，意味著：當(dāng)現(xiàn)行狀態(tài)為s、輸入為字符a時，將狀態(tài)轉(zhuǎn)換到下一個狀態(tài)s′。我們稱s′為s的一個后繼狀態(tài)。s0∈S，是唯一的初態(tài)。FS，是一個終態(tài)集（可空）。264.2.2DFA的矩陣表示及狀態(tài)轉(zhuǎn)換圖表示行表示狀態(tài)列表示輸入字符矩陣元素表示δ（s，a）的值。這個矩陣稱為狀態(tài)轉(zhuǎn)換矩陣。例子：M=（{0，1，2，3}，{a，b}，δ，0，{3}）其中δ為：δ(0，a)=1δ(0，b)=2δ(1，a)=3δ(1，b)=2δ(2，a)=1δ(2，b)=3δ(3，a)=3δ(3，b)=327對應(yīng)的狀態(tài)轉(zhuǎn)換矩陣：狀態(tài)ab012132213333一個DFA也可以表示成一張（確定的）狀態(tài)轉(zhuǎn)換圖：δ(0，a)=1δ(0，b)=2δ(1，a)=3δ(1，b)=2δ(2，a)=1δ(2，b)=3δ(3，a)=3δ(3，b)=31023ababa，bab28確定有限自動機(jī)（DFA）的三種表示形式1）狀態(tài)轉(zhuǎn)換函數(shù)2）狀態(tài)轉(zhuǎn)換矩陣3）狀態(tài)轉(zhuǎn)換圖開始狀態(tài)一般狀態(tài)終態(tài)狀態(tài)轉(zhuǎn)換圖節(jié)點的三種形式294.2.3有限自動機(jī)DFAM接受的語言從狀態(tài)轉(zhuǎn)換函數(shù)來看：如果對所有α∈Σ*，以下述方式遞歸擴(kuò)張δ的定義：δ（s，ε）＝s，δ(s，αa）＝δ（δ（s，α），a）（ａ∈Σ，s∈S），則有Ｌ（Ｍ）＝｛α｜α∈Σ*，若存在s∈Ｆ，使δ（s0，α）＝s｝對上例的DFAM和w=baa，δ（0，baa）=δ（2，aa）=δ(1，a）=3（注意：其中0代表0態(tài)，1表示1態(tài)，2表示2態(tài)，3表示3態(tài)）30從狀態(tài)轉(zhuǎn)換圖來看：對于Σ*上的任何字α，如果存在一條從初態(tài)結(jié)點到某一終態(tài)結(jié)點的通路，且這條通路上所有弧的標(biāo)記符連接成的字等于α，則稱α可為DFAM所識別（讀出或接受），如果M的初態(tài)結(jié)點同時又是終態(tài)結(jié)點，則空字ε可為DFAM所識別。DFAM所能識別的字的全體記為L(M)。課后例子：給出接受下列在字母表{0，1}上的語言的DFA：所有以00結(jié)束的串的集合；（1|0）*00所有具有三個0的串的集合。1*01*01*01*314.2.4DFA的程序模擬DFAM=（K，Σ，f，S，Z）的行為的模擬程序K=S；c=getchar;whilec<>eofdo{K=f(K,c);c=getchar;};ifKisinZthenreturn(‘yes’)Elsereturn(‘no’)324.3非確定有限自動機(jī)NFA一個非確定有限自動機(jī)NFAM是一個五元式：M=(S，Σ，δ，S0，F(xiàn))其中：S是一個有限集，它的每個元素稱為一個狀態(tài)；∑是一個有窮字母表，它的每個元素稱為一個輸入字符；δ是一個從Sx∑*至S的子集的映射，即δ：Sx∑*→2s（S集合的冪集/S的所有子集的集合）S0S，是一個非空初態(tài)集。FS,是一個終態(tài)集（可空）。33對于∑*中的任何一個字α，若存在一條從某一初態(tài)結(jié)點到某一終態(tài)結(jié)點的通路，且這條通路上所有弧的標(biāo)記字依序連接成的字（忽略那些標(biāo)記為ε的弧）等于α，則稱α可為NFAM所識別（讀出或接受）。若M的某些結(jié)點既是初態(tài)結(jié)點又是終態(tài)結(jié)點，或者存在一條從初態(tài)結(jié)點到某一終態(tài)結(jié)點的ε通路，那么，空字ε可為M所接受。例子：識別所有含有相繼兩個a或相繼兩個b的字NFA。5X12346Yaaaabbbbεεεε344.4DFAM和NFAM的等價性定理：對于每個NFAM存在一個DFAM′，使得L(M)=L(M′)證明思想：用M′的一個狀態(tài)對應(yīng)M的一個狀態(tài)集合，用這種方法，能從一個NFAM構(gòu)造一個DFAM′使得L（M′）=L（M），這種方法稱作子集構(gòu)造法。354.4.1狀態(tài)集的ε閉包定義設(shè)I是有限自動機(jī)的狀態(tài)集的子集，I的ε閉包ε_CLOSURE(I)為：(1)如果狀態(tài)q∈I，則q∈ε_CLOSURE（I）（既I中的狀態(tài)全部屬于ε_CLOSURE(I)）(2)如果狀態(tài)q∈I，那么從狀態(tài)q出發(fā)經(jīng)過任意ε弧而能到達(dá)的任何狀態(tài)q′都屬于ε_CLOSURE(I)。（注意：可以連續(xù)經(jīng)過多條ε?。?64.4.2有限自動機(jī)的轉(zhuǎn)移函數(shù)假定I是非確定有限自動機(jī)的狀態(tài)集的子集，則定義：

Ia=ε_CLOSURE(J)

其中：a∈Σ，J是從I中的某一狀態(tài)結(jié)點出發(fā)經(jīng)過一條a弧而達(dá)到的狀態(tài)結(jié)點的全體。

374.4.3從NFAM構(gòu)造DFAM的步驟（方法）（1）設(shè)NFAM=<S，Σ，δ，S0，F(xiàn)>，對M的狀態(tài)圖進(jìn)行改造：引進(jìn)新的初態(tài)結(jié)點X和終態(tài)結(jié)點Y，且X，Y?S，從X到S0中任意狀態(tài)結(jié)點連一條ε箭弧，從F中任意狀態(tài)結(jié)點連一條ε箭弧到Y(jié)；對M中的狀態(tài)圖進(jìn)行下圖所示的替換，其中k是新引進(jìn)的狀態(tài)。重復(fù)這種分裂過程直到狀態(tài)圖中的每條箭弧上的標(biāo)記或為ε，或為Σ中的單個字母。將最終得到的NFA記為M′，顯然L（M′）=L（M）ijikjABABijA|BijA*ijAB

ikjεεA38（2）將非確定有限自動機(jī)M′轉(zhuǎn)換成確定有限自動機(jī)M"

方法：假設(shè)Σ={a1，a2，a3，…，ak}，構(gòu)造狀態(tài)轉(zhuǎn)化表，表的構(gòu)成：a)每一行包含k+1列，首行首列為ε_CLOSURE(X)；b)如果每行的第一列假定為I，則該行的i+1列為Iai(i=1，2，…，k)。然后檢查該行的所有狀態(tài)子集，將未曾在第一列出現(xiàn)的填入到后面空行的第一列。c)重復(fù)上述b)，直到出現(xiàn)在表的第i+1列上的所有狀態(tài)子集均在第一列中出現(xiàn)。d)將構(gòu)造出來的表視為狀態(tài)轉(zhuǎn)換表，將其中的每個狀態(tài)子集視為新的狀態(tài)，顯然該表唯一的刻畫了一個DFAM"，該有限自動機(jī)的初態(tài)為該表的首行首列，終態(tài)為那些包含原終態(tài)的狀態(tài)子集。顯然L(M")=L(M')=L(M)39例子：p50正規(guī)式（a|b）*（aa|bb）（a|b）*對應(yīng)的NFA如例3.3中圖。其中X為初態(tài)，Y為終態(tài)。狀態(tài)轉(zhuǎn)換矩陣如下表：

IJIaJIb{X,5,1}{5,3}{5,3,1}{5,4}{5,4,1}{5,3,1}{5,3,2}{5,3,1,2,6,Y}{5,4}{5,4,1}{5,4,1}{5,3,1}{5,4,1,2,6,Y}{5,3,1,2,6,Y}{5,3,1,2,6,Y}{5,4,1,6,Y}{5,4,1,6,Y}{5,3,1,6,Y}{5,4,1,2,6,Y}{5,4,1,2,6,Y}{5,3,1,6,Y}{5,4,1,2,6,Y}{5,3,1,6,Y}{5,3,1,2,6,Y}{5,4,1,6,Y}X5126Y34εεεεababaabb40轉(zhuǎn)換成狀態(tài)轉(zhuǎn)換矩陣：（將第一列從上向下編號）

sab0121322153344655656340123564abababababbaba41312ababaBSAbabCaa，baaIaIb{S}{A,C}Φ{A,C}{A,C}{A,B}{A,B}{A,C}{A,B}42a，bSAaa，bbb132babIaIb{S}{S,A}{A}{S,A}{S,A}{S,A}{A}Φ{S,A}43124εbaεεb3cASBccabbIaIbIc{1，2，3，4}{1，2，3，4}{2，4}{3，4}{2，4}Φ{2，4}Φ{3，4}ΦΦ{3，4}444.5正規(guī)文法與有限自動機(jī)的等價性正規(guī)文法與有限自動機(jī)的等價性結(jié)論：對每個右線性正規(guī)文法GR或左線性正規(guī)文法GL，都存在一個有限自動機(jī)（FA）M，使得：L（M）=L（G）對每一個FAM，都存在一個右線性正規(guī)文法GR和左線性正規(guī)文法GL，使得：L（M）=L（GR）=L（GL）右線性正規(guī)文法：A→αB或A→α,α∈VT*，A，B∈VN左線性正規(guī)文法：A→Bα或A→α,α∈VT*，A，B∈VN45證明1：右線性正規(guī)文法GR同有限自動機(jī)的等價性（1）設(shè)右線性正規(guī)文法GR=<VT，VN，S，P>。將VN中的每一非終結(jié)符號視為狀態(tài)符號，并增加一個新的終結(jié)狀態(tài)符號f，f?VN。構(gòu)造有限自動機(jī)M=<VN∪{f}，VT

，δ，S，{f}>，其中狀態(tài)轉(zhuǎn)換函數(shù)δ定義如下：如果對某個A∈VN且a∈VT∪{ε}，P中有產(chǎn)生式A→a，則令δ（A，a）=f。對任意A∈VN且a∈VT∪{ε}，設(shè)P中左端為A，右端第一符號為a的所有產(chǎn)生式為：A→aA1|aA2|…|aAk（不包含：A→a）則令：δ（A，a）={A1，A2，…，AK}顯然，上述的自動機(jī)M為一非確定有限自動機(jī)（NFA）（為什么是非確定）。46（2）設(shè)左線性正規(guī)文法GL=<VT，VN，S，P>，將VN中的每一符號視為狀態(tài)符號，并且增加一個初態(tài)符號q0，q0VN。 令M=<VN∪{q0}，VT，δ，q0，{S}>，其中狀態(tài)轉(zhuǎn)換函數(shù)可以由以下規(guī)則定義：若對某個A∈VN及a∈VT∪{ε}，P中有產(chǎn)生式A→a，則令δ（q0，a）=A對任意的A∈VN及a∈VT∪{ε}，若P中所有右端第一符號為A，第二符號為a的產(chǎn)生式為：A1→Aa，A2→Aa，A3→Aa，…，Ak→Aa。則令δ（A，a）={A1，A2,…,Ak}q0AaAA1A2Ak…aaa47證明2：有限自動機(jī)同正規(guī)文法的等價性設(shè)DFAM=<S，Σ，δ，s0，F(xiàn)>，構(gòu)造右線性正規(guī)文法：（1）若s0?F，令GR=<Σ，S，s0，P>，其中P的產(chǎn)生式集合如下定義：對任何a∈Σ及A，B∈S，若有δ（A，a）=B則：當(dāng)B?F時，令A(yù)→aB；當(dāng)B∈F時，令A(yù)→a|aB；對于w∈Σ*，不妨設(shè)w=a1a2…ak，其中ai∈Σ(i=1,…,k)。若s0w，則存在一個最左推導(dǎo):s0?a1A1?

a1a2A2?…?a1…aiAi?…?a1a2…ak，因而，在M中有一條從s0出發(fā)依次經(jīng)過A1，…，Ak-1，達(dá)到終態(tài)的通路，該通路上所有箭弧依次標(biāo)記為a1，a2，…，ak。反之亦然。所以：w∈L(GR)當(dāng)且僅當(dāng)w∈L(M)。48（2）當(dāng)s0∈F，因為δ(s0，ε)=s0，所以ε∈L(M)。但ε不屬于上面構(gòu)造的GR產(chǎn)生的文法L(GR)。但是：L(GR)=L(M)-{ε}。所以在上面的GR中添加新的非終結(jié)符號s0′(s0′?S)和產(chǎn)生式s0′→s0|ε,并用s0′代替s0作開始符號。這樣修正后的文法GR′仍然是右線性正規(guī)文法，并且L(GR′)=L(M)。注意：構(gòu)造左線性正規(guī)文法，將終態(tài)視為開始符號，P的定義如下：對任何a

及A1，A2VN,有(A1，a)=A2,則

(a)A1是初態(tài)，A2a|A1a(b)A1不是初態(tài),A2A1a

如果有多個終態(tài)，需要引入新終態(tài)，將原來的終態(tài)連接到新終態(tài)，箭符上的標(biāo)記符為ε，將新的終態(tài)作為左線性正規(guī)文法的開始符號，其產(chǎn)生式為f′→f1|f2|…

49綜合例子：P52~53

DFAM=<{A,B,C,D},{0,1},δ,A,B>ADBC0,1000111504.6正規(guī)式與有限自動機(jī)的等價性包含兩方面的含義：（1）對于任何有限自動機(jī)M，都存在一個正規(guī)式r，使得L(r)=L(M)；（2）對于任何正規(guī)式r，都存在一個有限自動機(jī)M，使得L(M)=L(r)

正規(guī)文法、正規(guī)式、確定有限自動機(jī)和非確定有限自動機(jī)在接受語言的能力上是一致的。51證明1：對于Σ上的NFAM，構(gòu)造Σ上的正規(guī)式r，使得L(r)=L(M)；對M的狀態(tài)轉(zhuǎn)換圖進(jìn)行改造：在M中加入兩個結(jié)點X、Y。從X用ε弧連接到M的所有初態(tài)結(jié)點；從M的所有終態(tài)結(jié)點用ε連接到Y(jié)，從而形成一個新的NFA，記為M′，它只有一個初態(tài)X和一個終態(tài)Y。顯然，L(M)=L(M′)。按下列方式消除M′中的所有結(jié)點，直至只剩X和Y。

123V1V2ij12V1V2ijV1|V2V1V2123V1V3V2ijV1V2*V352證明2：有Σ上的正規(guī)式r，構(gòu)造一個NFAM（M只有一個終態(tài)，并且沒有從終態(tài)出發(fā)的箭?。┓椒ǎ簩中運算符數(shù)目進(jìn)行歸納證明：(運算符：|，*,*)(1)若r具有0個運算符，則r=ε，r=Φ，r=a，a∈Σ，下圖的三個有限自動機(jī)顯然符合要求。q0q0qfq0qfa對應(yīng)ε的狀態(tài)轉(zhuǎn)換圖(q0既是初態(tài)又是終態(tài))對應(yīng)Φ的狀態(tài)轉(zhuǎn)換圖（初態(tài)到終態(tài)沒有通路）對應(yīng)a的狀態(tài)轉(zhuǎn)換圖Thopmson

方法53（2）設(shè)結(jié)論對少于i(i≥1)個運算的正規(guī)表達(dá)式r成立。當(dāng)r有i個運算時，有三種情況：a)r=r1|r2，r2中的運算符個數(shù)少于k。由歸納假設(shè)，對ri存在Mi=<Si，Σi，δi，qi，fi>，使得L(Mi)=L(ri)，并且Mi沒有從終態(tài)出發(fā)的箭?。╥=1,2）。設(shè)S1∩S2=Φ，在S1∪S2中加入新狀態(tài)q0，f0。設(shè)M=<S1∪S2∪{q0，f0}，Σ1∪Σ2，δ，q0，f0>，其中δ定義為：(a)δ（q0，ε）={q1，q2}；(b)δ（q，a）=δ1（q，a），當(dāng)q∈S1–{f1}，a∈Σ1∪{ε}；

(c)δ（q，a）=δ2（q，a），當(dāng)q∈S2–{f2}，a∈Σ2∪{ε}；

(d)δ（f1，ε）=δ（f2，ε）={f0}M的狀態(tài)轉(zhuǎn)換圖中不難看出，M中有一條從q0到f0的通路w，當(dāng)且僅當(dāng)在M1中有一條從q1到f1的通路w或者在M2中有一條從q2到f2的通路w，即：L(M)=L(M1)∪L(M2)=L(r1)∪L(r2)=L(r)q0M1q1f1M2q2f2f0εεεε54b)r=r1r2。Mi同a)設(shè)M=<S1∪S2，∑1∪∑2，δ，q1，{f2}>δ:(a)δ（q，a）=δ1（q，a），當(dāng)q∈S1–{f1}，a∈Σ1∪{ε}；(b)δ（q，a）=δ2（q，a），當(dāng)q∈S2–{f2}，a∈Σ2∪{ε}；(c)δ（f1，ε）={q2}c)r=r1*。設(shè)M1同a)設(shè)M=<S1∪{q0，f0}，∑1，δ，q0，{f0}>，其中q0,f0?S1，δ:(a)δ（q0，ε）=δ（f1，ε）={q1，f0}；(b)δ（q，a）=δ1（q，a），當(dāng)q∈S1–{f1}，a∈Σ1∪{ε}

M1q1f1q0f0εεεε

M2

M1q1f1q2f2ε55Thompson方法所構(gòu)造的NFA的狀態(tài)數(shù)和轉(zhuǎn)換較多。可以采用下面方法減少之：

R=R1|R2R1R2

R=R1R2R1R2

R=R1*R1

RRR156本章教學(xué)線索1詞法分析程序的設(shè)計2詞法分析器的設(shè)計3狀態(tài)轉(zhuǎn)換圖4正規(guī)表達(dá)式與有限自動機(jī)5確定有限自動機(jī)的化簡6詞法分析程序的自動構(gòu)造工具LEX簡介575確定有限自動機(jī)的化簡1)確定的有限自動機(jī)的化簡一個DFAM=(，S，，s0，F(xiàn))的化簡是指尋找一個狀態(tài)數(shù)比較少的DFAM′，使L(M)=L(M′)。而且可以證明，存在一個最少狀態(tài)的DFAM′，使L(M)=L(M′)。2)等價狀態(tài)的定義設(shè)s，tS，若對任何w

*，(s，w)F當(dāng)且僅當(dāng)(t，w)F，則稱s和t是等價狀態(tài)。否則，稱s和t是可區(qū)別的。（即假定s和t是M的兩個不同狀態(tài)，如果從狀態(tài)s出發(fā)能夠讀出某個字而停于終態(tài)，同樣從t出發(fā)也能讀出某個字而停于終態(tài)，稱s和t是等價的，如果