第2講-詞法分析

第二講詞法分析詞法分析器的構(gòu)造正規(guī)表達(dá)式與有窮自動機(jī)詞法分析器的自動產(chǎn)生1CompilerPrinciples§1.詞法分析器的構(gòu)造

編譯程序首先在單詞級別上來分析和翻譯源程序。詞法分析的任務(wù)是：從左至右逐個字符地對源程序進(jìn)行掃描，產(chǎn)生一個個單詞符號，即把作為字符串的源程序改造成為單詞符號串的中間程序。因此，詞法分析是編譯的基礎(chǔ)。執(zhí)行詞法分析的程序稱為詞法分析器(通常又稱為掃描器,scanner）。2CompilerPrinciples一、一般考慮：

1.詞法分析程序的主要任務(wù)：讀入字符串形式的源程序—輸入剔除非單詞符號—空格、換行，注釋宏展開，……拼單詞符號—**、:=、FOR、BEGIN等源程序的列表輸出行號3CompilerPrinciples

2.詞法分析器的輸入和輸出形式輸入—字符串形式的源程序輸出—單詞符號串。程序語言的單詞符號一般分為五種：

關(guān)鍵字、運(yùn)算符、界符、標(biāo)識符、常數(shù)詞法分析器輸出的單詞符號常常表示為二元式：

（單詞種類編號，單詞符號的屬性值）4CompilerPrinciples

單詞種類編號一個語言的單詞符號分成幾種，怎樣編碼是一個技術(shù)性問題，它取決于處理上的方便。標(biāo)識符一般歸為一種。常數(shù)則宜按類型（整、實、布爾、字符等）分種。關(guān)鍵字可視其全體為一種，也可以一字一種。采用一字一種的分法實際處理起來較為方便。運(yùn)算符可采用一符一種的分法，但也可以把具有一定共性的運(yùn)算符視為一種。至于界符一般用一符一種的分法。

5CompilerPrinciples單詞符號的屬性值

如果一個種別只含有一個單詞符號，那么對于這個單詞符號，種別編碼就完全代表它自身了，因此屬性值就沒有意義了。若同一個種別含有多個單詞符號，那麼對于它的每個單詞符號，除了給出種別編碼之外，還應(yīng)給出各有關(guān)單詞符號的屬性信息。

屬性值是反映特性或特征的值。例如，對于某個標(biāo)識符，常將存放它有關(guān)信息的符號表項的指針作為其屬性值；對于某個字符串常量，則將該串的首地址指針作為其屬性值。6CompilerPrinciples作為例子考慮下述C++語句：

while(i>=j)i-

-;

若while種別為01,(種別為11,標(biāo)識符種別為20,>=種別為12,)種別為13,－－種別為14,;種別為30,則經(jīng)詞法分析器處理后，它將被轉(zhuǎn)換為如下的單詞符號序列：

(01,—)(11,—)(20,指向i的符號表項的指針)(12,—)(20,指向j的符號表項的指針)(13,—)(20,指向i的符號表項的指針)(14,—)(30,—)7CompilerPrinciples3.詞法分析器與語法分析器的銜接

通常把詞法分析器安排成一個獨立子程序，而不是單獨的一遍。這樣一來，就無須在存儲器中保留整個單詞符號串，而是每當(dāng)語法分析器需要單詞符號時就調(diào)用這個子程序。每一次調(diào)用，詞法分析器就從源程序字符串中識別出一個（一批）單詞符號，把它交給語法分析器。這樣做的好處是：壓縮編譯時掃描字符的時間詞法規(guī)則描述簡單，也便于獨立處理；使得語法分析獲得更多信息（上下文環(huán)境）；便于處理同一語言的幾種不同表示形式（擴(kuò)展）；

8CompilerPrinciples由以上考慮，可以初步設(shè)計為：源程序掃描器語法分析器取符號送符號9CompilerPrinciples二、進(jìn)一步考慮：

1.輸入、預(yù)處理

輸入串一般放在一個緩沖區(qū)中，這個緩沖區(qū)稱源程序輸入緩沖區(qū)。詞法分析器的工作可以直接在這個緩沖區(qū)中進(jìn)行。但在許多情況下，把輸入串預(yù)處理一下，對單詞符號的識別工作將是比較方便的。預(yù)處理工作包括對空白符、跳格符、回車符和換行符等編輯性字符的處理，及刪除注釋等。于是可以設(shè)想構(gòu)造一個預(yù)處理子程序，它完成上面的工作。每當(dāng)詞法分析器調(diào)用它時就處理出一串確定長度的輸入字符，并將其裝入詞法分析器所指定的緩沖區(qū)中（稱為掃描緩沖區(qū)）。這樣分析器就可以在此緩沖區(qū)中直接而方便地進(jìn)行單詞符號的識別工作。10CompilerPrinciples2.對半互補(bǔ)緩沖區(qū)

分析器對掃描緩沖區(qū)進(jìn)行掃描時一般使用兩個指示器，一個指向當(dāng)前正在識別單詞的開始位置（指向新單詞的首字符），另一個用于向前搜索以尋找單詞的終點。但是不論掃描緩沖區(qū)設(shè)得多大都不能保證單詞符號不會被緩沖區(qū)的邊界所打斷。因此，掃描緩沖區(qū)最好使用一分為二的區(qū)域，并使兩區(qū)首尾相接，形成一個對半互補(bǔ)緩沖區(qū)。

11CompilerPrinciples例如：

。。。。。。While。。。。。。

起點指針?biāo)阉髦羔?2CompilerPrinciples符號表單詞符號掃描器預(yù)處理子程序輸入緩沖區(qū)源程序掃描

緩沖區(qū)語法分析器取單詞

綜上所述，預(yù)處理子程序、掃描器和語法分析器相互之間的關(guān)系及工作情況可圖示如下：

13CompilerPrinciples3.單詞符號識別－超前搜索技術(shù)

問題發(fā)生在對基本字不加任何保護(hù)的語言中，基本字及用戶自定義的標(biāo)識符或標(biāo)號之間無特殊分界符，這使得關(guān)鍵字的識別甚為麻煩。

請看下面的例子：

1DO99K=1,102IF(5.EQ.M)I=103DO99K=1.104IF(5)=55

這四個語句都是正確的FORTRAN語句。語句1和2分別是DO和IF語句，它們都是以某基本字開頭的。語句3和4是賦值語句，它們都是以用戶自定義的標(biāo)識符開頭的。14CompilerPrinciples

為了從1、2中識別出關(guān)鍵字DO和IF，我們必須要能夠區(qū)別1、3和區(qū)別2、4。語句1、3的區(qū)別在于等號之后的第一個界符：一個為逗號，另一個為小數(shù)點，語句2、4的主要區(qū)別在于右括號后的第一個字符：一個為字母，另一個為等號。這就是說，為了識別1、2句中的關(guān)鍵字，我們必須超前掃描許多個字符，超前到能夠肯定詞性的地方為止。這種向前掃描若干字符直到找到能區(qū)分單詞的字符為止的技術(shù)就叫超前搜索。15CompilerPrinciples單一符號運(yùn)算符和復(fù)合運(yùn)算符：思考：如何從程序中刪除注釋：/**/16CompilerPrinciples17CompilerPrinciples4.詞法錯誤如果沒有其他組件的幫助，詞法分析器很難發(fā)現(xiàn)源代碼中的錯誤。18CompilerPrinciples[例]在TurboC下運(yùn)行下面的C程序

1intmain(){2intx=3;3 if(x%2==0)/*evennumber*/4 return0;5else/*oddnumber*/6 return1;7}19CompilerPrinciples如果把if寫成iif，則編譯得到以下2條錯誤信息：

Error…4:Statementmissing;infunctionmain.

Error…5:Misplacedelseinfunctionmain.如果把else寫成els，則編譯得到以下3條錯誤信息：

Error…6:Undefinedsymbol‘els’infunctionmain.Warning…6:Codehasnoeffectinfunctionmain.Error…6:Statementmissing;infunctionmain.

20CompilerPrinciples現(xiàn)在有關(guān)掃描器的輸入、處理、輸出等問題都清楚了，可以進(jìn)行掃描器的設(shè)計了。為此，引入一種新的圖形工具--狀態(tài)轉(zhuǎn)換圖。

1.

狀態(tài)轉(zhuǎn)換圖是一張有限個結(jié)點的有向圖，結(jié)點代表狀態(tài)，用圓圈表示，狀態(tài)之間用帶標(biāo)識的箭弧連結(jié)，箭弧上的標(biāo)識代表在射出結(jié)點（即箭弧始結(jié)點）狀態(tài)下可能出現(xiàn)的輸入字符或字符類。三、狀態(tài)轉(zhuǎn)換圖21CompilerPrinciples

如右圖所示：在狀態(tài)1下，若輸入字符為a，則讀進(jìn)a，并轉(zhuǎn)換到狀態(tài)2。若輸入字符為b，則讀進(jìn)b，并轉(zhuǎn)換到狀態(tài)3。一張轉(zhuǎn)換圖只包含有限個狀態(tài)（即有限個結(jié)點），其中有一個被認(rèn)為是初態(tài)，而且實際上至少要有一個終態(tài)（用雙圈表示），圖中3為終態(tài)。狀態(tài)轉(zhuǎn)換圖①②③ab22CompilerPrinciples2.狀態(tài)轉(zhuǎn)換圖可用來識別一定的字符串例如：

<標(biāo)識符>→字母|<標(biāo)識符>字母|<標(biāo)識符>數(shù)字

<整數(shù)>→數(shù)字|<整數(shù)>數(shù)字

終態(tài)上打個*號，表示多讀進(jìn)了一個不屬于該標(biāo)識符或數(shù)字部分的字符，應(yīng)把它退還給輸入串。012字母字母或數(shù)字其他**012數(shù)字?jǐn)?shù)字其他23CompilerPrinciples*01234576數(shù)字?jǐn)?shù)字··數(shù)字E或DE或D+或-數(shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字其它其它上圖是識別Fortran實常數(shù)的轉(zhuǎn)換圖思考：結(jié)合前面的思考題，作出能夠識別注釋的狀態(tài)轉(zhuǎn)換圖：/**/和//...24CompilerPrinciples3.狀態(tài)轉(zhuǎn)換圖可以用來識別程序語言的單詞符號

例：假設(shè)某程序語言只有前述的五類單詞符號，運(yùn)算符只有+、*、=，界符只有#、(、)，那么就可以用左邊的狀態(tài)轉(zhuǎn)換圖來識別其所有單詞符號。0→1→2識別的串是基本字還是標(biāo)識符，要查保留字表區(qū)分。

當(dāng)然，還要加上兩個限制：(1)所有基本字都是保留的；(2)所有單詞間若無明顯分界，則用空格分開；空白字母或數(shù)字01245678931011字母非字母與數(shù)字?jǐn)?shù)字非數(shù)字?jǐn)?shù)字=+*#（）其它**25CompilerPrinciples4.狀態(tài)轉(zhuǎn)換圖的程序?qū)崿F(xiàn)為每個狀態(tài)編寫一小段程序即可例：使用如下一組全局變量和過程，作為實現(xiàn)狀態(tài)轉(zhuǎn)換圖的基本部分：⑴CHAR：字符變量，存放最新讀進(jìn)的源程序字符；⑵Token：字符數(shù)組，存放構(gòu)成單詞符號的符號串；⑶GetChar：取字符過程，將下一個輸入字符讀到CHAR中，并把搜索指示器的指針前移一個字符位置；⑷GetBC：檢查CHAR中的字符是否為空白，若是則調(diào)用GetChar直至CHAR中進(jìn)入一個非空白字符；⑸ConCat：拼單詞過程，每調(diào)用一次就將CHAR中的字符連接到Token之后；26CompilerPrinciples⑹IsLetter和IsDigit：兩個布爾函數(shù)，分別判斷CHAR中的字符為字母或是數(shù)字而返回真假值；⑺Reserve：整型函數(shù)，對Token中的字符串查保留字表，查到則返回該保留字的整型編碼，否則返回0值；⑻Retract：回退子程序，專門用來把搜索指示器回調(diào)一個字符位置，并置CHAR為空；⑼Error：出錯處理子程序；⑽DTB：類型轉(zhuǎn)換函數(shù)，將Token中的十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)；于是，可編出如下程序：⊙Start:Token:=‘’;GetChar;GetBC;

27CompilerPrinciplesCASECHAROF‘A…z’:BEGINWHILEIsLetterORIsDigitDOBEGINConCat;GetCharEND;

Retract;C:=Reserve;IFC=0THENReturn($ID,Token)ELSEReturn(C,─)

END;‘0…9’:BEGINWHILEIsDigitDOBEGINConCat;GetCharEND;Retract;Return($INT,DTB)

END;

‘=‘:Return($ASSIGN,─);

‘+‘:Return($PLUS,─);

‘*‘:Return($START,─);

‘(‘:Return($LPAR,─);

‘)‘:Return($RPAR,─);‘#‘:Return($,─);

ENDOFCASE;DealError;GotoStart;

28CompilerPrinciples§2.正規(guī)表達(dá)式與有窮自動機(jī)

RegularExpressionandFiniteAutomata

上一節(jié)我們討論了掃描器的手工編制，是在討論了Scanner的主要工作拼單詞符號并進(jìn)行相應(yīng)的詞法檢查的基礎(chǔ)上，通過構(gòu)造狀態(tài)轉(zhuǎn)換圖再轉(zhuǎn)換為程序代碼來實現(xiàn)的。本節(jié)要進(jìn)一步討論兩個抽象的工具，以便研究詞法分析程序的自動生成問題。由于我們集中注意力于掃描器的自動生成，故對有關(guān)結(jié)論一般不加形式證明，大家若對這方面感興趣，可以查閱相關(guān)書籍，如《形式語言與自動機(jī)》（FormalLanguage&Automata）。

29CompilerPrinciples我們知道，任何高級程序設(shè)計語言都有自己的字母表，但并非字母表上的任何字符串都能稱為一個程序，我們感興趣的是能稱為程序的那些串，它們的集合稱為正規(guī)集。正規(guī)式是說明單詞的模式(pattern)的一種重要的表示法（記號），是定義正規(guī)集的數(shù)學(xué)工具，可用以描述單詞符號。這同樣是一個無窮語言的有窮描述的問題。1.正規(guī)式(RE)的定義：這是一種與我們以前常見的算術(shù)、邏輯等表達(dá)式不同的表達(dá)式。設(shè)Σ為字母表，⑴ε是

Σ上的正規(guī)式，它所表示的正規(guī)集分別為{ε}；⑵對于任何aΣ,a都是Σ上的一個正規(guī)式，它所表示的正規(guī)集為{a}；一、正規(guī)表達(dá)式和正規(guī)集30CompilerPrinciples⑶假定U和V都是Σ上的正規(guī)式，它們所表示的正規(guī)集分別記為L(U)和L(V),那么，(U|V),(UV)和(U)*也都是正規(guī)式，它們所表示的正規(guī)集分別為L(U)∪L(V),L(U)L(V)(連接積）和(L(U))*（閉包）。

僅由有限次使用上述三步驟而得到的表達(dá)式才是Σ上的正規(guī)式。僅由這些正規(guī)式所表示的字集才是Σ上的正規(guī)集。*這個定義本身是構(gòu)造型的，今后我們應(yīng)該習(xí)慣這種構(gòu)造型定義及證明方式。31CompilerPrinciples2.正規(guī)表達(dá)式的運(yùn)算順序：

括號→*（閉包）→·（連接）→∣（或）例1：Σ={a,b}?！遖,b都是正規(guī)式∴a*是正規(guī)式。

ba*也是正規(guī)式，它所表示的正規(guī)集為：{b,ba,baa,……}，也就是Σ上所有以b為首后跟著任意多個a的字。同樣，a(a|b)*

亦為Σ上的正規(guī)式，其所表示的正規(guī)集為Σ上所有以a為首的字；(a|b)*(aa|bb)(a|b)*

對應(yīng)的正規(guī)集是所有含有兩個相繼的a或相繼的b的字。

32CompilerPrinciples3.正規(guī)表達(dá)式的等價：若兩個正規(guī)式所表示的正規(guī)集相同，則認(rèn)為二者等價，記為‘=’。例：Σ={a,b}

∵L(b(ab)*)={b,bab,babab,…}L((ba)*b)={b,bab,babab,…}

∴b(ab)*=(ba)*b33CompilerPrinciples4.正規(guī)表達(dá)式的運(yùn)算律：

U∣V=V∣U（交換律）U∣(V∣W)=(U∣V)∣W（結(jié)合律）U(VW)=(UV)W（結(jié)合律）U(V∣W)=UV∣UW（分配律）(U∣V)W=UW∣VW（分配律）

εU=Uε=U（幺元）(R*)*=R*（冪等律）?思考：證明？34CompilerPrinciples5.標(biāo)識符的正規(guī)式 letter ->A|B|...|Z|a|b|...|z|_ digit ->0|1|...|9 id ->letter(letter|digit)*

擴(kuò)展寫法： letter ->[A-Za-z_] digit ->[0-9] id ->letter(letter|digit)*

35CompilerPrinciples練習(xí)：P72~78.3.2.2(1)~(4),3.2.5(3)3.2.11,3.2.1236CompilerPrinciples二、確定的有窮自動機(jī)（DFA)1.問題的提出：上節(jié)我們介紹了狀態(tài)轉(zhuǎn)換圖：

我們也可以寫：S0→aS1:δ(S0,a)=S1

S1→bS2:δ(S1,b)=S2

……于是我們可以認(rèn)為所有狀態(tài)構(gòu)成一個集合S，所有弧的標(biāo)識構(gòu)成一個集合Σ，函數(shù)δ，起始狀態(tài)S0和所有終態(tài)構(gòu)成的集合F。這樣我們可以把狀態(tài)轉(zhuǎn)換圖形式化為如下的數(shù)學(xué)系統(tǒng)—DFA。S0SnS1S2ab37CompilerPrinciples38CompilerPrinciples3.DFA的表示形式：由前所述，DFA是狀態(tài)轉(zhuǎn)換圖的抽象模型。顯然DFA也可以表示成一張（確定的）狀態(tài)轉(zhuǎn)換圖，它們是一一對應(yīng)的。假定DFAM含有m個狀態(tài)、n個輸入字符，那末，這張圖含有m個狀態(tài)結(jié)點，每個結(jié)點頂多有n條箭弧射出和別的結(jié)點相連接，每條箭弧用上的一個字符作標(biāo)記，整張圖含有唯一的初態(tài)和若干個（可以是0個）終態(tài)結(jié)點。

39CompilerPrinciplesDFA還可以用一個矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示δ(s,a）的值，該矩陣稱為狀態(tài)轉(zhuǎn)換矩陣。3012abababa,b狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換矩陣40CompilerPrinciples

對于*中的任何一個字符串，若存在一條從初態(tài)結(jié)點到某一終態(tài)結(jié)點的通路，且這條通路上所有箭弧的標(biāo)記符連接成的字等于，則稱為DFAM所識別（讀出或接受）。若M的初態(tài)結(jié)點同時又是終態(tài)結(jié)點，則空字可以為M所識別。DFAM所能識別的字的全體記為L(M).DFA的確定性表現(xiàn)在δ是一個從Sx→S的單值部分映射。也就是說，對任何狀態(tài)sS和輸入符號aΣ，δ(s,a)唯一地確定了下一個狀態(tài)。從狀態(tài)轉(zhuǎn)換圖的角度來看，任何狀態(tài)發(fā)出的弧具有不同的標(biāo)識。

41CompilerPrinciples例：DFAM=({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)=3問：有幾個狀態(tài),幾個輸入字符？并畫出其轉(zhuǎn)換圖。L(M)=?解：有0，1，2，3共四個狀態(tài)。輸入字符為a,b兩個。其狀態(tài)轉(zhuǎn)換圖如右L(M)為在上含相繼兩個a或相繼兩個b的字的集合。012abababa,b342CompilerPrinciples43CompilerPrinciples

顯然，NFA也可以表示成一張狀態(tài)轉(zhuǎn)換圖。假定NFA含有m個狀態(tài)、n個輸入字符，那么，這張圖含有m個狀態(tài)結(jié)點，每個結(jié)點可以射出若干條箭弧和別的結(jié)點相連接，每條箭弧用*上的一個字（不一定要不同的字而且可以是空字）作標(biāo)記（稱為輸入字），整張圖至少含有一個初態(tài)和若干個（可以是0個）終態(tài)結(jié)點。某些結(jié)點既可以是初態(tài)也可以是終態(tài)結(jié)點。對于*中的任何一個字符串，若存在一條從初態(tài)結(jié)點到某一終態(tài)結(jié)點的通路，且這條通路上所有箭弧的標(biāo)記符連接成的字（忽略那些標(biāo)記為的弧）等于，則稱為NFAM所識別。也就是：δ(S0,)∩F≠φ。若M的初態(tài)結(jié)點同時又是終態(tài)結(jié)點，或者存在一條某初態(tài)結(jié)點到某各終態(tài)結(jié)點的通路，則空字可以為M所識別。44CompilerPrinciples例：M=({0,1,2,3,4},{a,b},δ,{0},{2,4})，其中δ：

δ(0,a)={0,3},δ(1,a)=φ,δ(2,a)={2},

δ(3,a)={4},δ(4,a)={4},δ(0,b)={0,1},

δ(1,b)={2},δ(2,b)={2},δ(3,b)=φ,

δ(4,b)={4}03142a,ba,ba,baabb它能接受：所有含有兩個連續(xù)的a或兩個連續(xù)的b的串45CompilerPrinciples2.有窮自動機(jī)的等價：對于任何兩個有窮自動機(jī)M和M′，如果L(M)=L(M′)，則稱M和M′是等價的。對此我們有一個重要結(jié)論：判定任何兩個有窮自動機(jī)等價的算法是存在的。46CompilerPrinciples四、正規(guī)式與有窮自動機(jī)的等價性：

我們先來證明兩個重要的事實：1.定理1：Σ上的有窮自動機(jī)所接受的字的全體L(M)是Σ上的一個正規(guī)集。(1)一般考慮：要證明L(M)是Σ上的一個正規(guī)集，很容易想到正規(guī)式。因為正規(guī)集是正規(guī)式的值。同時我們又知道任何一個

FAM都可以表示成一個狀態(tài)轉(zhuǎn)換圖，而該圖中從某個初態(tài)結(jié)點到某個終態(tài)結(jié)點的路上所有弧的標(biāo)記連接而成的串，恰恰就是L(M)的一個字，L(M)就是這樣一些字的全體，于是我們想，是否能構(gòu)造一個正規(guī)表達(dá)式V，使得L(V)=L(M)呢？如果能構(gòu)造出這樣的一個V，問題也就解決了。為此，我們把轉(zhuǎn)換圖的概念加以拓廣，使每條弧可以用一個正規(guī)式來標(biāo)記，如，這樣我們就可以借助M來構(gòu)造V了。01a∣b47CompilerPrinciples(2)證明（簡略）：a.在NFAM的狀態(tài)轉(zhuǎn)換圖上加入唯一的初態(tài)X和終態(tài)Y，從X到M原來的每個初態(tài)用標(biāo)有ε的弧相連接，而每個原終態(tài)則用標(biāo)有ε的弧與Y相連接。顯然這樣的NFAM與NFAM′是等價的—L(M′)=L(M)。b.反復(fù)使用以下規(guī)則對M′中的所有狀態(tài)進(jìn)行逐步消去：

123V1V213V1V212V1V212V1∣V2123V1V2V313V1V2*V3由于M′的狀態(tài)集是有限的，因此經(jīng)過有限次使用上述規(guī)則，必然得到

，顯然L(V)=L（M′）=L（M）。

對于NFA的情況具有一般性，若用DFAM則更簡單。XYV48CompilerPrinciples①②③④abababa,b例：③bbab②①XYaaεεa,b拓廣①②③XεεYaabb④④(ba)*(ab)*Xε①④εYa(ba)*(a∣bb)b(ab)*(b∣aa)XY(a(ba)*(a∣bb)∣b(ab)*(b∣aa))(a∣b)*a,ba,b這樣就得到了與所給DFA等價的正規(guī)式。49CompilerPrinciples2.定理2：對于Σ上的每個正規(guī)表達(dá)式V，存在一個Σ上的DFAM，使得L(M)=L(V)。(1)一般考慮：由定理1的證明，我們很容易想到，對Σ上的每個正規(guī)式V，可以畫出拓廣轉(zhuǎn)換圖：然后我們與逐次減少結(jié)點過程相反，可以對V逐次分裂并加入新結(jié)點和弧，直到每條弧的標(biāo)記或者為Σ中的一個符號，或者為ε，這樣就構(gòu)造了一個轉(zhuǎn)換圖，也就是一個NFAM′,然后再把M′確定化為DFA就可以了。XYV50CompilerPrinciples(2)證明：

a.把正規(guī)式V表示成拓廣轉(zhuǎn)換圖

b.根據(jù)以下規(guī)則分裂V并加入新狀態(tài)結(jié)點和標(biāo)識弧

整個分裂過程保持和為唯一初態(tài)和終態(tài)，由正規(guī)式定義，顯然經(jīng)過有限次分裂就可以構(gòu)造出一個NFAM′使得L(M′)=L(V)。XYVXYijABijA∣BijA*ikjABijABikjεεA51CompilerPrinciples

c.對NFAM′確定化—構(gòu)造一個DFAM使得L(M)=L(M′)

＊一般考慮：變多值映射為單值映射，可采用子集法。NFA不確定的原因主要在于含有ε弧和從某結(jié)點經(jīng)由相同標(biāo)識的弧而到達(dá)不同的結(jié)點——結(jié)點集。這兩個問題解決了，NFA也就確定了。①預(yù)備定義1：狀態(tài)集I的ε閉包，記為

ε_CLOSURE(I),如下定義：ⅰ.若s∈I,則s∈ε_CLOSURE(I)；ⅱ.若s∈I，則由s出發(fā)經(jīng)任意條ε弧而能夠到

達(dá)的任何狀態(tài)s′∈ε_CLOSURE(I)；②預(yù)備定義2：對狀態(tài)集I和a∈Σ，定義Ia=ε_CLOSURE(J)；其中J是那些可從I中某一結(jié)點出發(fā)經(jīng)過一條a弧而到達(dá)的狀態(tài)結(jié)點的全體。52CompilerPrinciples設(shè)I={1}，則由I經(jīng)一條a弧而到達(dá)的狀態(tài)結(jié)點的全體J={5,3,4}，從而Ia=ε_CLOSURE(J)={5,6,2,3,8,4,7}例：狀態(tài)轉(zhuǎn)換圖如下：①⑤②④⑥③⑧⑦aaaεεεεε53CompilerPrinciples

③M′的確定化：從以上所談不難看出確定化的復(fù)雜程度與符號個數(shù)密切相關(guān)，為此我們設(shè)Σ={a,b}，并依如下過程構(gòu)造一個轉(zhuǎn)換矩陣。該矩陣有三列，分別記為I,Ia,Ib，第一行第一列置為ε_CLOSURE({X})，其中X為M′的初態(tài)集。由此我們就可以根據(jù)預(yù)備定義構(gòu)造Ia和Ib，然后檢查Ia、Ib中是否有不同于已構(gòu)造出的I的，若有則將其作為新的I，又可以構(gòu)造新的Ia和Ib。依次下去，直到不再有新的狀態(tài)子集出現(xiàn)為止。因為M′的狀態(tài)數(shù)是有限的，故上述過程必在有限步內(nèi)停止。把上述表中第一列的狀態(tài)子集進(jìn)行編號，最終可得到一個狀態(tài)矩陣，該矩陣唯一地畫出了一個確定的有窮自動機(jī)M，其唯一初態(tài)為ε_CLOSURE({X})，終態(tài)是那些含有M′的終態(tài)Y的子集。由上述構(gòu)造過程不難看出：L(M)=L(M′),于是達(dá)到了確定化的目的。54CompilerPrinciples例:設(shè)V=(a|b)*(aa|bb)(a|b)*(1)構(gòu)造NFAM′XY(a|b)*(aa|bb)(a|b)*①③④εεaabb②a,bXY⑤a,bε⑥ε(2)構(gòu)造狀態(tài)轉(zhuǎn)換矩陣012345655CompilerPrinciples(3)重新編號的狀態(tài)矩陣:(4)DFAM的狀態(tài)轉(zhuǎn)換圖為:b(5)DFAM=({0,1,2,3,4,5,6},{a,b},δ,0,{3,4,5,6}),其中δ如左上表所示。a0123456aaaaaabbbbbb56CompilerPrinciples3.推論1：一個字集V是正規(guī)的當(dāng)且僅當(dāng)有一自動機(jī)M,使得L(M)=L(V)。推論2：NFA與DFA接收相同的集合。

[定理]：推論2也可作為一個定理來證明：若L(M)被NFAM接受，則必定存在一個DFAM′接受L(M)。

證明過程不再介紹，感興趣者可以嘗試用構(gòu)造法加歸納法來證明。

57CompilerPrinciples五、DFA的化簡所謂對一個DFAM的化簡，就是找一個DFAM′，使得L(M)=L(M′)但是M′的狀態(tài)數(shù)比M少。1.等價狀態(tài)和可區(qū)別狀態(tài)：若分別從狀態(tài)s和t出發(fā)而停于終態(tài)能讀出同一個字α，則稱s,t為等價狀態(tài)；不等價的兩個狀態(tài)稱為可區(qū)別狀態(tài)。a0st12zaabaabb58CompilerPrinciples2.狀態(tài)的最小化過程所謂DFAM的狀態(tài)最小化過程就是找一個最少狀態(tài)的DFAM′使得L(M)=L(M′)。具體做法：把DFAM的狀態(tài)集分割成一些不相交的子集，使得不同的兩個子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個狀態(tài)都是等價的，最后讓每個子集選出一個代表，把所有與該子集相關(guān)的弧都與該代表相連接，并消去其他等價狀態(tài)，即可求得最少狀態(tài)的DFAM′。59CompilerPrinciples3.例：DFAM=({0,1,2,3,45,6},{a,b},δ,0,{3,4,5,6})其中δ：δ(0,a)=1,δ(0,b)=2,δ(1,a)=3,δ(1,b)=2,

δ(2,a)=1,δ(2,b)=4,δ(3,a)=3,δ(3,b)=5,

δ(4,a)=6,δ(4,b)=4,δ(5,a)=6,δ(5,b)=4,

δ(6,a)=3,δ(6,b)=5.狀態(tài)圖：0123456aaaaaabbbbbba（1）形成基本分劃π─分成兩個子集:非終態(tài)子集I(1)和終態(tài)子集I(2)即：I(1)＝{0,1,2}I(2)={3,4,5,6}b60CompilerPrinciples(2)對每個子集I(i)和每個a∈Σ,來考察Ia(i)是否包含在某個I(j)中(j=1,2,…n)，若不是完全包含在某個I(j)中則至少可一分為二，形成新的分劃。例：Ia(1)＝{0,1,2}a={1,3}而{1,3}不在π的任一子集中，故應(yīng)分割。又因{0,2}a={1}，故分成{0,2}和{1}，顯然{1}是不能再分割的了。至此得到：

π′={{0,2},{1},{3,4,5,6}}(3)重復(fù)(2)的工作直到所有子集不能再分割為止。

{0,2}b={2,4}不在任一子集中，故一分為二得:π′={{0},{1},{2},{3,4,5,6}}，而{3,4,5,6}a={3,6}{3,4,5,6},{3,4,5,6}b={5,4}{3,4,5,6},不能再分割了。所以最后的分劃:

π={{0},{1},{2},{3,4,5,6}}。61CompilerPrinciples(4)選等價狀態(tài)子集的代表，并重構(gòu)狀態(tài)圖。

如{3,4,5,6}的代表為{3}，可得狀態(tài)圖：02b13abba,baa(5)最后可得最少狀態(tài)自動機(jī)為：DFAM′=({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)=3.62CompilerPrinciplesRGDFANFAε-NFARE總結(jié)：

正規(guī)語言的描述模型63CompilerPrinciples§3.詞法分析器的自動產(chǎn)生

前面我們已經(jīng)談了狀態(tài)轉(zhuǎn)換圖可以用來識別單詞符號，DFA可以用一張確定的狀態(tài)轉(zhuǎn)換圖來表示，而DFA又與正規(guī)式等價，所以我們可以用正規(guī)式來描述程序語言的詞法規(guī)則。而從正規(guī)式到自動機(jī)（狀態(tài)圖）再到程序的轉(zhuǎn)換工作，可以交予一個程序來自動生成。這類程序就是詞法分析器的自動生成器。參考書3.4節(jié)介紹的Lex(Flex)就是其中典型的代表。此處不再贅述。

64CompilerPrinciples小結(jié)本講內(nèi)容：

★詞法分析器的構(gòu)造

★狀態(tài)轉(zhuǎn)換圖★正規(guī)表達(dá)式與正規(guī)集★DFA與NFA★RE,RG,DFA,NFA的等價關(guān)系★DFA的最小化65CompilerPrinciples

功能：分割字符串形式的源程序，得到單詞符號串輸入：字符串形式的源程序輸出：單詞符號串（二元式）分析技術(shù)超前搜索對半互補(bǔ)緩沖區(qū)預(yù)處理子程序設(shè)計獨立子程序狀態(tài)轉(zhuǎn)換圖─最小化DFA的狀態(tài)轉(zhuǎn)換圖

實現(xiàn)：最小化的DFA的每個狀態(tài)對應(yīng)一小段程序詞法分析器RERGA→Ba∣aA→aB∣aNFADFA最小化DFA轉(zhuǎn)換規(guī)則增加開始狀態(tài)增加終止?fàn)顟B(tài)確定化劃分等價類66CompilerPrinciples例題與解答[例1]寫出產(chǎn)生語言：{能被5整除的十進(jìn)制整數(shù)}的文法及正則表達(dá)式。解：能被5整除的正則表達(dá)式：

(+|-)A*(0|5)

A∈{0,1,2,3,4,5,6,7,8,9}如果要求除零以外不以0開頭，則文法為：G[Z]:Z→XAD

|D|-5A→AB|CB→0|C|BBC→1|2|3|4|5|6|7|8|9D→0|5X→+|-67CompilerPrinciples[例2]寫一個文法，使其語言是奇數(shù)集，且每個奇數(shù)不以0開頭。解：文法G(N)：

N→AB|B

A→AC|D

B→1|3|5|7|9

D→B|2|4|6|8

C→0|D

68CompilerPrinciples[例3]寫出能被3整除十進(jìn)制整數(shù)的文法和正則表達(dá)式：解：能被3整除的文法：G=({0,1,2,3,4,5,6,7,8,9},{S,A,B},S,P),其中P為：S→(0|3|6|9)S|εS→(1|4|7)A|(2|5|8)BA→(0|3|6|9)A|(1|4|7)B|(2|5|8)SB→(0|3|6|9)B|(2|5|8)A|(1|4|7)S正則表達(dá)式：

Z=a*|(bc)*|(cb)*|(a|cibi)*|(ci