編譯原理-(第三章詞法分析)課件

第二章詞法分析詞法分析的：

從左至右逐個(gè)字符地掃描源程序，產(chǎn)生一個(gè)個(gè)的，把作為字符串的源程序改造成為單詞符號(hào)串的中間程序。詞法分析器/掃描器：執(zhí)行詞法分析的程序。源程序掃描器scanner1、關(guān)鍵字詞法分析器的功能如下圖所示：2、標(biāo)識(shí)符5、界符4、運(yùn)算符3、常數(shù)由程序語(yǔ)言定義的具有固定意義的標(biāo)識(shí)符。也可稱為保留字或基本字。例如：Pascal中的begin，end，if等。界符：如逗號(hào)、分號(hào)、括號(hào)、/*，*/等。它是確定的。運(yùn)算符：如+、-、*、/等。它是確定的。常數(shù)的類型一般有整型、實(shí)型、布爾型、文字型等。它是不限的。用來(lái)表示各種名字，如變量名、數(shù)組名、過(guò)程名等。它是不限的。2.1對(duì)詞法分析器的要求2.1.1詞法分析器的功能和輸出形式詞法分析器的功能：輸入源程序，輸出單詞符號(hào)。單詞符號(hào)：一個(gè)程序語(yǔ)言的基本語(yǔ)法符號(hào)。分為以下5種。

1、關(guān)鍵字：由程序語(yǔ)言定義的具有固定意義的標(biāo)識(shí)符。也可稱為保留字或基本字。例如：Pascal中的begin，end，if等。它是確定的。2、標(biāo)識(shí)符：用來(lái)表示各種名字，如變量名、數(shù)組名、過(guò)程名等。它是不限的。3、常數(shù)：常數(shù)的類型一般有整型、實(shí)型、布爾型、文字型等。它是不限的。4、運(yùn)算符：如+、-、*、/等。它是確定的。5、界符：如逗號(hào)、分號(hào)、括號(hào)、/*，*/等。它是確定的。確定不限例2-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ù)類型，種別編碼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)制表示。例2-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)表指針)(--，_)(；，_)2.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作為子程序若識(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ū)。2.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í)符的一部分標(biāo)識(shí)符的識(shí)別多數(shù)語(yǔ)言的標(biāo)識(shí)符是字母開頭的“字母/數(shù)字”串，而且在程序中標(biāo)識(shí)符的出現(xiàn)后都跟著算符或界符。因此，不難識(shí)別。常數(shù)的識(shí)別對(duì)于某些語(yǔ)言的常數(shù)的識(shí)別也需要使用超前搜索。算符和界符的識(shí)別對(duì)于諸如C++語(yǔ)言中的“++”、“--”，這種復(fù)合成的算符，需要超前搜索。

XY(a)轉(zhuǎn)換圖示例2字母其他字母或數(shù)字*（b）識(shí)別標(biāo)識(shí)符的轉(zhuǎn)換圖其他2數(shù)字?jǐn)?shù)字*（c）識(shí)別整數(shù)的轉(zhuǎn)換圖例2-3：簡(jiǎn)單的狀態(tài)轉(zhuǎn)換圖示例：初態(tài)終態(tài)從0狀態(tài)到1狀態(tài)可能出現(xiàn)字母圖2.2狀態(tài)轉(zhuǎn)換圖7*·數(shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字E或D+或－數(shù)字其他E或D·數(shù)字其他數(shù)字例2-4：識(shí)別FORTRAN實(shí)型常數(shù)的轉(zhuǎn)換圖：例如下列實(shí)型常數(shù)可以被以下轉(zhuǎn)換圖識(shí)別：1.23E+4.56E-7單詞符號(hào)種別編碼助憶符內(nèi)碼值DIM1$DIM－IF2$IF－DO3$DO－STOP4$STOP－END5$END－標(biāo)識(shí)符6$ID內(nèi)部字符串常數(shù)（整）7$INT標(biāo)準(zhǔn)二進(jìn)制形式＝8$ASSIGN－＋9$PLUS－*10$STAR－**11$POWER－,12$COMMA－(13$LPAR－)14$RPAR－例2-5：綜合實(shí)例——做出識(shí)別下表所示的小語(yǔ)言的單詞符號(hào)的狀態(tài)轉(zhuǎn)換圖2.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中的字符置為空白。以上函數(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ǔ)句。具體見后面實(shí)例。

終態(tài)結(jié)一般對(duì)應(yīng)一個(gè)RETURN(C,VAL)語(yǔ)句。其中C為單詞種別編碼；VAL是字符數(shù)組的TOKEN，或者是一個(gè)整數(shù)值，或者無(wú)定義。具體見后面實(shí)例。為了把狀態(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)；若找不到，那么尋找該單詞的企圖就失敗了。失?。合刃兄羔槺仨氈匦禄氐介_始指針處，并用另一狀態(tài)圖來(lái)搜索另一單詞。如果所有的狀態(tài)轉(zhuǎn)換圖都試過(guò)之后，還沒(méi)有匹配的，就表明這是一個(gè)詞法錯(cuò)誤，此時(shí)，調(diào)用錯(cuò)誤校正程序。GETCHAR是過(guò)程，將下一輸入字符讀入CHAR，搜索指示器前移一個(gè)字符。對(duì)于如上的狀態(tài)轉(zhuǎn)換圖，狀態(tài)0的代碼如下所示：

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

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

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

state2：RETRACT();

RETURN($id，INSTALL())2字母其他字母或數(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不是保留字編碼）。例2－9：以下程序段對(duì)應(yīng)的狀態(tài)圖‘0’…‘9’：BEGINWHILEDIGITDOBEGINCONCAT；GETCHAREND；

RETRACT；

RETURN($INT,DTB)；END；非數(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ù)值返回。正規(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ī)集。2.3正規(guī)表達(dá)式與有限自動(dòng)機(jī)2.3.1正規(guī)式與正規(guī)集運(yùn)算符的優(yōu)先順序：先“*”，次“·”，最后“|”“|”讀做“或”“·”讀做“連接”“*”讀做“閉包”∑*的子集U,V：

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

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

UV1

UV2U…V的正則閉包V+=VV*2.3.2確定有限自動(dòng)機(jī)（DFA）一個(gè)確定有限自動(dòng)機(jī)（DFA）M是一個(gè)五元式：M＝(S,∑,δ,s0,F)，其中1、S是一個(gè)有限集，它的每個(gè)元素稱為一個(gè)狀態(tài)2、∑是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符3、δ是一個(gè)從S×∑至S的單值部分映射。δ(s,a)=s′意味著：當(dāng)現(xiàn)行狀態(tài)為S、輸入字符為a時(shí)，將轉(zhuǎn)換到下一狀態(tài)s′。我們稱s′為s的一個(gè)后繼狀態(tài)。4、s0∈S是唯一的初態(tài)5、FS是一個(gè)終態(tài)集（可空）。顯然，一個(gè)DFA可用一個(gè)矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示δ(s,a)的值。這個(gè)矩陣稱為狀態(tài)轉(zhuǎn)換矩陣。例2-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)換矩陣如下表：

一個(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)。3圖2.5狀態(tài)轉(zhuǎn)換圖aaaabbb狀態(tài)ab01213221333-如下表所示的狀態(tài)轉(zhuǎn)換矩陣對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖如右圖：3aaabbb上圖所示的狀態(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例2-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?abbb接受與正則式ab+|ab*|b*相同的語(yǔ)言的DFA如下所示：例2-14：串中只有一個(gè)b被如下所示的DFA接受：bnotbnotb例2-15：包含最多一個(gè)b的串被如下所示的DFA接受：bnotbnotb注意二者之間的區(qū)別

定理：如果一個(gè)DFAM的輸入字母表為∑，則我們也稱M是∑上的一個(gè)DFA?？梢宰C明:∑上的一個(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ī)的概念。2.3.3非確定有限自動(dòng)機(jī)（NFA）一個(gè)非確定有限自動(dòng)機(jī)（NFA）M是一個(gè)五元式：

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

→2s4、S0∈S是唯一的初態(tài)5、FS是一個(gè)終態(tài)集（可空）。一個(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,b2bbaba,b0ab,baaa,bbab,baaa,bbyaaaabεbbbεεε下圖所示的狀態(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)記字依序連接成的字（忽略ε）等于α，則稱α可以為NFAM識(shí)別。從初態(tài)x到終態(tài)y的連接通路弧上，有如下標(biāo)記字：εεaaεε，去除ε，為aa，所以字aa可為NFA接受。4aaεbεε例2-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*練習(xí)：考慮以下NFA通過(guò)怎樣的轉(zhuǎn)換接受串a(chǎn)cab：10aεbεεεεεεεεcDFA是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)稱為I的ε_(tái)閉包。ε_(tái)CLOSURE(I)的定義假定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定義∑={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ù)處理子集算法例2-17：考慮下圖所示NFA的確定化：yaaaabεbbbεεε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)換矩陣即可。對(duì)右下圖表中的所有子集重新命名，得到左圖中的狀態(tài)轉(zhuǎn)換矩陣形成如下狀態(tài)轉(zhuǎn)換矩陣，從而得到相應(yīng)的DFA。如圖所示：sab0121322153344655656343aaaabbb546abbabIIaIb{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)填寫表格ab例2-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}ε10letterεletterεεεεεε