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

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

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

4、限單詞符號的表示形式單詞符號的表示形式：詞法分析器所輸出的單詞符號常常表示成：詞法分析器所輸出的單詞符號常常表示成 二元式（單詞種別，單詞自身的值）二元式（單詞種別，單詞自身的值）。 單詞種別單詞種別可以用以下形式表示：可以用以下形式表示： 1 1、一類單詞統一用一個整數值代表其屬性。例如：、一類單詞統一用一個整數值代表其屬性。例如：1 1代表關鍵字，代表關鍵字，2 2代表標識符等。代表標識符等。 2 2、每一個單詞一個類別。例如：、每一個單詞一個類別。例如：1 1代表代表BEGINBEGIN，2 2代表代表ENDEND等。等。單詞自身的值單詞自身的值可以表示成：常量的二進制表示；常量、變量等

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

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

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

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

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

10、分析和語法分析詞法分析和語法分析方法方法不同，詞法分析可以使用正則文法自動構造不同，詞法分析可以使用正則文法自動構造scannerscanner簡單。簡單。有利于提高語法分析的有利于提高語法分析的效率效率。可以改善詞法分析的細節，甚至于一個語法分析配幾個可以改善詞法分析的細節，甚至于一個語法分析配幾個scannerscanner，把不同，把不同的輸入變成一種內部表示。的輸入變成一種內部表示。2 2、把詞法分析作為獨立的一、把詞法分析作為獨立的一遍遍scannerscanner當作一遍。當作一遍。把把scannerscanner當作子程序。當作子程序。 外存外存scannerscanner語法分

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

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

13、補補 輸輸 入入 緩緩 沖沖 區區120個字符個字符掃描緩沖區的掃描緩沖區的結構結構： 緩沖區大小緩沖區大小：120120個字符。個字符。 采用兩個采用兩個指示器指示器：起點指示器、搜索指示器。：起點指示器、搜索指示器。 兩個互補區兩個互補區。單詞符號識別的簡單方法：單詞符號識別的簡單方法：超前搜索。關鍵字識別關鍵字識別： 例如：在標準例如：在標準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為關鍵字為關鍵字其中的其中的DODO、IFIF為標識符為標識符的一部分的一部分標識符的識別標識符的識別 多數語言的標識符是字母開頭的多數語言的標識符是字母開頭的“字母字母/ /數字數字”串，串，而且在程序中標識符的出現后都跟著算符或界符。因此，而且在程序中標識符的出現后都跟著算符或界符。因此，不難識別。不難識別。常數的識別常數的識別 對于某些語言的常數的識別也需要使用超前搜索。對于某些語言的常數的識別也需要使用超前搜索。算符和界符的識別算符和界符的識別 對于諸如對于諸如C+C+語言中的語言中的“+ +”+ +”、“- -”- -”，這種復，

15、這種復合成的算符，需要超前搜索。合成的算符，需要超前搜索。 轉換圖轉換圖：是一張有限方向圖。在狀態轉換圖中，：是一張有限方向圖。在狀態轉換圖中，結點結點代表代表 狀態狀態，用圓圈表示。狀態之間用，用圓圈表示。狀態之間用箭弧箭弧連接。箭弧上連接。箭弧上的的標記（字符）標記（字符）代表在射出結狀態下可能出現的輸代表在射出結狀態下可能出現的輸入字符或字符類。入字符或字符類。狀態轉換圖的功能狀態轉換圖的功能: :用于識別一定的字符串。用于識別一定的字符串。初態初態：一張轉換圖的啟動條件，至少有一個：一張轉換圖的啟動條件，至少有一個, ,用圓圈表示。用圓圈表示。終態終態：一張轉換圖的結束條件，至少有一個

16、，用雙圈表示。：一張轉換圖的結束條件，至少有一個，用雙圈表示。* * ：表示多讀進了一個字符。：表示多讀進了一個字符。XY(a)(a)轉換圖示例轉換圖示例字母字母其他其他字母或數字字母或數字*（b b）識別標識符的轉換圖）識別標識符的轉換圖其他其他數字數字數字數字*（c c）識別整數的轉換圖）識別整數的轉換圖例例2-32-3：簡單的狀態轉換圖示例：簡單的狀態轉換圖示例：初態初態終態終態從從0 0狀態到狀態到1 1狀態狀態可能出現字母可能出現字母圖圖2.2 2.2 狀態轉換圖狀態轉換圖*數字數字數字數字數字數字數字數字E E 或或 D D+ +或或數字數字其他其他E E 或或 D D數字數字其他

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

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

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

20、8 8、RETRACTRETRACT 過程，把搜索指示器回調一個字節，把過程，把搜索指示器回調一個字節，把CHARCHAR中的字符置為空白。中的字符置為空白。 以上函數和子程序過程都不難編制，使用它們能夠方便以上函數和子程序過程都不難編制，使用它們能夠方便的構造狀態轉換圖的對應程序。一般，我們可以讓每的構造狀態轉換圖的對應程序。一般，我們可以讓每一個狀一個狀態結態結對應對應一個程序段一個程序段。 例如：我們可以讓不含回路的分叉結，對應一個例如：我們可以讓不含回路的分叉結，對應一個CASE CASE 語句，或者是一組語句，或者是一組IFTHENELSEIFTHENELSE語句。具體見后面實例。語

21、句。具體見后面實例。 終態結終態結一般對應一個一般對應一個RETURN(C,VAL)RETURN(C,VAL)語句。其中語句。其中C C為單詞為單詞種別編碼；種別編碼；VALVAL是字符數組的是字符數組的TOKEN TOKEN ，或者是一個整數值，或者是一個整數值，或者無定義。具體見后面實例。或者無定義。具體見后面實例。 為了把為了把狀態轉換圖狀態轉換圖轉化成轉化成程序程序，每個，每個狀態狀態要建立一段要建立一段程序程序，它要做的工作如下：，它要做的工作如下：第一步第一步：從輸入緩沖區中取一個字符。為此，我們使用函：從輸入緩沖區中取一個字符。為此，我們使用函數數GETCHARGETCHAR，每

22、次調用它，推進先行指針，送回一，每次調用它，推進先行指針，送回一個字符。個字符。第二步第二步：確定在本狀態下，哪一條箭弧是用剛剛來的輸入：確定在本狀態下，哪一條箭弧是用剛剛來的輸入字符標識的。如果找到，控制就轉到該弧所指向字符標識的。如果找到，控制就轉到該弧所指向的狀態；若找不到，那么尋找該單詞的企圖就失的狀態；若找不到，那么尋找該單詞的企圖就失敗了。敗了。失失 敗敗：先行指針必須：先行指針必須重新回到重新回到開始指針處，并用另一狀開始指針處，并用另一狀態圖來搜索態圖來搜索另一另一單詞。如果所有的狀態轉換圖都單詞。如果所有的狀態轉換圖都試過之后，還沒有匹配的，就表明這是一個詞法試過之后，還沒有

23、匹配的，就表明這是一個詞法錯誤，此時，調用錯誤校正程序。錯誤，此時，調用錯誤校正程序。GETCHAR是過程，是過程，將下一輸入字符讀入將下一輸入字符讀入CHAR，搜索指示器，搜索指示器前移一個字符。前移一個字符。例例2 26 6：以下：以下CASECASE語句段對應的狀態圖語句段對應的狀態圖: :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數

24、字數字字母字母 / /字符變量，存放最新字符變量，存放最新讀進的源程序字符。讀進的源程序字符。過程，將下一輸入字過程，將下一輸入字符讀入符讀入CHARCHAR，搜索指，搜索指示器前移一個字符。示器前移一個字符。對于如上的狀態轉換圖，對于如上的狀態轉換圖，狀態狀態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( )字母字母其他其他字母或數字字母或數字

25、LETTER( )是布爾是布爾函數過程，當且僅函數過程，當且僅當當C中的字符是字中的字符是字母，它返回真假值母，它返回真假值TRUE。FAIL( )是例子程序，是例子程序，它移回它移回先行指針先行指針（lookahead pointer）, 開始下一開始下一狀態轉換圖，或調用狀態轉換圖，或調用出錯程序。出錯程序。例例2-72-7：示例：示例如何把如何把狀態結狀態結對應于一段對應于一段程序程序：*對于如上的狀態轉換圖，對于如上的狀態轉換圖，狀態狀態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( )字母字母其他其他字母或數字字母或數字DIGIT( )是布爾函是布爾函數過程，當且僅當數過程，當且僅當C中的字符是數字，中的字符是數字，它返回真假值它返回真假值TRUE。DELIMITER(C)是過程，是過程，只要碰到標識符后的分只要碰到標識符后的分界符，它返回界符，它返回TRUE

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

28、，如我們識別出的標如我們識別出的標識符不在符號表中，識符不在符號表中，我們把它裝入我們把它裝入符號符號表表。我們還要給語。我們還要給語法分析程序返回一法分析程序返回一個個二元式二元式。*如果同時識別如果同時識別標識符標識符和和定義符定義符，則需要則需要修改修改為為State2：修改之后，修改之后，狀態狀態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( ) 整型函數整型函數過程過程,針對針對TOKEN中的中的字符串進行查找，看其字符串進行查找，看其是否是是否是保留字保留字，是保留，是保留字給出它的編碼，否則字給出它的編碼，否則回送回送0（假定（假定0不是保留不是保留字編碼）。字編碼）。例例2 28 8：以下程序段對應的狀態圖：以下程序段對應的狀態圖 state istate i：GETCHARGETCHAR； WHILE WHILE LETTERLETTER OR OR DIGITDIGIT DO DO GETCHARGETCHAR； state jsta

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

31、字非數字數字數字數字數字*RETURN RETURN 語句，對應終態語句，對應終態結，其中結，其中$INT為種別編為種別編碼，碼，DTB為一個把十進制為一個把十進制轉換到二進制的轉換函數。轉換到二進制的轉換函數。它把它把TOKENTOKEN中的數字譯成中的數字譯成標準二進制碼標準二進制碼，并以此為，并以此為函數值返回。函數值返回。正規式與正規集的遞歸定義：正規式與正規集的遞歸定義：1 1、和和都是都是字母表字母表上的正規式，它們所表示的正規集分別為上的正規式，它們所表示的正規集分別為 和和；2 2、任何、任何aa，a a是是上的一個上的一個正規式正規式，它所表示的，它所表示的正規集正規集為為a

32、a；3 3、 正規式正規式 正規集正規集 正規式正規式 正規集正規集 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)* *（閉包）（閉包） 僅由有限次使用上述三步驟而得到的表達式才是僅由有限次使用上述三步驟而得到的表達式才是上的上的正規式正規式。僅由這。僅由這 些正規式所表示的子集才是些正規式所表示的子集才是上的上的正規集正規集。運算符的優先順序：運算符的優先順序：先先“* *”，次，次“” ，最后最后“|”|”“| |”讀讀做做“或

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，下面是，下面是上的上的正規式正規式和相應的和相應的正規集正規集： 正規式正規式 正規集正規集 baba* * 上所有的以上所有的以b b為首，并且后跟任為首，并且后跟任 意多個意多個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)* * 上所有含有兩個連續的上所有含有兩個連續的a a或者或者b b的字的字例例2-102-10：令：令AA，B B，0 0，11，則：，則： 正規式正規式 正規集正規集 (A|B)(A|B|0|1)(A|B)(A|B|0|1)* * 上上“標識符標識符”的全的全體體 (0|1)(0|1)(0|1)(0|1)* * 上上“數數”的全體的全體若兩個正規式表若兩個正規式表示相同的正規集，示相同的正規集，則認為二者則認為二者等價等價，記為記為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均為均為正規式正規式，顯而易見，下列，顯而易見，下列關系關系普遍成立：普遍成立： 1 1、U|V = V|UU|V = V|U（交換律）；（交換律）； 2 2、U|(V|W) = (U|V)|WU|(V|W) = (U|V)|W（結合律）；（結合律）； 3 3、U(VW) = (UV)WU(VW) = (UV)W（結合律）；（結合律）； 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。 一個一個確定有限自動機（確定有限自動機（DFADFA） M M是一個五元式：是一個五元式： M M (S,(S,s,s0 0 ,F) ,F) ，其中，其中 1 1、S S是一個有限集，它的每個元素稱為一個是一個有限集，它的每個元素稱為一個狀態狀態 2 2、是一個有窮是一個有窮字母表字母表，它的每個元素稱為一個，它的每個元素稱為一個輸入字符輸入字符 3 3、是一個從是一個從S S至至S S的單值部分映射。的單值部分映射。 (s,a)=s(s,a)=s 意味著：當現行意味著：當現行狀態為狀態為S S、輸

37、入字符為、輸入字符為a a時，將轉換到下一狀態時，將轉換到下一狀態s s 。我們稱。我們稱s s 為為s s的的一個后繼狀態。一個后繼狀態。 4 4、 s s0 0SS是唯一的是唯一的初態初態 5 5、 F SF S是一個是一個終態集終態集（可空）。（可空）。 顯然，一個顯然，一個DFADFA可用一個矩陣表示，該矩陣的行表示狀態，可用一個矩陣表示，該矩陣的行表示狀態，列表示輸入字符，矩陣元素表示列表示輸入字符，矩陣元素表示(s,a)的值。這個矩陣稱為的值。這個矩陣稱為狀態轉換矩陣狀態轉換矩陣。例例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 相應的狀態轉換矩陣如下表：相應的狀態轉換矩陣如下表： 一個一個DFADFA也可用一張（確定的）也可用一張（確定的）狀態轉換圖狀態轉換圖來表示。假定來表示。假定DFA MDFA M含有含有m m個狀態和個狀態和n n個個輸入字符輸入字符，那么，這個狀態轉換圖含有，那么，這個狀態轉換圖含有m m個個狀態結點狀態結點，每個結點頂多有，每個結點頂多有n n條箭弧射出和別的結點相連接，條箭弧射出和別的結點相連接，整張圖含有一個整張圖

39、含有一個初態結點初態結點和若干個（可以為和若干個（可以為0 0）終態結點終態結點。圖圖2.5 2.5 狀態轉換圖狀態轉換圖a aa aa aa ab bb bb b如下表所示的狀態轉換矩陣如下表所示的狀態轉換矩陣對應的狀態轉換圖如右圖：對應的狀態轉換圖如右圖：a aa aa ab bb bb b上圖所示的狀態轉換圖的上圖所示的狀態轉換圖的S S、及及* *如下：如下： S = 0,1,2,3S = 0,1,2,3 = a,b = a,b * *= | = | 為為，或者，或者為為a、b的任意組合的任意組合 從初態從初態0 0到終態到終態3 3有如有如圖所示的通路，箭弧圖所示的通路，箭弧上到標記

40、符連接起來上到標記符連接起來的字的字aaaa屬于屬于* *，所，所以右圖所示的以右圖所示的DFADFA可可以識別字以識別字aaaa。同理：從初態同理：從初態0 0到終到終態態3 3還有如圖所示的還有如圖所示的通路，箭弧上到標記通路，箭弧上到標記符連接起來的字符連接起來的字bbabba屬于屬于* *，所以右圖，所以右圖所示的所示的DFADFA可以識別可以識別字字bbabba。a a例例2-132-13：科學表示法中數字常量的：科學表示法中數字常量的正則表達式正則表達式對應的對應的DFADFA： digitdigitdigitdigitnatnat對應的對應的DFADFA如下圖如下圖 digit

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

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

43、 定理定理：如果一個：如果一個DFA M DFA M 的的輸入字母表輸入字母表為為，則我們也稱，則我們也稱M M是是上的一個上的一個 DFADFA。可以證明。可以證明: :上的一個字集上的一個字集V V * *是正規是正規的，當且僅當存在的，當且僅當存在上的上的DFA MDFA M，使得，使得V =L(M)V =L(M)。 DFA DFA的的確定性確定性表現在映射表現在映射： S SSS是一個是一個單值函數單值函數。即：對于任何狀態即：對于任何狀態sSsS和輸入符號和輸入符號a a， (s,a)(s,a)唯一確定了唯一確定了一個狀態。一個狀態。 從轉換圖角度，我們也可以得到答案。從轉換圖角度，

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

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

46、可以為和若干個（可以為0 0）終態結點。某些結點既可以是初態結點也）終態結點。某些結點既可以是初態結點也可以是終態結點。可以是終態結點。aaaaa,ba,bbbbbababa,ba,bab,baab,baaa,bbaa,bbab,baab,baaa,bbaa,bba aa aa aa ab bb bb bb b下圖所示的狀態轉換圖的下圖所示的狀態轉換圖的S S、及及* *如下：如下： S = 0,1,2,3S = 0,1,2,3 = a,b = a,b * *= | = | 為為，或者，或者為為a、b的任意組合的任意組合 對于對于* *中的任何一個字中的任何一個字，若，若存在一條從某一初態結點

47、到某一存在一條從某一初態結點到某一終態結點的通路，且這條通路上終態結點的通路，且這條通路上所有弧上的標記字依序連接成的所有弧上的標記字依序連接成的字（忽略字（忽略）等于）等于，則稱，則稱可可以為以為NFA MNFA M 識別識別。從初態從初態x x到終態到終態y y的連接通路弧上，有如下標記字：的連接通路弧上，有如下標記字： a a ，去除，去除，為，為aa，所以字，所以字aa可為可為NFA接受。接受。a aa ab b424243142421bbabba例例2-162-16：上圖所示的：上圖所示的NFANFA的以下兩個轉換序列都可以接受串的以下兩個轉換序列都可以接受串abbabb：允許接允許

48、接受受abab允許接受與允許接受與abab* *匹配的匹配的字符串字符串允許接受與允許接受與b b* *匹配的字匹配的字符串符串允許接受與允許接受與abab+ +匹配的字匹配的字符串符串由此，我們可以看由此，我們可以看出這個出這個NFANFA接受與正接受與正則式則式abab+ +|ab|ab* *|b|b* * 相相同的語言！同的語言！接受接受abab接受接受abab接受接受abab接受接受abab接受接受abab接受接受abab* *接受接受abab接受接受abab接受接受abab* *接受接受b b* *練習：考慮以下練習：考慮以下NFANFA通過怎樣的轉換通過怎樣的轉換接受串接受串aca

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

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

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

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

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