編譯原理-西安交通大學(xué)(馮博琴)2_詞法分析_30

1、 詞法分析的詞法分析的任務(wù)任務(wù)： 從左至右逐個(gè)字符地掃描源程序，產(chǎn)生從左至右逐個(gè)字符地掃描源程序，產(chǎn)生一個(gè)個(gè)的一個(gè)個(gè)的單詞符號(hào)單詞符號(hào)，把作為字符串的源程序，把作為字符串的源程序改造成為單詞符號(hào)串的改造成為單詞符號(hào)串的中間程序中間程序。 詞法分析器詞法分析器/ /掃描器掃描器：執(zhí)行詞法分析的程序。執(zhí)行詞法分析的程序。源程序掃描器scanner1 1、關(guān)鍵字、關(guān)鍵字詞法分析器的詞法分析器的功能功能如下圖所示：如下圖所示：2 2、標(biāo)識(shí)符、標(biāo)識(shí)符5 5、界符、界符4 4、運(yùn)算符、運(yùn)算符3 3、常數(shù)、常數(shù)由程序語言定義的具有固定意義的標(biāo)識(shí)符。也可稱為保留字或基本字。例如：Pascal中的begin，e

2、nd，if等。界符：如逗號(hào)、分號(hào)、括號(hào)、/*，*/ 等。它是確定的。運(yùn)算符：如+、-、*、/ 等。它是確定的。常數(shù)的類型一般有整型、實(shí)型、布爾型、文字型等。它是不限的。用來表示各種名字，如變量名、數(shù)組名、過程名等。它是不限的。詞法分析器的詞法分析器的功能功能：輸入源程序，輸出單詞符號(hào)。：輸入源程序，輸出單詞符號(hào)。單詞符號(hào)單詞符號(hào)：一個(gè)程序語言的基本語法符號(hào)。分為以下：一個(gè)程序語言的基本語法符號(hào)。分為以下5 5種。種。 1 1、關(guān)鍵字關(guān)鍵字：由程序語言定義的具有固定意義的標(biāo)識(shí)符。也：由程序語言定義的具有固定意義的標(biāo)識(shí)符。也可稱為保留字或基本字。例如：可稱為保留字或基本字。例如：PascalPas

3、cal中的中的beginbegin，endend，ifif等。它是等。它是確定確定的。的。 2 2、標(biāo)識(shí)符標(biāo)識(shí)符：用來表示各種名字，如變量名、數(shù)組名、過程：用來表示各種名字，如變量名、數(shù)組名、過程名等。它是名等。它是不限不限的。的。 3 3、常數(shù)常數(shù)：常數(shù)的類型一般有整型、實(shí)型、布爾型、文字型：常數(shù)的類型一般有整型、實(shí)型、布爾型、文字型等。它是等。它是不限不限的。的。 4 4、運(yùn)算符運(yùn)算符：如：如+ +、- -、* *、/ / 等。它是等。它是確定確定的。的。 5 5、界符界符：如逗號(hào)、分號(hào)、括號(hào)、：如逗號(hào)、分號(hào)、括號(hào)、/ /* *，* */ / 等。它是等。它是確定確定的。的。確定確定不限不

4、限單詞符號(hào)的表示形式單詞符號(hào)的表示形式：詞法分析器所輸出的單詞符號(hào)常常表示成：詞法分析器所輸出的單詞符號(hào)常常表示成 二元式（單詞種別，單詞自身的值）二元式（單詞種別，單詞自身的值）。 單詞種別單詞種別可以用以下形式表示：可以用以下形式表示： 1 1、一類單詞統(tǒng)一用一個(gè)整數(shù)值代表其屬性。例如：、一類單詞統(tǒng)一用一個(gè)整數(shù)值代表其屬性。例如：1 1代表關(guān)鍵字，代表關(guān)鍵字，2 2代表標(biāo)識(shí)符等。代表標(biāo)識(shí)符等。 2 2、每一個(gè)單詞一個(gè)類別。例如：、每一個(gè)單詞一個(gè)類別。例如：1 1代表代表BEGINBEGIN，2 2代表代表ENDEND等。等。單詞自身的值單詞自身的值可以表示成：常量的二進(jìn)制表示；常量、變量等

5、在符號(hào)表可以表示成：常量的二進(jìn)制表示；常量、變量等在符號(hào)表種的地址碼，等等。種的地址碼，等等。注意：注意：一個(gè)語言的單詞符號(hào)如何分種，分幾種，怎樣編碼，是一個(gè)技術(shù)一個(gè)語言的單詞符號(hào)如何分種，分幾種，怎樣編碼，是一個(gè)技術(shù)問題。標(biāo)識(shí)符一般同歸為一種。常數(shù)則宜按類型（整、實(shí)、布爾）分。問題。標(biāo)識(shí)符一般同歸為一種。常數(shù)則宜按類型（整、實(shí)、布爾）分。關(guān)鍵字可以將其全體視為一種，也可關(guān)鍵字可以將其全體視為一種，也可一字一種一字一種。運(yùn)算符可采用一符一種，運(yùn)算符可采用一符一種，但也可把具有一定共性的視為一種。界符則一般采用但也可把具有一定共性的視為一種。界符則一般采用一符一種一符一種。如何進(jìn)。如何進(jìn)行分種主

6、要取決于處理上的方便。行分種主要取決于處理上的方便。 若是一符一種分種，單詞自身值就不需要了。否則，要查符號(hào)表。若是一符一種分種，單詞自身值就不需要了。否則，要查符號(hào)表。例例2-12-1：151151FORTRANFORTRAN編譯程序的詞法分析器在掃描輸入串編譯程序的詞法分析器在掃描輸入串 IF (5EQIF (5EQM) GOTO 100M) GOTO 100 后，它輸出的后，它輸出的單詞符號(hào)串單詞符號(hào)串是：是： 邏輯邏輯IF IF （3434，_ _） 左括號(hào)左括號(hào) （2 2，_ _） 整常數(shù)整常數(shù) （2020，55的二進(jìn)制表示）的二進(jìn)制表示） 等號(hào)等號(hào) （6 6，_ _） 標(biāo)識(shí)符標(biāo)識(shí)符

7、 （2626，MM） 右括號(hào)右括號(hào) （1616，_ _） GOTO GOTO （3030，_ _） 標(biāo)號(hào)標(biāo)號(hào) （1919，100100的二進(jìn)制表示）的二進(jìn)制表示）IFIF為關(guān)鍵字，種別編碼為關(guān)鍵字，種別編碼3434，采用一符一種的編碼方式。采用一符一種的編碼方式。常數(shù)類型，種別編碼常數(shù)類型，種別編碼2020，單詞自，單詞自身的值為身的值為55的二進(jìn)制表示。的二進(jìn)制表示。(為界符，種別編碼為界符，種別編碼2 2，采，采用一符一種的編碼方式。用一符一種的編碼方式。等號(hào)為運(yùn)算符，種別編碼等號(hào)為運(yùn)算符，種別編碼6 6，采用一符一種的編碼方式。采用一符一種的編碼方式。M M為標(biāo)識(shí)符，種別編碼為標(biāo)識(shí)符，種

8、別編碼2626，單，單詞自身值為詞自身值為MM。)為界符，種別編碼為界符，種別編碼1616，采用一符一種的編碼方式。采用一符一種的編碼方式。GOTOGOTO為關(guān)鍵字，種別編碼為關(guān)鍵字，種別編碼3030，采用一符一種的編碼方式。采用一符一種的編碼方式。100100為標(biāo)號(hào)，種別編碼為標(biāo)號(hào)，種別編碼1919，單詞，單詞內(nèi)部的值用內(nèi)部的值用100100的二進(jìn)制表示。的二進(jìn)制表示。例例2-2 2-2 ：下述：下述C+C+代碼段：代碼段：while ( i = j ) i - -while ( i = j ) i - -； 經(jīng)詞法分析器處理以后，它將被轉(zhuǎn)換為如下的經(jīng)詞法分析器處理以后，它將被轉(zhuǎn)換為如下的單

9、詞符號(hào)串單詞符號(hào)串 ( while ( while ，_ )_ )( ( ( ( ，_ )_ )( id ( id ，指向，指向i i的符號(hào)表指針的符號(hào)表指針 ) )( = ( = ，_ )_ )( id ( id ，指向，指向j j的符號(hào)表指針的符號(hào)表指針 ) )( ) ( ) ，_ )_ )( id ( id ，指向，指向i i的符號(hào)表指針的符號(hào)表指針 ) )( - - ( - - ，_ _ ) )( ( ； ，_ )_ )1 1、把詞法分析從語法分析中脫離出來的、把詞法分析從語法分析中脫離出來的優(yōu)點(diǎn)優(yōu)點(diǎn)：使編譯程序的使編譯程序的結(jié)構(gòu)結(jié)構(gòu)更加簡(jiǎn)潔、清晰和條理化。更加簡(jiǎn)潔、清晰和條理化。詞法

10、分析和語法分析詞法分析和語法分析方法方法不同，詞法分析可以使用正則文法自動(dòng)構(gòu)造不同，詞法分析可以使用正則文法自動(dòng)構(gòu)造scannerscanner簡(jiǎn)單。簡(jiǎn)單。有利于提高語法分析的有利于提高語法分析的效率效率?？梢愿纳圃~法分析的細(xì)節(jié)，甚至于一個(gè)語法分析配幾個(gè)可以改善詞法分析的細(xì)節(jié)，甚至于一個(gè)語法分析配幾個(gè)scannerscanner，把不同，把不同的輸入變成一種內(nèi)部表示。的輸入變成一種內(nèi)部表示。2 2、把詞法分析作為獨(dú)立的一、把詞法分析作為獨(dú)立的一遍遍scannerscanner當(dāng)作一遍。當(dāng)作一遍。把把scannerscanner當(dāng)作子程序。當(dāng)作子程序。 外存外存scannerscanner語法分

11、析語法分析源程序單詞符號(hào)scannerscanner作為一遍作為一遍語法語法分析分析scannerscanner源程序源程序scannerscanner作為子程序作為子程序設(shè)計(jì)前提設(shè)計(jì)前提： 把把scannerscanner作為一個(gè)獨(dú)立的子程序；作為一個(gè)獨(dú)立的子程序； 詞法分析器的任務(wù)為輸出單詞符號(hào)。詞法分析器的任務(wù)為輸出單詞符號(hào)。必要性必要性：編輯性字符如空白符、回車符等，除了出現(xiàn)在文字和編輯性字符如空白符、回車符等，除了出現(xiàn)在文字和 常數(shù)中以外，在別處出現(xiàn)都沒有意義。常數(shù)中以外，在別處出現(xiàn)都沒有意義。功功 能能： 剔除無用字符。剔除無用字符。實(shí)實(shí) 現(xiàn)現(xiàn)： 預(yù)處理子程序。預(yù)處理子程序。輸入列

12、表預(yù)處理預(yù)處理子程序子程序掃描器掃描器掃描緩沖區(qū)掃描緩沖區(qū)輸入緩沖區(qū)輸入緩沖區(qū)單詞符號(hào)圖圖2.1 2.1 詞法分析器詞法分析器語法分析器語法分析器預(yù)預(yù)處處理理部部分分掃掃描描器器若若識(shí)別識(shí)別輸入語句輸入語句 IF (5.EQ.M) GOTO 100，若緩沖區(qū)情況如下所示：，若緩沖區(qū)情況如下所示： IF (5.EQ.M) GO 起點(diǎn)指示器起點(diǎn)指示器 搜索指示器搜索指示器輸入緩沖區(qū)輸入緩沖區(qū) TO 100 IF (5.EQ.M) GO 起點(diǎn)指示器起點(diǎn)指示器 搜索指示器搜索指示器輸入緩沖區(qū)輸入緩沖區(qū)TO 100 IF (5.EQ.M) GO 起點(diǎn)指示器起點(diǎn)指示器搜索指示器搜索指示器兩兩 個(gè)個(gè) 互互

13、補(bǔ)補(bǔ) 輸輸 入入 緩緩 沖沖 區(qū)區(qū)120個(gè)字符個(gè)字符掃描緩沖區(qū)的掃描緩沖區(qū)的結(jié)構(gòu)結(jié)構(gòu)： 緩沖區(qū)大小緩沖區(qū)大?。?20120個(gè)字符。個(gè)字符。 采用兩個(gè)采用兩個(gè)指示器指示器：起點(diǎn)指示器、搜索指示器。：起點(diǎn)指示器、搜索指示器。 兩個(gè)互補(bǔ)區(qū)兩個(gè)互補(bǔ)區(qū)。單詞符號(hào)識(shí)別的簡(jiǎn)單方法：?jiǎn)卧~符號(hào)識(shí)別的簡(jiǎn)單方法：超前搜索。關(guān)鍵字識(shí)別關(guān)鍵字識(shí)別： 例如：在標(biāo)準(zhǔn)例如：在標(biāo)準(zhǔn)FORTRANFORTRAN中中 1 1、DO99KDO99K = 1,10 = 1,10 2 2、IFIF(5.EQ.M)I = 10(5.EQ.M)I = 10 3 3、DO99KDO99K = 1.10 = 1.10 4 4、IFIF(5) =

14、 55(5) = 55 其中的其中的DODO、IFIF為關(guān)鍵字為關(guān)鍵字其中的其中的DODO、IFIF為標(biāo)識(shí)符為標(biāo)識(shí)符的一部分的一部分標(biāo)識(shí)符的識(shí)別標(biāo)識(shí)符的識(shí)別 多數(shù)語言的標(biāo)識(shí)符是字母開頭的多數(shù)語言的標(biāo)識(shí)符是字母開頭的“字母字母/ /數(shù)字?jǐn)?shù)字”串，串，而且在程序中標(biāo)識(shí)符的出現(xiàn)后都跟著算符或界符。因此，而且在程序中標(biāo)識(shí)符的出現(xiàn)后都跟著算符或界符。因此，不難識(shí)別。不難識(shí)別。常數(shù)的識(shí)別常數(shù)的識(shí)別 對(duì)于某些語言的常數(shù)的識(shí)別也需要使用超前搜索。對(duì)于某些語言的常數(shù)的識(shí)別也需要使用超前搜索。算符和界符的識(shí)別算符和界符的識(shí)別 對(duì)于諸如對(duì)于諸如C+C+語言中的語言中的“+ +”+ +”、“- -”- -”，這種復(fù)，

15、這種復(fù)合成的算符，需要超前搜索。合成的算符，需要超前搜索。 轉(zhuǎn)換圖轉(zhuǎn)換圖：是一張有限方向圖。在狀態(tài)轉(zhuǎn)換圖中，：是一張有限方向圖。在狀態(tài)轉(zhuǎn)換圖中，結(jié)點(diǎn)結(jié)點(diǎn)代表代表 狀態(tài)狀態(tài)，用圓圈表示。狀態(tài)之間用，用圓圈表示。狀態(tài)之間用箭弧箭弧連接。箭弧上連接。箭弧上的的標(biāo)記（字符）標(biāo)記（字符）代表在射出結(jié)狀態(tài)下可能出現(xiàn)的輸代表在射出結(jié)狀態(tài)下可能出現(xiàn)的輸入字符或字符類。入字符或字符類。狀態(tài)轉(zhuǎn)換圖的功能狀態(tài)轉(zhuǎn)換圖的功能: :用于識(shí)別一定的字符串。用于識(shí)別一定的字符串。初態(tài)初態(tài)：一張轉(zhuǎn)換圖的啟動(dòng)條件，至少有一個(gè)：一張轉(zhuǎn)換圖的啟動(dòng)條件，至少有一個(gè), ,用圓圈表示。用圓圈表示。終態(tài)終態(tài)：一張轉(zhuǎn)換圖的結(jié)束條件，至少有一個(gè)

16、，用雙圈表示。：一張轉(zhuǎn)換圖的結(jié)束條件，至少有一個(gè)，用雙圈表示。* * ：表示多讀進(jìn)了一個(gè)字符。：表示多讀進(jìn)了一個(gè)字符。XY(a)(a)轉(zhuǎn)換圖示例轉(zhuǎn)換圖示例字母字母其他其他字母或數(shù)字字母或數(shù)字*（b b）識(shí)別標(biāo)識(shí)符的轉(zhuǎn)換圖）識(shí)別標(biāo)識(shí)符的轉(zhuǎn)換圖其他其他數(shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字*（c c）識(shí)別整數(shù)的轉(zhuǎn)換圖）識(shí)別整數(shù)的轉(zhuǎn)換圖例例2-32-3：簡(jiǎn)單的狀態(tài)轉(zhuǎn)換圖示例：簡(jiǎn)單的狀態(tài)轉(zhuǎn)換圖示例：初態(tài)初態(tài)終態(tài)終態(tài)從從0 0狀態(tài)到狀態(tài)到1 1狀態(tài)狀態(tài)可能出現(xiàn)字母可能出現(xiàn)字母圖圖2.2 2.2 狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖*數(shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字E E 或或 D D+ +或或數(shù)字?jǐn)?shù)字其他其他E E 或或 D D數(shù)字?jǐn)?shù)字其他

17、其他數(shù)字?jǐn)?shù)字例例2-42-4：識(shí)別：識(shí)別FORTRANFORTRAN實(shí)型常數(shù)實(shí)型常數(shù)的轉(zhuǎn)換圖：的轉(zhuǎn)換圖：例如下列實(shí)型常數(shù)可以例如下列實(shí)型常數(shù)可以被以下轉(zhuǎn)換圖識(shí)別：被以下轉(zhuǎn)換圖識(shí)別： 1.23E+41.23E+4 .56E-7 .56E-7例例2-52-5：綜合實(shí)例：綜合實(shí)例做出識(shí)別下表所示的小語言的做出識(shí)別下表所示的小語言的單詞符號(hào)單詞符號(hào)的狀態(tài)轉(zhuǎn)換圖的狀態(tài)轉(zhuǎn)換圖*字母字母非字母與數(shù)字非字母與數(shù)字字母或數(shù)字字母或數(shù)字*空白空白數(shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字非數(shù)字非數(shù)字*非*，（）其他其他。右圖即為對(duì)上頁所示右圖即為對(duì)上頁所示的簡(jiǎn)單語言進(jìn)行的簡(jiǎn)單語言進(jìn)行詞法詞法分析分析的狀態(tài)轉(zhuǎn)換圖。的狀態(tài)轉(zhuǎn)換圖。1、CHAR

18、CHAR 字符變量，存放最新讀進(jìn)的源程序字符。字符變量，存放最新讀進(jìn)的源程序字符。2 2、TOKENTOKEN 字符數(shù)組，存放構(gòu)成單詞的字符串。字符數(shù)組，存放構(gòu)成單詞的字符串。3 3、GETCHARGETCHAR 過程，將下一輸入字符讀入過程，將下一輸入字符讀入CHARCHAR，搜索指示器前移一個(gè)字符。，搜索指示器前移一個(gè)字符。4 4、GETBCGETBC 過程，檢查過程，檢查CHARCHAR中的字符是否為空白。若是，則調(diào)用中的字符是否為空白。若是，則調(diào)用GETCHARGETCHAR 直至直至CHARCHAR中進(jìn)入一個(gè)非空白字符。中進(jìn)入一個(gè)非空白字符。5 5、CONCAT CONCAT 過程，

19、把過程，把CHARCHAR中的字符連接到中的字符連接到TOKENTOKEN之后。之后。6 6、LETTERLETTER 布爾函數(shù)過程，它們分別判斷布爾函數(shù)過程，它們分別判斷CHARCHAR中的字符是數(shù)字或是字母，中的字符是數(shù)字或是字母， DIGITDIGIT 從而給出真假值從而給出真假值TRUETRUE、FALSEFALSE。7 7、RESERVERESERVE 整型函數(shù)過程，用整型函數(shù)過程，用TOKENTOKEN中的字符串查保留字表，若是一個(gè)保留中的字符串查保留字表，若是一個(gè)保留 字則給予編碼，否則回送字則給予編碼，否則回送0 0值（假定值（假定0 0不是保留字的編碼）。不是保留字的編碼）。

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

21、句。具體見后面實(shí)例。 終態(tài)結(jié)終態(tài)結(jié)一般對(duì)應(yīng)一個(gè)一般對(duì)應(yīng)一個(gè)RETURN(C,VAL)RETURN(C,VAL)語句。其中語句。其中C C為單詞為單詞種別編碼；種別編碼；VALVAL是字符數(shù)組的是字符數(shù)組的TOKEN TOKEN ，或者是一個(gè)整數(shù)值，或者是一個(gè)整數(shù)值，或者無定義。具體見后面實(shí)例?；蛘邿o定義。具體見后面實(shí)例。 為了把為了把狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖轉(zhuǎn)化成轉(zhuǎn)化成程序程序，每個(gè)，每個(gè)狀態(tài)狀態(tài)要建立一段要建立一段程序程序，它要做的工作如下：，它要做的工作如下：第一步第一步：從輸入緩沖區(qū)中取一個(gè)字符。為此，我們使用函：從輸入緩沖區(qū)中取一個(gè)字符。為此，我們使用函數(shù)數(shù)GETCHARGETCHAR，每

22、次調(diào)用它，推進(jìn)先行指針，送回一，每次調(diào)用它，推進(jìn)先行指針，送回一個(gè)字符。個(gè)字符。第二步第二步：確定在本狀態(tài)下，哪一條箭弧是用剛剛來的輸入：確定在本狀態(tài)下，哪一條箭弧是用剛剛來的輸入字符標(biāo)識(shí)的。如果找到，控制就轉(zhuǎn)到該弧所指向字符標(biāo)識(shí)的。如果找到，控制就轉(zhuǎn)到該弧所指向的狀態(tài)；若找不到，那么尋找該單詞的企圖就失的狀態(tài)；若找不到，那么尋找該單詞的企圖就失敗了。敗了。失失 敗?。合刃兄羔槺仨殻合刃兄羔槺仨氈匦禄氐街匦禄氐介_始指針處，并用另一狀開始指針處，并用另一狀態(tài)圖來搜索態(tài)圖來搜索另一另一單詞。如果所有的狀態(tài)轉(zhuǎn)換圖都單詞。如果所有的狀態(tài)轉(zhuǎn)換圖都試過之后，還沒有匹配的，就表明這是一個(gè)詞法試過之后，還沒有

23、匹配的，就表明這是一個(gè)詞法錯(cuò)誤，此時(shí)，調(diào)用錯(cuò)誤校正程序。錯(cuò)誤，此時(shí)，調(diào)用錯(cuò)誤校正程序。GETCHAR是過程，是過程，將下一輸入字符讀入將下一輸入字符讀入CHAR，搜索指示器，搜索指示器前移一個(gè)字符。前移一個(gè)字符。例例2 26 6：以下：以下CASECASE語句段對(duì)應(yīng)的狀態(tài)圖語句段對(duì)應(yīng)的狀態(tài)圖: :state istate i： GETCHARGETCHAR； CASE CASE CHARCHAR OF OF A.Z A.Z： state j state j ； 0.90.9： state k state k ； / / ： state l state l ； ENDEND； FAILFAIL數(shù)

24、字?jǐn)?shù)字字母字母 / /字符變量，存放最新字符變量，存放最新讀進(jìn)的源程序字符。讀進(jìn)的源程序字符。過程，將下一輸入字過程，將下一輸入字符讀入符讀入CHARCHAR，搜索指，搜索指示器前移一個(gè)字符。示器前移一個(gè)字符。對(duì)于如上的狀態(tài)轉(zhuǎn)換圖，對(duì)于如上的狀態(tài)轉(zhuǎn)換圖，狀態(tài)狀態(tài)0 0的代碼如下所示：的代碼如下所示： state 0state 0： C := C := GETCHAR GETCHAR ; ; if if LETTER(C)LETTER(C) then goto state 1 then goto state 1 else else FAIL( )FAIL( )字母字母其他其他字母或數(shù)字字母或數(shù)字

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

26、TER( C)LETTER( C) or or DIGIT(C)DIGIT(C) then goto state then goto state 1 1 else if else if DELIMITER(C)DELIMITER(C) then goto state 2 else else FAIL( )FAIL( )字母字母其他其他字母或數(shù)字字母或數(shù)字DIGIT( )是布爾函是布爾函數(shù)過程，當(dāng)且僅當(dāng)數(shù)過程，當(dāng)且僅當(dāng)C中的字符是數(shù)字，中的字符是數(shù)字，它返回真假值它返回真假值TRUE。DELIMITER(C)是過程，是過程，只要碰到標(biāo)識(shí)符后的分只要碰到標(biāo)識(shí)符后的分界符，它返回界符，它返回TRUE

27、。分界符分界符一般為：空格、一般為：空格、算術(shù)、邏輯符號(hào)，括號(hào)、算術(shù)、邏輯符號(hào)，括號(hào)、；、. 、，。*對(duì)于如上的狀態(tài)轉(zhuǎn)換圖，終態(tài)對(duì)于如上的狀態(tài)轉(zhuǎn)換圖，終態(tài)狀態(tài)狀態(tài)2 2的代碼如下所示：的代碼如下所示： state 2state 2： RETRACT( )RETRACT( ) ; ; RETURN($id RETURN($id ，INSTALL( ) )INSTALL( ) )字母字母其他其他字母或數(shù)字字母或數(shù)字RETRACT( )是過程，是過程，由于分界符不屬于由于分界符不屬于標(biāo)識(shí)符，所以我們標(biāo)識(shí)符，所以我們要把先行指針要把先行指針回調(diào)回調(diào)一個(gè)字符。一個(gè)字符。INSTALL( )是過程，是過程

28、，如我們識(shí)別出的標(biāo)如我們識(shí)別出的標(biāo)識(shí)符不在符號(hào)表中，識(shí)符不在符號(hào)表中，我們把它裝入我們把它裝入符號(hào)符號(hào)表表。我們還要給語。我們還要給語法分析程序返回一法分析程序返回一個(gè)個(gè)二元式二元式。*如果同時(shí)識(shí)別如果同時(shí)識(shí)別標(biāo)識(shí)符標(biāo)識(shí)符和和定義符定義符，則需要?jiǎng)t需要修改修改為為State2：修改之后，修改之后，狀態(tài)狀態(tài)2 2的代碼如下所示：的代碼如下所示： state 2state 2： RETRACT( )RETRACT( ) ; ; c := c := RESERVE( );RESERVE( ); if c = 0 if c = 0 then then RETURN($id ，INSTALL ) els

29、e else RETURN(C , _ )RETURN(C , _ )RESERVE( ) 整型函數(shù)整型函數(shù)過程過程,針對(duì)針對(duì)TOKEN中的中的字符串進(jìn)行查找，看其字符串進(jìn)行查找，看其是否是是否是保留字保留字，是保留，是保留字給出它的編碼，否則字給出它的編碼，否則回送回送0（假定（假定0不是保留不是保留字編碼）。字編碼）。例例2 28 8：以下程序段對(duì)應(yīng)的狀態(tài)圖：以下程序段對(duì)應(yīng)的狀態(tài)圖 state istate i：GETCHARGETCHAR； WHILE WHILE LETTERLETTER OR OR DIGITDIGIT DO DO GETCHARGETCHAR； state jsta

30、te j： 布爾函數(shù)過程，它們分別布爾函數(shù)過程，它們分別判斷判斷CHARCHAR中的字符是數(shù)字中的字符是數(shù)字或是字母，從而給出真假或是字母，從而給出真假值值TRUETRUE、FALSEFALSE。其它其它字母或數(shù)字字母或數(shù)字例例2 29 9：以下程序段對(duì)應(yīng)的狀態(tài)圖：以下程序段對(duì)應(yīng)的狀態(tài)圖0 90 9：BEGINBEGIN WHILE WHILE DIGITDIGIT DO DO BEGIN BEGIN CONCATCONCAT；GETCHARGETCHAR END END； RETRACTRETRACT； RETURN($INT,DTB)RETURN($INT,DTB) ； ENDEND；非數(shù)

31、字非數(shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字*RETURN RETURN 語句，對(duì)應(yīng)終態(tài)語句，對(duì)應(yīng)終態(tài)結(jié)，其中結(jié)，其中$INT為種別編為種別編碼，碼，DTB為一個(gè)把十進(jìn)制為一個(gè)把十進(jìn)制轉(zhuǎn)換到二進(jìn)制的轉(zhuǎn)換函數(shù)。轉(zhuǎn)換到二進(jìn)制的轉(zhuǎn)換函數(shù)。它把它把TOKENTOKEN中的數(shù)字譯成中的數(shù)字譯成標(biāo)準(zhǔn)二進(jìn)制碼標(biāo)準(zhǔn)二進(jìn)制碼，并以此為，并以此為函數(shù)值返回。函數(shù)值返回。正規(guī)式與正規(guī)集的遞歸定義：正規(guī)式與正規(guī)集的遞歸定義：1 1、和和都是都是字母表字母表上的正規(guī)式，它們所表示的正規(guī)集分別為上的正規(guī)式，它們所表示的正規(guī)集分別為 和和；2 2、任何、任何aa，a a是是上的一個(gè)上的一個(gè)正規(guī)式正規(guī)式，它所表示的，它所表示的正規(guī)集正規(guī)集為為a

32、a；3 3、 正規(guī)式正規(guī)式 正規(guī)集正規(guī)集 正規(guī)式正規(guī)式 正規(guī)集正規(guī)集 U L(U) U L(U) （U U | | V V） L(U)L(U)L(V)L(V) V L(V) V L(V) （U UV V） L(U)L(V)L(U)L(V) (U) (U)* * L(U)L(U)* *（閉包）（閉包） 僅由有限次使用上述三步驟而得到的表達(dá)式才是僅由有限次使用上述三步驟而得到的表達(dá)式才是上的上的正規(guī)式正規(guī)式。僅由這。僅由這 些正規(guī)式所表示的子集才是些正規(guī)式所表示的子集才是上的上的正規(guī)集正規(guī)集。運(yùn)算符的優(yōu)先順序：運(yùn)算符的優(yōu)先順序：先先“* *”，次，次“” ，最后最后“|”|”“| |”讀讀做做“或

33、或”“”讀做讀做“連接連接”“* *”讀做讀做“閉包閉包”* 的子集的子集 U , V： 積積 UV =| U U & V V n次積次積 V n= VVV V V0 = V的閉包的閉包 V* = V0 U V1 U V2 U V的正則閉包的正則閉包 V+ = V V* 例例2-112-11：令：令aa，bb，下面是，下面是上的上的正規(guī)式正規(guī)式和相應(yīng)的和相應(yīng)的正規(guī)集正規(guī)集： 正規(guī)式正規(guī)式 正規(guī)集正規(guī)集 baba* * 上所有的以上所有的以b b為首，并且后跟任為首，并且后跟任 意多個(gè)意多個(gè)a a的字，的字，b, ba,baa,baaa,b, ba,baa,baaa, a(a|b)a(a

34、|b)* * 上所有的以上所有的以a a為首的字為首的字 (a|b)(a|b)* * (aa|bb) (a|b) (aa|bb) (a|b)* * 上所有含有兩個(gè)連續(xù)的上所有含有兩個(gè)連續(xù)的a a或者或者b b的字的字例例2-102-10：令：令A(yù)A，B B，0 0，11，則：，則： 正規(guī)式正規(guī)式 正規(guī)集正規(guī)集 (A|B)(A|B|0|1)(A|B)(A|B|0|1)* * 上上“標(biāo)識(shí)符標(biāo)識(shí)符”的全的全體體 (0|1)(0|1)(0|1)(0|1)* * 上上“數(shù)數(shù)”的全體的全體若兩個(gè)正規(guī)式表若兩個(gè)正規(guī)式表示相同的正規(guī)集，示相同的正規(guī)集，則認(rèn)為二者則認(rèn)為二者等價(jià)等價(jià)，記為記為U=VU=V。例如：

35、。例如：b(ab)b(ab)* *=(ba)=(ba)* *b b(a|b)(a|b)* *=(a=(a* *b b* *) )* *令令U U、V V和和W W均為均為正規(guī)式正規(guī)式，顯而易見，下列，顯而易見，下列關(guān)系關(guān)系普遍成立：普遍成立： 1 1、U|V = V|UU|V = V|U（交換律）；（交換律）； 2 2、U|(V|W) = (U|V)|WU|(V|W) = (U|V)|W（結(jié)合律）；（結(jié)合律）； 3 3、U(VW) = (UV)WU(VW) = (UV)W（結(jié)合律）；（結(jié)合律）； 4 4、U(V|W) = UV|UWU(V|W) = UV|UW（分配律）（分配律） (V|W)U

36、 = VU|WU(V|W)U = VU|WU； 5 5、U = UU = U = U = U。 一個(gè)一個(gè)確定有限自動(dòng)機(jī)（確定有限自動(dòng)機(jī)（DFADFA） M M是一個(gè)五元式：是一個(gè)五元式： M M (S,(S,s,s0 0 ,F) ,F) ，其中，其中 1 1、S S是一個(gè)有限集，它的每個(gè)元素稱為一個(gè)是一個(gè)有限集，它的每個(gè)元素稱為一個(gè)狀態(tài)狀態(tài) 2 2、是一個(gè)有窮是一個(gè)有窮字母表字母表，它的每個(gè)元素稱為一個(gè)，它的每個(gè)元素稱為一個(gè)輸入字符輸入字符 3 3、是一個(gè)從是一個(gè)從S S至至S S的單值部分映射。的單值部分映射。 (s,a)=s(s,a)=s 意味著：當(dāng)現(xiàn)行意味著：當(dāng)現(xiàn)行狀態(tài)為狀態(tài)為S S、輸

37、入字符為、輸入字符為a a時(shí)，將轉(zhuǎn)換到下一狀態(tài)時(shí)，將轉(zhuǎn)換到下一狀態(tài)s s 。我們稱。我們稱s s 為為s s的的一個(gè)后繼狀態(tài)。一個(gè)后繼狀態(tài)。 4 4、 s s0 0SS是唯一的是唯一的初態(tài)初態(tài) 5 5、 F SF S是一個(gè)是一個(gè)終態(tài)集終態(tài)集（可空）。（可空）。 顯然，一個(gè)顯然，一個(gè)DFADFA可用一個(gè)矩陣表示，該矩陣的行表示狀態(tài)，可用一個(gè)矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示列表示輸入字符，矩陣元素表示(s,a)的值。這個(gè)矩陣稱為的值。這個(gè)矩陣稱為狀態(tài)轉(zhuǎn)換矩陣狀態(tài)轉(zhuǎn)換矩陣。例例2-122-12：有：有DFADFA M = (0,1,2,3,a,b,M = (0,1,2,3,

38、a,b,0,3),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 相應(yīng)的狀態(tài)轉(zhuǎn)換矩陣如下表：相應(yīng)的狀態(tài)轉(zhuǎn)換矩陣如下表： 一個(gè)一個(gè)DFADFA也可用一張（確定的）也可用一張（確定的）狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖來表示。假定來表示。假定DFA MDFA M含有含有m m個(gè)狀態(tài)和個(gè)狀態(tài)和n n個(gè)個(gè)輸入字符輸入字符，那么，這個(gè)狀態(tài)轉(zhuǎn)換圖含有，那么，這個(gè)狀態(tài)轉(zhuǎn)換圖含有m m個(gè)個(gè)狀態(tài)結(jié)點(diǎn)狀態(tài)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)頂多有，每個(gè)結(jié)點(diǎn)頂多有n n條箭弧射出和別的結(jié)點(diǎn)相連接，條箭弧射出和別的結(jié)點(diǎn)相連接，整張圖含有一個(gè)整張圖

39、含有一個(gè)初態(tài)結(jié)點(diǎn)初態(tài)結(jié)點(diǎn)和若干個(gè)（可以為和若干個(gè)（可以為0 0）終態(tài)結(jié)點(diǎn)終態(tài)結(jié)點(diǎn)。圖圖2.5 2.5 狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖a aa aa aa ab bb bb b如下表所示的狀態(tài)轉(zhuǎn)換矩陣如下表所示的狀態(tài)轉(zhuǎn)換矩陣對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖如右圖：對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖如右圖：a aa aa ab bb bb b上圖所示的狀態(tài)轉(zhuǎn)換圖的上圖所示的狀態(tài)轉(zhuǎn)換圖的S S、及及* *如下：如下： S = 0,1,2,3S = 0,1,2,3 = a,b = a,b * *= | = | 為為，或者，或者為為a、b的任意組合的任意組合 從初態(tài)從初態(tài)0 0到終態(tài)到終態(tài)3 3有如有如圖所示的通路，箭弧圖所示的通路，箭弧上到標(biāo)記

40、符連接起來上到標(biāo)記符連接起來的字的字aaaa屬于屬于* *，所，所以右圖所示的以右圖所示的DFADFA可可以識(shí)別字以識(shí)別字aaaa。同理：從初態(tài)同理：從初態(tài)0 0到終到終態(tài)態(tài)3 3還有如圖所示的還有如圖所示的通路，箭弧上到標(biāo)記通路，箭弧上到標(biāo)記符連接起來的字符連接起來的字bbabba屬于屬于* *，所以右圖，所以右圖所示的所示的DFADFA可以識(shí)別可以識(shí)別字字bbabba。a a例例2-132-13：科學(xué)表示法中數(shù)字常量的：科學(xué)表示法中數(shù)字常量的正則表達(dá)式正則表達(dá)式對(duì)應(yīng)的對(duì)應(yīng)的DFADFA： digitdigitdigitdigitnatnat對(duì)應(yīng)的對(duì)應(yīng)的DFADFA如下圖如下圖 digit

41、= 0-9 digit = 0-9 nat = digit nat = digit + + signedNat = ( +|- )? nat signedNat = ( +|- )? natnumber = signedNat(“”nat)number = signedNat(“”nat)？signedNatsignedNat對(duì)應(yīng)的對(duì)應(yīng)的DFADFA如下圖如下圖加上可選的小數(shù)部分，加上可選的小數(shù)部分，數(shù)字常量的數(shù)字常量的正則表達(dá)式正則表達(dá)式number = signedNat(“”nat)？對(duì)應(yīng)的對(duì)應(yīng)的DFADFA如下圖：如下圖：+ +digitdigitdigitdigitdigitdigi

42、t-+ +digitdigitdigitdigitdigitdigit-digitdigitdigitdigita ab bb bb b接受與接受與正則式正則式ab+|abab+|ab* *|b|b* * 相同的語言的相同的語言的DFADFA如下所示：如下所示：例例2-142-14：串中：串中只有一個(gè)只有一個(gè)b b被如下所示的被如下所示的DFADFA接受接受：b bnot bnot bnot bnot b例例2-152-15：包含：包含最多一個(gè)最多一個(gè)b b的串被如下所示的的串被如下所示的DFADFA接受：接受：b bnot bnot bnot bnot b注意二者之注意二者之間的區(qū)別間的區(qū)別

43、 定理定理：如果一個(gè)：如果一個(gè)DFA M DFA M 的的輸入字母表輸入字母表為為，則我們也稱，則我們也稱M M是是上的一個(gè)上的一個(gè) DFADFA?？梢宰C明?？梢宰C明: :上的一個(gè)字集上的一個(gè)字集V V * *是正規(guī)是正規(guī)的，當(dāng)且僅當(dāng)存在的，當(dāng)且僅當(dāng)存在上的上的DFA MDFA M，使得，使得V =L(M)V =L(M)。 DFA DFA的的確定性確定性表現(xiàn)在映射表現(xiàn)在映射： S SSS是一個(gè)是一個(gè)單值函數(shù)單值函數(shù)。即：對(duì)于任何狀態(tài)即：對(duì)于任何狀態(tài)sSsS和輸入符號(hào)和輸入符號(hào)a a， (s,a)(s,a)唯一確定了唯一確定了一個(gè)狀態(tài)。一個(gè)狀態(tài)。 從轉(zhuǎn)換圖角度，我們也可以得到答案。從轉(zhuǎn)換圖角度，

44、我們也可以得到答案。 如果允許是一個(gè)如果允許是一個(gè)多值函數(shù)多值函數(shù)，我們就得到下一節(jié)要講到的，我們就得到下一節(jié)要講到的非確定自動(dòng)機(jī)非確定自動(dòng)機(jī)的概念。的概念。一個(gè)一個(gè)非確定有限自動(dòng)機(jī)（非確定有限自動(dòng)機(jī)（NFANFA） M M是一個(gè)五元式：是一個(gè)五元式： M M (S,(S,S,S0 0 ,F),F) ，其中，其中 1 1、S S是一個(gè)有限集，它的每個(gè)元素稱為一個(gè)是一個(gè)有限集，它的每個(gè)元素稱為一個(gè)狀態(tài)狀態(tài) 2 2、是一個(gè)是一個(gè)有窮有窮字母表字母表，它的每個(gè)元素稱為一個(gè)，它的每個(gè)元素稱為一個(gè)輸入字符輸入字符 3 3、是一個(gè)從是一個(gè)從S S* *至至S S的子集的映射，即的子集的映射，即： S S*

45、 * 2 2s s 4 4、 S S0 0SS是唯一的是唯一的初態(tài)初態(tài) 5 5、 F F S S是一個(gè)是一個(gè)終態(tài)集終態(tài)集（可空）。（可空）。 一個(gè)含有一個(gè)含有m m個(gè)狀態(tài)和個(gè)狀態(tài)和n n個(gè)輸入字符的個(gè)輸入字符的NFANFA可用一張如下的狀態(tài)可用一張如下的狀態(tài)轉(zhuǎn)換圖來表示：該圖含有轉(zhuǎn)換圖來表示：該圖含有m m個(gè)狀態(tài)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)可以射出若干個(gè)狀態(tài)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)可以射出若干條弧與別的結(jié)點(diǎn)相連接，條弧與別的結(jié)點(diǎn)相連接，每條弧用每條弧用* *中的一個(gè)字（可以是不同中的一個(gè)字（可以是不同的字，也可以是空字）做標(biāo)記的字，也可以是空字）做標(biāo)記，整張圖至少含有一個(gè)初態(tài)結(jié)點(diǎn)，整張圖至少含有一個(gè)初態(tài)結(jié)點(diǎn)和若干個(gè)（

46、可以為和若干個(gè)（可以為0 0）終態(tài)結(jié)點(diǎn)。某些結(jié)點(diǎn)既可以是初態(tài)結(jié)點(diǎn)也）終態(tài)結(jié)點(diǎn)。某些結(jié)點(diǎn)既可以是初態(tài)結(jié)點(diǎn)也可以是終態(tài)結(jié)點(diǎn)?？梢允墙K態(tài)結(jié)點(diǎn)。aaaaa,ba,bbbbbababa,ba,bab,baab,baaa,bbaa,bbab,baab,baaa,bbaa,bba aa aa aa ab bb bb bb b下圖所示的狀態(tài)轉(zhuǎn)換圖的下圖所示的狀態(tài)轉(zhuǎn)換圖的S S、及及* *如下：如下： S = 0,1,2,3S = 0,1,2,3 = a,b = a,b * *= | = | 為為，或者，或者為為a、b的任意組合的任意組合 對(duì)于對(duì)于* *中的任何一個(gè)字中的任何一個(gè)字，若，若存在一條從某一初態(tài)結(jié)點(diǎn)

47、到某一存在一條從某一初態(tài)結(jié)點(diǎn)到某一終態(tài)結(jié)點(diǎn)的通路，且這條通路上終態(tài)結(jié)點(diǎn)的通路，且這條通路上所有弧上的標(biāo)記字依序連接成的所有弧上的標(biāo)記字依序連接成的字（忽略字（忽略）等于）等于，則稱，則稱可可以為以為NFA MNFA M 識(shí)別識(shí)別。從初態(tài)從初態(tài)x x到終態(tài)到終態(tài)y y的連接通路弧上，有如下標(biāo)記字：的連接通路弧上，有如下標(biāo)記字： a a ，去除，去除，為，為aa，所以字，所以字aa可為可為NFA接受。接受。a aa ab b424243142421bbabba例例2-162-16：上圖所示的：上圖所示的NFANFA的以下兩個(gè)轉(zhuǎn)換序列都可以接受串的以下兩個(gè)轉(zhuǎn)換序列都可以接受串a(chǎn)bbabb：允許接允許

48、接受受abab允許接受與允許接受與abab* *匹配的匹配的字符串字符串允許接受與允許接受與b b* *匹配的字匹配的字符串符串允許接受與允許接受與abab+ +匹配的字匹配的字符串符串由此，我們可以看由此，我們可以看出這個(gè)出這個(gè)NFANFA接受與正接受與正則式則式abab+ +|ab|ab* *|b|b* * 相相同的語言！同的語言！接受接受abab接受接受abab接受接受abab接受接受abab接受接受abab接受接受abab* *接受接受abab接受接受abab接受接受abab* *接受接受b b* *練習(xí)：考慮以下練習(xí)：考慮以下NFANFA通過怎樣的轉(zhuǎn)換通過怎樣的轉(zhuǎn)換接受串接受串a(chǎn)ca

49、bacab：a ab bc c10987432765274321 bac DFA DFA是是NFANFA的特例的特例，可以采用，可以采用子集法子集法將將NFANFA確定化。確定化。假定假定I I是是NFA MNFA M的狀態(tài)集的狀態(tài)集(S)(S)的一個(gè)的一個(gè)子集子集， 我們定義我們定義_CLOSURE(I)_CLOSURE(I)為：為： 1 1、若、若ssI I，則則s s _CLOSURE(I)(I)；2 2、若、若sIsI，那么從，那么從s s出發(fā)經(jīng)過出發(fā)經(jīng)過任意任意條條弧弧而能而能到達(dá)的到達(dá)的任何狀態(tài)任何狀態(tài)ss都屬于都屬于_CLOSURE(I)_CLOSURE(I)。狀態(tài)集狀態(tài)集_CL

50、OSURE(I)_CLOSURE(I)稱為稱為I I的的_ _閉包閉包。 假定假定 I I 是是NFA MNFA M的狀態(tài)集的的狀態(tài)集的子集子集，a(aa(a是輸是輸入字符入字符),),定義定義 Ia Ia=_CLOSURE(J)_CLOSURE(J)其中，其中，J J是那些可從是那些可從I I中的某一狀態(tài)結(jié)點(diǎn)出發(fā)中的某一狀態(tài)結(jié)點(diǎn)出發(fā)經(jīng)過一條經(jīng)過一條a a弧弧而而到達(dá)的狀態(tài)結(jié)點(diǎn)的全體。到達(dá)的狀態(tài)結(jié)點(diǎn)的全體。 = a1,a2,.ak = a1,a2,.ak 。先先構(gòu)造一張表構(gòu)造一張表，該表每，該表每一行含有一行含有k+1k+1列。置該列。置該表的表的首行首列為首行首列為_CLOSURE(X)。

51、重復(fù)上述過程，重復(fù)上述過程，直至所有直至所有第二列第二列和和第三列第三列的的子集子集均已均已在在第一列第一列上出現(xiàn)了上出現(xiàn)了為止。為止。 如果某一行的第一列的如果某一行的第一列的狀態(tài)子集已經(jīng)確定，例如記狀態(tài)子集已經(jīng)確定，例如記為為I I, ,那么，求出這一行的第那么，求出這一行的第二個(gè)和第三個(gè)子集二個(gè)和第三個(gè)子集I Ia a和和I Ib b看看它們是否已它們是否已 在表的第一列在表的第一列出現(xiàn)，將未出現(xiàn)的出現(xiàn)，將未出現(xiàn)的填入填入到后到后面空行的第一列。面空行的第一列。 1 1 表的表的初始化初始化構(gòu)造構(gòu)造2 2 處理表的處理表的一行一行3 3 重復(fù)處理重復(fù)處理例例2-172-17：考慮下圖所示

52、：考慮下圖所示NFANFA的的確定化確定化：a aa aa aa ab bb bb bb bI=I=_CLOSUREX_CLOSUREX為為X,5,1X,5,1。從狀從狀態(tài)態(tài)I I出發(fā)經(jīng)過一條出發(fā)經(jīng)過一條a a弧而能到達(dá)的狀態(tài)弧而能到達(dá)的狀態(tài)全體全體J J為為5,3,5,3,而而_CLOSURE(J)=5, _CLOSURE(J)=5, 3,13,1。從而。從而Ia=5, Ia=5, 3,13,1。初態(tài)初態(tài)_ _閉包閉包X,5,1X,5,1JaJa為為5,35,3_CLOSURE(J)為為5,35,3，11（根據(jù)（根據(jù)_閉包閉包的定義）的定義）根據(jù)此方法依次求根據(jù)此方法依次求出左邊表中的狀態(tài)出

53、左邊表中的狀態(tài)轉(zhuǎn)換矩陣即可。轉(zhuǎn)換矩陣即可。對(duì)右下圖表中的所有對(duì)右下圖表中的所有子集子集重新命名，得到左圖中的狀態(tài)轉(zhuǎn)換矩重新命名，得到左圖中的狀態(tài)轉(zhuǎn)換矩陣形成如下狀態(tài)轉(zhuǎn)換矩陣，從而得到相應(yīng)的陣形成如下狀態(tài)轉(zhuǎn)換矩陣，從而得到相應(yīng)的DFADFA。如圖所示：。如圖所示：a aa aa aa ab bb bb ba ab bb ba ab b重命名為重命名為狀態(tài)狀態(tài)0 0重命名為重命名為狀態(tài)狀態(tài)1 1根據(jù)重命根據(jù)重命名的狀態(tài)名的狀態(tài)填寫表格填寫表格ab例例2-182-18：考慮下圖所示：考慮下圖所示NFANFA的確定化：的確定化：11在在letterletter上有到上有到22的轉(zhuǎn)換的轉(zhuǎn)換：2=2，3，4，5，7，10letterletter在在letterletter上有到上有到66的轉(zhuǎn)換的轉(zhuǎn)換：6=4，5，6，7，9，10letterletter在在 digitdigit上有到上有到88的轉(zhuǎn)換的轉(zhuǎn)換：8=4，5，7，8，9，10digitdigitletterletterdigitdigitdigitdigitle