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

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

（單詞種別，單詞符號(hào)的屬性值）單詞種別通常用整數(shù)編碼。詞類編碼提供給語法分析程序使用；單詞自身的屬性值提供給語義分析程序使用。具體的分類設(shè)計(jì)以方便語法分析程序使用為原則。單詞分種策略標(biāo)識(shí)符一般統(tǒng)規(guī)為一種；常數(shù)則宜按類型（整、實(shí)、布爾等）分種；關(guān)鍵字可以將全體視為一種，也可以一字一種；運(yùn)算符可采用一字一種，一個(gè)將具有共性的運(yùn)算符視為一種。界符一般采用一字一種。71.2詞法分析程序作為一個(gè)獨(dú)立子程序（1）語法分析程序的子程序；（2）組織成一遍掃描。（為什么？）復(fù)雜問題分解，模塊化設(shè)計(jì)，使得整個(gè)編譯程序的結(jié)構(gòu)更簡(jiǎn)潔、清晰。由于詞法分析程序相對(duì)于語法分析程序來說要簡(jiǎn)單得多，如果把詞法分析和語法分析合在一起將會(huì)導(dǎo)致語法分析程序變得非常復(fù)雜，并且使編譯程序的執(zhí)行效率變得很低。8詞法分析語法分析語義分析和中間代碼生成源程序中間代碼符號(hào)表管理錯(cuò)誤的診查處理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的符號(hào)表入口的指針〉〈relational－op，NE〉〈id，指向j的符號(hào)表入口的指針〉〈do，——〉〈if，——〉〈id，指向i的符號(hào)表入口的指針〉〈id，指向j的符號(hào)表入口的指針〉例子：10本章教學(xué)線索1詞法分析程序的設(shè)計(jì)2詞法分析器的設(shè)計(jì)2.1輸入、輸出預(yù)處理2.2單詞符號(hào)的識(shí)別（P40—41）3狀態(tài)轉(zhuǎn)換圖4正規(guī)表達(dá)式與有限自動(dòng)機(jī)5確定有限自動(dòng)機(jī)的化簡(jiǎn)6詞法分析程序的自動(dòng)構(gòu)造工具LEX簡(jiǎn)介112.1輸入、輸出預(yù)處理（1）去除掉空白符、跳格符、回車符和換行符等編輯性字符；（2）去除程序中的注釋符；（3）掃描緩沖區(qū)122.2單詞符號(hào)的識(shí)別（P40—41）超前搜索問題關(guān)鍵字的識(shí)別標(biāo)識(shí)符的識(shí)別常數(shù)的識(shí)別算符和界符的識(shí)別13本章教學(xué)線索1詞法分析程序的設(shè)計(jì)2詞法分析器的設(shè)計(jì)3狀態(tài)轉(zhuǎn)換圖3.1狀態(tài)轉(zhuǎn)換圖的概念3.2構(gòu)造識(shí)別一種簡(jiǎn)單語言的單詞符號(hào)的轉(zhuǎn)換圖4正規(guī)表達(dá)式與有限自動(dòng)機(jī)5確定有限自動(dòng)機(jī)的化簡(jiǎn)6詞法分析程序的自動(dòng)構(gòu)造工具LEX簡(jiǎn)介143.1狀態(tài)轉(zhuǎn)換圖的概念狀態(tài)轉(zhuǎn)換圖是一張有限方向圖，在狀態(tài)轉(zhuǎn)換圖中，結(jié)點(diǎn)代表狀態(tài)，用圓圈表示。狀態(tài)之間用箭弧連結(jié)。箭弧上的標(biāo)記（字符、正規(guī)式）代表在射出結(jié)點(diǎn)（即箭符始結(jié)點(diǎn)）狀態(tài)下可能出現(xiàn)的輸入字符或字符類。一張狀態(tài)轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)（即有限個(gè)結(jié)點(diǎn)），其中含有一個(gè)初態(tài)（用雙線箭頭指示）和若干個(gè)終態(tài)（用雙圈表示），而且實(shí)際上至少要有一個(gè)終態(tài)，初態(tài)表示分析的開始，終態(tài)表示分析的結(jié)束。一個(gè)狀態(tài)轉(zhuǎn)換圖可用于識(shí)別（或接受）一定的字符串。15012*字母其它字母或數(shù)字圖A—識(shí)別標(biāo)識(shí)符的轉(zhuǎn)換圖012*數(shù)字其它圖B—識(shí)別整數(shù)的轉(zhuǎn)換圖數(shù)字017*其它圖C—識(shí)別Fortran實(shí)型常數(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)造識(shí)別一種簡(jiǎn)單語言的單詞符號(hào)的轉(zhuǎn)換圖限制條件：（1）所有關(guān)鍵字都是“保留字”，用戶不得使用它們作為自己定義的標(biāo)識(shí)符。（2）關(guān)鍵字作為一類特殊的標(biāo)識(shí)符來處理，不再專門設(shè)置對(duì)應(yīng)的轉(zhuǎn)換圖，把它們預(yù)先安排在一張表格中，當(dāng)轉(zhuǎn)換圖識(shí)別出一個(gè)標(biāo)識(shí)符，就去查詢這張表，確定是否為一個(gè)關(guān)鍵字。（3）如果關(guān)鍵字、標(biāo)識(shí)符和常數(shù)之間沒有確定的運(yùn)算符或界符作間隔，則必須至少用一個(gè)空白符作間隔2**38*121311非*空白字母非字母與數(shù)字字母或數(shù)字?jǐn)?shù)字?jǐn)?shù)字非數(shù)字=+*...，（）其它1819本章教學(xué)線索1詞法分析程序的設(shè)計(jì)2詞法分析器的設(shè)計(jì)3狀態(tài)轉(zhuǎn)換圖4正規(guī)表達(dá)式與有限自動(dòng)機(jī)4.1正規(guī)式與正規(guī)集4.2確定有限自動(dòng)機(jī)（DFA）4.3非確定有限自動(dòng)機(jī)NFA4.4DFAM和NFAM的等價(jià)性4.5正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性4.6正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性5確定有限自動(dòng)機(jī)的化簡(jiǎn)6詞法分析程序的自動(dòng)構(gòu)造工具LEX簡(jiǎn)介204.1正規(guī)式與正規(guī)集4.1.1正規(guī)式與正規(guī)集的定義（概念）（1）ε、Φ都是∑上的正規(guī)式，它們所表示的正規(guī)集分別為{ε}和Φ；（2）任何a∈∑，a是∑上的一個(gè)正規(guī)式，它所表示的正規(guī)集為{a}；（3）如果U、V都是∑上的正規(guī)式，它們所表示的正規(guī)集分別記為L(zhǎng)（U）和L（V），那么，（U|V）、（U*V）和（U）*也是正規(guī)式，它們所表示的正規(guī)集分別為L(zhǎng)（U）∪L（V）、L（U）L（V）和（L（U））*；僅由有限次使用上述步驟而得到的表達(dá)式才是∑上的正規(guī)式；僅由這些正規(guī)式所表示的字集才是∑上的正規(guī)集。21例子：令∑={a，b}，下面是∑上的正規(guī)式和相應(yīng)的正規(guī)集正規(guī)式正規(guī)集ba*∑上所有以b為首后跟任意多個(gè)a的字a(a|b)*∑上所有以a為首的字（a|b）*

(aa|bb)(a|b)*∑上所有含有兩個(gè)相繼的a或兩個(gè)相繼的b的字224.1.2正規(guī)式的數(shù)學(xué)運(yùn)算交換律：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á)式由一個(gè)單字符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），因此，括號(hào)并不改變語言，它們只調(diào)整運(yùn)算的優(yōu)先權(quán)。24需要注意：｜的優(yōu)先權(quán)最低，連結(jié)次之，*則最高。另外還注意到在這個(gè)定義中，5個(gè)符號(hào)|、*、*、（和）都有了元字符的含義。正規(guī)式的連接一般不滿足交換律254.2確定有限自動(dòng)機(jī)（DFA）4.2.1確定有限自動(dòng)機(jī)的定義

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

Ia=ε_(tái)CLOSURE(J)

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

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

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

方法：假設(shè)Σ={a1，a2，a3，…，ak}，構(gòu)造狀態(tài)轉(zhuǎn)化表，表的構(gòu)成：a)每一行包含k+1列，首行首列為ε_(tái)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)換表，將其中的每個(gè)狀態(tài)子集視為新的狀態(tài)，顯然該表唯一的刻畫了一個(gè)DFAM"，該有限自動(dòng)機(jī)的初態(tài)為該表的首行首列，終態(tài)為那些包含原終態(tài)的狀態(tài)子集。顯然L(M")=L(M')=L(M)39例子：p50正規(guī)式（a|b）*（aa|bb）（a|b）*對(duì)應(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)換矩陣：（將第一列從上向下編號(hào)）

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ī)文法與有限自動(dòng)機(jī)的等價(jià)性正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性結(jié)論：對(duì)每個(gè)右線性正規(guī)文法GR或左線性正規(guī)文法GL，都存在一個(gè)有限自動(dòng)機(jī)（FA）M，使得：L（M）=L（G）對(duì)每一個(gè)FAM，都存在一個(gè)右線性正規(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同有限自動(dòng)機(jī)的等價(jià)性（1）設(shè)右線性正規(guī)文法GR=<VT，VN，S，P>。將VN中的每一非終結(jié)符號(hào)視為狀態(tài)符號(hào)，并增加一個(gè)新的終結(jié)狀態(tài)符號(hào)f，f?VN。構(gòu)造有限自動(dòng)機(jī)M=<VN∪{f}，VT

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

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

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

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

49綜合例子：P52~53

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

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

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

方法53（2）設(shè)結(jié)論對(duì)少于i(i≥1)個(gè)運(yùn)算的正規(guī)表達(dá)式r成立。當(dāng)r有i個(gè)運(yùn)算時(shí)，有三種情況：a)r=r1|r2，r2中的運(yùn)算符個(gè)數(shù)少于k。由歸納假設(shè)，對(duì)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è)計(jì)2詞法分析器的設(shè)計(jì)3狀態(tài)轉(zhuǎn)換圖4正規(guī)表達(dá)式與有限自動(dòng)機(jī)5確定有限自動(dòng)機(jī)的化簡(jiǎn)6詞法分析程序的自動(dòng)構(gòu)造工具LEX簡(jiǎn)介575確定有限自動(dòng)機(jī)的化簡(jiǎn)1)確定的有限自動(dòng)機(jī)的化簡(jiǎn)一個(gè)DFAM=(，S，，s0，F(xiàn))的化簡(jiǎn)是指尋找一個(gè)狀態(tài)數(shù)比較少的DFAM′，使L(M)=L(M′)。而且可以證明，存在一個(gè)最少狀態(tài)的DFAM′，使L(M)=L(M′)。2)等價(jià)狀態(tài)的定義設(shè)s，tS，若對(duì)任何w

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