第2講-詞法分析

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

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

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

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

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

（單詞種類編號(hào)，單詞符號(hào)的屬性值）4CompilerPrinciples

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

5CompilerPrinciples單詞符號(hào)的屬性值

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

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

while(i>=j)i-

-;

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

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

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

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

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

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

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

11CompilerPrinciples例如：

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

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

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

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

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

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

請(qǐng)看下面的例子：

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

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

為了從1、2中識(shí)別出關(guān)鍵字DO和IF，我們必須要能夠區(qū)別1、3和區(qū)別2、4。語(yǔ)句1、3的區(qū)別在于等號(hào)之后的第一個(gè)界符：一個(gè)為逗號(hào)，另一個(gè)為小數(shù)點(diǎn)，語(yǔ)句2、4的主要區(qū)別在于右括號(hào)后的第一個(gè)字符：一個(gè)為字母，另一個(gè)為等號(hào)。這就是說(shuō)，為了識(shí)別1、2句中的關(guān)鍵字，我們必須超前掃描許多個(gè)字符，超前到能夠肯定詞性的地方為止。這種向前掃描若干字符直到找到能區(qū)分單詞的字符為止的技術(shù)就叫超前搜索。15CompilerPrinciples單一符號(hào)運(yùn)算符和復(fù)合運(yùn)算符：思考：如何從程序中刪除注釋：/**/16CompilerPrinciples17CompilerPrinciples4.詞法錯(cuò)誤如果沒(méi)有其他組件的幫助，詞法分析器很難發(fā)現(xiàn)源代碼中的錯(cuò)誤。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條錯(cuò)誤信息：

Error…4:Statementmissing;infunctionmain.

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

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

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

1.

狀態(tài)轉(zhuǎn)換圖是一張有限個(gè)結(jié)點(diǎn)的有向圖，結(jié)點(diǎn)代表狀態(tài)，用圓圈表示，狀態(tài)之間用帶標(biāo)識(shí)的箭弧連結(jié)，箭弧上的標(biāo)識(shí)代表在射出結(jié)點(diǎn)（即箭弧始結(jié)點(diǎn)）狀態(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)換圖只包含有限個(gè)狀態(tài)（即有限個(gè)結(jié)點(diǎn)），其中有一個(gè)被認(rèn)為是初態(tài)，而且實(shí)際上至少要有一個(gè)終態(tài)（用雙圈表示），圖中3為終態(tài)。狀態(tài)轉(zhuǎn)換圖①②③ab22CompilerPrinciples2.狀態(tài)轉(zhuǎn)換圖可用來(lái)識(shí)別一定的字符串例如：

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

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

終態(tài)上打個(gè)*號(hào)，表示多讀進(jìn)了一個(gè)不屬于該標(biāo)識(shí)符或數(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ù)字其它其它上圖是識(shí)別Fortran實(shí)常數(shù)的轉(zhuǎn)換圖思考：結(jié)合前面的思考題，作出能夠識(shí)別注釋的狀態(tài)轉(zhuǎn)換圖：/**/和//...24CompilerPrinciples3.狀態(tài)轉(zhuǎn)換圖可以用來(lái)識(shí)別程序語(yǔ)言的單詞符號(hào)

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

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

RegularExpressionandFiniteAutomata

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

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

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

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

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

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

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

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

32CompilerPrinciples3.正規(guī)表達(dá)式的等價(jià)：若兩個(gè)正規(guī)式所表示的正規(guī)集相同，則認(rèn)為二者等價(jià)，記為‘=’。例：Σ={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)識(shí)符的正規(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二、確定的有窮自動(dòng)機(jī)（DFA)1.問(wèn)題的提出：上節(jié)我們介紹了狀態(tài)轉(zhuǎn)換圖：

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

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

……于是我們可以認(rèn)為所有狀態(tài)構(gòu)成一個(gè)集合S，所有弧的標(biāo)識(shí)構(gòu)成一個(gè)集合Σ，函數(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)換圖，它們是一一對(duì)應(yīng)的。假定DFAM含有m個(gè)狀態(tài)、n個(gè)輸入字符，那末，這張圖含有m個(gè)狀態(tài)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)頂多有n條箭弧射出和別的結(jié)點(diǎn)相連接，每條箭弧用上的一個(gè)字符作標(biāo)記，整張圖含有唯一的初態(tài)和若干個(gè)（可以是0個(gè)）終態(tài)結(jié)點(diǎn)。

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

對(duì)于*中的任何一個(gè)字符串，若存在一條從初態(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)，則空字可以為M所識(shí)別。DFAM所能識(shí)別的字的全體記為L(zhǎng)(M).DFA的確定性表現(xiàn)在δ是一個(gè)從Sx→S的單值部分映射。也就是說(shuō)，對(duì)任何狀態(tài)sS和輸入符號(hào)aΣ，δ(s,a)唯一地確定了下一個(gè)狀態(tài)。從狀態(tài)轉(zhuǎn)換圖的角度來(lái)看，任何狀態(tài)發(fā)出的弧具有不同的標(biāo)識(shí)。

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

顯然，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)。對(duì)于*中的任何一個(gè)字符串，若存在一條從初態(tài)結(jié)點(diǎn)到某一終態(tài)結(jié)點(diǎn)的通路，且這條通路上所有箭弧的標(biāo)記符連接成的字（忽略那些標(biāo)記為的?。┑扔?，則稱為NFAM所識(shí)別。也就是：δ(S0,)∩F≠φ。若M的初態(tài)結(jié)點(diǎn)同時(shí)又是終態(tài)結(jié)點(diǎn)，或者存在一條某初態(tài)結(jié)點(diǎn)到某各終態(tài)結(jié)點(diǎn)的通路，則空字可以為M所識(shí)別。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它能接受：所有含有兩個(gè)連續(xù)的a或兩個(gè)連續(xù)的b的串45CompilerPrinciples2.有窮自動(dòng)機(jī)的等價(jià)：對(duì)于任何兩個(gè)有窮自動(dòng)機(jī)M和M′，如果L(M)=L(M′)，則稱M和M′是等價(jià)的。對(duì)此我們有一個(gè)重要結(jié)論：判定任何兩個(gè)有窮自動(dòng)機(jī)等價(jià)的算法是存在的。46CompilerPrinciples四、正規(guī)式與有窮自動(dòng)機(jī)的等價(jià)性：

我們先來(lái)證明兩個(gè)重要的事實(shí)：1.定理1：Σ上的有窮自動(dòng)機(jī)所接受的字的全體L(M)是Σ上的一個(gè)正規(guī)集。(1)一般考慮：要證明L(M)是Σ上的一個(gè)正規(guī)集，很容易想到正規(guī)式。因?yàn)檎?guī)集是正規(guī)式的值。同時(shí)我們又知道任何一個(gè)

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

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

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

對(duì)于NFA的情況具有一般性，若用DFAM則更簡(jiǎn)單。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等價(jià)的正規(guī)式。49CompilerPrinciples2.定理2：對(duì)于Σ上的每個(gè)正規(guī)表達(dá)式V，存在一個(gè)Σ上的DFAM，使得L(M)=L(V)。(1)一般考慮：由定理1的證明，我們很容易想到，對(duì)Σ上的每個(gè)正規(guī)式V，可以畫出拓廣轉(zhuǎn)換圖：然后我們與逐次減少結(jié)點(diǎn)過(guò)程相反，可以對(duì)V逐次分裂并加入新結(jié)點(diǎn)和弧，直到每條弧的標(biāo)記或者為Σ中的一個(gè)符號(hào)，或者為ε，這樣就構(gòu)造了一個(gè)轉(zhuǎn)換圖，也就是一個(gè)NFAM′,然后再把M′確定化為DFA就可以了。XYV50CompilerPrinciples(2)證明：

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

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

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

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

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

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

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

③M′的確定化：從以上所談不難看出確定化的復(fù)雜程度與符號(hào)個(gè)數(shù)密切相關(guān)，為此我們?cè)O(shè)Σ={a,b}，并依如下過(guò)程構(gòu)造一個(gè)轉(zhuǎn)換矩陣。該矩陣有三列，分別記為I,Ia,Ib，第一行第一列置為ε_(tái)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)為止。因?yàn)镸′的狀態(tài)數(shù)是有限的，故上述過(guò)程必在有限步內(nèi)停止。把上述表中第一列的狀態(tài)子集進(jìn)行編號(hào)，最終可得到一個(gè)狀態(tài)矩陣，該矩陣唯一地畫出了一個(gè)確定的有窮自動(dòng)機(jī)M，其唯一初態(tài)為ε_(tái)CLOSURE({X})，終態(tài)是那些含有M′的終態(tài)Y的子集。由上述構(gòu)造過(guò)程不難看出：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)重新編號(hào)的狀態(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：一個(gè)字集V是正規(guī)的當(dāng)且僅當(dāng)有一自動(dòng)機(jī)M,使得L(M)=L(V)。推論2：NFA與DFA接收相同的集合。

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

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

57CompilerPrinciples五、DFA的化簡(jiǎn)所謂對(duì)一個(gè)DFAM的化簡(jiǎn)，就是找一個(gè)DFAM′，使得L(M)=L(M′)但是M′的狀態(tài)數(shù)比M少。1.等價(jià)狀態(tài)和可區(qū)別狀態(tài)：若分別從狀態(tài)s和t出發(fā)而停于終態(tài)能讀出同一個(gè)字α，則稱s,t為等價(jià)狀態(tài)；不等價(jià)的兩個(gè)狀態(tài)稱為可區(qū)別狀態(tài)。a0st12zaabaabb58CompilerPrinciples2.狀態(tài)的最小化過(guò)程所謂DFAM的狀態(tài)最小化過(guò)程就是找一個(gè)最少狀態(tài)的DFAM′使得L(M)=L(M′)。具體做法：把DFAM的狀態(tài)集分割成一些不相交的子集，使得不同的兩個(gè)子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個(gè)狀態(tài)都是等價(jià)的，最后讓每個(gè)子集選出一個(gè)代表，把所有與該子集相關(guān)的弧都與該代表相連接，并消去其他等價(jià)狀態(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）形成基本分劃π─分成兩個(gè)子集:非終態(tài)子集I(1)和終態(tài)子集I(2)即：I(1)＝{0,1,2}I(2)={3,4,5,6}b60CompilerPrinciples(2)對(duì)每個(gè)子集I(i)和每個(gè)a∈Σ,來(lái)考察Ia(i)是否包含在某個(gè)I(j)中(j=1,2,…n)，若不是完全包含在某個(gè)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)選等價(jià)狀態(tài)子集的代表，并重構(gòu)狀態(tài)圖。

如{3,4,5,6}的代表為{3}，可得狀態(tài)圖：02b13abba,baa(5)最后可得最少狀態(tài)自動(dòng)機(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ī)語(yǔ)言的描述模型63CompilerPrinciples§3.詞法分析器的自動(dòng)產(chǎn)生

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

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

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

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

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

實(shí)現(xiàn)：最小化的DFA的每個(gè)狀態(tài)對(duì)應(yīng)一小段程序詞法分析器RERGA→Ba∣aA→aB∣aNFADFA最小化DFA轉(zhuǎn)換規(guī)則增加開始狀態(tài)增加終止?fàn)顟B(tài)確定化劃分等價(jià)類66CompilerPrinciples例題與解答[例1]寫出產(chǎn)生語(yǔ)言：{能被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]寫一個(gè)文法，使其語(yǔ)言是奇數(shù)集，且每個(gè)奇數(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