1、第第3 3章章 詞法分析詞法分析Never look down on yourself. 永遠不要小看自己。永遠不要小看自己。編譯過程編譯過程第第3 3章章 詞法分析詞法分析 （P28P28） n3.1 詞法分析的功能詞法分析的功能 n3.2 程序語言的單詞符號種類及詞法分析輸出程序語言的單詞符號種類及詞法分析輸出 n3.3 正則文法及狀態圖正則文法及狀態圖n3.4 詞法分析程序的設計與實現詞法分析程序的設計與實現n3.5 正則表達式正則表達式n3.6 有窮自動機有窮自動機n3.7 詞法分析程序的自動生成器詞法分析程序的自動生成器LEX(略略)學習重點學習重點 n1、根據狀態圖進行詞法分析程序

2、的設計與實現、根據狀態圖進行詞法分析程序的設計與實現n2、根據正則文法畫狀態圖或反過來。、根據正則文法畫狀態圖或反過來。n3、正則文法到正則表達式的轉換、正則文法到正則表達式的轉換n4、NFA到到DFA的轉化的轉化n5、根據正則表達式構造、根據正則表達式構造FA3.13.1詞法分析的功能詞法分析的功能（P28P28） n詞法分析程序詞法分析程序（或（或詞法分析器詞法分析器或或掃描器掃描器）：詞法分）：詞法分析程序是編譯程序中完成詞法分析任務的程序。析程序是編譯程序中完成詞法分析任務的程序。 源 程 序詞 法 分 析 器單 詞 符 號n 詞法分析程序的任務詞法分析程序的任務其他任務：其他任務：濾

3、掉空格，刪除或跳過注釋、換行符、濾掉空格，刪除或跳過注釋、換行符、續行符、標號等非實質性的字符，填符號表，詞法續行符、標號等非實質性的字符，填符號表，詞法錯誤檢查等錯誤檢查等主要任務：主要任務：讀源程序，產生單詞符號讀源程序，產生單詞符號3.13.1詞法分析的功能詞法分析的功能 n詞法分析程序與語法分析程序的詞法分析程序與語法分析程序的2種種接口接口方式：方式：1、詞法分析作為獨立的一遍、詞法分析作為獨立的一遍，識別出源程序中的單詞，識別出源程序中的單詞序列，輸出到一個序列，輸出到一個中間文件中間文件供語法分析程序使用。供語法分析程序使用。字符串源程序字符串源程序 詞法分析器詞法分析器 符號串

4、源程序符號串源程序 2、詞法分析程序和語法分析程序作為同一遍、詞法分析程序和語法分析程序作為同一遍。把詞法。把詞法分析程序設計成一個分析程序設計成一個子程序子程序，當語法分析程序需要單，當語法分析程序需要單詞時，則調用詞法分析程序。詞時，則調用詞法分析程序。字符串源程序字符串源程序 詞法分析器詞法分析器 語法分析器語法分析器 取符號取符號 送符號送符號 3.2 3.2 程序語言的單詞符號種類及詞法分析輸出程序語言的單詞符號種類及詞法分析輸出（P29P29） n單詞符號單詞符號是程序設計語言的基本語法單位和最小的語是程序設計語言的基本語法單位和最小的語義單位。義單位。n例例 設設PASCAL源程

5、序段：源程序段： n:=1; while n=10 do n:=n+1; 從該程序順序找出如下單詞符號：從該程序順序找出如下單詞符號： n 、:=、1、;、 while、n、=、=、!=、+等。等。 n程序語言中的保留字、分界符的數量都是確定的，程序語言中的保留字、分界符的數量都是確定的，但是標識符和無符號數的數量是不確定的。但是標識符和無符號數的數量是不確定的。 3.2 3.2 程序語言的單詞符號種類及詞法分析輸出程序語言的單詞符號種類及詞法分析輸出 單詞類別單詞類別 單詞值單詞值 n詞法分析程序的輸出形式常采用二元式詞法分析程序的輸出形式常采用二元式單詞類別的表示：單詞類別的表示：p同一類

6、單詞統一用一個整數值或記號代表其屬性。同一類單詞統一用一個整數值或記號代表其屬性。例如用例如用1表示標識符，表示標識符，2表示無符號數等表示無符號數等p對于保留字和分界符采用一個符號對應一個單詞類對于保留字和分界符采用一個符號對應一個單詞類別碼別碼 單詞值的表示：單詞值的表示：p 常量的二進制表示常量的二進制表示p 常量、變量等在符號表中的地址碼等常量、變量等在符號表中的地址碼等p 對于一符一類的保留字和分界符用空值對于一符一類的保留字和分界符用空值3.2 3.2 程序語言的單詞符號種類及詞法分析輸出程序語言的單詞符號種類及詞法分析輸出 n例例 設設PASCAL源程序段：源程序段： n:=1;

7、 while n=10 do n:=n+1;經詞法分析器識別后其輸出單詞符號串如下圖所示：經詞法分析器識別后其輸出單詞符號串如下圖所示： 1n 的內部碼n5 1: =21 的二進制形式15 4;6w h i l e1n 的內部碼n3 8 =21 0 的二進制形式1 0d o1n 的內部碼n5 1: =1n 的內部碼n3 1+21 的二進制形式15 4;73.3 3.3 正則文法及狀態圖正則文法及狀態圖(P30)(P30) n狀態圖狀態圖：一張有窮的有向圖一張有窮的有向圖u結點代表狀態，用圓圈表示。結點代表狀態，用圓圈表示。u狀態間用有向弧線連接，連接弧狀態間用有向弧線連接，連接弧上標記有符號（

8、表示在弧線射出端上標記有符號（表示在弧線射出端的狀態下，讀入弧線上標記的符號的狀態下，讀入弧線上標記的符號可轉換到弧線指向的狀態）。可轉換到弧線指向的狀態）。u狀態個數是有窮的，其中狀態個數是有窮的，其中有一個有一個是開始狀態是開始狀態，至少有一個至少有一個狀態是狀態是結結束狀態束狀態，結束狀態常用，結束狀態常用雙圈雙圈表示。表示。 SUVZ00111狀態圖示例狀態圖示例 03.3 3.3 正則文法及狀態圖正則文法及狀態圖n 用正則文法（即用正則文法（即3型文法）來描述程序設計語言的詞型文法）來描述程序設計語言的詞法規則。正則文法形式為：法規則。正則文法形式為：Ua|Wa或或U = a|aW

9、，其中：其中： U，WVn， a Vt。n 根據正則文法畫狀態圖的方法根據正則文法畫狀態圖的方法: (左線性規則左線性規則) 文法中的每個非終結符號對應狀態圖中的一個結點，即圖中的文法中的每個非終結符號對應狀態圖中的一個結點，即圖中的每個結點代表一個非終結符號。每個結點代表一個非終結符號。 增設一個結點代表開始狀態增設一個結點代表開始狀態S，而文法中的開始符號對應的結，而文法中的開始符號對應的結點為結束狀態。點為結束狀態。 對于文法中的每一條形如對于文法中的每一條形如Ua的規則，畫一條從結點的規則，畫一條從結點S指向結指向結點點U的弧線，并在弧上標記的弧線，并在弧上標記a。 對于文法中每一條形

10、如對于文法中每一條形如U =Wa的規則，畫一條從結點的規則，畫一條從結點W指向指向結點結點U的弧線，并在弧上標記的弧線，并在弧上標記a。 3.3 3.3 正則文法及狀態圖正則文法及狀態圖n例例3-1(P30) 設有正則文法設有正則文法GZ：ZU0|V1UZ1|1VZ0|0畫出該文法對應的狀態圖。畫出該文法對應的狀態圖。SUVZ000111n根據正則文法畫狀態圖的方法根據正則文法畫狀態圖的方法：文法中的每個非終結符號對應文法中的每個非終結符號對應狀態圖中的一個結點。狀態圖中的一個結點。增設一個結點代表開始狀態增設一個結點代表開始狀態S，而文法中的開始符號對應的結而文法中的開始符號對應的結點為結束

11、狀態。點為結束狀態。對于文法中的每一條形如對于文法中的每一條形如Ua的規則，畫一條從結點的規則，畫一條從結點S指向指向結點結點U的弧線，并在弧上標記的弧線，并在弧上標記a。對于文法中每一條形如對于文法中每一條形如U =Wa的規則，畫一條從結的規則，畫一條從結點點W指向結點指向結點U的弧線，并在的弧線，并在弧上標記弧上標記a。 3.3 3.3 正則文法及狀態圖正則文法及狀態圖n練習練習 設有正則文法設有正則文法G： =1 | 2| | 9| 0 =1 | 2 | | 9 | 0畫出該文法對應的狀態圖。畫出該文法對應的狀態圖。n根據正則文法畫狀態圖的方法根據正則文法畫狀態圖的方法：文法中的每個非終

12、結符號對應狀態圖中的一個結點。文法中的每個非終結符號對應狀態圖中的一個結點。增設一個結點代表開始狀態增設一個結點代表開始狀態S，而文法中的開始符號對應的結點，而文法中的開始符號對應的結點為結束狀態。為結束狀態。對于文法中的每一條形如對于文法中的每一條形如Ua的規則，畫一條從結點的規則，畫一條從結點S指向結指向結點點U的弧線，并在弧上標記的弧線，并在弧上標記a。對于文法中每一條形如對于文法中每一條形如U =Wa的規則，畫一條從結點的規則，畫一條從結點W指向指向結點結點U的弧線，并在弧上標記的弧線，并在弧上標記a。 3.3 3.3 正則文法及狀態圖正則文法及狀態圖n利用狀態圖來分析和識別字符串的方

13、法利用狀態圖來分析和識別字符串的方法如下：如下：1.首先首先設置開始狀態設置開始狀態S為當前狀態為當前狀態。從輸入串的最左字符開始從輸入串的最左字符開始重復步驟重復步驟2，直到到達輸入串的右端為止。，直到到達輸入串的右端為止。2.掃描輸入串的下一個字符，在當前狀態所射出的弧中，找出掃描輸入串的下一個字符，在當前狀態所射出的弧中，找出標記有該字符的弧，并沿此弧前進，過渡到下一個狀態。標記有該字符的弧，并沿此弧前進，過渡到下一個狀態。n若若找不到標記有該字符的弧找不到標記有該字符的弧，則說明輸入串不是合法的句，則說明輸入串不是合法的句子，分析過程子，分析過程失敗結束失敗結束；n若掃描的字符是輸入串

14、的若掃描的字符是輸入串的最后一個字符最后一個字符，且標記有該字符，且標記有該字符的弧線的弧線到達結束狀態到達結束狀態，則表示輸入串是該文法的合法句子，則表示輸入串是該文法的合法句子，識別過程識別過程成功成功結束；否則識別過程結束；否則識別過程失敗結束失敗結束。3.3 3.3 正則文法及狀態圖正則文法及狀態圖n例例3-2（P31）設有正則文法）設有正則文法GZ：ZU0|V1UZ1|1VZ0|0對句子對句子0110進行的分析。進行的分析。步驟步驟 狀態狀態 掃描的字符掃描的字符 余留部分余留部分1S01102V1103Z104U0 5Z ZU0Z1V100110的語法樹的語法樹 解：解：利用它的狀

15、態圖對利用它的狀態圖對0110進行分析的過程進行分析的過程: SUVZ00011100和和100是否是否是文法是文法G的的句子句子?3.4 3.4 詞法分析程序的設計與實現詞法分析程序的設計與實現（P32P32） nTEST語言的單詞符號有語言的單詞符號有：標識符標識符：以字母開頭，后接字母或數字。如：以字母開頭，后接字母或數字。如a1等等保留字保留字（它是標識符的子集）（它是標識符的子集）: if、else、for、while、do、int、read和和write無符號整數無符號整數：100、256等等單分界符單分界符：如：如+、-、*、/、（、）、；、（、）、；、,等等雙分界符雙分界符：=

16、、=、!=、= =等等注釋符注釋符：用：用/*.*/括起括起 TEST語言的詞法規則語言的詞法規則 =| | =| = a|b|z|A|B|Z =1|2|9|0 =+|-|*|/|=|（|）|：|，|；|! =|=|!=|= =/* =*/ n在上述規則中，標識符、無符號整數、雙分界符以及注在上述規則中，標識符、無符號整數、雙分界符以及注釋規則表面看不是正則文法，轉換可變成正則文法。釋規則表面看不是正則文法，轉換可變成正則文法。TEST語言的各類單詞符號的正則文法語言的各類單詞符號的正則文法 =a|b|Z|a|Z |0|9 =0|1|9|0|9 =+|-|*|/|=|（|）|：|，|；|! =

17、 = |!|= = * =* =/ n由于部分單分界符與雙分界符或注釋的首字符相同，由于部分單分界符與雙分界符或注釋的首字符相同，如如、.(連接連接)|(或或/選擇選擇)。3.5 正則表達式n 例例 設設=a,b，則有：，則有：正則表達式正則表達式e正規集正規集L(e) bL(b)=babL(ab)=L(a)L(b)=ab=aba|bL(a|b)=L(a)L(b)=ab=a,ba*L(a*)=(L(a)*=a*= ,a,aa,aaa,ba* L(ba*)=L(b)L(a*)=ba*=b,ba,baa, 3.5 正則表達式3.5 正則表達式n 正則表達式相等正則表達式相等：設：設e1和和e2都是

18、都是上的正則表上的正則表達式，若達式，若L(e1)=L(e2)，則稱，則稱e1和和e2等價，記為等價，記為e1=e2。n例例 判斷判斷a|(ba)*和和 (ba)*|a是否等價。是否等價。解：解： L(a|(ba)*)=L(a)L(ba)*)L(ba)*|a)=L(ba)*)L(a) =L(a)L(ba)*)=L(a|(ba)*)a|(ba)*=(ba)*|a3.5 正則表達式n 例例(P37) 標識符的正則表達式為：標識符的正則表達式為： =字母字母字母字母|數字數字=字母字母(字母字母|數字數字)* 帶有符號的實數的正則表達式為：帶有符號的實數的正則表達式為： =( |+|-)(數字數字.

19、數字數字數字數字) =( |+|-)(數字數字)*.數字數字(數字數字)*)n例例3-6(P38) 設字母表設字母表=0，求表達式，求表達式00與與000|0定義的語言。定義的語言。解：表達式解：表達式00=00*所定義的語言是所定義的語言是0n|n1表達式表達式000|0=000*|0所定義的語言是所定義的語言是0n|n1 3.5 正則表達式n設設e1、e2和和e3是是上的正則表達式上的正則表達式,則滿足以下定律則滿足以下定律:交換律交換律：e1|e2= e2|e1除除 e1=e1 =e1外，外，連接不滿足交換律連接不滿足交換律結合律結合律：(e1e2)e3=e1(e2e3) (e1|e2)

20、|e3=e1|(e2|e3) 分配律分配律：e1(e2|e3)=e1e2|e1e3 (e1|e2)e3=e1e3|e2e33.5 正則表達式n正則文法與正則表達式有等價性，即可以將正則文正則文法與正則表達式有等價性，即可以將正則文法轉換成該文法的法轉換成該文法的開始符號開始符號所對應的正則表達式。所對應的正則表達式。其其轉換規則轉換規則為為:(1) 產生式產生式U:=V，V:=, 其中其中,U,V Vn，, Vt* ，轉換成正則表達式轉換成正則表達式U=；若；若U:=V，V:=,則轉換成正則表達式則轉換成正則表達式U=(2) 產生式產生式U:=U|,轉換成正則表達式轉換成正則表達式U=*；產生

21、式產生式U:=U|，轉換成正規表達式，轉換成正規表達式U=*(3) 產生式產生式U:=|，轉換成正則表達式，轉換成正則表達式U=|3.5 正則表達式n例例3-7(P39) 有正則文法如有正則文法如下，將其轉換下，將其轉換成等價的正則成等價的正則表達式。表達式。S aS|aBB bCC aC|a解：解：由由C aC|a，有，有C=a*a由由B bC，有，有B= ba*a由由S aS|aB，有，有 S=a*aB=a*aba*a所求的正則表達式為：所求的正則表達式為： a*aba*a3.5 正則表達式n例例(P38) 標識符的文法規則如下：標識符的文法規則如下：標識符標識符 = a|b|z |標識符

22、標識符a|標識符標識符b|標識符標識符z |標識符標識符0|標識符標識符1|標識符標識符9將該文法轉換成正則表達式。將該文法轉換成正則表達式。解：解：由標識符由標識符 = a|b|z |標識符標識符a|標識符標識符b|標識符標識符z |標識符標識符0|標識符標識符1|標識符標識符9，有，有標識符標識符 = a|b|z |標識符標識符(a|b|z|0|1|9)，則有：，則有：標識符標識符=(a|b|c|z)(a|b|z|0|1|9)* 所求的正則表達式為：所求的正則表達式為： (a|b|c|z)(a|b|z|0|1|9)*3.6 3.6 有窮自動機有窮自動機（P39P39）n有窮自動機有窮自動機

23、(FA)不是一臺具體的機器，而是一種不是一臺具體的機器，而是一種具有離散輸入與輸出系統的數學模型。具有離散輸入與輸出系統的數學模型。n有窮自動機分為兩種類型有窮自動機分為兩種類型:確定的有窮自動機確定的有窮自動機(DFA)：是指在當前的狀：是指在當前的狀態下，輸入一個符號，有窮自動機將轉換到態下，輸入一個符號，有窮自動機將轉換到唯一的后繼狀態。唯一的后繼狀態。不確定的有窮自動機不確定的有窮自動機(NFA)：在當前狀態下：在當前狀態下輸入一個符號，可能有兩種或兩種以上可選輸入一個符號，可能有兩種或兩種以上可選擇的后繼狀態。擇的后繼狀態。 n確定的有窮自動機（確定的有窮自動機（DFA）的形式定義：

24、）的形式定義：一個確定的有窮自動機一個確定的有窮自動機M（記作（記作DFA M）是一個五元組：）是一個五元組： M=（ Q， ，q0，F，）其中：其中：Q：是一個有窮的狀態集合。：是一個有窮的狀態集合。 ：是一個字母表，它的每個元素稱為一個輸入符號。：是一個字母表，它的每個元素稱為一個輸入符號。 q0：q0Q，是唯一的開始狀態。，是唯一的開始狀態。 F：F Q，稱為結束狀態集合。，稱為結束狀態集合。 ：狀態轉換函數，是一個：狀態轉換函數，是一個QQ的的單值單值映射。映射。在確定的有窮自動機中，狀態轉換函數的具體形式如下：在確定的有窮自動機中，狀態轉換函數的具體形式如下：(q,a)=q ,其中，

25、其中，q, qQ，a。這是一個單值函數，表示在當前狀這是一個單值函數，表示在當前狀態為態為q下，輸入符號為下，輸入符號為a時，自動機時，自動機將從狀態將從狀態q轉換到下一個狀態轉換到下一個狀態q,q稱稱為為q的的后繼狀態后繼狀態。3.6 3.6 有窮自動機有窮自動機 n例例3-8(P40) 設有窮自動機設有窮自動機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)=33.6 3.6 有窮自動機有窮自動機n確定的有窮自動機確定的有窮自動機M=(Q, q0,F,)可以用可以用狀態圖狀態

26、圖來來表示。表示。其對應關系為其對應關系為 ：狀態圖中的結點代表狀態，：狀態圖中的結點代表狀態，用圓圈表示，它與自動機用圓圈表示，它與自動機M中的狀態集合中的狀態集合Q相對應，相對應，其中包括開始狀態其中包括開始狀態q0和結束狀態集合和結束狀態集合F，結束狀態用，結束狀態用雙圈表示。狀態間用有向弧線連接，連接弧上標記雙圈表示。狀態間用有向弧線連接，連接弧上標記有符號，每條弧線對應一個狀態轉換函數，弧線上有符號，每條弧線對應一個狀態轉換函數，弧線上標記的符號集合就是字母表標記的符號集合就是字母表。 3.6 3.6 有窮自動機有窮自動機n例例3-8(P40) 設有窮自動機設有窮自動機DFA M=（

27、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畫出該自動機對應的狀態圖。畫出該自動機對應的狀態圖。3.6 3.6 有窮自動機有窮自動機a,b0123baaabbn 確定的有窮自動機確定的有窮自動機M=(Q, q0,F,)還可以用還可以用狀態轉狀態轉換矩陣換矩陣來表示。來表示。其對應關系為：其對應關系為：矩陣中的第一列元素矩陣中的第一列元素與自動機與自動機M中的狀態集合中的狀態集合Q一一對應，且一一對應，且初始狀態初始狀態q0是是第一列的第一個元素，右上角標記第一列的第一個元素，右上角標記

28、*的元素對應結束狀的元素對應結束狀態。態。狀態轉換矩陣的第一行元素與字母表中的每個符狀態轉換矩陣的第一行元素與字母表中的每個符號相對應。矩陣中的元素對應每個狀態轉換函數。如號相對應。矩陣中的元素對應每個狀態轉換函數。如果有狀態轉換函數果有狀態轉換函數(q,a)=q，其中，其中q,q Q，a，那么，就在矩陣中狀態那么，就在矩陣中狀態q對應的行和符號對應的行和符號a對應的列單對應的列單元中填入元中填入q 。3.6 3.6 有窮自動機有窮自動機n例例3-8(P40) 設有窮自動機設有窮自動機DFA M=（0,1,2,3，a,b,0,3,）(0,a)=1 (0,b)=2(1,a)=3 (1,b)=2(

29、2,a)=1 (2,b)=3(3,a)=3 (3,b)=3畫出該自動機對應的狀態轉換畫出該自動機對應的狀態轉換矩陣。矩陣。3.6 3.6 有窮自動機有窮自動機a,b0123baaabb S a b 0123* 1 2 3 2 1 3 3 3 n對對DFA的狀態轉換函數的擴充定義的狀態轉換函數的擴充定義： (q,at)=(q,a),t)其中其中a，t *，即，即t是是上的符號串。上的符號串。3.6 3.6 有窮自動機有窮自動機n對一個確定的有窮自動機對一個確定的有窮自動機M= (Q, q0,F,)以及某個以及某個符號串符號串x（ x *），如果有），如果有(q0, x)=p，且，且pF，則，則字

30、符串字符串x就被該自動機就被該自動機M所接受所接受。也就是從自動機開始。也就是從自動機開始狀態開始，在讀完全部輸入串以后，自動機剛好到達狀態開始，在讀完全部輸入串以后，自動機剛好到達結束狀態，那么該輸入串為該自動機所接受。從狀態結束狀態，那么該輸入串為該自動機所接受。從狀態圖上看，如果一個字符串能被自動機接受，那么從開圖上看，如果一個字符串能被自動機接受，那么從開始狀態出發，則存在一條到達某一結束狀態的路徑，始狀態出發，則存在一條到達某一結束狀態的路徑，且組成這條路徑的弧線上標記的符號連接起來正好就且組成這條路徑的弧線上標記的符號連接起來正好就是字符串是字符串x。 n例例3-9(P41) 設計

31、能接受偶數個設計能接受偶數個0和偶數個和偶數個1組成的串的有窮自動機，畫出其狀態圖及狀組成的串的有窮自動機，畫出其狀態圖及狀態轉換矩陣并判別態轉換矩陣并判別110101、11101能否被該自能否被該自動機接受。動機接受。 S 0 1 S *ABC B A C S S C A B SABC11010010 狀態轉換圖狀態轉換圖狀態轉換矩陣狀態轉換矩陣下面判別下面判別110101、11101能否被該自動機接受：能否被該自動機接受：(S，110101)=(A，10101)=(S，0101)=(B，101)=(C，01)=(A，1)= S(接受接受)(S，11101)=(A，1101)=(S，101)

32、=(A，01)=(C，1)= B(拒絕拒絕) 解：首先設計能接受偶數個解：首先設計能接受偶數個0和偶數個和偶數個1組成組成的數字串的有窮自動機如下：的數字串的有窮自動機如下：M1=（S，A，B，C，0，1， S，S，） （S，0）=B （S，1）=A （A，0）=C （A，1）=S （B，0）=S （B，1）=C （C，0）=A （C，1）=B其狀態圖及狀態轉換矩陣分別如圖所示。其狀態圖及狀態轉換矩陣分別如圖所示。 n一個一個確定的有窮自動機確定的有窮自動機M所接受的語言所接受的語言就是所能就是所能接受的輸入串構成的集合，用接受的輸入串構成的集合，用L(M)表示，有表示，有: L(M)=t |

33、(q0, t) F，t * 3.6 3.6 有窮自動機有窮自動機n確定有窮自動機的等價性確定有窮自動機的等價性：兩個確定有窮自動機：兩個確定有窮自動機A1和和A2，如果，如果L(A1)= L(A2)，則稱自動機，則稱自動機A1與與A2等等價。價。 n例例 已知：已知：DFA A=(q0,q1,a,b, ,q0,q0),其中，其中，(q0,a)=q1, (q1,b)=q0；DFA B=(q0,q1,q2,a,b, ,q0,q0,q2)，其中，其中,(q0,a)=q1,(q1,b)=q2,(q2,a)=q1。判斷。判斷DFA A和和DFA B是否等價？是否等價？3.6 3.6 有窮自動機有窮自動機

34、q0q1abq1abaq2q0DFA ADFA BL(A)=L(B)=(ab)n|n0，DFA A與與DFA B是等價的。是等價的。 n不確定的有窮自動機不確定的有窮自動機(NFA)的形式定義的形式定義（P42）:一個不確定的有窮自動機一個不確定的有窮自動機NFA M是一個五元式是一個五元式M=(Q， ，q0，F，)其中：其中：Q：有窮狀態集：有窮狀態集 ：輸入字母表與空串組成的集合，輸入可以是字：輸入字母表與空串組成的集合，輸入可以是字母表中的符號，也可以是空串母表中的符號，也可以是空串q0 ：開始狀態：開始狀態F：終止狀態集：終止狀態集F Q：狀態轉換函數，為：狀態轉換函數，為Q () 到

35、到Q的子集的子集的的多值多值映映射。射。3.6 3.6 有窮自動機有窮自動機n不確定的有窮自動機也可以用不確定的有窮自動機也可以用狀態圖和狀態轉換矩陣狀態圖和狀態轉換矩陣來表示，表示方法與確定的有窮自動機相同。來表示，表示方法與確定的有窮自動機相同。 n例例3-10(P42) 有有NFA M=(0,1,2,a,b,0,2,)其中：其中：(0,a)=2, (0,)=1,(1,b)=1,2,(2,a)=2,(2,b)=2，畫出其狀態圖及狀態轉換矩陣，確定該自動，畫出其狀態圖及狀態轉換矩陣，確定該自動機接收的語言。機接收的語言。3.6 3.6 有窮自動機有窮自動機該自動機接受的語言為該自動機接受的語

36、言為 L(M)= (a|bm) (a|b)n | m1,n0 021ba,bab Sab02111,22*22狀態圖狀態圖狀態轉換矩陣狀態轉換矩陣n設設(q, a)=p1,p2,pn，其中，其中a ，q, p1,p2,pn Q，對不確定的有窮自動機的狀態轉換函數的補充定義對不確定的有窮自動機的狀態轉換函數的補充定義：1) (q, )= -closure(q) 其中其中-closure(q)表示從狀態表示從狀態q出發，沿著出發，沿著弧到達的后弧到達的后繼狀態集合以及再從這些后繼狀態沿著繼狀態集合以及再從這些后繼狀態沿著弧所能到達的所有弧所能到達的所有狀態集合。狀態集合。2)(q, at)=(q,

37、 a),t)=(p1, t)(p2, t) (pn, t) 其中其中t *。3)(q1, q2,qn,x) =(q1, x) (q2, x)(qn, x) 其中其中x * ，表示從不確定自動機的狀態集出發，掃，表示從不確定自動機的狀態集出發，掃描字符串描字符串x后，所到達的狀態集等于從當前狀態集的每一后，所到達的狀態集等于從當前狀態集的每一個狀態集出發，掃描字符串個狀態集出發，掃描字符串x后所到達的狀態集之和。后所到達的狀態集之和。 3.6 3.6 有窮自動機有窮自動機n對某臺不確定的有窮自動機對某臺不確定的有窮自動機NFA M=（Q,q0,F,)及某個字符串及某個字符串 x（ x*），若有）

38、，若有(q0, x )=Q，且，且QF，則則x為為M所接受所接受。3.6 3.6 有窮自動機有窮自動機n不確定的有窮自動機不確定的有窮自動機M所接受的語言所接受的語言： L(M)=x|x*,(q0, x )=Q, 且且 QF n 非確定有窮自動機的等價性非確定有窮自動機的等價性: 兩個非確定有窮自動機兩個非確定有窮自動機A1和和A2 ，如果如果L(A1)= L(A2)，則稱自動機，則稱自動機A1與與A2等價。等價。 n設設P是一是一NFA M的狀態集的狀態集Q的一個子集，的一個子集，狀態集狀態集P的的閉包閉包 (記為記為-closure(P),P43)的計算方法的計算方法如下：如下：1）若）若

39、qP，則，則q-closure(P)，即，即P的所有成員都的所有成員都是是p的的閉包的成員閉包的成員;2）若）若qP，那么從，那么從q出發經過任意條出發經過任意條弧而能到達弧而能到達的任何狀態都屬于的任何狀態都屬于-closure(P)。3.6 3.6 有窮自動機有窮自動機n-closure(P)是狀態集是狀態集Q的一個子集。的一個子集。n例例3-11(P43)，對如圖所示的，對如圖所示的NFA M ，求，求P=1、P=2、P=1，2的的閉包。閉包。3.6 3.6 有窮自動機有窮自動機143265aaa NFA M狀態圖狀態圖 解：解：-closure(1)=1,3,4,6-closure(2

40、)=2,6-closure(1,2)=-closure(1)-closure(2)=1,3,4,62,6=1,2,3,4,6 n設設P仍是一自動機仍是一自動機M的狀態集的子集，的狀態集的子集， P =p1, p2,pn ， a，狀態集狀態集P的的a弧轉換集弧轉換集(記為記為Pa,P44)為：為： Pa=-closure(J) 其中其中 J=(p1, a )(p2,a)(pn,a) ，即即J是從狀態子集是從狀態子集P中的每一個狀態出發，沿著標記中的每一個狀態出發，沿著標記為為a的弧而到達的狀態所組成的集合。的弧而到達的狀態所組成的集合。3.6 3.6 有窮自動機有窮自動機n例例3-12(P44)

41、 對如圖所示的對如圖所示的NFA M ，若，若P=1，求，求Pa。3.6 3.6 有窮自動機有窮自動機143265aaaNFA M狀態圖狀態圖 解：解：Pa=-closure(J) =-closure(1, a )=-closure(2,4)=2,4,6 n根據根據NFA M=(Q,q0,F, )構造等價的構造等價的DFA M=(Q,q0,F,)的過程的過程(即即NFA的確定化的確定化，P44):1) = 2) 先求先求由由NFA M 的開始狀態的開始狀態q0 構成的集合構成的集合的的閉包，閉包，從而確定從而確定DFA M的開始狀態的開始狀態q0。3) 求開始狀態求開始狀態q0對每個輸入符號的

42、弧轉換集，若出現對每個輸入符號的弧轉換集，若出現不同于開始狀態不同于開始狀態q0的新狀態，則轉的新狀態，則轉4)。4) 求新狀態對每個輸入符號的弧轉換集，重復該步驟，求新狀態對每個輸入符號的弧轉換集，重復該步驟，直至沒有新狀態產生為止。直至沒有新狀態產生為止。5) 根據上面求出的各個狀態確定結束狀態集根據上面求出的各個狀態確定結束狀態集F=P|P F ，其中，其中P為為M的每個狀態子集。的每個狀態子集。3.6 3.6 有窮自動機有窮自動機n例例 將將NFA(見下圖見下圖)確定化。確定化。3.6 3.6 有窮自動機有窮自動機SZA10B C0 ,1解：將解：將NFA轉換為轉換為DFA的過程的過程

43、B,C,Z q3B,C q2B,C,Z q3B,C,Z q3B,C q2B,C q2B,C,Z q3B,C q2A,B,C q1 A,B,C q1S q0P1P0Pq0q1011q20q3010NFA相應的相應的DFA的狀態轉換圖為：的狀態轉換圖為：n例例 將將NFA(見下圖見下圖)確定化。確定化。3.6 3.6 有窮自動機有窮自動機解：將解：將NFA轉換為轉換為DFA的過程的過程NFA相應的相應的DFA的狀態轉換圖為：的狀態轉換圖為：B,C,Z q2B,C q1B,C,Z q2B,C,Z q2B,C q1B,C q1B,C,Z q2 B,C q1S,A,B,C q0P1P0Pn練習練習 將將

44、NFA(見下圖見下圖)確定化。確定化。3.6 3.6 有窮自動機有窮自動機解：將解：將NFA轉換為轉換為DFA的過程的過程NFA相應的相應的DFA的狀態轉換圖為：的狀態轉換圖為：3,4 q43,4 q4Pc4 q32 q22 q24 q33,4 q44 q32 q22,3 q12,3 q11,4 q0PbPaP1234aaaccbq0q1q2q3q4aaabbccn根據正則表達式可構造與之等價的有窮自動機，反根據正則表達式可構造與之等價的有窮自動機，反之亦然。之亦然。3.6 3.6 有窮自動機有窮自動機n根據正則表達式構造有窮自動機的分解規則（根據正則表達式構造有窮自動機的分解規則（P46）S

45、0S1S0S1S0S1a1) 與與、和和a （a ）等價的）等價的NFA分別是：分別是： 與與R1R2（或（或R1.R2 ）等價的）等價的NFA為：為：3.6 3.6 有窮自動機有窮自動機與與R1 |R2 等價的等價的NFA為：為：S0S1R1R2 S0S2S1R1 R2 S0S1R1|R2 S0S1R1 R2 與與R*（或（或R）等價的）等價的NFA為：為： S0S1R* S0S2S1 Rn例例3-13（P47） 有正則表達式有正則表達式R=(a)*(|bb)(a|b)* ，構，構造出等價的造出等價的NFA，然后轉化成，然后轉化成DFA。3.6 3.6 有窮自動機有窮自動機解：構造過程如下：

46、解：構造過程如下：01(a)*(|bb)(a|b)* 02(a)*31|bb (a|b)* 0231|bb a|b 45a 0231 a45a 6b b bn練習練習 構造正則表達式構造正則表達式a(ab*|ba*)*b的的NFA。 3.6 3.6 有窮自動機有窮自動機SZAbaC BbDaEbaG F n將將DFA M轉換成正則表達式的方法轉換成正則表達式的方法（P48）：）：3.6 3.6 有窮自動機有窮自動機填加兩個新的結點填加兩個新的結點S和和T，將結點，將結點S與與DFA M上的開上的開始狀態結點連接，將每個結束狀態結點與始狀態結點連接，將每個結束狀態結點與T結點用弧線結點用弧線連接

47、，所有連接弧線上均標記為連接，所有連接弧線上均標記為，從而，使，從而，使NFA M只只有一個開始狀態有一個開始狀態S和一個結束狀態和一個結束狀態T。逐步去掉逐步去掉NFA M中的結點，直到只剩下結點中的結點，直到只剩下結點S和和T。在去掉結點的過程中，逐步用正則表達式來標記弧線。在去掉結點的過程中，逐步用正則表達式來標記弧線。去掉結點的規則如下。去掉結點的規則如下。 p 連接：連接：13R1R2 123R1 R2 p選擇：選擇：3.6 3.6 有窮自動機有窮自動機p閉包（或重復）閉包（或重復）:12R1|R2 12R1 R2 13R* 123 Rn例例 設設NFA M的狀態轉換圖如下圖所示，在

48、的狀態轉換圖如下圖所示，在x,y上構造一個正則表達式上構造一個正則表達式e，使，使L(e)=L(M)。 3.6 3.6 有窮自動機有窮自動機123xyyx4x ,yyxn解：構造過程如下：解：構造過程如下：3.6 3.6 有窮自動機有窮自動機123xyyx4x ,yyxS T 1x,yS 4T xy*yyx*x3.6 3.6 有窮自動機有窮自動機1x,yS Txy*y|yx*xST(x|y)*(xy*y|yx*x)所求的正則表達式為：所求的正則表達式為：(x|y)*(xy*y|yx*x)3.6 3.6 有窮自動機有窮自動機n如果有兩個確定的有窮自動機如果有兩個確定的有窮自動機DFA A1和和D

49、FA A2所接所接受的語言完全一樣，我們說這兩個自動機是等價的。受的語言完全一樣，我們說這兩個自動機是等價的。n對于任何給定的對于任何給定的DFA，都有一個含有最少狀態的等價，都有一個含有最少狀態的等價的的DFA（稱為（稱為最小化的最小化的DFA），而且這個最小化的），而且這個最小化的DFA是唯一的。是唯一的。n等價狀態與不等價狀態等價狀態與不等價狀態(P49)： 在一個確定的有窮自動機里，在一個確定的有窮自動機里，如果從如果從S1狀態出發接受的所有符狀態出發接受的所有符號串集合與從號串集合與從S2狀態出發接受的狀態出發接受的所有符號串集合一樣，那么稱狀所有符號串集合一樣，那么稱狀態態S1和和

50、S2是等價的；否則是不等是等價的；否則是不等價的。價的。02134abaabn多余狀態：多余狀態：一是從初始狀態到該狀態之間沒有通路；一是從初始狀態到該狀態之間沒有通路；二是從該狀態到終止狀態之間沒有通路。二是從該狀態到終止狀態之間沒有通路。n例例3-15 (P49) 判斷如下的狀態圖中，哪些狀態是多余判斷如下的狀態圖中，哪些狀態是多余狀態。狀態。012345bba0234bb有多余狀態的狀態圖有多余狀態的狀態圖 刪除多余狀態的狀態圖刪除多余狀態的狀態圖 n多余狀態是無用的，應該刪除。刪除多余狀態的方法多余狀態是無用的，應該刪除。刪除多余狀態的方法是直接將多余狀態結點以及相關的弧線刪除，即可得

51、到是直接將多余狀態結點以及相關的弧線刪除，即可得到等價的自動機。等價的自動機。 aab3.6 3.6 有窮自動機有窮自動機3.6 3.6 有窮自動機有窮自動機n設設DFA M=(Q,q0,F)，最小化（或化簡）最小化（或化簡）DFA的算的算法法(P49) :1）先將自動機的狀態劃分成）先將自動機的狀態劃分成非結束狀態集非結束狀態集S1和和結束結束狀態集狀態集S2。2）對各狀態集按下面方法劃分，直到所有狀態集不）對各狀態集按下面方法劃分，直到所有狀態集不再產生新的劃分為止。設第再產生新的劃分為止。設第m次劃分將次劃分將Q分成分成n個狀態個狀態集，即集，即Q= S1S2Sn 。 對狀態集合對狀態集

52、合Si（i=1，2，n）中的各個狀態逐一檢查，設狀態）中的各個狀態逐一檢查，設狀態q1和和q2是狀是狀態集合態集合Si中的兩個狀態，對于輸入符號中的兩個狀態，對于輸入符號a（a），有），有(q1,a)= S、(q2,a)=S,若狀態若狀態S 和和S屬于同一狀態屬于同一狀態集合，則將狀態集合，則將狀態q1和和q2放在同一狀態集合中；否則，將放在同一狀態集合中；否則，將狀態狀態q1和和q2分為兩個集合。分為兩個集合。3.6 3.6 有窮自動機有窮自動機3）重復第）重復第2步，直到所有狀態集合都不能劃分。此時，步，直到所有狀態集合都不能劃分。此時，每個狀態集合中的狀態都是等價的。每個狀態集合中的狀態

53、都是等價的。4）將每個狀態集合中的等價狀態合并成一個等價代）將每個狀態集合中的等價狀態合并成一個等價代表狀態。將狀態函數中的所有狀態用相應的等價代表表狀態。將狀態函數中的所有狀態用相應的等價代表狀態表示。從狀態圖上看，要將一個狀態集合中的等狀態表示。從狀態圖上看，要將一個狀態集合中的等價狀態結點合并成一個結點。價狀態結點合并成一個結點。5）刪除多余狀態。）刪除多余狀態。 3.6 3.6 有窮自動機有窮自動機n例例 將將DFA（見右圖）最小化。（見右圖）最小化。解：將狀態集分成非結束狀態集解：將狀態集分成非結束狀態集S1=q0,q1,q2和結束狀態集和結束狀態集S2=q3 。在在S1中，由于狀態

54、中，由于狀態q0無輸入無輸入1，而，而狀態狀態q1和狀態和狀態q2有輸入有輸入1，所以將，所以將S1分割成分割成S11=q0和和S12=q1,q2。又因為又因為 (q1,0)=q2S12， (q2,0)=q2S12， (q1,1)=q3S2， (q2,1)=q3S2，所以狀態，所以狀態q1和狀態和狀態q2等價。等價。將原狀態集合分割成以下子集：將原狀態集合分割成以下子集：q0，q1,q2，q3q0q1011q20q30103.6 3.6 有窮自動機有窮自動機n例例3-16(P50) 對如圖所示的有窮自動機化簡。對如圖所示的有窮自動機化簡。01234bbbaaabaab待化簡的有窮自動機待化簡的

55、有窮自動機 解：將狀態集分成非結束狀態集解：將狀態集分成非結束狀態集S1=0,1,2和結束狀態集和結束狀態集S2 =3，4 。對對S1=0，1，2的劃分的劃分:(0,a)=1,(1,a) =3,(2,a) =1,(0,b)=2,(1,b) =2,(2,b) =4將將S1分成分成S4=0，S5=1, S6=2對對S2=3，4的化分的化分:(3,a)=3，(4,a) =3,(3,b)=4，(4,b) =4狀態狀態3和和4等價。等價。最終得到不能劃分的狀態集有最終得到不能劃分的狀態集有: S2=3,4, S4=1,S5=0,S6=2。0123bbbaaaab化簡后的有窮自動機化簡后的有窮自動機 3.

56、6 3.6 有窮自動機有窮自動機n練習練習 將將DFA（見下圖）最小化。（見下圖）最小化。01xy234576xxxxxxyyyyyy3.6 3.6 有窮自動機有窮自動機n練習練習 將將DFA（見下圖）最小化。（見下圖）最小化。01xy234576xxxxxxyy yyyy01xy235xxxyyy最小化最小化DFA待化簡的待化簡的DFA3.6 3.6 有窮自動機有窮自動機n根據根據DFA來構造詞法分析程序的方法來構造詞法分析程序的方法（P51）：）：直接編程的詞法分析器直接編程的詞法分析器 用程序來模擬用程序來模擬DFA的行為。在這種方法里，將的行為。在這種方法里，將DFA用狀態圖表示，按下列步驟根據狀態圖畫出詞法分析程用狀態圖表示，按下列步驟根據狀態圖畫出詞法分析程序流程圖：序流程圖：p1) 開始狀態對應程序的開始；開始狀態對應程序的開始；p2) 結束狀態對應程序的結束；結束狀態對應程序的結束；p3) 狀態轉移對應條件語句或多分支選擇語句；狀態轉移對應條件語句或多分支選擇語句；p4) 狀態圖的環對應程序中循環語句；狀態圖的環對應程序中循環語句；p5) 結束