編譯原理詞法分析(與“狀態(tài)”有關(guān)的文檔共115張)

編譯原理詞法分析第一頁，共115頁。2.1詞法分析器設(shè)計方法詞法分析是編譯的第一個階段，其任務(wù)是：從左至右逐個字符地對源程序進行掃描，產(chǎn)生一個個單詞符號，把字符串形式的源程序改造成為單詞符號串形式的中間程序。執(zhí)行詞法分析的程序稱為詞法分析程序，也稱為詞法分析器或掃描器。詞法分析器的功能是輸入源程序，輸出單詞符號。第二頁，共115頁。詞法分析可以采用如下兩種處理結(jié)構(gòu)：

(1)把詞法分析程序作為主程序。將詞法分析工作作為獨立的一遍來完成，即把詞法分析與語法分析明顯分開，由詞法分析程序?qū)⒆址问降脑闯绦蚋脑斐蓡卧~符號串形式的中間程序，以這個中間程序作為語法分析程序的輸入。在這種處理結(jié)構(gòu)中，詞法分析和語法分析是分別實現(xiàn)的，如圖2–1(a)所示。第三頁，共115頁。

(2)把詞法分析程序作為語法分析程序調(diào)用的子程序。在進行語法分析時，每當語法分析程序需要一個單詞時便調(diào)用詞法分析程序，詞法分析程序每一次調(diào)用便從字符串源程序中識別出一個單詞交給語法分析程序。在這種處理結(jié)構(gòu)中，詞法分析和語法分析實際上是交替進行的，如圖2–1(b)所示。由于把詞法分析器安排成一個子程序比較自然，因此，詞法分析程序通常采用第二種處理結(jié)構(gòu)。第四頁，共115頁。圖2-1詞法分析的兩種處理結(jié)構(gòu)(a)詞法分析程序作為主程序；(b)詞法分析程序作為子程序第五頁，共115頁。

2.1.1單詞符號的分類與輸出形式

1．單詞符號分類詞法分析程序簡單地說就是讀單詞程序，該程序掃描用高級語言編寫的源程序，將源程序中由單詞符號組成的字符串分解出一個個單詞來。因此，單詞符號是程序語言的基本語法單位，具有確定的語法意義。程序語言的單詞符號通常可分為下面五種：第六頁，共115頁。

(1)保留字(也稱基本字)：如C語言中的if、else、while和do等，這些字保留了語言所規(guī)定的含義，是編譯程序識別各類語法成分的依據(jù)。幾乎所有程序語言都限制用戶使用保留字來作為標識符。

(2)標識符：用來標記常量、數(shù)組、類型、變量、過程或函數(shù)名等，通常由用戶自己定義。

(3)常數(shù)：包括各種類型的常數(shù)，如整型常數(shù)386、實型常數(shù)、布爾型常數(shù)TRUE等。第七頁，共115頁。

(4)運算符：如“+”、“?”、“*”、“/”、“>”、“<”等。

(5)界符：在語言中是作為語法上的分界符號使用的，如“，”、“；”、“（”、“）”等。

一個程序語言的保留字、運算符和界符的個數(shù)是確定的，而標識符或常數(shù)的使用則不限定個數(shù)。

第八頁，共115頁。

2．詞法分析程序輸出單詞的形式我們知道，詞法分析程序的輸入是源程序字符串，而輸出是與源程序等價的單詞符號序列，并且所輸出的單詞符號通常表示成如下的二元式：（單詞種別，單詞自身的值）

(1)單詞種別。單詞種別表示單詞的種類，它是語法分析所需要的信息。一個語言的單詞符號如何劃分種類、分為幾類、如何編碼都屬于技術(shù)性問題，主要取決于處理上的方便。通常讓每種單詞對應(yīng)一個整數(shù)碼，這樣可最大限度地把各個單詞區(qū)別開來。第九頁，共115頁。對于保留字，可將其全體視為一種，也可一字一種，采用一字一種的分類方法處理起來比較方便；標識符一般統(tǒng)歸為一種；常數(shù)可統(tǒng)歸為一種，也可按整型、實型、布爾型等分為幾種；運算符和界符可采用一符一種的分法，也可統(tǒng)歸為一種。第十頁，共115頁。

(2)單詞自身的值。單詞自身的值是編譯中其它階段所需要的信息。對于單詞符號來說，如果一個種別只含有一個單詞符號，那么對于這個單詞符號，其種別編碼就完全代表了它自身的值。如果一個種別含有多個單詞符號，那么對于它的每個單詞符號，除了給出種別編碼之外還應(yīng)給出單詞符號自身的值，以便把同一種類的單詞區(qū)別開來。注意，標識符自身的值就是標識符自身的字符串，而常數(shù)自身的值是常數(shù)本身的二進制數(shù)值。此外，我們也可用指向某類表格中一個特定項目的指針來區(qū)分同類中的不同單詞。例如，對于標識符，可以用它在符號表的入口指針作為它自身的值；而常數(shù)也可用它在常數(shù)表的入口指針作為它自身的值。第十一頁，共115頁。

2.1.2狀態(tài)轉(zhuǎn)換圖

在詞法分析中，可以用狀態(tài)轉(zhuǎn)換圖來識別單詞。狀態(tài)轉(zhuǎn)換圖是有限的有向圖，結(jié)點代表狀態(tài)，用圓圈表示；結(jié)點之間可由有向邊連接，有向邊上可標記字符。例如，圖2-2表示在狀態(tài)i下，若輸入字符為x，則讀入x并轉(zhuǎn)換到狀態(tài)j；若輸入字符為y，則讀入y并轉(zhuǎn)換到狀態(tài)k。

狀態(tài)（即結(jié)點）數(shù)是有限的，其中必有一初始狀態(tài)以及若干終止狀態(tài)，終止狀態(tài)(終態(tài))的結(jié)點用雙圈表示以區(qū)別于其它狀態(tài)。圖2-3給出了用于識別標識符、無符號整數(shù)、無符號數(shù)的狀態(tài)轉(zhuǎn)換圖，其初始狀態(tài)均用0狀態(tài)表示。第十二頁，共115頁。圖2–2不同輸入字符的狀態(tài)轉(zhuǎn)換第十三頁，共115頁。圖2-3標識符及無符號數(shù)的狀態(tài)轉(zhuǎn)換圖(a)標識符；(b)無符號整數(shù)；(c)無符號數(shù)第十四頁，共115頁。當?shù)竭_一類單詞符號的終止狀態(tài)時即可給出相應(yīng)的單詞編碼。某些終止狀態(tài)是在讀入了一個其它不屬于該單詞的符號后才得到相應(yīng)的單詞編碼的，這表明在識別單詞的過程中多讀入了一個符號，所以識別出單詞后應(yīng)將最后多讀入的這個符號予以回退；我們對此類情況的處理是在終態(tài)上以“*”作為標識。對于不含回路的分支狀態(tài)來說，可以讓它對應(yīng)一個switch()語句或一組if-else語句。例如，圖2-4(a)的狀態(tài)i所對應(yīng)的switch語句如下：第十五頁，共115頁。s=getchar();switch(s){case'a':case'b':…case'z':…; /*實現(xiàn)狀態(tài)j功能的語句*/case'0':case'1':…case'9':…; /*實現(xiàn)狀態(tài)k功能的語句*/}第十六頁，共115頁。對于含回路的狀態(tài)來說，可以讓它對應(yīng)一個while語句。例如，圖2-4(b)的狀態(tài)i所對應(yīng)的while語句如下：

getchar();while(letter()||chgit())getchar();

…; /*實現(xiàn)狀態(tài)j功能的語句*/

終態(tài)一般對應(yīng)一個return()語句；return意味著從詞法分析器返回到調(diào)用段，一般指返回到語法分析器。第十七頁，共115頁。圖2-4含有分支或回路的狀態(tài)示意(a)含分支的狀態(tài)i；(b)含回路的狀態(tài)i第十八頁，共115頁。2.2一個簡單的詞法分析器示例

2.2.1C語言子集的單詞符號表示一個非常重要的事實是：大多數(shù)程序語言的單詞符號都可以用狀態(tài)轉(zhuǎn)換圖予以識別。作為一個綜合例子，我們來構(gòu)造一個C語言子集的簡單詞法分析器。表列出了這個C語言子集的所有單詞符號以及它們的種別編碼和內(nèi)碼值。由于直接使用整數(shù)編碼不利于記憶，故該例中用一些特殊符號來表示種別編碼。第十九頁，共115頁。表2.1C語言子集的單詞符號及內(nèi)碼值單詞符號種別編碼助記符內(nèi)碼值while1while—if2if—else3else—switch4switch—case5case—標識符6idid在符號表中的位置常數(shù)7numnum在常數(shù)表中的位置+8+—?9?—*10*—<=11relopLE<11relopLT==11relopEQ=12=—；13；—第二十頁，共115頁。

2.2.2C語言子集對應(yīng)的狀態(tài)轉(zhuǎn)換圖在設(shè)計的狀態(tài)轉(zhuǎn)換圖中，首先對輸入串做預(yù)處理，即剔除多余的空白符（在實際的詞法分析中，預(yù)處理還包括剔除注釋和制表換行符等編輯性字符的工作），使詞法分析工作既簡單又清晰。其次，將保留字作為一類特殊的標識符來處理，也即對保留字不專設(shè)對應(yīng)的狀態(tài)轉(zhuǎn)換圖，當轉(zhuǎn)換圖識別出一個標識符時就去查對表的前五項，確定它是否為一個保留字。當然，也可以專設(shè)一個保留字表來進行處理。圖2–5就是對應(yīng)表這個簡單詞法分析的狀態(tài)轉(zhuǎn)換圖。

第二十一頁，共115頁。圖2–5簡單詞法分析的狀態(tài)轉(zhuǎn)換圖第二十二頁，共115頁。在狀態(tài)2時，所識別出的標識符應(yīng)先與表的前五項逐一比較，若匹配，則該標識符是一個保留字，否則就是標識符。如果是標識符，應(yīng)先查符號表，看表中是否有此標識符。若表中無此標識符，則將它登錄到符號表中，然后返回其在符號表中的入口指針（地址）作為該標識符的內(nèi)碼值；若表中有此標識符，則給出重名錯誤信息。在狀態(tài)4時，應(yīng)將識別的常數(shù)轉(zhuǎn)換成二進制常數(shù)并將其登錄到常數(shù)表，然后返回其在常數(shù)表中的入口指針作為該常數(shù)的內(nèi)碼值。第二十三頁，共115頁。

2.2.3狀態(tài)轉(zhuǎn)換圖的實現(xiàn)狀態(tài)轉(zhuǎn)換圖非常容易用程序?qū)崿F(xiàn)，最簡單的辦法是讓每個狀態(tài)對應(yīng)一小段程序。對于圖2–5的狀轉(zhuǎn)換圖，我們首先引進一組變量和過程如下：

(1)character：字符變量，存放最新讀入的源程序字符。

(2)token：字符數(shù)組，存放構(gòu)成單詞符號的字符串。

(3)getbe()：若character中的字符為空白，則調(diào)用getchar()，直至character為非空白符為止。第二十四頁，共115頁。

(4)concatenation()：將token中的字符串與character中的字符連接并作為token中新的字符串。

(5)letter()和digit()：判斷character中的字符是否為字母和數(shù)字的布爾函數(shù)，是則返回true，否則返回false。

(6)reserve()：按token數(shù)組中的字符串查表中的前五項(即判別其是否為保留字)，若是保留字則返回它的編碼，否則返回0值。第二十五頁，共115頁。

(7)retract()：掃描指針回退一個字符，同時將character置為空白。

(8)buildlist()：將標識符登錄到符號表或?qū)⒊?shù)登錄到常數(shù)表。

(9)error()：出現(xiàn)非法字符，顯示出錯信息。相對于圖2-5的詞法分析器構(gòu)造如下：第二十六頁，共115頁。token=''; /*對token數(shù)組初始化*/s=getchar();getbe(); /*濾除空格*/switch(s){case'a':case'b':…case'z':while(letter()‖digit())第二十七頁，共115頁。{concatenation(); /*將當前讀入的字符送入token數(shù)組*/getchar();}retract(); /*掃描指針回退一個字符*/c=reserve();if(c==0){buildlist(); /*將標識符登錄到符號表中*/return(id，指向id的符號表入口指針);}第二十八頁，共115頁。elsereturn(保留字碼，null);break;case'0':case'1':…case'9':while(digit()){concatenation();getchar();}retract();第二十九頁，共115頁。buildlist(); /*將常數(shù)登錄到常數(shù)表中*/return(num，num的常數(shù)表入口指針);break;case'+':return('+'，null);break;case'?':return('?'，null);break;case'*':return('*'，null);第三十頁，共115頁。break;case'<':getchar();if(character=='=')return(relop,LE);else{retract();return(relop，LT);}break;case'=':getchar();if(character=='=')第三十一頁，共115頁。return(relop,EQ);else{retract();return('=',_);}break;case';':return(';',_);break;default:error();}第三十二頁，共115頁。2.3正規(guī)表達式與有限自動機簡介

2.3.1正規(guī)表達式與正規(guī)集狀態(tài)轉(zhuǎn)換圖對構(gòu)造詞法分析程序是行之有效的，為了便于詞法分析器的自動生成，還須將狀態(tài)轉(zhuǎn)換圖的概念加以形式化。正規(guī)表達式就是一種形式化的表示法，它可以表示單詞符號的結(jié)構(gòu)，從而精確地定義單詞符號集。正規(guī)表達式簡稱為正規(guī)式，它表示的集合即為正規(guī)集。為了理解正規(guī)式與正規(guī)集的含義，我們以程序語言中的標識符為例予以說明。

第三十三頁，共115頁。程序語言中使用的標識符是一個以字母開頭的字母數(shù)字串，如果字母用letter表示，數(shù)字用digit表示，則標識符可表示為

letter(letter∣digit)*

其中，letter與(letter∣digit)*的并置表示兩者的連接；括號中的“∣”表示letter或digit兩者選一；“*”表示零次或多次引用由“*”標記的表達式；(letter∣digit)*是letter∣digit的零次或多次并置，即表示一長度為0、1、2、…的字母數(shù)字串；letter(letter∣digit)*表示以字母開頭的字母數(shù)字串，也即標識符集。letter(letter∣digit)*就是表示標識符的正規(guī)式，而標識符集就是這個正規(guī)式所表示的正規(guī)集。第三十四頁，共115頁。對于給定的字母表Σ，正規(guī)式和正規(guī)集的遞歸定義如下：

(1)ε和Ф都是Σ上的正規(guī)式，它們所表示的正規(guī)集分別為{ε}和Ф。

(2)對任一個a∈Σ，a是Σ上的一個正規(guī)式，它所表示的正規(guī)集為{a}。

(3)如果R和S是Σ上的正規(guī)式，它們所表示的正規(guī)集分別為L(R)和L(S)，則：第三十五頁，共115頁。①R∣S是Σ上的正規(guī)式，它所表示的正規(guī)集為L(R)∪L(S)；②是Σ上的正規(guī)式，它所表示的正規(guī)集為L(R)L(S)；③(R)*是Σ上的正規(guī)式，它所表示的正規(guī)集為(L(R))*；④R也是Σ上的正規(guī)式，它所表示的正規(guī)集為L(R)。第三十六頁，共115頁。

(4)僅由有限次使用規(guī)則(1)～(3)得到的表示式是Σ上的正規(guī)式，它所表示的集合是Σ上的正規(guī)集。在上述定義中，規(guī)則(1)、(2)為基礎(chǔ)規(guī)則，規(guī)則(3)為歸納規(guī)則，規(guī)則(4)是界限規(guī)則或終止規(guī)則。此外，Σ上的一個字是指由Σ中的字符所構(gòu)成的一個有窮序列；不包含任何字符的序列稱為空字，用ε表示。我們用Σ*表示Σ上所有字的全體，則空字ε也在其中。例如，若Σ={a，b}，則Σ*={ε，a，b，aa，ab，ba，bb，aaa，…}。我們還用Ф表示不含任何元素的空集{}。這里需要注意ε、{}和{ε}的區(qū)別：{ε}是由空字組成的集合，而{}則表示不含任何字的集合。1第三十七頁，共115頁。正規(guī)式間的運算符“∣”表示或，“·

”表示連接（通?？墒÷裕?，“*”表示閉包，使用括號可以改變運算的次序。如果規(guī)定“*”優(yōu)先于“·

”，“·

”優(yōu)先于“∣”，則在不出現(xiàn)混淆的情況下括號也可以省去。注意，Σ*的正規(guī)式R和S的連接可以形式化地定義為

RS={αβ∣α∈R&β∈S}

即集合RS中的字是由R和S中的字連接而成的，且R自身的n次連接記為第三十八頁，共115頁。我們規(guī)定R0={ε}，并令R*=R0∪R1∪R2∪R3∪…，則稱R*是R的閉包；此外，令R+=RR*，并稱R+是R的正閉包。閉包R*中的每個字都是由R中的字經(jīng)過有限次連接而成的。對于Σ上的正規(guī)式R和S，如果它所表示的正規(guī)集L(R)=L(S)，則稱R和S等價并記為R=S。不難證明，正規(guī)式具有下列性質(zhì)：

(1)交換律：R∣S=S∣R。

(2)結(jié)合律：R∣(S∣T)=(R∣S)∣T；

R(ST)=(RS)T。

(3)分配律：R∣(S∣T)=RS∣RT；

(R∣S)T=RT∣ST。

(4)同一律：εR=Rε=R。第三十九頁，共115頁。例2.1令Σ={a,b}，設(shè)R=a(a∣b)*是Σ上的正規(guī)式，試求其表示的正規(guī)集。

[解答]L(R)=L(a(a∣b)*)=L(a)L((a∣b)*)=L(a)(L(a∣b))*=L(a)(L(a)∪L(b))*={a}({a}∪)*={a}{a,b}*={a}{ε,a,b,aa,ab,ba,bb,aaa,…}={a,aa,ab,aaa,aab,aba,abb,aaaa,…}

例2.2判斷下述正規(guī)式之間是否等價：

(1)(a∣b)*與a*∣b*(2)(ab)*與a*b*(3)(a∣b)*與(a*b*)*第四十頁，共115頁。

[解答](1)(a∣b)*對應(yīng)的正規(guī)集其a、b可任意交替出現(xiàn)，如abbaaaba…；而(a*∣b*)對應(yīng)的正規(guī)集只可出現(xiàn)任意個a或者任意個b；因此兩者不等價。

(2)(ab)*對應(yīng)的正規(guī)集是以任意個ab對出現(xiàn)的，即ababab…；而a*b*對應(yīng)的正規(guī)集則是先出現(xiàn)任意個a后接任意個b，即a…ab…b；因此兩者不等價。

(3)由于(a∣b)*對應(yīng)的正規(guī)集其a、b可任意交替出現(xiàn)，如aababbb；而(a*b*)*可采用如下構(gòu)造方法得到字aababbb：

(a*b*)2=(a*b*)0∪(a2b1)1∪(a1b3)2=aababbb

反之，對(a*b*)*產(chǎn)生的任意字也可由(a∣b)*得到，即兩者是等價的。第四十一頁，共115頁。例2.3證明：設(shè)L(a+)={a}*?{ε}，則有a+=aa*。[證明]L(a+)={a}*?{ε}={ε,a,a2,a3,…}?{ε}={a,a2,a3,…}={a}·{ε,a,a2…}={a}{a}*=L(a)L(a*)=L(aa*)

故a+=aa*第四十二頁，共115頁。

2.3.2有限自動機有限自動機（FA）是更一般化的狀態(tài)轉(zhuǎn)換圖，它分為確定有限自動機DFA和非確定有限自動機NFA兩種。

1．確定有限自動機（DFA）一個確定的有限自動機Md（記為DFAMd）是一個五元組Md=（S,Σ,f,s0,Z），其中：

(1)S是一個有限狀態(tài)集，它的每一個元素稱為一個狀態(tài)；

(2)Σ是一個有窮輸入字母表，它的每一個元素稱為一個輸入字符；第四十三頁，共115頁。

(3)f是一個從S×Σ到S的單值映射，即f(si,a)=sj且有si、sj∈S和a∈Σ；

(4)s0∈S，是惟一的一個初態(tài)；

(5)Z(S，是一個終態(tài)集。例如，對圖2-6所給出的狀態(tài)s1有：

f(s1,a)=s2f(s1,b)=s3f(s1,c)=s4

因此，f是單值映射函數(shù)。第四十四頁，共115頁。圖2-6DFA的狀態(tài)轉(zhuǎn)換示意第四十五頁，共115頁。

2．非確定有限自動機(NFA)

一個非確定有限自動機Mn（記為NFAMn）是一個五元組Mn=(S,Σ,f,Q,Z)，其中：

(1)S、Σ、Z的意義與DFA相同；

(2)f是一個從S×Σ*到S的子集映射；

(3)Q(S，是一個非空初態(tài)集。

第四十六頁，共115頁。

NFA和DFA的區(qū)別主要有兩點：其一是NFA可以有若干個初始狀態(tài)，而DFA僅有一個初始狀態(tài)；其二是NFA的狀態(tài)轉(zhuǎn)換函數(shù)f不是單值函數(shù)，而是一個多值函數(shù)，即f(si，a)={某些狀態(tài)的集合}（si∈S），它表示不能由當前狀態(tài)和當前輸入字符惟一地確定下一個要轉(zhuǎn)換的狀態(tài)，也即允許同一個狀態(tài)對同一個輸入字符可以有不同的輸出邊。第四十七頁，共115頁。圖2–7NFA的狀態(tài)轉(zhuǎn)換示意第四十八頁，共115頁。例如，對圖2-7所給出的狀態(tài)s1有：

f(s1，a)={s1，s2，s3}

即f是一個從S×Σ*到S的子集映射；Σ*表示輸出邊上所標記的不僅是字符，也可以是字。此外，NFA還允許f(s1，ε)={某些狀態(tài)的集合}，即在NFA的狀態(tài)轉(zhuǎn)換圖中輸出邊上的標記還可是ε(空字)。第四十九頁，共115頁。

3．狀態(tài)轉(zhuǎn)換圖與狀態(tài)轉(zhuǎn)換矩陣

DFA和NFA都可以用狀態(tài)轉(zhuǎn)換圖表示。假定DFA（或NFA）有m個狀態(tài)、n個輸入字符（或字），則這個狀態(tài)轉(zhuǎn)換圖含有m個狀態(tài)，每個狀態(tài)最多有n條輸出邊與其它狀態(tài)相連接，每一條輸出邊用Σ（或Σ*）中的一個不同的輸入字符（或一個輸入字）作標記，整個圖含有惟一一個初態(tài)（或多個初態(tài)）和若干個終態(tài)。

DFA和NFA也可以用狀態(tài)轉(zhuǎn)換矩陣表示。狀態(tài)轉(zhuǎn)換矩陣的行表示狀態(tài)，列表示輸入符號，矩陣元素表示f(si，a)的值。第五十頁，共115頁。例2.4假定DFAMd=({s0，s1，s2}，{a，b}，f，s0，{s2})，且有：

f(s0，a)=s1 f(s0，b)=s2 f(s1，a)=s1 f(s1，b)=s2 f(s2，a)=s2 f(s2，b)=s1

試給出DFAMd的狀態(tài)轉(zhuǎn)換圖與狀態(tài)轉(zhuǎn)換矩陣。

[解答]DFAMd的狀態(tài)轉(zhuǎn)換圖見圖2-8，狀態(tài)轉(zhuǎn)換矩陣見表。第五十一頁，共115頁。表2.2狀態(tài)轉(zhuǎn)換矩陣字符狀態(tài)abs0s1s2s1s1s2s2s2s1第五十二頁，共115頁。圖2-8例的DFAMd狀態(tài)轉(zhuǎn)換圖第五十三頁，共115頁。例2.5假定NFAMn=({s0，s1，s2}，{a，b}，f，{s0，s2}，{s1})，且有：

f(s0，a)={s2} f(s0，b)={s0,s1} f(s1，a)=Φ f(s1，b)={s2} f(s2，a)=Φ f(s2，b)={s1}

試給出NFAMn的狀態(tài)轉(zhuǎn)換圖與狀態(tài)矩陣。第五十四頁，共115頁。

[解答]NFAMn的狀態(tài)轉(zhuǎn)換圖見圖2-9，狀態(tài)轉(zhuǎn)換矩陣見表。對于FAM和任一Σ上的字符串α（即α∈Σ*），如果存在一條從初始狀態(tài)到終止狀態(tài)的通路，通路上有向邊（輸出邊）所標識的字符依次連接所得到的字符串恰為α，則稱α可以為FAM所接受或稱α為FAM所識別。FAM所能識別的字符串集稱為FAM所識別的語言，記為L(M)。第五十五頁，共115頁。表2.3狀態(tài)轉(zhuǎn)換矩陣字符狀態(tài)abs0{s2}{s0，s1}s1Φ{s2}s2Φ{s1}第五十六頁，共115頁。圖2–9例的NFAMn的狀態(tài)轉(zhuǎn)換圖第五十七頁，共115頁。2.4正規(guī)表達式到有限自動機的構(gòu)造

2.4.1由正規(guī)表達式構(gòu)造等價的NFAM

由正規(guī)表達式構(gòu)造等價的NFAM的方法如下：

(1)將正規(guī)表達式R表示成如圖2–10所示的拓廣轉(zhuǎn)換圖。

(2)對正規(guī)表達式采用如圖2-11所示的三條轉(zhuǎn)換規(guī)則來構(gòu)造NFAM。第五十八頁，共115頁。圖2-10拓廣轉(zhuǎn)換圖第五十九頁，共115頁。圖2-11轉(zhuǎn)換規(guī)則第六十頁，共115頁。對于給定的正規(guī)表達式R，首先將其表示成如圖2–10所示的形式，其中X為初始狀態(tài)，Y為終止狀態(tài)；然后逐步將這個拓廣轉(zhuǎn)換圖運用三條轉(zhuǎn)換規(guī)則不斷加入新結(jié)點進行分解，直至每條有向邊上僅標識有Σ的一個字母或ε為止，則NFAM構(gòu)造完成。例2.6對給定正規(guī)表達式b*(d∣ad)(b∣ab)+構(gòu)造其NFAM。

[解答]先用R+=RR*改造題設(shè)的正規(guī)表達式為b*(d∣ad)(b∣ab)(b∣ab)*，然后構(gòu)造其NFAM，如圖2-12所示。第六十一頁，共115頁。圖2-12NFAM第六十二頁，共115頁。

2.4.2NFAM的確定化

NFA的確定化是指對給定的NFA都能相應(yīng)地構(gòu)造出一個與之等價的DFA，使它們能夠識別相同的語言。我們采用子集法來對NFAM確定化。首先定義FAM的一個狀態(tài)子集I的ε_閉包，即ε_CLOSURE(I)，則：

(1)若si∈I，則si∈ε_CLOSURE(I)；

(2)若si∈I，則對從si出發(fā)經(jīng)過ε通路所能到達的任何狀態(tài)sj，都有sj∈ε_CLOSURE(I)。其次，對FAM的一個狀態(tài)子集I，若a是Σ中的一個字符，定義

Ia=ε_CLOSURE(J)第六十三頁，共115頁。其中，J是所有那些可以從I中的某一狀態(tài)出發(fā)經(jīng)過有向邊a而能到達的狀態(tài)集。

例2.7已知一狀態(tài)轉(zhuǎn)換圖如圖2–13所示，且假定I=ε_{1}={1，2}，試求從狀態(tài)I出發(fā)經(jīng)過一條有向邊a而能到達的狀態(tài)集J和ε_CLOSURE(J)。第六十四頁，共115頁。圖2–13例的狀態(tài)轉(zhuǎn)換圖第六十五頁，共115頁。

[解答]從狀態(tài)I中的狀態(tài)1或狀態(tài)2出發(fā)經(jīng)過一條a弧而能到達的狀態(tài)集J為

{5，3，4}

若si∈J，則由si出發(fā)經(jīng)過任意條ε有向邊而能到達的任何狀態(tài)sj∈ε_CLOSURE(J)，因此ε_CLOSURE(J)為

{5，6，2，3，8，4，7}第六十六頁，共115頁。用子集法對NFA確定化的方法如下：

(1)構(gòu)造一張轉(zhuǎn)換表，其第一列為狀態(tài)子集I，對不同的a(a∈Σ)在表中單設(shè)一列Ia。

(2)表的第一行第一列其狀態(tài)子集I為ε_CLOSURE(s0)；其中，s0為初始狀態(tài)。

(3)根據(jù)第一列中的I為每一個a求其Ia并記入對應(yīng)的Ia列中，如果此Ia不同于第一列已存在的所有狀態(tài)子集I，則將其順序列入空行中的第一列。

(4)重復(fù)步驟（3）直至對每個I及a均已求得Ia，并且無新的狀態(tài)子集Ia加入第一列時為止；此過程可在有限步后終止。第六十七頁，共115頁。

(5)重新命名第一列的每一狀態(tài)子集，則轉(zhuǎn)換表便成為新的狀態(tài)轉(zhuǎn)換矩陣，其狀態(tài)轉(zhuǎn)換函數(shù)f是S×Σ到S的單值映射，即為與NFAM等價的DFAM'。例2.8正規(guī)表達式（a∣b）*(aa∣bb)(a∣b)*的NFAM如圖2–14所示，試將其確定化為DFAM'。

[解答]用子集法將圖2-14所示的NFAM確定化為表。對表中的所有子集重新命名，得到表的狀態(tài)轉(zhuǎn)換矩陣及對應(yīng)的狀態(tài)轉(zhuǎn)換圖(見圖2-15)。第六十八頁，共115頁。圖2–14例的NFAM第六十九頁，共115頁。表2.4例的轉(zhuǎn)換表IIaIb{X,1,2}{1,2,3}{1,2,4}{1,2,3}{1,2,3,5,6,Y}{1,2,4}{1,2,4}{1,2,3}{1,2,4,5,6,Y}{1,2,3,5,6,Y}{1,2,3,5,6,Y}{1,2,4,6,Y}{1,2,4,5,6,Y}{1,2,3,6,Y}{1,2,4,5,6,Y}{1,2,4,6,Y}{1,2,3,6,Y}{1,2,4,5,6,Y}{1,2,3,6,Y}{1,2,3,5,6,Y}{1,2,4,6,Y}第七十頁，共115頁。圖2–15例未化簡的DFAM′第七十一頁，共115頁。表2.5例的狀態(tài)轉(zhuǎn)換矩陣Sab012132214335464564635第七十二頁，共115頁。

2.4.3DFAM的化簡對NFA確定化后所得到的DFA可能含有多余的狀態(tài)，因此還應(yīng)對其進行化簡。所謂DFAM的化簡，是指尋找一個狀態(tài)數(shù)比M少的DFAM'，使得L(M)=L(M')?；喠说腄FAM'滿足下述兩個條件：

(1)沒有多余狀態(tài)；

(2)在其狀態(tài)集中，沒有兩個相互等價的狀態(tài)存在。第七十三頁，共115頁。所謂兩個狀態(tài)相互等價是指：對一給定的DFAM，若存在狀態(tài)s1、s2∈S且s1≠s2，如果從s1出發(fā)能識別字符串α而停于終態(tài)，從s2出發(fā)也同樣能夠識別這個α而停于終態(tài)；反之，若從s2出發(fā)能識別β而停于終態(tài)，則從s1出發(fā)也能識別這個β而停于終態(tài)，則稱s1和s2是等價的，否則就是可區(qū)分的。一個DFAM的狀態(tài)最小化過程是將M的狀態(tài)集分割成一些不相交的子集，使得任何不同的兩個子集其狀態(tài)都是可區(qū)分的，而同一子集中的任何兩個狀態(tài)都是等價的。第七十四頁，共115頁。最后，從每個子集中選出一種狀態(tài)，同時消去其它等價狀態(tài)，就得到最簡的DFAM'且L(M)=L(M')。DFAM的化簡方法如下：

(1)首先將DFAM的狀態(tài)集S中的終態(tài)與非終態(tài)分開，形成兩個子集，即得到基本劃分。

(2)對當前已劃分出的I(1)、I(2)、…、I(m)

子集（屬于不同子集的狀態(tài)是可區(qū)分的），看每一個I是否能進一步劃分；也即對某個I(i)=｛s1,s2,…,sk｝，若存在一個輸入字符a（a∈Σ）使得Ia(i)不全包含在當前劃分的某一子集I(j)中（即跨越到兩個子集），就將I(i)一分為二（見圖2–16）。第七十五頁，共115頁。圖2–16是否劃分示意(a)無需劃分；(b)需要劃分第七十六頁，共115頁。

(3)重復(fù)步驟(2)，直到子集個數(shù)不再增加為止（即每個子集已是不可再分的了）。所謂不能劃分，是指該子集或者僅有一個狀態(tài)，或者雖有多個狀態(tài)但這些狀態(tài)均不可區(qū)分（即等價）。那么，如何進行劃分呢？假定當前子集I(i)=｛s1,s2,…｝，且狀態(tài)s1和s2經(jīng)過有向邊a分別到達狀態(tài)t1和t2，而t1和t2又分屬于當前已劃分出的兩個不同子集I(j)和I(k)，則此時應(yīng)將I(i)分為兩部分，使得一部分含有s1：

I(i1)=｛s∣s∈I(i)且s經(jīng)有向邊a到達t1｝第七十七頁，共115頁。而另一部分含有s2：

I(i2)=I(i)?I(i1)

由于t1和t2是可區(qū)分的，即存在一個字符串α，t1將讀出α而停于終態(tài)，而t2或讀不出α或者可以讀出α但不能到達終態(tài)。因此，字符串α將把狀態(tài)s1和s2區(qū)分開來，也就是說，I(i1)中的狀態(tài)與I(i2)中的狀態(tài)是可區(qū)分的。至此，我們已將I(i)

劃分為兩個子集I(i1)和I(i2)，形成了新的劃分。第七十八頁，共115頁。例

化簡由例得到的DFA。

[解答](1)首先將狀態(tài)集S={0，1，2，3，4，5，6}劃分為終態(tài)集{3，4，5，6}和非終態(tài)集{0，1，2}。

(2)考察{0，1，2}a：因0a=2a={1}，而1a={3}，分屬于非終態(tài)集和終態(tài)集，故將{0,1,2}劃分為{0，2}和{1}。

(3)考察{0，2}b：0b={2}，2b={4}，它們分屬于兩個不同的狀態(tài)集，故{0，2}劃分為{0}和{2}。第七十九頁，共115頁。

(4)考察{3,4,5,6}a：3a=6a={3}{3,4,5,6}；4a=5a={6}{3,4,5,6}，即都屬于終態(tài)集，故不進行劃分。

(5)考察{3,4,5,6}b：3b=6b={5}{3,4,5,6}；4b=5b={4}{3,4,5,6}，即都屬于終態(tài)集，故不進行劃分。

(6)按順序重新命名狀態(tài)子集{0}、{1}、{2}、{3,4,5,6}為0、1、2、3，則得到化簡后的狀態(tài)轉(zhuǎn)換矩陣（見表）和DFAM''(見圖2–17)。第八十頁，共115頁。表2.6例的狀態(tài)轉(zhuǎn)換矩陣

Sab012132213333第八十一頁，共115頁。圖2–17例化簡后的DFAM''第八十二頁，共115頁。

2.4.4正規(guī)表達式到有限自動機構(gòu)造示例例

試用DFA的等價性證明正規(guī)表達式(a∣b)*與(a*b*)*等價。

[解答](1)正規(guī)表達式(a∣b)*對應(yīng)的NFA如圖2–18所示。用子集法將圖2–18的NFA確定化得到如表所列的轉(zhuǎn)換表，重新命名后得到如表所列的狀態(tài)轉(zhuǎn)換矩陣。第八十三頁，共115頁。表2.7(a∣b)*的轉(zhuǎn)換表

IIaIb{X,1,Y}{1,Y}{1,Y}{1,Y}{1,Y}{1,Y}第八十四頁，共115頁。圖2–18(a∣b)*的NFA第八十五頁，共115頁。表2.8(a∣b)*的狀態(tài)轉(zhuǎn)換矩陣

Sab011111第八十六頁，共115頁。由于狀態(tài)0和狀態(tài)1均為終態(tài)，故無論輸入什么字符，其下一狀態(tài)仍是終態(tài)，故最簡DFA如圖2–19所示。

(2)正規(guī)表達式(a*b*)*對應(yīng)的NFA如圖2–20所示。用子集法將圖2–20的NFA確定化得到如表所列的轉(zhuǎn)換表，重新命名得到如表所列的狀態(tài)轉(zhuǎn)換矩陣。第八十七頁，共115頁。表2.9(a*b*)*的轉(zhuǎn)換表

IIaIb{X,1,2,3,Y}{2,3,1,Y}{2,3,1,Y}{2,3,Y}{2,3,1,Y}{2,3,1,Y}第八十八頁，共115頁。表2.10(a*b*)*的狀態(tài)轉(zhuǎn)換矩陣Sab011111第八十九頁，共115頁。由于表和表的狀態(tài)轉(zhuǎn)換矩陣相同，故(a∣b)*和(a*b*)*等價。例C語言可接受的合法的文件名為，其中第一部分（device:）和第三部分(.extension)可缺省。若device、name和extension都是字母串，長度不限，但至少為1，試畫出識別這種文件名的DFAM。

[解答]以字母“c”代表字母，則所求正規(guī)式為(cc*:∣ε)cc*(.cc*∣ε)

由此得到的NFAM如圖2–21所示。第九十頁，共115頁。圖2–21例的NFAM第九十一頁，共115頁。用子集法將NFAM確定化，得到如表所列的轉(zhuǎn)換表；重新命名后得到如表所列的狀態(tài)轉(zhuǎn)換矩陣和如圖2-22所示的DFAM'。第九十二頁，共115頁。表2.11例的轉(zhuǎn)換表

表2.12例狀態(tài)轉(zhuǎn)換矩陣

IIcI:I.{X,2}{1,3,Y}——{1,3,Y}{1,3,Y}{2}{4}{2}{3,Y}——{4}{Y}——{3,Y}{3,Y}—{4}{Y}{Y}——重新命名Sc:.01——112324——35——44—355——第九十三頁，共115頁。圖2–22例的DFA?M'第九十四頁，共115頁。例

某高級程序語言無符號數(shù)的正規(guī)表達式為digit+(.digit+)?(e(+∣?)?digit+)?

其中，digit表示數(shù)字，(?)?表(?)中的內(nèi)容可有可無，試給出其DFAM。

[解答]我們用d代表digit，則用狀態(tài)轉(zhuǎn)換圖表示接受無符號數(shù)的NFA如圖2–23所示。用子集法將NFAM確定化，得到如表所列的轉(zhuǎn)換表；重新命名后得到如表所列的狀態(tài)轉(zhuǎn)換矩陣和如圖2–24所示的DFAM'。第九十五頁，共115頁。圖2–23例的NFAM第九十六頁，共115頁。表2.13例的轉(zhuǎn)換表

II±IdI.Ie{X}—{1,Y}——{1,Y}—{1,Y}{2}{4,5}{2}—{3,Y}——{4,5}{5}{Y}——{3,Y}—{3,Y}—{4,5}{5}—{Y}——{Y}—{Y}——重新命名S±d.e0—1——

1—1232—4——356——4—4—35—6——6—6——第九十七頁，共115頁。圖2–24例的DFAM'第九十八頁，共115頁。由狀態(tài)轉(zhuǎn)換矩陣可以看出：狀態(tài)5和狀態(tài)6面對輸入符號的下一狀態(tài)都是相同的，但狀態(tài)5為非終態(tài)，而狀態(tài)6為終態(tài)，故圖2–24的DFA已為最簡。例2.13

構(gòu)造一個DFA，它接收Σ=｛a,b｝上所有滿足下述條件的字符串：該字符串中的每個a都有至少一個b直接跟在其右邊。

[解答]已知Σ=｛a,b｝，根據(jù)題意得到正規(guī)表達式為b*(abb*)*。根據(jù)此正規(guī)表達式畫出相應(yīng)的NFAM如圖2–25所示。第九十九頁，共115頁。圖2–25例的NFAM第一百頁，共115頁。用子集法將NFAM確定化，得到如表所列的轉(zhuǎn)換表；重新命名后得到如表所列的狀態(tài)轉(zhuǎn)換矩陣和如圖2–26所示的DFAM'。用DFAM的化簡方法得到最終劃分：｛0,2,3｝、｛1｝，按順序重新命名后得到的最終化簡的DFAM''?如圖2–27所示。最后需要說明的是，采用如圖2–28所示的三條轉(zhuǎn)換規(guī)則可以實現(xiàn)從FAM到正規(guī)表達式的轉(zhuǎn)換。第一百零一頁，共115頁。表2.15例的轉(zhuǎn)換表表2.16例的狀態(tài)轉(zhuǎn)換矩陣重新命名IIaIbSab｛X,1,2,Y｝｛3｝｛1,2,Y｝012｛3｝—｛4,2,Y｝1—3｛1,2,Y｝｛3｝｛1,2,Y｝212｛4,2,Y｝｛3｝｛4,2,Y｝313第一百零二頁，共115頁。用DFAM的化簡方法得到最終劃分：｛0,2,3｝、｛1｝，按順序重新命名后得到的最終化簡的DFAM''?如圖2–27所示。最后需要說明的是，采用如圖2–28所示的三條轉(zhuǎn)換規(guī)則可以實現(xiàn)從FAM到正規(guī)表達式的轉(zhuǎn)換。第一百零三頁，共115頁。圖2–26例的DFAM'圖2–27例最終化簡后的DFAM''第一百零四頁，共115頁。圖2–28轉(zhuǎn)換規(guī)則第一百零五頁，共115頁。2.5詞法分析器的自動生成由于各種不同的高級程序語言中單詞的總體結(jié)構(gòu)大致相同，基本上都可用一組正規(guī)表達式描述，因而人們希望構(gòu)造這樣的自動生成系統(tǒng)：只要給出某高級語言各類單詞詞法結(jié)構(gòu)的一組正規(guī)表達式以及識別各類單詞時詞法分析程序應(yīng)采取的語義動作，該系統(tǒng)便可自動產(chǎn)生此高級程序語言的詞法分析程序。所生成的詞法分