第三章詞法分析

第三章詞法分析第1頁(yè)，共54頁(yè)，2023年，2月20日，星期三源程序掃描器scanner1、關(guān)鍵字詞法分析器的功能如下圖所示：2、標(biāo)識(shí)符5、界符4、運(yùn)算符3、常數(shù)由程序語(yǔ)言定義的具有固定意義的標(biāo)識(shí)符。也可稱(chēng)為保留字或基本字。例如：Pascal中的begin，end，if等。界符：如逗號(hào)、分號(hào)、括號(hào)、/*，*/等。它是確定的。運(yùn)算符：如+、-、*、/等。它是確定的。常數(shù)的類(lèi)型一般有整型、實(shí)型、布爾型、文字型等。它是不限的。用來(lái)表示各種名字，如變量名、數(shù)組名、過(guò)程名等。它是不限的。第2頁(yè)，共54頁(yè)，2023年，2月20日，星期三3.1對(duì)詞法分析器的要求3.1.1詞法分析器的功能和輸出形式詞法分析器的功能：輸入源程序，輸出單詞符號(hào)。單詞符號(hào)：一個(gè)程序語(yǔ)言的基本語(yǔ)法符號(hào)。分為以下5種。

1、關(guān)鍵字：由程序語(yǔ)言定義的具有固定意義的標(biāo)識(shí)符。也可稱(chēng)為保留字或基本字。例如：Pascal中的begin，end，if等。它是確定的。

2、標(biāo)識(shí)符：用來(lái)表示各種名字，如變量名、數(shù)組名、過(guò)程名等。它是不限的。

3、常數(shù)：常數(shù)的類(lèi)型一般有整型、實(shí)型、布爾型、文字型等。它是不限的。

4、運(yùn)算符：如+、-、*、/等。它是確定的。

5、界符：如逗號(hào)、分號(hào)、括號(hào)、/*，*/等。它是確定的。確定不限第3頁(yè)，共54頁(yè)，2023年，2月20日，星期三單詞符號(hào)的表示形式：詞法分析器所輸出的單詞符號(hào)常常表示成

二元式（單詞種別，單詞自身的值）。單詞種別可以用以下形式表示：

1、一類(lèi)單詞統(tǒng)一用一個(gè)整數(shù)值代表其屬性。例如：1代表關(guān)鍵字，2代表標(biāo)識(shí)符等。

2、每一個(gè)單詞一個(gè)類(lèi)別。例如：1代表BEGIN，2代表END等。單詞自身的值可以表示成：常量的二進(jìn)制表示；常量、變量等在符號(hào)表種的地址碼，等等。注意：一個(gè)語(yǔ)言的單詞符號(hào)如何分種，分幾種，怎樣編碼，是一個(gè)技術(shù)問(wèn)題。標(biāo)識(shí)符一般同歸為一種。常數(shù)則宜按類(lèi)型（整、實(shí)、布爾）分。關(guān)鍵字可以將其全體視為一種，也可一字一種。運(yùn)算符可采用一符一種，但也可把具有一定共性的視為一種。界符則一般采用一符一種。如何進(jìn)行分種主要取決于處理上的方便。若是一符一種分種，單詞自身值就不需要了。否則，要查符號(hào)表。第4頁(yè)，共54頁(yè)，2023年，2月20日，星期三例3-1：151－FORTRAN編譯程序的詞法分析器在掃描輸入串

IF(5·EQ·M)GOTO100

后，它輸出的單詞符號(hào)串是：

邏輯IF（34，_）左括號(hào)（2，_）整常數(shù)（20，‘5’的二進(jìn)制表示）等號(hào)（6，_）標(biāo)識(shí)符（26，‘M’）右括號(hào)（16，_）

GOTO（30，_）標(biāo)號(hào)（19，‘100’的二進(jìn)制表示）IF為關(guān)鍵字，種別編碼34，采用一符一種的編碼方式。常數(shù)類(lèi)型，種別編碼20，單詞自身的值為‘5’的二進(jìn)制表示?！?’為界符，種別編碼2，采用一符一種的編碼方式。等號(hào)為運(yùn)算符，種別編碼6，采用一符一種的編碼方式。M為標(biāo)識(shí)符，種別編碼26，單詞自身值為‘M’?！?’為界符，種別編碼16，采用一符一種的編碼方式。GOTO為關(guān)鍵字，種別編碼30，采用一符一種的編碼方式。100為標(biāo)號(hào)，種別編碼19，單詞內(nèi)部的值用100的二進(jìn)制表示。第5頁(yè)，共54頁(yè)，2023年，2月20日，星期三例3-2：下述C++代碼段：while(i>=j)i--；經(jīng)詞法分析器處理以后，它將被轉(zhuǎn)換為如下的單詞符號(hào)串

(while，_)((，_)(id，指向i的符號(hào)表指針)(>=，_)(id，指向j的符號(hào)表指針)()，_)(id，指向i的符號(hào)表指針)(--，_)(；，_)第6頁(yè)，共54頁(yè)，2023年，2月20日，星期三3.1.2詞法分析與語(yǔ)法分析的關(guān)系1、把詞法分析從語(yǔ)法分析中脫離出來(lái)的優(yōu)點(diǎn)：使編譯程序的結(jié)構(gòu)更加簡(jiǎn)潔、清晰和條理化。詞法分析和語(yǔ)法分析方法不同，詞法分析可以使用正則文法自動(dòng)構(gòu)造scanner簡(jiǎn)單。有利于提高語(yǔ)法分析的效率?？梢愿纳圃~法分析的細(xì)節(jié)，甚至于一個(gè)語(yǔ)法分析配幾個(gè)scanner，把不同的輸入變成一種內(nèi)部表示。2、把詞法分析作為獨(dú)立的一遍scanner當(dāng)作一遍。把scanner當(dāng)作子程序。外存scanner語(yǔ)法分析源程序單詞符號(hào)scanner作為一遍語(yǔ)法分析scanner源程序scanner作為子程序第7頁(yè)，共54頁(yè)，2023年，2月20日，星期三3.2詞法分析器的設(shè)計(jì)設(shè)計(jì)前提：

把scanner作為一個(gè)獨(dú)立的子程序；詞法分析器的任務(wù)為輸出單詞符號(hào)。3.2.1預(yù)處理必要性：編輯性字符如空白符、回車(chē)符等，除了出現(xiàn)在文字和常數(shù)中以外，在別處出現(xiàn)都沒(méi)有意義。功能：剔除無(wú)用字符。實(shí)現(xiàn)：預(yù)處理子程序。輸入列表預(yù)處理子程序掃描器掃描緩沖區(qū)輸入緩沖區(qū)單詞符號(hào)圖3.1詞法分析器語(yǔ)法分析器預(yù)處理部分掃描器第8頁(yè)，共54頁(yè)，2023年，2月20日，星期三若識(shí)別輸入語(yǔ)句IF(5.EQ.M)GOTO100，若緩沖區(qū)情況如下所示：

IF(5.EQ.M)GO起點(diǎn)指示器搜索指示器輸入緩沖區(qū)

TO100IF(5.EQ.M)GO起點(diǎn)指示器搜索指示器輸入緩沖區(qū)TO100IF(5.EQ.M)GO起點(diǎn)指示器搜索指示器兩個(gè)互補(bǔ)輸入緩沖區(qū)120個(gè)字符掃描緩沖區(qū)的結(jié)構(gòu)：

緩沖區(qū)大?。?20個(gè)字符。采用兩個(gè)指示器：起點(diǎn)指示器、搜索指示器。

兩個(gè)互補(bǔ)區(qū)。第9頁(yè)，共54頁(yè)，2023年，2月20日，星期三3.2.2單詞符號(hào)的識(shí)別——超前搜索單詞符號(hào)識(shí)別的簡(jiǎn)單方法：超前搜索。關(guān)鍵字識(shí)別：

例如：在標(biāo)準(zhǔn)FORTRAN中

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

其中的DO、IF為關(guān)鍵字其中的DO、IF為標(biāo)識(shí)符的一部分第10頁(yè)，共54頁(yè)，2023年，2月20日，星期三標(biāo)識(shí)符的識(shí)別多數(shù)語(yǔ)言的標(biāo)識(shí)符是字母開(kāi)頭的“字母/數(shù)字”串，而且在程序中標(biāo)識(shí)符的出現(xiàn)后都跟著算符或界符。因此，不難識(shí)別。常數(shù)的識(shí)別對(duì)于某些語(yǔ)言的常數(shù)的識(shí)別也需要使用超前搜索。算符和界符的識(shí)別對(duì)于諸如C++語(yǔ)言中的“++”、“--”，這種復(fù)合成的算符，需要超前搜索。

第11頁(yè)，共54頁(yè)，2023年，2月20日，星期三3.2.3狀態(tài)轉(zhuǎn)換圖轉(zhuǎn)換圖：是一張有限方向圖。在狀態(tài)轉(zhuǎn)換圖中，結(jié)點(diǎn)代表狀態(tài)，用圓圈表示。狀態(tài)之間用箭弧連接。箭弧上的標(biāo)記（字符）代表在射出結(jié)狀態(tài)下可能出現(xiàn)的輸入字符或字符類(lèi)。狀態(tài)轉(zhuǎn)換圖的功能:用于識(shí)別一定的字符串。初態(tài)：一張轉(zhuǎn)換圖的啟動(dòng)條件，至少有一個(gè),用圓圈表示。終態(tài)：一張轉(zhuǎn)換圖的結(jié)束條件，至少有一個(gè)，用雙圈表示。*：表示多讀進(jìn)了一個(gè)字符。第12頁(yè)，共54頁(yè)，2023年，2月20日，星期三123XY(a)轉(zhuǎn)換圖示例201字母其他字母或數(shù)字*（b）識(shí)別標(biāo)識(shí)符的轉(zhuǎn)換圖其他201數(shù)字?jǐn)?shù)字*（c）識(shí)別整數(shù)的轉(zhuǎn)換圖例3-3：簡(jiǎn)單的狀態(tài)轉(zhuǎn)換圖示例：初態(tài)終態(tài)從0狀態(tài)到1狀態(tài)可能出現(xiàn)字母第13頁(yè)，共54頁(yè)，2023年，2月20日，星期三圖3.2狀態(tài)轉(zhuǎn)換圖7*65·數(shù)字101數(shù)字?jǐn)?shù)字2數(shù)字3E或D+或－數(shù)字其他E或D·數(shù)字其他數(shù)字例3-4：識(shí)別FORTRAN實(shí)型常數(shù)的轉(zhuǎn)換圖：例如下列實(shí)型常數(shù)可以被以下轉(zhuǎn)換圖識(shí)別：

1.23E+4.56E-7第14頁(yè)，共54頁(yè)，2023年，2月20日，星期三單詞符號(hào)種別編碼助憶符內(nèi)碼值DIM1$DIM－IF2$IF－DO3$DO－STOP4$STOP－END5$END－標(biāo)識(shí)符6$ID－常數(shù)（整）7$INT內(nèi)部字符串＝8$ASSIGN標(biāo)準(zhǔn)二進(jìn)制形式＋9$PLUS－*10$STAR－**11$POWER－

,12$COMMA－(13$LPAR－)14$RPAR－例3-5：綜合實(shí)例——做出識(shí)別下表所示的小語(yǔ)言的單詞符號(hào)的狀態(tài)轉(zhuǎn)換圖第15頁(yè)，共54頁(yè)，2023年，2月20日，星期三*120字母非字母與數(shù)字字母或數(shù)字*空白543數(shù)字?jǐn)?shù)字非數(shù)字*6101113127*89*非*，（）其他＝＋。。右圖即為對(duì)上頁(yè)所示的簡(jiǎn)單語(yǔ)言進(jìn)行詞法分析的狀態(tài)轉(zhuǎn)換圖。第16頁(yè)，共54頁(yè)，2023年，2月20日，星期三3.2.4狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)1、CHAR

字符變量，存放最新讀進(jìn)的源程序字符。2、TOKEN

字符數(shù)組，存放構(gòu)成單詞的字符串。3、GETCHAR

過(guò)程，將下一輸入字符讀入CHAR，搜索指示器前移一個(gè)字符。4、GETBC

過(guò)程，檢查CHAR中的字符是否為空白。若是，則調(diào)用GETCHAR

直至CHAR中進(jìn)入一個(gè)非空白字符。5、CONCAT

過(guò)程，把CHAR中的字符連接到TOKEN之后。6、LETTER

布爾函數(shù)過(guò)程，它們分別判斷CHAR中的字符是數(shù)字或是字母，

DIGIT

從而給出真假值TRUE、FALSE。7、RESERVE

整型函數(shù)過(guò)程，用TOKEN中的字符串查保留字表，若是一個(gè)保留字則給予編碼，否則回送0值（假定0不是保留字的編碼）。8、RETRACT

過(guò)程，把搜索指示器回調(diào)一個(gè)字節(jié)，把CHAR中的字符置為空白。第17頁(yè)，共54頁(yè)，2023年，2月20日，星期三以上函數(shù)和子程序過(guò)程都不難編制，使用它們能夠方便的構(gòu)造狀態(tài)轉(zhuǎn)換圖的對(duì)應(yīng)程序。一般，我們可以讓每一個(gè)狀態(tài)結(jié)對(duì)應(yīng)一個(gè)程序段。例如：我們可以讓不含回路的分叉結(jié)，對(duì)應(yīng)一個(gè)CASE語(yǔ)句，或者是一組IF…THEN…ELSE語(yǔ)句。具體見(jiàn)后面實(shí)例。

終態(tài)結(jié)一般對(duì)應(yīng)一個(gè)RETURN(C,VAL)語(yǔ)句。其中C為單詞種別編碼；VAL是字符數(shù)組的TOKEN，或者是一個(gè)整數(shù)值，或者無(wú)定義。具體見(jiàn)后面實(shí)例。第18頁(yè)，共54頁(yè)，2023年，2月20日，星期三為了把狀態(tài)轉(zhuǎn)換圖轉(zhuǎn)化成程序，每個(gè)狀態(tài)要建立一段程序，它要做的工作如下：第一步：從輸入緩沖區(qū)中取一個(gè)字符。為此，我們使用函數(shù)GETCHAR，每次調(diào)用它，推進(jìn)先行指針，送回一個(gè)字符。第二步：確定在本狀態(tài)下，哪一條箭弧是用剛剛來(lái)的輸入字符標(biāo)識(shí)的。如果找到，控制就轉(zhuǎn)到該弧所指向的狀態(tài)；若找不到，那么尋找該單詞的企圖就失敗了。失?。合刃兄羔槺仨氈匦禄氐介_(kāi)始指針處，并用另一狀態(tài)圖來(lái)搜索另一單詞。如果所有的狀態(tài)轉(zhuǎn)換圖都試過(guò)之后，還沒(méi)有匹配的，就表明這是一個(gè)詞法錯(cuò)誤，此時(shí)，調(diào)用錯(cuò)誤校正程序。GETCHAR是過(guò)程，將下一輸入字符讀入CHAR，搜索指示器前移一個(gè)字符。第19頁(yè)，共54頁(yè)，2023年，2月20日，星期三例3－6：以下CASE語(yǔ)句段對(duì)應(yīng)的狀態(tài)圖:statei：GETCHAR；

CASECHAROF‘A’..‘Z’：…statej…；‘0’..‘9’：…statek…；‘/’：…statel…；

END；

FAIL數(shù)字ijkl字母/字符變量，存放最新讀進(jìn)的源程序字符。過(guò)程，將下一輸入字符讀入CHAR，搜索指示器前移一個(gè)字符。第20頁(yè)，共54頁(yè)，2023年，2月20日，星期三對(duì)于如上的狀態(tài)轉(zhuǎn)換圖，狀態(tài)0的代碼如下所示：

state0：C:=GETCHAR;ifLETTER(C)thengotostate1elseFAIL()201字母其他字母或數(shù)字LETTER()是布爾函數(shù)過(guò)程，當(dāng)且僅當(dāng)C中的字符是字母，它返回真假值TRUE。FAIL()是例子程序，它移回先行指針（lookaheadpointer）,開(kāi)始下一狀態(tài)轉(zhuǎn)換圖，或調(diào)用出錯(cuò)程序。例3-7：示例——如何把狀態(tài)結(jié)對(duì)應(yīng)于一段程序：*第21頁(yè)，共54頁(yè)，2023年，2月20日，星期三對(duì)于如上的狀態(tài)轉(zhuǎn)換圖，狀態(tài)1的代碼如下所示：

state1：C:=GETCHAR;ifLETTER(C)orDIGIT(C)thengotostate1elseifDELIMITER(C)

thengotostate2elseFAIL()201字母其他字母或數(shù)字DIGIT()是布爾函數(shù)過(guò)程，當(dāng)且僅當(dāng)C中的字符是數(shù)字，它返回真假值TRUE。DELIMITER(C)是過(guò)程，只要碰到標(biāo)識(shí)符后的分界符，它返回TRUE。分界符一般為：空格、算術(shù)、邏輯符號(hào)，括號(hào)、‘＝’、‘；’、‘.’、‘，’。*第22頁(yè)，共54頁(yè)，2023年，2月20日，星期三對(duì)于如上的狀態(tài)轉(zhuǎn)換圖，終態(tài)——狀態(tài)2的代碼如下所示：

state2：RETRACT();

RETURN($id，INSTALL())201字母其他字母或數(shù)字RETRACT()是過(guò)程，由于分界符不屬于標(biāo)識(shí)符，所以我們要把先行指針回調(diào)一個(gè)字符。INSTALL()是過(guò)程，如我們識(shí)別出的標(biāo)識(shí)符不在符號(hào)表中，我們把它裝入符號(hào)表。我們還要給語(yǔ)法分析程序返回一個(gè)二元式。*如果同時(shí)識(shí)別標(biāo)識(shí)符和定義符，則需要修改為State2：修改之后，狀態(tài)2的代碼如下所示：

state2：RETRACT();c:=RESERVE();ifc=0thenRETURN($id，INSTALL)

elseRETURN(C,_)RESERVE()

整型函數(shù)過(guò)程,針對(duì)TOKEN中的字符串進(jìn)行查找，看其是否是保留字，是保留字給出它的編碼，否則回送0（假定0不是保留字編碼）。第23頁(yè)，共54頁(yè)，2023年，2月20日，星期三例3－8：以下程序段對(duì)應(yīng)的狀態(tài)圖

statei：GETCHAR；

WHILELETTERORDIGITDOGETCHAR；

statej：…布爾函數(shù)過(guò)程，它們分別判斷CHAR中的字符是數(shù)字或是字母，從而給出真假值TRUE、FALSE。ij其它字母或數(shù)字第24頁(yè)，共54頁(yè)，2023年，2月20日，星期三例3－9：以下程序段對(duì)應(yīng)的狀態(tài)圖‘0’…‘9’：BEGINWHILEDIGITDOBEGINCONCAT；GETCHAREND；

RETRACT；

RETURN($INT,DTB)

；

END；3非數(shù)字?jǐn)?shù)字?jǐn)?shù)字4*RETURN語(yǔ)句，對(duì)應(yīng)終態(tài)結(jié)，其中$INT為種別編碼，DTB為一個(gè)把十進(jìn)制轉(zhuǎn)換到二進(jìn)制的轉(zhuǎn)換函數(shù)。它把TOKEN中的數(shù)字譯成標(biāo)準(zhǔn)二進(jìn)制碼，并以此為函數(shù)值返回。第25頁(yè)，共54頁(yè)，2023年，2月20日，星期三正規(guī)式與正規(guī)集的遞歸定義：1、ε和Φ都是字母表∑上的正規(guī)式，它們所表示的正規(guī)集分別為{ε}和Φ；2、任何a∈∑，a是∑上的一個(gè)正規(guī)式，它所表示的正規(guī)集為{a}；3、正規(guī)式正規(guī)集正規(guī)式正規(guī)集UL(U)（U|V）L(U)∪L(V)VL(V)（U·V）L(U)L(V)(U)*

L(U)*（閉包）僅由有限次使用上述三步驟而得到的表達(dá)式才是∑上的正規(guī)式。僅由這些正規(guī)式所表示的子集才是∑上的正規(guī)集。3.3正規(guī)表達(dá)式與有限自動(dòng)機(jī)3.3.1正規(guī)式與正規(guī)集運(yùn)算符的優(yōu)先順序：先“*”，次“·”

，最后“|”“|”讀做“或”“·”讀做“連接”“*”讀做“閉包”∑*的子集U,V：

積UV={αβ|α∈U&β∈V}

n次積V=VVV…VV0={ε}V的閉包V*=V0UV1

UV2U…V的正則閉包V+=VV*第26頁(yè)，共54頁(yè)，2023年，2月20日，星期三例3-11：令∑＝{a，b}，下面是∑上的正規(guī)式和相應(yīng)的正規(guī)集：

正規(guī)式正規(guī)集

ba*∑上所有的以b為首，并且后跟任

意多個(gè)a的字，{b,ba,baa,baaa,…}

a(a|b)*

∑上所有的以a為首的字

(a|b)*(aa|bb)(a|b)*

∑上所有含有兩個(gè)連續(xù)的a或者b的字例310：令∑＝{A，B，0，1}，則：

正規(guī)式正規(guī)集

(A|B)(A|B|0|1)*

∑上“標(biāo)識(shí)符”的全體

(0|1)(0|1)*∑上“數(shù)”的全體若兩個(gè)正規(guī)式表示相同的正規(guī)集，則認(rèn)為二者等價(jià)，記為U=V。例如：b(ab)*=(ba)*b(a|b)*=(a*b*)*第27頁(yè)，共54頁(yè)，2023年，2月20日，星期三令U、V和W均為正規(guī)式，顯而易見(jiàn)，下列關(guān)系普遍成立：1、U|V=V|U（交換律）；2、U|(V|W)=(U|V)|W（結(jié)合律）；3、U(VW)=(UV)W（結(jié)合律）；4、U(V|W)=UV|UW（分配律）(V|W)U=VU|WU；5、εU=Uε=U。

第28頁(yè)，共54頁(yè)，2023年，2月20日，星期三3.3.2確定有限自動(dòng)機(jī)（DFA）一個(gè)確定有限自動(dòng)機(jī)（DFA）M是一個(gè)五元式：M＝(S,∑,δ,s0,F)，其中1、S是一個(gè)有限集，它的每個(gè)元素稱(chēng)為一個(gè)狀態(tài)2、∑是一個(gè)有窮字母表，它的每個(gè)元素稱(chēng)為一個(gè)輸入字符3、δ是一個(gè)從S×∑至S的單值部分映射。δ(s,a)=s′意味著：當(dāng)現(xiàn)行狀態(tài)為、輸入字符為a時(shí)，將轉(zhuǎn)換到下一狀態(tài)s′。我們稱(chēng)s′為s的一個(gè)后繼狀態(tài)。4、s0∈S是唯一的初態(tài)5、FS是一個(gè)終態(tài)集（可空）。第29頁(yè)，共54頁(yè)，2023年，2月20日，星期三顯然，一個(gè)DFA可用一個(gè)矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示δ(s,a)的值。這個(gè)矩陣稱(chēng)為狀態(tài)轉(zhuǎn)換矩陣。例3-12：有DFA

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)=3

狀態(tài)ab012132213333相應(yīng)的狀態(tài)轉(zhuǎn)換矩陣如下表：第30頁(yè)，共54頁(yè)，2023年，2月20日，星期三

一個(gè)DFA也可用一張（確定的）狀態(tài)轉(zhuǎn)換圖來(lái)表示。假定DFAM含有m個(gè)狀態(tài)和n個(gè)輸入字符，那么，這個(gè)狀態(tài)轉(zhuǎn)換圖含有m個(gè)狀態(tài)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)頂多有n條箭弧射出和別的結(jié)點(diǎn)相連接，整張圖含有一個(gè)初態(tài)結(jié)點(diǎn)和若干個(gè)（可以為0）終態(tài)結(jié)點(diǎn)。301圖3.5狀態(tài)轉(zhuǎn)換圖2aaaabbb狀態(tài)aB012132213333如下表所示的狀態(tài)轉(zhuǎn)換矩陣對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖如右圖：第31頁(yè)，共54頁(yè)，2023年，2月20日，星期三3012aaabbb上圖所示的狀態(tài)轉(zhuǎn)換圖的S、∑及∑*如下：S={0,1,2,3}∑={a,b}∑*={α|α為ε，或者α為a、b的任意組合}從初態(tài)0到終態(tài)3有如圖所示的通路，箭弧上到標(biāo)記符連接起來(lái)的字aa屬于∑*，所以右圖所示的DFA可以識(shí)別字aa。同理：從初態(tài)0到終態(tài)3還有如圖所示的通路，箭弧上到標(biāo)記符連接起來(lái)的字bba屬于∑*，所以右圖所示的DFA可以識(shí)別字bba。a第32頁(yè)，共54頁(yè)，2023年，2月20日，星期三例3-13：科學(xué)表示法中數(shù)字常量的正則表達(dá)式對(duì)應(yīng)的DFA：digitdigitnat對(duì)應(yīng)的DFA如下圖

digit=[0-9]nat=digit+

signedNat=(+|-)?natnumber=signedNat(“·”nat)？signedNat對(duì)應(yīng)的DFA如下圖加上可選的小數(shù)部分，數(shù)字常量的正則表達(dá)式number=signedNat(“·”nat)？對(duì)應(yīng)的DFA如下圖：+digitdigitdigit-+digitdigitdigit-digitdigit?第33頁(yè)，共54頁(yè)，2023年，2月20日，星期三abbb接受與正則式ab+|ab*|b*

相同的語(yǔ)言的DFA如下所示：第34頁(yè)，共54頁(yè)，2023年，2月20日，星期三例3-14：串中只有一個(gè)b被如下所示的DFA接受：bnotbnotb例3-15：包含最多一個(gè)b的串被如下所示的DFA接受：bnotbnotb注意二者之間的區(qū)別第35頁(yè)，共54頁(yè)，2023年，2月20日，星期三

定理：如果一個(gè)DFAM的輸入字母表為∑，則我們也稱(chēng)M是∑上的一個(gè)DFA。可以證明：∑上的一個(gè)字集V∑*是正規(guī)的，當(dāng)且僅當(dāng)存在∑上的DFAM，使得V=L(M)。DFA的確定性表現(xiàn)在映射δ：S×∑→S是一個(gè)單值函數(shù)。即：對(duì)于任何狀態(tài)s∈S和輸入符號(hào)a∈∑，δ(s,a)唯一確定了一個(gè)狀態(tài)。從轉(zhuǎn)換圖角度，我們也可以得到答案。如果允許是一個(gè)多值函數(shù)，我們就得到下一節(jié)要講到的非確定自動(dòng)機(jī)的概念。第36頁(yè)，共54頁(yè)，2023年，2月20日，星期三3.3.3非確定有限自動(dòng)機(jī)（NFA）一個(gè)非確定有限自動(dòng)機(jī)（NFA）M是一個(gè)五元式：

M＝(S,∑,δ,S0,F)，其中1、S是一個(gè)有限集，它的每個(gè)元素稱(chēng)為一個(gè)狀態(tài)2、∑是一個(gè)有窮字母表，它的每個(gè)元素稱(chēng)為一個(gè)輸入字符3、δ是一個(gè)從S×∑*至S的子集的映射，即δ：S×∑*

→2s4、S0∈S是唯一的初態(tài)5、FS是一個(gè)終態(tài)集（可空）。第37頁(yè)，共54頁(yè)，2023年，2月20日，星期三一個(gè)含有m個(gè)狀態(tài)和n個(gè)輸入字符的NFA可用一張如下的狀態(tài)轉(zhuǎn)換圖來(lái)表示：該圖含有m個(gè)狀態(tài)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)可以射出若干條弧與別的結(jié)點(diǎn)相連接，每條弧用∑*中的一個(gè)字（可以是不同的字，也可以是空字）做標(biāo)記，整張圖至少含有一個(gè)初態(tài)結(jié)點(diǎn)和若干個(gè)（可以為0）終態(tài)結(jié)點(diǎn)。某些結(jié)點(diǎn)既可以是初態(tài)結(jié)點(diǎn)也可以是終態(tài)結(jié)點(diǎn)。1aaa,b2bbab0a,b01ab,baaa,bbab,baaa,bb第38頁(yè)，共54頁(yè)，2023年，2月20日，星期三yx15aaaabεb4326bbεεε下圖所示的狀態(tài)轉(zhuǎn)換圖的S、∑及∑*如下：S={0,1,2,3}∑={a,b}∑*={α|α為ε，或者α為a、b的任意組合}對(duì)于∑*中的任何一個(gè)字α，若存在一條從某一初態(tài)結(jié)點(diǎn)到某一終態(tài)結(jié)點(diǎn)的通路，且這條通路上所有弧上的標(biāo)記字依序連接成的字（忽略ε）等于α，則稱(chēng)α可以為NFAM識(shí)別。從初態(tài)x到終態(tài)y的連接通路弧上，有如下標(biāo)記字：εεaaεε，去除ε，為aa，所以字aa可為NFA接受。第39頁(yè)，共54頁(yè)，2023年，2月20日，星期三1432aaεbεε例3-16：上圖所示的NFA的以下兩個(gè)轉(zhuǎn)換序列都可以接受串a(chǎn)bb：允許接受ab允許接受與ab*匹配的字符串允許接受與b*匹配的字符串允許接受與ab+匹配的字符串由此，我們可以看出這個(gè)NFA接受與正則式ab+|ab*|b*

相同的語(yǔ)言！接受ab接受ab接受ab＋接受ab接受ab＋接受ab*接受ab接受ab＋接受ab*接受b*第40頁(yè)，共54頁(yè)，2023年，2月20日，星期三練習(xí)：考慮以下NFA通過(guò)怎樣的轉(zhuǎn)換接受串a(chǎn)cab：10aε21b3756489εεεεεεεεc第41頁(yè)，共54頁(yè)，2023年，2月20日，星期三

DFA是NFA的特例，可以采用子集法將NFA確定化。假定I是NFAM的狀態(tài)集的一個(gè)子集，我們定義ε_(tái)CLOSURE(I)為：

1、若s∈I，則s∈ε_(tái)CLOSURE(I)；2、若s∈I，那么從s出發(fā)經(jīng)過(guò)任意條ε弧而能到達(dá)的任何狀態(tài)s’都屬于ε_(tái)CLOSURE(I)。狀態(tài)集ε_(tái)CLOSURE(I)稱(chēng)為I的ε_(tái)閉包。ε_(tái)CLOSURE(I)的定義第42頁(yè)，共54頁(yè)，2023年，2月20日，星期三假定I是NFAM的狀態(tài)集的子集，a∈∑,定義Ia=ε_(tái)CLOSURE(J)其中，J是那些可從I中的某一狀態(tài)結(jié)點(diǎn)出發(fā)經(jīng)過(guò)一條a弧而到達(dá)的狀態(tài)結(jié)點(diǎn)的全體。Ia定義第43頁(yè)，共54頁(yè)，2023年，2月20日，星期三∑={a1,a2,….ak}。先構(gòu)造一張表，該表每一行含有k+1列。置該表的首行首列為ε_(tái)CLOSURE(X)。重復(fù)上述過(guò)程，直至所有第二列和第三列的子集均已在第一列上出現(xiàn)了為止。如果某一行的第一列的狀態(tài)子集已經(jīng)確定，例如記為I,那么，求出這一行的第二個(gè)和第三個(gè)子集Ia和Ib看它們是否已在表的第一列出現(xiàn)，將未出現(xiàn)的填入到后面空行的第一列。

1表的初始化構(gòu)造2處理表的一行3重復(fù)處理子集算法第44頁(yè)，共54頁(yè)，2023年，2月20日，星期三例3-17：考慮下圖所示NFA的確定化：yx15aaaabεb4326bbεεεIIaIb{X,5,1}{5,3,1}{5,4,1}{5,3,1}{5,3,1,2,6,Y}{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}I=ε_(tái)CLOSURE{X}為{X,5,1}。從狀態(tài)I出發(fā)經(jīng)過(guò)一條a弧而能到達(dá)的狀態(tài)全體J為{5,3},而ε_(tái)CLOSURE(J)={5,3,1}。從而Ia={5,3,1}。初態(tài)ε_(tái)閉包{X,5,1}Ja為{5,3}ε_(tái)CLOSURE(J)為{5,3，1}（根據(jù)ε_(tái)閉包的定義）根據(jù)此方法依次求出左邊表中的狀態(tài)轉(zhuǎn)換矩陣即可。第45頁(yè)，共54頁(yè)，2023年，2月20日，星期三對(duì)右下圖表中的所有子集重新命名，得到左圖中的狀態(tài)轉(zhuǎn)換矩陣形成如下?tīng)顟B(tài)轉(zhuǎn)換矩陣，從而得到相應(yīng)的DFA。如圖所示：sab0121322153344655656343012aaaabbb546abbabIIaIb{X,5,1}{5,3,1}{5,4,1}{5,3,1}{5,3,1,2,6,Y}{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}重命名為狀態(tài)0重命名為狀態(tài)1根據(jù)重命名的狀態(tài)填寫(xiě)表格ab第46頁(yè)，共54頁(yè)，2023年，2月20日，星期三例3-18：考慮下圖所示NFA的確定化：{1}在letter上有到{2}的轉(zhuǎn)換：{2}={2，3，4，5，7，10}{2,3,4,5,7,10}letter在letter上有到{6}的轉(zhuǎn)換：{6}={4，5，6，7，9，10}{4,5,6，7,9，10}letter在digit上有到{8}的轉(zhuǎn)換：{8}={4，5，7，8，9，10}{4,5,7，8,9，10}digitletterdigitdigitletter注意：所有這些狀態(tài)都有在letter和digit上的轉(zhuǎn)換。上圖所示NFA的確定化后的DFA如下：子集構(gòu)造過(guò)程如下：初始狀態(tài)：{1}={1}78ε10letterε43letter59612εεεεεεdigitε第47頁(yè)，共54頁(yè)，2023年，2月20日，星期三3.3.4正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性對(duì)于正規(guī)文法G和有限自動(dòng)機(jī)M，如果L(G)=L(M),則稱(chēng)G和M是等價(jià)的。關(guān)于正規(guī)文法和有限自動(dòng)機(jī)的等價(jià)性，有以下結(jié)論：1、對(duì)于每一個(gè)正規(guī)文法G，都存在一個(gè)有限自動(dòng)機(jī)M，使得L(M)=L(G)。2、對(duì)于每一個(gè)有限自動(dòng)機(jī)M，都存在一個(gè)正規(guī)文法G,使得L(M)=