第2講--詞法分析

1、CompilerPrinciples1u詞法分析器的構(gòu)造詞法分析器的構(gòu)造u正規(guī)表達式與有窮自動機正規(guī)表達式與有窮自動機u詞法分析器的自動產(chǎn)生詞法分析器的自動產(chǎn)生CompilerPrinciples21.1.詞法分析器的構(gòu)造詞法分析器的構(gòu)造 編譯程序首先在單詞級別上來分析編譯程序首先在單詞級別上來分析和翻譯源程序。詞法分析的任務是：從和翻譯源程序。詞法分析的任務是：從左至右逐個字符地對源程序進行掃描，左至右逐個字符地對源程序進行掃描，產(chǎn)生一個個單詞符號，即產(chǎn)生一個個單詞符號，即把作為字符串把作為字符串的源程序改造成為單詞符號串的中間程的源程序改造成為單詞符號串的中間程序序。因此，詞法分析是編譯的

2、基礎。執(zhí)。因此，詞法分析是編譯的基礎。執(zhí)行詞法分析的程序稱為詞法分析器行詞法分析的程序稱為詞法分析器( (通常通常又稱為又稱為掃描器掃描器,scanner,scanner）。）。CompilerPrinciples3一、一般考慮：一、一般考慮： 1.詞法分析程序的主要任務：讀入字符串形式的源程序輸入剔除非單詞符號空格、換行，注釋宏展開，拼單詞符號*、:=、FOR、BEGIN等源程序的列表輸出行號CompilerPrinciples4 2.詞法分析器的輸入和輸出形式詞法分析器的輸入和輸出形式l輸入字符串形式的源程序l輸出單詞符號串。l程序語言的單詞符號一般分為五種： 關(guān)鍵字、運算符、界符、標識符

3、、常數(shù)關(guān)鍵字、運算符、界符、標識符、常數(shù)l詞法分析器輸出的單詞符號常常表示為二元式： （單詞種類編號，單詞符號的屬性值）（單詞種類編號，單詞符號的屬性值）CompilerPrinciples5 v單詞種類編號一個語言的單詞符號分成幾種，怎樣編碼是一個技術(shù)性問題，它取決于處理上的方便。標識符一般歸為一種。常數(shù)則宜按類型（整、實、布爾、字符等）分種。關(guān)鍵字可視其全體為一種，也可以一字一種。采用一字一種的分法實際處理起來較為方便。運算符可采用一符一種的分法，但也可以把具有一定共性的運算符視為一種。至于界符一般用一符一種的分法。 CompilerPrinciples6v單詞符號的屬性值單詞符號的屬性值

4、 如果一個種別只含有一個單詞符號，那么對于這個單詞符號，種別編碼就完全代表它自身了，因此屬性值就沒有意義了。若同一個種別含有多個單詞符號，那麼對于它的每個單詞符號，除了給出種別編碼之外，還應給出各有關(guān)單詞符號的屬性信息。 屬性值是反映特性或特征的值。例如，對于某個標識符，常將存放它有關(guān)信息的符號表項的指針作為其屬性值；對于某個字符串常量，則將該串的首地址指針作為其屬性值。CompilerPrinciples7 作為例子考慮下述作為例子考慮下述C+C+語句：語句： while (i=j) i-while (i=j) i- -;-; 若若whilewhile種別為種別為01,(01,(種別為種別為

5、11,11,標識符種別為標識符種別為20,=20,=種別種別為為12,)12,)種別為種別為13,13,種別為種別為14,;14,;種別為種別為30,30,則經(jīng)詞法則經(jīng)詞法分析器處理后，它將被轉(zhuǎn)換為如下的單詞符號序列：分析器處理后，它將被轉(zhuǎn)換為如下的單詞符號序列： ( 01, )( 01, ) ( 11, ) ( 11, ) ( 20 , ( 20 ,指向指向i i的符號表項的指針的符號表項的指針 ) ) ( 12 , ) ( 12 , ) ( 20 , ( 20 ,指向指向j j的符號表項的指針的符號表項的指針 ) ) ( 13 , ) ( 13 , ) ( 20 , ( 20 ,指向指向i

6、 i的符號表項的指針的符號表項的指針 ) ) ( 14 , ) ( 14 , ) ( 30 , ) ( 30 , )CompilerPrinciples83.詞法分析器與語法分析器的銜接詞法分析器與語法分析器的銜接 通常把詞法分析器安排成一個獨立子程序，而不是單獨的一遍。這樣一來，就無須在存儲器中保留整個單詞符號串，而是每當語法分析器需要單詞符號時就調(diào)用這個子程序。每一次調(diào)用，詞法分析器就從源程序字符串中識別出一個（一批）單詞符號，把它交給語法分析器。這樣做的好處是：l壓縮編譯時掃描字符的時間l詞法規(guī)則描述簡單，也便于獨立處理；l使得語法分析獲得更多信息（上下文環(huán)境）；l便于處理同一語言的幾種

7、不同表示形式（擴展）； CompilerPrinciples9v由以上考慮，可以初步設計為：源程序源程序掃描器掃描器語法分析器語法分析器取符號取符號送符號送符號CompilerPrinciples10二、進一步考慮：二、進一步考慮： 1. 1. 輸入、預處理輸入、預處理 輸入串一般放在一個緩沖區(qū)中，這個緩沖區(qū)稱源程序輸入緩沖區(qū)。詞法分析器的工作可以直接在這個緩沖區(qū)中進行。但在許多情況下，把輸入串預處理一下，對單詞符號的識別工作將是比較方便的。 預處理工作包括對空白符、跳格符、回車符和換行符等編輯性字符的處理，及刪除注釋等。于是可以設想構(gòu)造一個預處理子程序，它完成上面的工作。每當詞法分析器調(diào)用它

8、時就處理出一串確定長度的輸入字符，并將其裝入詞法分析器所指定的緩沖區(qū)中（稱為掃描緩沖區(qū)）。這樣分析器就可以在此緩沖區(qū)中直接而方便地進行單詞符號的識別工作。CompilerPrinciples11v2.2.對半互補緩沖區(qū)對半互補緩沖區(qū) 分析器對掃描緩沖區(qū)進行掃描時一般使用兩個指示器，一個指向當前正在識別單詞的開始位置（指向新單詞的首字符），另一個用于向前搜索以尋找單詞的終點。 但是不論掃描緩沖區(qū)設得多大都不能保證單詞符號不會被緩沖區(qū)的邊界所打斷。 因此，掃描緩沖區(qū)最好使用一分為二的區(qū)域，并使兩區(qū)首尾相接，形成一個對半互補緩沖區(qū)。 CompilerPrinciples12v例如： 。W h i l

9、 e。 起點指針起點指針搜索指針搜索指針CompilerPrinciples13符號表符號表單詞符號單詞符號掃描器掃描器預處理預處理子程序子程序輸入緩沖區(qū)輸入緩沖區(qū)源程序源程序掃描掃描 緩沖區(qū)緩沖區(qū)語法分析器語法分析器取單詞取單詞 綜上所述，預處理子程序、掃描器和語法分析器相互之間的關(guān)系及工作情況可圖示如下： CompilerPrinciples14 3. 單詞符號識別單詞符號識別超前搜索技術(shù)超前搜索技術(shù) 問題發(fā)生在對基本字不加任何保護的語言中，基本字及用戶自定義的標識符或標號之間無特殊分界符，這使得關(guān)鍵字的識別甚為麻煩。 請看下面的例子： 1 DO99K=1,10 2 IF(5.EQ.M)I

10、=10 3 DO99K=1.10 4 IF(5)=55 這四個語句都是正確的FORTRAN語句。語句1和2分別是DO和IF語句，它們都是以某基本字開頭的。語句3和4是賦值語句，它們都是以用戶自定義的標識符開頭的。CompilerPrinciples15 為了從1、2中識別出關(guān)鍵字DO和IF，我們必須要能夠區(qū)別1、3和區(qū)別2、4。語句1、3的區(qū)別在于等號之后的第一個界符：一個為逗號，另一個為小數(shù)點，語句2、4的主要區(qū)別在于右括號后的第一個字符：一個為字母，另一個為等號。這就是說，為了識別 1、2句中的關(guān)鍵字，我們必須超前掃描許多個字符，超前到能夠肯定詞性的地方為止。 這種向前掃描若干字符直到找到

11、能區(qū)分單詞的字符為止的技術(shù)就叫超前搜索超前搜索。CompilerPrinciples16v單一符號運算符和復合運算符：思考：如何從程序中刪除注釋： /* . */ CompilerPrinciples17CompilerPrinciples184. 詞法錯誤 如果沒有其他組件的幫助，詞法分析器很難發(fā)現(xiàn)源代碼中的錯誤。CompilerPrinciples19v例在在TurboC下運行下面的下運行下面的C程序程序 1 int main()2 int x = 3 ;3 if( x%2 = 0 ) /* even number */4return 0 ;5 else /* odd number */6

12、return 1 ;7 CompilerPrinciples20v如果把 if 寫成 iif ，則編譯得到以下2條錯誤信息：Error4: Statement missing ; ; in function main.Error5: Misplaced else in function main.v如果把 else 寫成 els ，則編譯得到以下3條錯誤信息： Error6: Undefined symbol els in function main. Warning6: Code has no effect in function main. Error6: Statement missin

13、g ; ; in function main. CompilerPrinciples21 現(xiàn)在有關(guān)掃描器的輸入、處理、輸出等問題都清楚了，可以進行掃描器的設計了。為此，引入一種新的圖形工具-狀態(tài)轉(zhuǎn)換圖。 1.1. 狀態(tài)轉(zhuǎn)換圖是一張有限個結(jié)點的有向圖，結(jié)點代表狀態(tài)，用圓圈表示，狀態(tài)之間用帶標識的箭弧連結(jié)，箭弧上的標識代表在射出結(jié)點（即箭弧始結(jié)點）狀態(tài)下可能出現(xiàn)的輸入字符或字符類。三、三、狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖CompilerPrinciples22 如右圖所示： 在狀態(tài)1下，若輸入字符為a，則讀進a，并轉(zhuǎn)換到狀態(tài)2。若輸入字符為b，則讀進b，并轉(zhuǎn)換到狀態(tài)3。一張轉(zhuǎn)換圖只包含有限個狀態(tài)（即有限個結(jié)點

14、），其中有一個被認為是初態(tài)，而且實際上至少要有一個終態(tài)（用雙圈表示），圖中3為終態(tài)。abCompilerPrinciples232.狀態(tài)轉(zhuǎn)換圖可用來識別一定的字符串狀態(tài)轉(zhuǎn)換圖可用來識別一定的字符串 例如： 字母|字母|數(shù)字 數(shù)字|數(shù)字 終態(tài)上打個*號，表示多讀進了一個不屬于該標識符或數(shù)字部分的字符，應把它退還給輸入串。012字母字母或數(shù)字其他*012數(shù)字數(shù)字其他CompilerPrinciples24*01234576數(shù)字數(shù)字數(shù)字E或DE或D+或-數(shù)字數(shù)字數(shù)字數(shù)字其它其它上圖是識別上圖是識別Fortran實常數(shù)的轉(zhuǎn)換圖實常數(shù)的轉(zhuǎn)換圖思考：結(jié)合前面的思考題，作出能夠識別注釋的狀態(tài)轉(zhuǎn)換圖： /*

15、. */ 和 /.CompilerPrinciples253.狀態(tài)轉(zhuǎn)換圖可以用來識別程序語言的單詞符號狀態(tài)轉(zhuǎn)換圖可以用來識別程序語言的單詞符號 例：假設某程序語言只有前述的五類單詞符號，運算符只有+、*、=，界符只有#、(、)，那么就可以用左邊的狀態(tài)轉(zhuǎn)換圖來識別其所有單詞符號。 012識別的串是基本字還是標識符，要查保留字表區(qū)分。 當然，還要加上兩個限制：(1)所有基本字都是保留的；(2)所有單詞間若無明顯分界，則用空格分開；空白字母或數(shù)字01245678931011字母非字母與數(shù)字數(shù)字非數(shù)字數(shù)字 =+*#（）其它*CompilerPrinciples264.狀態(tài)轉(zhuǎn)換圖的程序?qū)崿F(xiàn)狀態(tài)轉(zhuǎn)換圖的程

16、序?qū)崿F(xiàn)-為每個狀態(tài)編寫一小段程為每個狀態(tài)編寫一小段程序即可序即可例：例：使用如下一組全局變量和過程，作為實現(xiàn)狀態(tài)轉(zhuǎn)換圖的基本部分： CHAR：字符變量，存放最新讀進的源程序字符； Token：字符數(shù)組，存放構(gòu)成單詞符號的符號串； GetChar：取字符過程，將下一個輸入字符讀到CHAR中，并把搜索指示器的指針前移一個字符位置； GetBC：檢查CHAR中的字符是否為空白，若是則調(diào)用GetChar直至CHAR中進入一個非空白字符； ConCat：拼單詞過程，每調(diào)用一次就將CHAR中的字符連接到Token之后；CompilerPrinciples27 IsLetter和IsDigit：兩個布爾函數(shù)

17、，分別判斷CHAR中的字符為字母或是數(shù)字而返回真假值； Reserve：整型函數(shù)，對Token中的字符串查保留字表，查到則返回該保留字的整型編碼，否則返回0值； Retract：回退子程序，專門用來把搜索指示器回調(diào)一個字符位置，并置CHAR為空； Error：出錯處理子程序； DTB：類型轉(zhuǎn)換函數(shù)，將Token中的十進制數(shù)轉(zhuǎn)換為二進制數(shù)；于是，可編出如下程序： Start: Token:= ; GetChar ; GetBC ; CompilerPrinciples28CASE CHAR OF Az: BEGIN WHILE IsLetter OR IsDigit DO BEGIN ConCa

18、t; GetChar END; Retract; C:=Reserve; IF C=0 THEN Return($ID,Token) ELSE Return(C,) END;09: BEGIN WHILE IsDigit DO BEGIN ConCat ; GetChar END; Retract; Return($INT, DTB) END; =: Return($ASSIGN, ) ; +: Return($PLUS, ) ; *: Return($START, ) ; (: Return($LPAR, ) ; ): Return($RPAR, ) ; #: Return($ , ) ;

19、END OF CASE; DealError; Goto Start; CompilerPrinciples292.2.正規(guī)表達式與有窮自動機正規(guī)表達式與有窮自動機Regular Expression and Finite AutomatRegular Expression and Finite Automata a 上一節(jié)我們討論了掃描器的手工編制，是在討論了Scanner的主要工作-拼單詞符號并進行相應的詞法檢查-的基礎上，通過構(gòu)造狀態(tài)轉(zhuǎn)換圖再轉(zhuǎn)換為程序代碼來實現(xiàn)的。本節(jié)要進一步討論兩個抽象的工具，以便研究詞法分析程序的自動生成問題。 由于我們集中注意力于掃描器的自動生成，故對有關(guān)結(jié)論一般

20、不加形式證明，大家若對這方面感興趣，可以查閱相關(guān)書籍，如形式語言與自動機（Formal Language & Automata）。 CompilerPrinciples30 我們知道，任何高級程序設計語言都有自己的字母表，但并非字母表上的任何字符串都能稱為一個程序，我們感興趣的是能稱為程序的那些串，它們的集合稱為正規(guī)集。正規(guī)式是說明單詞的模式(pattern)的一種重要的表示法（記號），是定義正規(guī)集的數(shù)學工具，可用以描述單詞符號。這同樣是一個無窮語言的有窮描述的問題。1.正規(guī)式正規(guī)式(RE)的定義：的定義： 這是一種與我們以前常見的算術(shù)、邏輯等表達式不同的表達式。設為字母表，是 上的正

21、規(guī)式，它所表示的正規(guī)集分別為 ；對于任何a, a都是上的一個正規(guī)式，它所表示的正規(guī)集為a；一、正規(guī)表達式和正規(guī)集一、正規(guī)表達式和正規(guī)集CompilerPrinciples31假定U和V都是上的正規(guī)式，它們所表示的正規(guī)集分別記為L(U)和L(V),那么，(U|V), (UV)和(U)*也都是正規(guī)式，它們所表示的正規(guī)集分別為L(U)L(V), L(U)L(V) (連接積）和(L(U)*（閉包）。 僅由有限次使用上述三步驟而得到的表達式才是僅由有限次使用上述三步驟而得到的表達式才是上上的正規(guī)式。僅由這些正規(guī)式所表示的字集才是的正規(guī)式。僅由這些正規(guī)式所表示的字集才是上上的正規(guī)集。的正規(guī)集。*這個定義本

22、身是構(gòu)造型的，今后我們應該習慣這種構(gòu)造型定義及證明方式。CompilerPrinciples322.正規(guī)表達式的運算順序：正規(guī)表達式的運算順序： 括號括號 * *（閉包）（閉包）（連接）（連接）（或）（或）例1：=a, b。 a,b都是正規(guī)式 a*是正規(guī)式。 ba*也是正規(guī)式，它所表示的正規(guī)集為：b, ba, baa,，也就是上所有以b為首后跟著任意多個a的字。 同樣，a(a|b)* 亦為上的正規(guī)式，其所表示的正規(guī)集為上所有以a為首的字； (a|b)*(aa|bb)(a|b)* 對應的正規(guī)集是所有含有兩個相繼的a或相繼的b的字。 CompilerPrinciples333.正規(guī)表達式的等價：正

23、規(guī)表達式的等價： 若兩個正規(guī)式所表示的正規(guī)集相同，則認為二者等價，記為=。 例：=a, b L(b(ab)*) = b, bab, babab, L(ba)*b) = b, bab, babab, b(ab)* = (ba)*bCompilerPrinciples344.正規(guī)表達式的運算律：正規(guī)表達式的運算律： UV=VU （交換律） U(VW)=(UV)W （結(jié)合律） U(V W)=(U V) W （結(jié)合律） U(VW)=U VU W （分配律） (UV)W=U WV W （分配律） U=U=U （幺元） (R*)* = R* （冪等律） 思考：證明？CompilerPrinciples35

24、5 5. .標識符的正規(guī)式標識符的正規(guī)式letterletter - A|B|.|Z|a|b|.|z|_- A|B|.|Z|a|b|.|z|_digitdigit- 0|1|.|9- 0|1|.|9idid- letter(letter|digit)- letter(letter|digit)* * 擴展寫法：擴展寫法：letterletter - A-Za-z_- A-Za-z_digitdigit- 0-9- 0-9idid- letter(letter|digit)- letter(letter|digit)* * CompilerPrinciples36v練習：P72

25、(1)(4), 3.2.5 (3)3.2.11, 3.2.12CompilerPrinciples37二、確定的有窮自動機二、確定的有窮自動機（DFA)DFA)1.問題的提出：問題的提出：上節(jié)我們介紹了狀態(tài)轉(zhuǎn)換圖： 我們也可以寫： S0aS1:(S0,a)=S1 S1bS2:(S1,b)=S2 于是我們可以認為所有狀態(tài)構(gòu)成一個集合S，所有弧的標識構(gòu)成一個集合，函數(shù)，起始狀態(tài)S0和所有終態(tài)構(gòu)成的集合F。這樣我們可以把狀態(tài)轉(zhuǎn)換圖形式化為如下的數(shù)學系統(tǒng)DFA。S0SnS1S2abCompilerPrinciples38CompilerPrinciples393.DFA的表示形式：的表示形式： 由前所

26、述，由前所述，DFA是狀態(tài)轉(zhuǎn)換圖的是狀態(tài)轉(zhuǎn)換圖的抽象抽象模型。顯然模型。顯然DFA也可以表示成一張（確定也可以表示成一張（確定的）狀態(tài)轉(zhuǎn)換圖，它們是一一對應的。的）狀態(tài)轉(zhuǎn)換圖，它們是一一對應的。 假定假定DFA M 含有含有m個狀態(tài)、個狀態(tài)、n個輸入字個輸入字符，那末，這張圖含有符，那末，這張圖含有m個狀態(tài)結(jié)點，每個狀態(tài)結(jié)點，每個結(jié)點頂多有個結(jié)點頂多有n條箭弧射出和別的結(jié)點相連條箭弧射出和別的結(jié)點相連接，每條箭弧用接，每條箭弧用 上的一個字符作標記，整上的一個字符作標記，整張圖含有唯一的初態(tài)和若干個（可以是張圖含有唯一的初態(tài)和若干個（可以是0個）個）終態(tài)結(jié)點。終態(tài)結(jié)點。 CompilerPri

27、nciples40vDFA還可以用一個矩陣表示，該矩陣的行表示狀態(tài)，還可以用一個矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示列表示輸入字符，矩陣元素表示(s,a）的值，該矩）的值，該矩陣稱為陣稱為狀態(tài)轉(zhuǎn)換矩陣狀態(tài)轉(zhuǎn)換矩陣。3012abababa,b狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換矩陣CompilerPrinciples41 對于*中的任何一個字符串，若存在一條從初態(tài)結(jié)點到某一終態(tài)結(jié)點的通路，且這條通路上所有箭弧的標記符連接成的字等于，則稱為DFA M所識別（讀出或接受）。 若M的初態(tài)結(jié)點同時又是終態(tài)結(jié)點，則空字可以為M所識別。DFA M所能識別的字的全體記為L(M). DFA的確定性表現(xiàn)在是一

28、個從S x S的單值部分映射。也就是說，對任何狀態(tài)sS和輸入符號a，(s,a)唯一地確定了下一個狀態(tài)。從狀態(tài)轉(zhuǎn)換圖的角度來看，任何狀態(tài)發(fā)出的弧具有不同的標識。 CompilerPrinciples42例：例：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)問：有幾個狀態(tài),幾個輸入字符？幾個輸入字符？并畫出其轉(zhuǎn)換圖。并畫出其轉(zhuǎn)換圖。L(M)=?解：有解：有0，1，2，3共四個狀態(tài)。共四個狀態(tài)。輸入字符為輸入字符為a,b兩個。其狀態(tài)轉(zhuǎn)兩

29、個。其狀態(tài)轉(zhuǎn)換圖如右換圖如右L(M)為在為在 上含相繼兩個上含相繼兩個a或相繼或相繼兩個兩個b的字的集合。的字的集合。012abababa,b3CompilerPrinciples43CompilerPrinciples44 顯然，NFA也可以表示成一張狀態(tài)轉(zhuǎn)換圖。假定NFA 含有m個狀態(tài)、n個輸入字符，那么，這張圖含有m個狀態(tài)結(jié)點，每個結(jié)點可以射出若干條箭弧和別的結(jié)點相連接，每條箭弧用*上的一個字（不一定要不同的字而且可以是空字）作標記（稱為輸入字），整張圖至少含有一個初態(tài)和若干個（可以是0個）終態(tài)結(jié)點。某些結(jié)點既可以是初態(tài)也可以是終態(tài)結(jié)點。 對于*中的任何一個字符串，若存在一條從初態(tài)結(jié)點到

30、某一終態(tài)結(jié)點的通路，且這條通路上所有箭弧的標記符連接成的字（忽略那些標記為的?。┑扔?，則稱為NFA M所識別。也就是：(S0,)F。 若M的初態(tài)結(jié)點同時又是終態(tài)結(jié)點，或者存在一條某初態(tài)結(jié)點到某各終態(tài)結(jié)點的通路，則空字可以為M所識別。CompilerPrinciples45v例： M=(0,1,2,3,4,a,b,0,2,4)，其中： (0,a)=0,3, (1,a)=, (2,a)=2, (3,a)=4, (4,a)=4, (0,b)=0,1 , (1,b)=2, (2,b)=2, (3,b)=, (4,b)=4 03142a, ba, ba, baabb它能接受：所有含有兩個連續(xù)的a或兩個連

31、續(xù)的b的串CompilerPrinciples462.有窮自動機的等價：有窮自動機的等價： 對于任何兩個有窮自動機M和M，如果L(M)=L(M)，則稱M和M是等價的。對此我們有一個重要結(jié)論：判定任何兩個有窮自動機等價的算法是存在的。CompilerPrinciples47四、正規(guī)式與有窮自動機的等價性：四、正規(guī)式與有窮自動機的等價性： 我們先來證明兩個重要的事實：1.定理定理1：上的有窮自動機所接受的字的全體上的有窮自動機所接受的字的全體L L(M)(M)是是上的一個正規(guī)集。上的一個正規(guī)集。(1)一般考慮：要證明L(M)是上的一個正規(guī)集，很容易想到正規(guī)式。因為正規(guī)集是正規(guī)式的值。同時我們又知道

32、任何一個 FA M 都可以表示成一個狀態(tài)轉(zhuǎn)換圖，而該圖中從某個初態(tài)結(jié)點到某個終態(tài)結(jié)點的路上所有弧的標記連接而成的串，恰恰就是L(M)的一個字，L(M)就是這樣一些字的全體，于是我們想，是否能構(gòu)造一個正規(guī)表達式V，使得L(V)=L(M)呢？如果能構(gòu)造出這樣的一個V，問題也就解決了。為此，我們把轉(zhuǎn)換圖的概念加以拓廣，使每條弧可以用一個正規(guī)式來標記，如 ， 這樣我們就可以借助M來構(gòu)造V了。01abCompilerPrinciples48(2)證明（簡略）： a.在NFA M的狀態(tài)轉(zhuǎn)換圖上加入唯一的初態(tài)X和終態(tài)Y，從X到M原來的每個初態(tài)用標有的弧相連接，而每個原終態(tài)則用標有的弧與Y相連接。顯然這樣的N

33、FA M 與NFA M是等價的L(M)=L(M)。 b.反復使用以下規(guī)則對M中的所有狀態(tài)進行逐步消去： 123V1V213V1V212V1V212V1V2123V1V2V313V1V2*V3由于由于M 的狀態(tài)集是有限的，因此經(jīng)過有限次使用上述規(guī)則，的狀態(tài)集是有限的，因此經(jīng)過有限次使用上述規(guī)則，必然得到必然得到 ，顯然，顯然L(V)=LL(V)=L（M M ）=L=L（M M）。）。 對于對于NFANFA的情況具有一般性，若用的情況具有一般性，若用DFA MDFA M則更簡單。則更簡單。XYVCompilerPrinciples49abababa,b例：例：bbabXYaaa,b拓廣拓廣XYaa

34、bb(ba)*(ab)*XYa(ba)*(a bb)b(ab)*(b aa)XY(a(ba)*(a bb) b(ab)*(b aa) (a b)*a,ba,b這樣就得到了與所給DFA等價的正規(guī)式。CompilerPrinciples502.定理定理2：對于：對于上的每個正規(guī)表達式上的每個正規(guī)表達式V V，存在，存在一個一個上的上的DFADFA M M，使得，使得L(M)=L(V)L(M)=L(V)。(1)一般考慮：由定理1的證明，我們很容易想到，對上的每個正規(guī)式V，可以畫出拓廣轉(zhuǎn)換圖： 然后我們與逐次減少結(jié)點過程相反，可以對V逐次分裂并加入新結(jié)點和弧，直到每條弧的標記或者為中的一個符號，或者為

35、，這樣就構(gòu)造了一個轉(zhuǎn)換圖，也就是一個NFA M,然后再把M確定化為DFA就可以了。XYVCompilerPrinciples51(2)證明： a.把正規(guī)式V表示成拓廣轉(zhuǎn)換圖 b.根據(jù)以下規(guī)則分裂V并加入新狀態(tài)結(jié)點和標識弧 整個分裂過程保持 和 為唯一初態(tài)和終態(tài)，由正規(guī)式定義，顯然經(jīng)過有限次分裂就可以構(gòu)造出一個NFA M使得L(M)=L(V)。XYVXYijABijABijA*ikjABijABikjACompilerPrinciples52 c.對對NFA M確定化確定化構(gòu)造一個構(gòu)造一個DFA MDFA M使得使得L(M)=L(ML(M)=L(M ) ) 一般考慮：變多值映射為單值映射，可采用

36、子集法。NFA不確定的原因主要在于含有弧和從某結(jié)點經(jīng)由相同標識的弧而到達不同的結(jié)點結(jié)點集。這兩個問題解決了，NFA也就確定了。 預備定義1：狀態(tài)集I的閉包，記為 _CLOSURE(I)_CLOSURE(I),如下定義： .若sI,則s_CLOSURE(I)； .若sI，則由s出發(fā)經(jīng)任意條弧而能夠到 達的任何狀態(tài)s_CLOSURE(I)； 預備定義2：對狀態(tài)集I和a，定義 Ia=_CLOSURE(J)；其中J是那些可從I中某一結(jié)點出發(fā)經(jīng)過一條a弧而到達的狀態(tài)結(jié)點的全體。CompilerPrinciples53v設I=1，則由I經(jīng)一條a弧而到達的狀態(tài)結(jié)點的全體J=5,3,4，從而 Ia=_CLOS

37、URE(J)=5,6,2,3,8,4,7例：例：狀態(tài)轉(zhuǎn)換圖如下：aaaCompilerPrinciples54 M的確定化：從以上所談不難看出確定化的復雜程度與符號個數(shù)密切相關(guān)，為此我們設=a,b，并依如下過程構(gòu)造一個轉(zhuǎn)換矩陣。 該矩陣有三列，分別記為I,Ia,Ib，第一行第一列置為_CLOSURE(X)_CLOSURE(X) ，其中X為M的初態(tài)集。由此我們就可以根據(jù)預備定義構(gòu)造Ia和Ib，然后檢查Ia、Ib中是否有不同于已構(gòu)造出的I的，若有則將其作為新的I，又可以構(gòu)造新的Ia和Ib。依次下去，直到不再有新的狀態(tài)子集出現(xiàn)不再有新的狀態(tài)子集出現(xiàn)為止。因為M的狀態(tài)數(shù)是有限的，故上述過程必在有限步內(nèi)

38、停止。把上述表中第一列的狀態(tài)子集進行編號，最終可得到一個狀態(tài)矩陣，該矩陣唯一地畫出了一個確定的有窮自動機M，其唯一初態(tài)為_CLOSURE(X)_CLOSURE(X)，終態(tài)是那些含有M的終態(tài)Y的子集。 由上述構(gòu)造過程不難看出：L(M)=L(M),于是達到了確定化的目的。CompilerPrinciples55v例:設V=(a|b)*(aa|bb)(a|b)* (1)構(gòu)造NFA MXY(a|b)*(aa|bb)(a|b)*aabba,bXYa,b(2)構(gòu)造狀態(tài)轉(zhuǎn)換矩陣0123456CompilerPrinciples56(3)重新編號的狀態(tài)矩陣:(4)DFA M的狀態(tài)轉(zhuǎn)換圖為:b(5)DFA M=

39、 (0,1,2,3,4,5,6, a,b, , 0, 3,4,5,6),其中如左上表所示。a0123456aaaaaabbbbbbCompilerPrinciples573.推論1：一個字集V是正規(guī)的當且僅當有一自動機M,使得L(M)=L(V)。 推論2：NFA與 DFA接收相同的集合。 定理：推論2也可作為一個定理來證明：若L(M)被NFA M接受，則必定存在一個DFA M接受L(M)。 證明過程不再介紹，感興趣者可以嘗試用構(gòu)造法加歸納法來證明。 CompilerPrinciples58五五、DFADFA的化簡的化簡v所謂對一個DFA M的化簡，就是找一個DFA M，使得L(M)=L(M)但

40、是M的狀態(tài)數(shù)比M少。1.等價狀態(tài)和可區(qū)別狀態(tài)等價狀態(tài)和可區(qū)別狀態(tài)：若分別從狀態(tài)s和t出發(fā)而停于終態(tài)能讀出同一個字，則稱s, t為等價狀態(tài)；不等價的兩個狀態(tài)稱為可區(qū)別狀態(tài)。a0st12zaabaabbCompilerPrinciples592.狀態(tài)的最小化過程狀態(tài)的最小化過程v所謂DFA M的狀態(tài)最小小化過程就是找一個最少狀態(tài)的DFA M使得L(M)=L(M)。v具體做法：把具體做法：把DFA M的狀態(tài)集分割成一些不的狀態(tài)集分割成一些不相交的子集，使得不同的兩個子集的狀態(tài)都相交的子集，使得不同的兩個子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個狀態(tài)是可區(qū)別的，而同一子集中的任何兩個狀態(tài)都是等價的

41、，最后讓每個子集選出一個代表，都是等價的，最后讓每個子集選出一個代表，把所有與該子集相關(guān)的弧都與該代表相連接，把所有與該子集相關(guān)的弧都與該代表相連接，并消去其他等價狀態(tài)，即可求得最少狀態(tài)的并消去其他等價狀態(tài)，即可求得最少狀態(tài)的DFA M。CompilerPrinciples603.例： DFA M=(0,1,2,3,45,6,a,b, ,0,3,4,5,6)其中：(0,a)=1, (0,b)=2, (1,a)=3, (1,b)=2, (2,a)=1,(2,b)=4, (3,a)=3, (3,b)=5, (4,a)=6, (4,b)=4,(5,a)=6, (5,b)=4, (6,a)=3, (6

42、,b)=5.狀態(tài)圖：0123456aaaaaabbbbbba（1）形成基本分）形成基本分劃劃分成兩個子集:非終態(tài)子集I(1)和終態(tài)子集I(2)即：I(1)0,1,2I(2)=3,4,5,6bCompilerPrinciples61(2)對每個子集對每個子集I I(i)(i)和每個和每個a, ,來考察來考察I Ia a(i)(i)是否包含是否包含在某個在某個I I(j)(j)中中(j=1,2,n)(j=1,2,n)，若不是完全包含在某個，若不是完全包含在某個I I(j)(j)中則至少可一分為二，形成新的分劃。中則至少可一分為二，形成新的分劃。例： Ia(1)0,1,2a=1,3而1,3不在的任一

43、子集中，故應分割。又因0,2a=1，故分成0,2和1，顯然1是不能再分割的了。至此得到： =0,2,1,3,4,5,6(3)(3)重復重復(2)(2)的工作直到所有子集不能再分割為止。的工作直到所有子集不能再分割為止。 0,2b=2,4不在任一子集中，故一分為二得: = 0,1,2,3,4,5,6，而3,4,5,6a =3,6 3,4,5,6, 3,4,5,6b=5,4 3,4,5,6,不能再分割了。所以最后的分劃: =0,1,2,3,4,5,6。CompilerPrinciples62(4)選等價狀態(tài)子集的代表，并重構(gòu)狀態(tài)圖。選等價狀態(tài)子集的代表，并重構(gòu)狀態(tài)圖。 如3,4,5,6的代表為3，

44、可得狀態(tài)圖：02b13abba,baa(5)最后可得最少狀態(tài)自動機為：最后可得最少狀態(tài)自動機為： 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.CompilerPrinciples63RGDFANFA-NFARE總結(jié)：總結(jié)： 正規(guī)語言的描述模型正規(guī)語言的描述模型CompilerPrinciples643.3.詞法分析器的自動產(chǎn)生詞法分析器的自動產(chǎn)生 前面我們已經(jīng)談了狀態(tài)轉(zhuǎn)換圖可以用來識別單詞符號，DFA可以用一張確定的狀態(tài)轉(zhuǎn)換圖來表示，而D

45、FA又與正規(guī)式等價，所以我們可以用正規(guī)式來描述程序語言的詞法規(guī)則。而從正規(guī)式到自動機（狀態(tài)圖）再到程序的轉(zhuǎn)換工作，可以交予一個程序來自動生成。這類程序就是詞法分析器的詞法分析器的自動生成器自動生成器。 參考書3.4節(jié)介紹的Lex(Flex)Lex(Flex)就是其中典型的代表。此處不再贅述。 CompilerPrinciples65小結(jié)本講內(nèi)容： 詞法分析器的構(gòu)造 狀態(tài)轉(zhuǎn)換圖 正規(guī)表達式與正規(guī)集 DFA與NFA RE,RG,DFA,NFA的等價關(guān)系 DFA的最小化CompilerPrinciples66 功能：分割字符串形式的源程序，得到單詞符號串 輸入：字符串形式的源程序 輸出：單詞符號串（

46、二元式） 分析技術(shù) 超前搜索 對半互補緩沖區(qū) 預處理子程序 設計 獨立子程序 狀態(tài)轉(zhuǎn)換圖最小化DFA的狀態(tài)轉(zhuǎn)換圖 實現(xiàn)：最小化的DFA的每個狀態(tài)對應一小段程序詞詞法法分分析析器器RERGABaBaaAaBaBaNFADFA最小化最小化DFA轉(zhuǎn)換規(guī)則轉(zhuǎn)換規(guī)則增加開始狀態(tài)增加開始狀態(tài)增加終止狀態(tài)增加終止狀態(tài)確定化確定化劃分等劃分等價類價類CompilerPrinciples67例題與解答例題與解答例1寫出產(chǎn)生語言：能被5整除的十進制整數(shù)的文法及正則表達式。解：能被5整除的正則表達式： (+| - )A*(0|5) A0,1,2,3,4,5,6,7,8,9如果要求除零以外不以0開頭，則文法為： GZ: ZXAD |D|-5 AAB|C B0|C|BB C 1|2|3|4|5|6|7|8|9 D0|5 X+|-