編譯原理與技術(shù)講義 第2章 詞法分析

1、編譯原理與技術(shù)第2章 詞法分析青島大學(xué)信息工程學(xué)院主要內(nèi)容詞法分析器的設(shè)計(jì) 詞法分析器的一種手工實(shí)現(xiàn) 正規(guī)表達(dá)式 有限自動(dòng)機(jī)詞法分析的自動(dòng)生成器Lex編譯原理與技術(shù)2詞法分析器在編譯中的位置 詞法分析器語法分析器符號表源程序單詞取下一個(gè)單詞單詞記號編譯原理與技術(shù)32.1 詞法分析器的設(shè)計(jì)詞法分析器的基本功能按照語言的定義規(guī)則，逐個(gè)地讀入源程序的符號，識別出對語言有意義的符號串，即單詞符號；分析單詞記號的屬性，并把單詞記號及其屬性填寫在符號表中；同時(shí)把源程序改造成等價(jià)的計(jì)算機(jī)內(nèi)部表示單詞記號，以便編譯的后續(xù)階段使用。還要對源程序進(jìn)行預(yù)處理工作，包括：刪除源程序中的空格、制表符、換行、注釋等不影響

2、程序語法、語義的結(jié)構(gòu)。 編譯原理與技術(shù)42.1 詞法分析器的設(shè)計(jì)高級程序語言的五種單詞記號：保留字 是程序語言定義的具有固定意義的英文單詞，有時(shí)稱為基本字或關(guān)鍵字。例如，在C+中， char、float、extern、friend、switch、new都是關(guān)鍵字。保留字一般不能另作它用。標(biāo)識符 表示各種名字的字符串，如變量名、類型名、函數(shù)名、對象名等。運(yùn)算符 如+、= =、=等。常量 常量的類型一般有整型、實(shí)型、布爾型、文字型等。分界符 如分號、括號、注釋標(biāo)記/*、*/等。編譯原理與技術(shù)52.1 詞法分析器的設(shè)計(jì)詞法分析器的輸出單詞記號一般采用形式為 的二元式。單詞的種別是語法分析需要的信息，

3、通常用整數(shù)表示；單詞的屬性值則是編譯的語義分析和代碼生成等階段需要的信息。編譯原理與技術(shù)62.1 詞法分析器的設(shè)計(jì)例2.1：假如保留字的編碼是1，標(biāo)識符的為2，運(yùn)算符為3，分界符為4，整型常量為10，實(shí)型常量為11。那么，對于源程序代碼：for (i = 1, sum = 9.8; i = 100; i+) sum += i3.14;詞法分析器產(chǎn)生的結(jié)果是單詞記號序列3，編譯原理與技術(shù)72.1 詞法分析器的設(shè)計(jì)詞法掃描器與符號表 對符號表的操作主要是填表、查詢和更新。每當(dāng)詞法分析器識別了一個(gè)單詞的時(shí)候，第一項(xiàng)工作就是查詢符號表。對于不同的單詞種別，查詢的方式和隨后的處理完全不同。例如，對于關(guān)鍵

4、字、分界符和運(yùn)算符等，只需在各自的符號表中查詢，獲得并記錄其它屬性值，生成相應(yīng)的單詞記號。處理常量，特別是處理標(biāo)識符要復(fù)雜的多，而且僅僅在詞法分析階段是無法獲得一個(gè)標(biāo)識符的所有信息。當(dāng)詞法掃描器識別了一個(gè)標(biāo)識符的時(shí)候，首先查詢關(guān)鍵字表，看它是否是關(guān)鍵字；如果不是，還要在標(biāo)識符表中查詢，看它是否已經(jīng)存在，如果不存在就把它填入標(biāo)識符表，并填入種別、類型等信息。 編譯原理與技術(shù)82.1 詞法分析器的設(shè)計(jì)詞法分析器的兩種實(shí)現(xiàn)模式 完全獨(dú)立模式和相對獨(dú)立模式在完全獨(dú)立模式下，詞法分析器作為編譯的子系統(tǒng)單獨(dú)地運(yùn)行一趟，掃描整個(gè)源程序，把識別的單詞序列以機(jī)器內(nèi)碼的形式輸出在一個(gè)中間文件上，供為語法分析使用。

5、編譯原理與技術(shù)92.1 詞法分析器的設(shè)計(jì)完全獨(dú)立模式的好處編譯程序結(jié)構(gòu)清晰、條理化而且便于高效地實(shí)現(xiàn)；在設(shè)計(jì)高級語言時(shí)能獨(dú)立地研究詞法與語法兩個(gè)方面的特性；增強(qiáng)編譯程序的可移植性：可以就同一個(gè)語言為不同的機(jī)器寫不同的詞法分析器，而只編寫一個(gè)共同的語法分析，使用這些詞法分析器相同的單詞機(jī)內(nèi)表示；把同一個(gè)詞法由于單詞記號的語法可以用較簡單的文法描述，把詞法和語法分開，就能為這種文法建立有效的特殊方法和自動(dòng)構(gòu)造技術(shù)。 編譯原理與技術(shù)102.1 詞法分析器的設(shè)計(jì)相對獨(dú)立模式：詞法分析器設(shè)計(jì)成一個(gè)子程序，每當(dāng)語法分析需要一個(gè)單詞的時(shí)候，就調(diào)用該子程序。 相對獨(dú)立模式的好處：詞法分析器和語法分析器被設(shè)計(jì)在

6、同一趟，省去了存放單詞的終結(jié)文件。 編譯原理與技術(shù)112.1 詞法分析器的設(shè)計(jì)詞法錯(cuò)誤的處理 在詞法分析階段發(fā)現(xiàn)的錯(cuò)誤統(tǒng)稱為詞法錯(cuò)誤，它們大多是單詞拼寫錯(cuò)誤，這或者是因?yàn)闀鴮戝e(cuò)誤、或者因?yàn)殒I入錯(cuò)誤，例如把關(guān)鍵字拼寫錯(cuò)。 對詞法錯(cuò)誤校正的常用策略是修補(bǔ)嘗試，一般包括：刪除一個(gè)多余的字符；插入一個(gè)遺漏的字符；用一個(gè)正確的字符替換一個(gè)不正確的字符；交換兩個(gè)相鄰的字符。編譯原理與技術(shù)122.2 詞法分析器的一種手工實(shí)現(xiàn) 輸入的預(yù)處理 對于許多程序語言來說，空格、制表符、換行符等編輯性字符除了出現(xiàn)在文字常量中，在其它任何地方的出現(xiàn)都沒有意義，而注釋作為程序的重要文檔幾乎可以出現(xiàn)在程序中的任何地方。它們的

7、存在可以改善程序的可讀性和易理解性，卻不影響程序的語法結(jié)構(gòu)和執(zhí)行語義。通常在編譯的詞法分析階段被預(yù)處理過程刪除掉。 編譯原理與技術(shù)132.2 詞法分析器的一種手工實(shí)現(xiàn)輸入的預(yù)處理掃描器對緩沖區(qū)進(jìn)行掃描時(shí)一般使用兩個(gè)指針：一個(gè)指向當(dāng)前正在識別的單詞的起始位置，另一個(gè)用于向前搜索以尋找該單詞的終點(diǎn)，兩個(gè)指針之間的符號串就是要識別的單詞符號。無論掃描緩沖區(qū)設(shè)計(jì)的多大都不能保證單詞符號不會(huì)超過其邊界。掃描緩沖區(qū)一分為二的兩段置.f o r ( s u m = 0 , i = 1 .搜索指針起點(diǎn)指針.C a r.e e l . 2 .編譯原理與技術(shù)142.2 詞法分析器的一種手工實(shí)現(xiàn)超前搜索和最長匹配

8、為了識別一個(gè)更有意義的單詞符號，在找到了可能是單詞符號的起點(diǎn)或者構(gòu)成了單詞部分時(shí)，掃描器并不滿足，還要繼續(xù)讀入輸入串，看是否能找到由更多符號所組成的單詞（即最長匹配），有時(shí)可能要掃描到一個(gè)可以“斷句”的符號（超前搜索），才能決定最后一個(gè)掃描的符號不屬于之前的符號串所構(gòu)成的單詞。超前搜索符號通常是最長匹配單詞的結(jié)束標(biāo)志，可以是空格符、回車符、制表符等可以被預(yù)處理掉的符號；也可能是下一個(gè)單詞記號的起始符。編譯原理與技術(shù)152.2 詞法分析器的一種手工實(shí)現(xiàn)超前搜索和最長匹配的例子在識別“for”的時(shí)候，要掃描到左括弧(時(shí)才知道，它不屬于標(biāo)識符的符號；當(dāng)讀到了，以便構(gòu)造出小于等于“=”或不等于“”的比

9、較運(yùn)算符，否則，就構(gòu)造小于運(yùn)算符。 編譯原理與技術(shù)162.2 詞法分析器的一種手工實(shí)現(xiàn)狀態(tài)轉(zhuǎn)換圖 狀態(tài)轉(zhuǎn)換圖是構(gòu)造詞法分析器的一個(gè)良好工具，它描繪了為得到一個(gè)單詞記號，詞法分析器應(yīng)該執(zhí)行的動(dòng)作。狀態(tài)轉(zhuǎn)換圖是一個(gè)有向圖，結(jié)點(diǎn)代表狀態(tài)，用圓圈表示，內(nèi)部用數(shù)字表示狀態(tài)名稱；狀態(tài)之間由箭弧連接，箭弧上有符號作為標(biāo)記，稱為從箭弧尾的離開狀態(tài)讀入標(biāo)記符號以后轉(zhuǎn)換到箭弧頭的進(jìn)入狀態(tài)。若離開狀態(tài)s的某個(gè)標(biāo)記為other，則表示離開s的其它箭弧標(biāo)記以外的任意符號。每個(gè)狀態(tài)轉(zhuǎn)換圖中的狀態(tài)數(shù)量有限，都有唯一的一個(gè)起始狀態(tài)（本書用一個(gè)進(jìn)入的箭頭表示）和至少一個(gè)終結(jié)狀態(tài)（用雙圈表示）。 編譯原理與技術(shù)172.2 詞法分

10、析器的一種手工實(shí)現(xiàn)狀態(tài)轉(zhuǎn)換圖識別或接受一定的輸入符號串從起始狀態(tài)開始，讀進(jìn)輸入符號串的一個(gè)符號a，沿著狀態(tài)轉(zhuǎn)換標(biāo)記為a進(jìn)入下一個(gè)狀態(tài)，重復(fù)執(zhí)行直到進(jìn)入終結(jié)狀態(tài)。即，如果存在一個(gè)從起始狀態(tài)到終結(jié)狀態(tài)的路徑，路徑上的標(biāo)記用連接運(yùn)算連接在一起形成一個(gè)符號串，它和輸入符號串相同，則稱該輸入符號串可以接受。如果不能進(jìn)入任何一個(gè)終結(jié)狀態(tài)，則稱該狀態(tài)轉(zhuǎn)換圖不能識別或接受這個(gè)輸入符號串 編譯原理與技術(shù)182.2 詞法分析器的一種手工實(shí)現(xiàn)digit01letterletter對于符號串var1，有狀態(tài)序列， 例2.2： 標(biāo)識符一般定義為字母打頭的字母數(shù)字序列.編譯原理與技術(shù)192.2 詞法分析器的一種手工實(shí)現(xiàn)5

11、other=1=032例2.3：類似語言中的關(guān)系符的狀態(tài)轉(zhuǎn)換圖 。在終結(jié)狀態(tài)加了星號*，表示在狀態(tài)1、2和3都還不能確定它們是否是符合最長匹配準(zhǔn)則的單詞記號，還需要在讀入一個(gè)字符才能確定。而為實(shí)現(xiàn)最長匹配的一個(gè)超前搜索符號“其它”則不屬于這個(gè)單詞，應(yīng)該推給掃描緩沖區(qū)。 編譯原理與技術(shù)202.2 詞法分析器的一種手工實(shí)現(xiàn)例2.4：Pascal語言中數(shù)的狀態(tài)轉(zhuǎn)換圖 。在這個(gè)復(fù)雜的例子中，狀態(tài)3、5和8分別表示識別是整數(shù)、不帶指數(shù)部分的實(shí)數(shù)以及帶有指數(shù)部分的實(shí)數(shù)，但是，只能在超前搜索一個(gè)其它符號以后，才能在狀態(tài)9確定識別了一個(gè)Pascal的數(shù)。讀者可以自己驗(yàn)證例子數(shù)2005，+1998，81.07，

12、2.0036，看它們是否能被這個(gè)轉(zhuǎn)換圖所接受。3digitdigitotherdigitdigitdigit9814562+, E7+,digitEdigitotherother*編譯原理與技術(shù)212.2 詞法分析器的一種手工實(shí)現(xiàn)基于狀態(tài)轉(zhuǎn)換圖的詞法分析器的實(shí)現(xiàn)code表示單詞記號的種別；value存放標(biāo)識符或數(shù)在符號表的入口地址；過程getghar(ch)從掃描緩沖區(qū)得到一個(gè)搜索符號，存儲(chǔ)在變量ch中；函數(shù)isLetter(ch)和isDigit(ch)分別檢查ch是否是字母/數(shù)字；函數(shù)lookup(token, table) 在符號表table中查詢是否包含單詞token；insert (

13、token, table)在則把單詞token插入符號表table中并返回在符號表的地址；函數(shù)reporterror()報(bào)告并簡單處理詞法錯(cuò)誤。 編譯原理與技術(shù)222.2 詞法分析器的一種手工實(shí)現(xiàn)根據(jù)狀態(tài)棧圖編寫詞法掃描器的方法一讓狀態(tài)轉(zhuǎn)移對應(yīng)一個(gè)讀入字符的語句或函數(shù)，然后與轉(zhuǎn)移上的標(biāo)記比較，如果相等就進(jìn)入轉(zhuǎn)移對應(yīng)的程序段或子程序；否則，調(diào)用錯(cuò)誤處理程序。多個(gè)轉(zhuǎn)移就對應(yīng)分支語句；如果轉(zhuǎn)移返回自身，形成一個(gè)圈，對應(yīng)程序段的就是循環(huán)語句。 編譯原理與技術(shù)232.2 詞法分析器的一種手工實(shí)現(xiàn)標(biāo)識符狀態(tài)轉(zhuǎn)換圖的一個(gè)實(shí)現(xiàn)int code, value;char token =”;/ 在開始狀態(tài)0do t

14、oken = token+ch;/ 不斷讀入字母或數(shù)字，合并成一個(gè)標(biāo)識符 getchar(ch);/ 保持在狀態(tài)1 while (!isLetter(ch) | !isDigit(ch)； / isLetter(ch)和isDigit(ch)分別檢查ch是否是字母/數(shù)字/ 進(jìn)入結(jié)束開始狀態(tài)2code = lookup(token, keywordsTable);/ 在關(guān)鍵字表中查詢token，若它是關(guān)鍵字就返回1if (code= =1) return(1, token);/ 返回關(guān)鍵字的單詞記號，假如關(guān)鍵字種別是1else value=insert(token, identifierTabl

15、e); / 把token插入標(biāo)識符表，返回入口地址return (2, value)/ 返回標(biāo)識符的單詞記號，假如標(biāo)識符種別是2編譯原理與技術(shù)242.2 詞法分析器的一種手工實(shí)現(xiàn)根據(jù)狀態(tài)棧圖編寫詞法掃描器的方法二采用一個(gè)變量來記錄當(dāng)前的狀態(tài)，把狀態(tài)轉(zhuǎn)換嵌入到一個(gè)循環(huán)體內(nèi)的分支語句中，其中的第一個(gè)分支測試當(dāng)前狀態(tài)，而嵌入內(nèi)層的第一個(gè)分支語句則對給定的狀態(tài)測試輸入符號，以決定轉(zhuǎn)移進(jìn)入的狀態(tài)。 編譯原理與技術(shù)252.2 詞法分析器的一種手工實(shí)現(xiàn)例2.5：下圖示意的是識別C風(fēng)格注釋，即形式/*.*/，的狀態(tài)轉(zhuǎn)換圖。狀態(tài)2中的標(biāo)記other是除*之外的其它符號，而從狀態(tài)3到狀態(tài)2的標(biāo)記other是除*和

16、/之外的其它符號。 413 2other*0/other*編譯原理與技術(shù)262.2 詞法分析器的一種手工實(shí)現(xiàn)int state = 0;while (state = 0, 1, 2, 3 ) switch state case 0: getchar(ch);if (ch = = /) state = 1; getchar(ch) ;else reporterror();case 1: getchar(ch);if (ch = = *) state = 2; getchar(ch) ;else reporterror();case 2: getchar(ch);if (ch = = *) sta

17、te = 3; getchar(ch) ;else getcharch(ch); / 還是在狀態(tài)2case 3: getchar(ch);switch ch case /: state = 4; getchar(ch) ; case *: state =3; getchar(ch) ; default: state = 2if (state = = 4 ) return; else reporterror();編譯原理與技術(shù)27Id-keywordsnumberotherotherotherEAotherotherotherdigitotherinIDstartLNE=*= =other*le

18、tter, digitletter23inNum*digitdigit*commentGE=*+*/=+*/digit課本圖2.6:int code, value,;char state = “start”;char token =”;state_sets表示所有狀態(tài)名的集合編譯原理與技術(shù)282.2 詞法分析器的一種手工實(shí)現(xiàn)while (state屬于state_sets) switch state case “comment”: getchar(ch); if (ch = = ) state = “start”; getchar(ch) ; case “start”: getchar(ch)

19、;switch ch case isletter(ch): state = “inID”; token = ch; getchar(ch) ; case isdigit(ch): state = “inNum”; token = ch; getchar(ch) ; case ch = = : state = “comment”; getchar(ch) ; case ch = = : state = “GE”; token = ch; getchar(ch) ; case ch = =+ : state = “+” ; token = ch; case ch = = : state = “”

20、; token = ch; case ch = =* : state = “*” ; token = ch; case ch = =/ : state = “/” ; token = ch; default:getchar(ch);/ 過濾掉無用的符號 編譯原理與技術(shù)292.2 詞法分析器的一種手工實(shí)現(xiàn)case “inNum”: while (state屬于inNumber, 2, 3) / 處理數(shù) switch state case “inNum”: switch ch / 處理整數(shù) case isdigit(ch): token = token+ch; getchar(ch) ; case

21、 ch = = . : state = “2”; token = token+ch; getchar(ch);default: state = “number”; code=10; / 處理實(shí)數(shù)case “2”: if (isdigit(ch) state = “3”; token = token+ch; getchar(ch); else reporterror (); case “3”: if (isdigit(ch) state = “3”; token = token+ch; getchar(ch); else code = 11; state = “number”; case “nu

22、mber”: value = insert (token, identifierTable); return(code, value); 編譯原理與技術(shù)302.2 詞法分析器的一種手工實(shí)現(xiàn)case “inID”: while (isletter(ch) | isdigit(ch) token = token+ch; getchar(ch) ; code = lookup(token, keywordsTable); / 在關(guān)鍵字表中查詢token if (code= =1) return(1, token); / 返回關(guān)鍵字的單詞記號 else value=insert(token, iden

23、tifierTable); / 把token插入標(biāo)識符表 return (2, value); / 返回標(biāo)識符的單詞記號 case “LNE”: getchar(ch); if (ch = = ) getchar(ch); return(3, “”); if (ch = = =) getchar(ch); return(3, “=”); else return(3, “=”); else return(3, “”); case “+”: getchar(ch); return(3, “+”);case “”: getchar(ch); return(3, “”);case “”: getcha

24、r(ch); return(3, “”);case “/”: getchar(ch); return(3, “/”);編譯原理與技術(shù)312.3 正規(guī)表達(dá)式 符號、符號串與符號集合 定義2.1：字母表是有限的非空的符號集合，字母表中的元素稱作符號。例如，二進(jìn)制數(shù)語言的字母表是0, 1；Java語言的字母表可以說是一切可以打印字符組成的集合。 編譯原理與技術(shù)322.3 正規(guī)表達(dá)式定義2.2：由字母表中的符號所組成的任何有限序列稱為符號串。一個(gè)符號串所包含符號的個(gè)數(shù)稱為該符號串的長度。例如，對于字母表a, b，a、b、aa、ab、ba和abba都是上的符號串。符號串b、ab和abba的長度分別是1、

25、2和4。符號串中符號的排列順序十分重要，上面的ab和ba表示不同的符號串。通常用小寫的希臘字母、等表示符號串。符號的長度表示成|，例如|abba|=4。允許空符號串，即不包含任何符號的符號串，用希臘字母表示，|=0。 編譯原理與技術(shù)332.3 正規(guī)表達(dá)式如果x=uv是一個(gè)符號串，則稱u是x的頭，稱v是x的尾。當(dāng)我們堆一個(gè)符號串的某些部分感興趣、堆其它部分不感興趣時(shí)，通常忽略調(diào)不感興趣的部分，而只保留感興趣的部分。例如，若我們只關(guān)心符號串x=t中的符號t，也可以用x=.t.表示；同樣，x=t和x=t.這兩種表示都只關(guān)注符號的頭時(shí)符號t。 編譯原理與技術(shù)342.3 正規(guī)表達(dá)式定義2.3：設(shè)和是同一

26、字母表上的符號串，把的各個(gè)符號相繼地寫在之后所的到的符號串稱為和的連接（并置），記做。顯然，|=|+|。例如，字母表a, b, 0, 1上的符號串=bb11、=a00，是bb11a00，而是a00bb11，而且| = | = 7 =| + | = | +| = 4+3 = 7。顯然，對于任何符號串，都有。 定義2.4：設(shè)u是某一字母表上的符號串，把u自身連接n次，即=u.u(n個(gè)u)，稱作符號串u的n次方冪，記做=un。例如，u1=u，u2=uu，u4=uuuu。特別地，當(dāng)n=0時(shí)，u0=。顯然，uun-1 = un-1u= un。編譯原理與技術(shù)352.3 正規(guī)表達(dá)式定義2.5：若集合A中的所

27、有元素都是某字母表上的符號串，則稱集合A是該字母表上的符號集合。字母表上的符號集合通常用大寫字母A、B、C等表示。例如，字母表a, b, 0, 1上長度為2的符號串集合A= | =xy，并且x和y是中的一個(gè)符號；字母表上單詞B= | 是a, b中的符號串。定義2.6：兩個(gè)符號串集合A和B的乘積AB定義為：AB=uv | uA并且vB。例如，設(shè)A=a, b，B=0, 1，那么AB=a0, a1, b0, b1，BA=0a, 1a, 0b, 1b，AA=aa, ab, ba, bb。由于對于任何符號串x都有xxx，所以A=A=A，但是，對于空集，卻有等式A=A=。類似于符號串的方冪，可以定義符號串

28、集合的方冪，特別地，定義字母表A的方冪為A0= ，A1=A，An= An-1 A ( n 0 )， 顯然，若u An，則| u | = n。編譯原理與技術(shù)362.3 正規(guī)表達(dá)式定義2.7：字母表的閉包*01.n.，正閉包+12.n. 。例如，對于字母表a, b，+= a, b, aa, bb, ab, ba, aaa, bbb, aab, bba, aba, bab, abb, baa, .。顯然，*0+，+= * = *。*表示字母表上所有長度的符號串的集合，包括空符號串；+表示長度至少為1的符號串的集合。+實(shí)際上就表示了該字母表所構(gòu)成的語言，句子就是其中的符號串。對于C語言，可以說，C語言

29、是其字母表，也即基本符號正閉包的真子集。編譯原理與技術(shù)372.3 正規(guī)表達(dá)式例2.6：令字母表L=A, B, ., Z, a, b, ., z，D=0, 1, ., 9，那么LD是字母和數(shù)字的集合；LD4表示以字母開頭、跟隨4個(gè)數(shù)字的串的集合；L(LD)15表示長度為16的標(biāo)識符，即以字母開始的16位的字母和數(shù)字串的集合；D*表示不含空的數(shù)字串的集合。編譯原理與技術(shù)382.3 正規(guī)表達(dá)式正規(guī)式與正規(guī)集 字母表上的正規(guī)表達(dá)式用來描述一種稱為正規(guī)集的語言。定義2.8：字母表上的正規(guī)表達(dá)式（簡稱正規(guī)式）按照下列規(guī)則遞歸地定義：（1）是上的正規(guī)式，它表示的正規(guī)集是；（2）是上的正規(guī)式，它表示的正規(guī)集是

30、；（3）中的任意符號a都是上的正規(guī)式，它表示的正規(guī)集是a（4）若r和t都是正規(guī)式，它們所表示的正規(guī)集分別是L(r)和L(t)，那么(r)、r|t 、rt和 r*都是正規(guī)式，表示的正規(guī)集分別是L(r)、L(r)L(t)、L(r)L(t)、( L(r) *。根據(jù)顯然定義有下列等式： L(a)=a，L()=，L()=，L(r)= L(r)，L(rt)= L(r)L(t)，L(r|t)= L(r)L(t)，L(r*)= ( L(r) *。 編譯原理與技術(shù)392.3 正規(guī)表達(dá)式例2.7：令字母表=a, b, c，那么(a|b)(a|b)aa, ab, ba, bb；(a|c)*表示所有a和c組成的符號串

31、，其中包含空串；(a|c)*b(a|c)*表示只包含一個(gè)b的字母表上的所有符號串，例如b，abc，baaac，caccb，ccbaaa。最多包含一個(gè)b的字母表上的符號串的集合可以表示成(a|c)*| (a|c)*b(a|c)*)，或者(a|c)*(b|)(a|c)*。(a|c)*b(a|c)* b表示的集合是什么呢？它表示只含兩個(gè)b的符號串的集合。編譯原理與技術(shù)402.3 正規(guī)表達(dá)式定義2.9：如果兩個(gè)正規(guī)式r與t表示的正規(guī)集相同，則稱它們的等價(jià)的，記做r=t。正規(guī)式等價(jià)的例子如a|(ba)*= (ba)*|a，(a|b)=(b|a)。 定理解釋r|t = t|r| 的交換律r|(s|t) =

32、 (r|s)|tr(st) = (rs)t結(jié)合律r(s|t) = rs | rt(r|s)t = rt | st分配律r = r = rr = r = rr | = r吸收律r* = (r | )*閉包運(yùn)算和之間的關(guān)系編譯原理與技術(shù)412.3 正規(guī)表達(dá)式擴(kuò)展的正規(guī)式 （1）一個(gè)或多次重復(fù)：一元后綴算符“+”表示一個(gè)或多次重復(fù)，即正規(guī)式r+表示一個(gè)或多個(gè)r的串的集合。這樣，(0|1)+表示所有二進(jìn)制數(shù)字的集合，而(0|1)*同時(shí)還包含了可串。（2）字符集的范圍：對于字母或數(shù)字的集合，可以使用a|b|.|z或0|1|.|9。更簡潔的方式是用方括弧，用連接線表示范圍，這樣，上面的字母或數(shù)字就可以分別

33、表示成a-z和0-9。類似的，a|b|c|d可以寫成a-d或者abcd。標(biāo)識符是字母打頭的字母數(shù)字串，可以表示成A-Za-z A-Za-z0-9*。（3）零個(gè)或一個(gè)：一元后綴算符“?”表示零個(gè)或一個(gè)，r?是r|的縮寫。帶符號的整數(shù)可以寫成(+|)?1-90-9*編譯原理與技術(shù)422.3 正規(guī)表達(dá)式如果正規(guī)式很長，可以給它命名，使它們可以像普通的符號一樣，在隨后的正規(guī)式中使用這些名字來引用相應(yīng)的正規(guī)式，以便得到簡潔的正規(guī)式。如果r如是字母表上的正規(guī)式，那么正規(guī)定義的形式是：name r。這樣，正規(guī)式r的名字name就可以像中的符號一樣，在以后構(gòu)造上正規(guī)式的時(shí)候使用。編譯原理與技術(shù)432.3 正規(guī)

34、表達(dá)式例2.8：Pascal語言的標(biāo)識符集合是字母開頭的字母數(shù)字串，下面就是這個(gè)集合的正規(guī)定義：letter A-Za-zdigit 0-9identifier letter( letter| digit )*編譯原理與技術(shù)442.3 正規(guī)表達(dá)式例2.9：Pascal語言的數(shù)是2005，+1998，81.07，2.0036這樣的串，即由整數(shù)、小數(shù)和指數(shù)三個(gè)部分組成。小數(shù)和指數(shù)部分是可選的，其中指數(shù)標(biāo)記E后面可以有+或，再跟上一個(gè)或多個(gè)數(shù)字，而小數(shù)點(diǎn)之后必須至少有一個(gè)數(shù)字。下面就是Pascal語言的數(shù)的集合的正規(guī)定義：digit 0-9digits digit digit*signed + |

35、fraction (.digits)?exponent (E(signed)?digits)?number signed? digits fraction exponent編譯原理與技術(shù)452.3 正規(guī)表達(dá)式正規(guī)表達(dá)式的實(shí)現(xiàn)和應(yīng)用正規(guī)表達(dá)式實(shí)際上是描述和識別一組字符串的模板（模式），它包含字符、元符號（如表示重復(fù)的*和選擇符|）和一些具有特殊意義的符號。這個(gè)模板決定什么樣的字符串屬于某一個(gè)集合。正規(guī)表達(dá)式在處理文本方面具有強(qiáng)大的能力，它在計(jì)算機(jī)領(lǐng)域的應(yīng)用不僅僅局限于構(gòu)造編譯器的詞法掃描器，其它著名的應(yīng)用還包括UNIX操作系統(tǒng)的命令工具如grep，處理復(fù)雜文本分析與操作的腳本語言Perl，Tcl

36、，Python，PHP和awk以及通用程序開發(fā)編輯器emacs。由于正規(guī)表達(dá)式的重要而廣泛的應(yīng)用，Java語言通過包java.util.regex還對正規(guī)表達(dá)式的處理提供了直接支持。 編譯原理與技術(shù)462.4 有限自動(dòng)機(jī) 為什么引入有限自動(dòng)機(jī)確定的有限自動(dòng)機(jī)和不確定的有限自動(dòng)機(jī)都能識別正規(guī)集，即它們識別的語言正好就是正規(guī)式所能表達(dá)的語言，而且在識別語言的能力上，它們完全等價(jià)。但是，實(shí)現(xiàn)這兩類有限狀態(tài)機(jī)的效率不同，用它們構(gòu)造的詞法分析器在識別語言中單詞記號的效率方面也有顯著的差別。 正規(guī)式不確定的有限自動(dòng)機(jī)確定的有限自動(dòng)機(jī)詞法分析器編譯原理與技術(shù)472.4 有限自動(dòng)機(jī)確定的有限自動(dòng)機(jī) DFA定義

37、2.10：一個(gè)確定的有限自動(dòng)機(jī)DFA M是五元組，其中：（1）S是非空的有限的狀態(tài)集合；（2）是非空的輸入字母表；（3）T是部分單值映射S S，又稱轉(zhuǎn)移函數(shù)；T(s1, a)= s2表示輸入符號a時(shí)，把狀態(tài)s1轉(zhuǎn)換到s2，成為當(dāng)前狀態(tài)；（4）s0S，是唯一的起始狀態(tài)；（5）FS，是非空的終結(jié)狀態(tài)。被M接受或識別的語言，記做L(M)，定義為字符串的集合，其中每個(gè)ci，并且存在狀態(tài)序列s1=T(s0, c1), s2=T(s1, c2), . , sn=T(sn-1, cn)，sn F。 編譯原理與技術(shù)482.4 有限自動(dòng)機(jī)例2.10：一個(gè)有限自動(dòng)機(jī)DFA N= ，其中T的定義如下:T(A, +)

38、=BT(A, )=BT(A, )=CT(A, d)=DT(B, )=DT(B, d)=CT(C, )ET(C, d)=CT(D, d)E T(E, d)E狀態(tài)A是起始狀態(tài)，E是終結(jié)狀態(tài)。 編譯原理與技術(shù)492.4 有限自動(dòng)機(jī)轉(zhuǎn)換函數(shù)可以用狀態(tài)轉(zhuǎn)換矩陣或狀態(tài)轉(zhuǎn)換表來表示，該表的行表示狀態(tài)，列對應(yīng)輸入的符號，表元素表示狀態(tài)轉(zhuǎn)移的狀態(tài)，空白元素對應(yīng)的二元組沒有定義。 +dABBCDBDCCECDEEE例2.10有限自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換矩陣 編譯原理與技術(shù)502.4 有限自動(dòng)機(jī)一個(gè)DFA也可以表示成一個(gè)確定的狀態(tài)轉(zhuǎn)換圖，狀態(tài)轉(zhuǎn)換函數(shù)T(s1, a)=s2對應(yīng)了連接兩個(gè)結(jié)點(diǎn)s1和 s2，標(biāo)記為a的有向弧。

39、+, CEdADBdddd例2.10有限自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換圖 從狀態(tài)A到B的轉(zhuǎn)換上的標(biāo)記“+, ”表示兩條從A到B的弧的標(biāo)記+和 ，這是常用的簡化方式。 編譯原理與技術(shù)512.4 有限自動(dòng)機(jī)定義2.11：對于有限自動(dòng)機(jī)M的*中的任何一個(gè)符號串，若存在一條從起始狀態(tài)到某一終結(jié)狀態(tài)的通路，且這條通路上所有弧的標(biāo)記符連成的串等于，則稱被M識別（讀出或接受）。若起始狀態(tài)也是一個(gè)終結(jié)狀態(tài)，則空串可以為M接受。DFA M所能識別的所有字的集合稱為M識別的語言，記做L(M)。編譯原理與技術(shù)522.4 有限自動(dòng)機(jī)例如，考慮上述的有限自動(dòng)機(jī)，如果d代表任意一個(gè)數(shù)字0，1，.，9，它能否接受符號串30.、+.28和

40、813.19？對于它們，可以分別給出從狀態(tài)A到終結(jié)狀態(tài)E的路徑：因而它們都是這個(gè)DFA N可以接受的數(shù)。編譯原理與技術(shù)532.4 有限自動(dòng)機(jī)定義2.12(a)：兩個(gè)有限自動(dòng)機(jī)M1和M2是等價(jià)的，當(dāng)且僅當(dāng)它們識別相同的語言，即L(M1)=L(M2)。定義2.12(b)：兩個(gè)有限自動(dòng)機(jī)M1和M2是等價(jià)的，當(dāng)且僅當(dāng)對于每個(gè)M1接受的符號串，M2接受。編譯原理與技術(shù)542.4 有限自動(dòng)機(jī)不確定的有限自動(dòng)機(jī)NFA 定義：一個(gè)不確定的有限自動(dòng)機(jī)NFA M是五元組，其中：（1）S是非空的有限的狀態(tài)集合；（2）是非空的輸入字母表；（3）T是S() 2S（S的冪集），它可以把一個(gè)狀態(tài)映射到一組狀態(tài) ；T(s1,

41、 a)= s2表示輸入符號a時(shí)，把狀態(tài)s1轉(zhuǎn)換到s2，成為當(dāng)前狀態(tài)；（4）s0S，是唯一的起始狀態(tài)；（5）FS，是非空的終結(jié)狀態(tài)。被M接受或識別的語言，記做L(M)，定義為字符串的集合，其中每個(gè)ci，并且存在狀態(tài)序列s1=T(s0, c1), s2=T(s1, c2), . , sn=T(sn-1, cn)，sn F。編譯原理與技術(shù)552.4 有限自動(dòng)機(jī)例2.11：識別語言(a|b)nabb | n0的一個(gè)NFA M = ，ab01,2111,212334aa24a031bbbba這個(gè)NFA識別aabbabb，即存在一個(gè)狀態(tài)序列，從狀態(tài)0到狀態(tài)4，路經(jīng)上的標(biāo)記連接是aabbabb：編譯原理與技

42、術(shù)562.4 有限自動(dòng)機(jī)兩個(gè)NFA N1和N2稱為等價(jià)的，當(dāng)且僅當(dāng)它們識別同一個(gè)語言，即L(N1)=L(N2)。為什么要引入NFA？首先，需要有限自動(dòng)機(jī)的主要目的是用來識別正規(guī)式所描述語言的單詞記號，直接從正規(guī)式構(gòu)造出DFA的算法比較復(fù)雜，而從正規(guī)式構(gòu)造NFA的算法則相對簡單；然后，再從NFA構(gòu)造等價(jià)的DFA作為記號的識別分析器。其次，我們有時(shí)需要多值映射以及所謂的空轉(zhuǎn)移，即形式為N的產(chǎn)生式，以便簡潔地表達(dá)多種可能的選擇。而且，使用空轉(zhuǎn)移描述對空串的匹配，更加直觀和自然。 編譯原理與技術(shù)572.4 有限自動(dòng)機(jī)從NFA到DFA的等價(jià)變換定理2.1：對于任意一個(gè)NFA N都存在一個(gè)等價(jià)的DFA M

43、，即L(N) = L(M)。為了從NFA構(gòu)造出等價(jià)的DFA，需要消除N形式的產(chǎn)生式，即消除空轉(zhuǎn)移；確定化每個(gè)多重轉(zhuǎn)移，即拆分多值函數(shù)為單值函數(shù)。一個(gè)常用的方法是子集法。編譯原理與技術(shù)582.4 有限自動(dòng)機(jī)定義2.13：設(shè)I是NFA N=中一個(gè)狀態(tài)子集，對I的閉包運(yùn)算-closure(I)的結(jié)果是一個(gè)狀態(tài)子集，定義為-closure(I) = s | s I s | s -closure(I)并且存在T(s, )=s。直觀地說，狀態(tài)子集I的閉包就是從I中的任何一個(gè)狀態(tài)經(jīng)過任意個(gè)連線所能達(dá)到的所有狀態(tài)。 編譯原理與技術(shù)592.4 有限自動(dòng)機(jī)例2.12：下圖是接受連續(xù)a或b的語言的一個(gè)NFA，盡管在

44、每個(gè)狀態(tài)，對應(yīng)字母表上符號的轉(zhuǎn)移是唯一的，但是，由于增加了所謂的空轉(zhuǎn)移轉(zhuǎn)移，所以，它不是DFA。abE5132B6baaa4bb例如，一個(gè)子集I=B，按照定義，計(jì)算-closure(B)的序列如下： -closure(B) B B, 5 B, 5, 1 編譯原理與技術(shù)602.4 有限自動(dòng)機(jī)定義2.14：設(shè)I是NFA N=中一個(gè)狀態(tài)子集，a，對I移動(dòng)的閉包運(yùn)算Ia的結(jié)果是一個(gè)狀態(tài)子集，定義為Ia=-closure(J)，其中J = s | s I并且存在T(s, a)=s。直觀上，狀態(tài)子集Ia是從I中的任何一個(gè)狀態(tài)經(jīng)過標(biāo)記為a的一次轉(zhuǎn)移之后所能到達(dá)的所有狀態(tài)的閉包。計(jì)算Ia的兩個(gè)步驟：（1）計(jì)算

45、從I讀入符號a所達(dá)到的狀態(tài)集合J；（2）求J的閉包，即-closure(J)。 編譯原理與技術(shù)61算法2.1 從NFA到DFA的等價(jià)構(gòu)造算法輸入： NFA N=)輸出： 等價(jià)的DFA假設(shè) =a1,a2,., an（1）首先構(gòu)造DFA的狀態(tài)轉(zhuǎn)換表MATRIX：這是一個(gè)n+1列、行動(dòng)態(tài)增長的表格；第零列的每個(gè)元素對應(yīng)DFA的狀態(tài)，隨著算法的執(zhí)行，遞增地產(chǎn)生新的狀態(tài)，即增加新行；初始化：row = 1; / MATRIX的行sn = row; / DFA的狀態(tài)個(gè)數(shù)MATRIXrow, 0 = -closure(q0)；S= MATRIXrow, 0 ；/ 加入DFA狀態(tài)集合的第一個(gè)狀態(tài)，它本身是一個(gè)

46、集合do / 逐行地填表for i = 1 to n do MATRIXrow, i = Iai；/ 在每行逐列地填表 if Iai S thenS = S Iai； / 把Iai加入Ssn = sn + 1;MATRIXsn, 0 = Iai； / 狀態(tài)轉(zhuǎn)換表增加一行，即增加一個(gè)新的狀態(tài) end if;end for；row = row + 1;/ 計(jì)算下一個(gè)狀態(tài)的Iai while sn = = row / 直到?jīng)]有新的狀態(tài)為止（2）矩陣中第一行第零列所表示的狀態(tài)就是DFA的起始狀態(tài)；（3）包含了NFA終結(jié)狀態(tài)的新狀態(tài)就是DFA的終結(jié)狀態(tài)。（4）可選：重新命名DFA的狀態(tài)，相應(yīng)地改變狀態(tài)轉(zhuǎn)

47、換函數(shù)中狀態(tài)名字。編譯原理與技術(shù)622.4 有限自動(dòng)機(jī)例2.13：對例2.12表示的NFA構(gòu)造等價(jià)的DFA。 首先，把-closure(q0)=-closure(B)=B, 5, 1填入轉(zhuǎn)換矩陣表的第一行第一列。然后對每個(gè)a計(jì)算Ia并填入表中，如果Ia是新的狀態(tài)集合，則在狀態(tài)轉(zhuǎn)換矩陣表中新增一行，把它加入其中。對于a，計(jì)算Ia=-closure(B, 5, 1) =5, 1, 3，是個(gè)新的狀態(tài)集合，加入表的第二行；對于對于b，計(jì)算Ib=-closure(B, 5, 1) =5, 1, 4，也是個(gè)新的狀態(tài)集合，加入表的第三行。然后，把5, 1, 3看作I，對每個(gè)a計(jì)算Ia并填入表中。Ia= 5,

48、 1, 3, 2, 6, E是個(gè)新的狀態(tài)集合，加入表中的下一行，而Ib= 5, 1, 4已經(jīng)出現(xiàn)過，什么也不做。編譯原理與技術(shù)632.4 有限自動(dòng)機(jī)這樣繼續(xù)下去，最后得到的狀態(tài)轉(zhuǎn)換矩陣如表2.5(a)所示。IaIbB, 5, 15, 1, 35, 1, 45, 1, 35, 1, 3, 2, 6, E5, 1, 45, 1, 45, 1, 35, 1, 4, 2, 6, E5, 1, 3, 2, 6, E5, 1, 3, 2, 6, E5, 1, 4, 6, E5, 1, 4, 2, 6, E5, 1, 3, 6, E5, 1, 4, 2, 6, E5, 1, 4, 6, E5, 1, 3,

49、6, E5, 1, 4, 2, 6, E5, 1, 3, 6, E5, 1, 3, 2, 6, E5, 1, 4, 6, E編譯原理與技術(shù)642.4 有限自動(dòng)機(jī)狀態(tài)子集重新命名，并將Ia和Ib分別視為a與b后得表2.5(b)，對應(yīng)的狀態(tài)轉(zhuǎn)換圖如圖2.13所示。 ab01213221435646435ab34a01bbba256baabbaa編譯原理與技術(shù)652.4 有限自動(dòng)機(jī)例2.14：對例子2.11表示的NFA（如下圖）構(gòu)造等價(jià)的DFA。ab43 ab01bbba2baaa IaIb01, 211, 21, 21, 311, 211, 31, 21, 41, 41, 21編譯原理與技術(shù)662

50、.4 有限自動(dòng)機(jī)DFA的最小化 定理2.2：對任意一個(gè)DFA N都存在一個(gè)等價(jià)的DFA M，它包含最少的狀態(tài)數(shù)，而且這個(gè)最小狀態(tài)的DFA M是唯一的（狀態(tài)名不同的同構(gòu)情況除外）。關(guān)鍵在于把DFA的狀態(tài)劃分成一些不相交的等價(jià)子集，使得任何兩個(gè)不同子集中的狀態(tài)都可以區(qū)別，而每個(gè)子集內(nèi)的狀態(tài)都是等價(jià)的。這樣，每個(gè)子集用一個(gè)狀態(tài)代表，刪除子集中的其它狀態(tài)，就得到了狀態(tài)個(gè)數(shù)最少的DFA。 編譯原理與技術(shù)672.4 有限自動(dòng)機(jī)定義2.15：設(shè)q1和q2是DFA N中的兩個(gè)不同的狀態(tài)，如果從狀態(tài)q1出發(fā)能掃描任意串而停于終結(jié)狀態(tài)，當(dāng)且僅當(dāng)從q2出發(fā)也能掃描任意串而停于終結(jié)狀態(tài)，稱狀態(tài)q1和q2是等價(jià)的。定義

51、2.16：若兩個(gè)狀態(tài)q1和q2不是等價(jià)的，則稱這兩個(gè)狀態(tài)是可區(qū)分的。例如，例2.14中狀態(tài)1和3是可區(qū)別的，因?yàn)閺臓顟B(tài)1讀入一個(gè)b而停在終結(jié)狀態(tài)3 ，但是，從狀態(tài)3讀入一個(gè)b而沒有達(dá)到終結(jié)狀態(tài)4。又如空串把一切終結(jié)狀態(tài)與任何非終結(jié)狀態(tài)區(qū)別開。 編譯原理與技術(shù)682.4 有限自動(dòng)機(jī)DFA最小化的方法對一個(gè)DFA M=的狀態(tài)劃分，不斷地嘗試對其中的狀態(tài)子集尋找可區(qū)別的狀態(tài)，進(jìn)行分裂，直到?jīng)]有狀態(tài)子集可以分裂為止，直至每個(gè)子集內(nèi)的狀態(tài)是等價(jià)的，而每個(gè)狀態(tài)子集是可區(qū)分的。假如在某個(gè)時(shí)刻，劃分=I1,I2,.,Im，其中的任何一個(gè)都是狀態(tài)子集。對于任意一個(gè)狀態(tài)子集Ijq1,q2,.,qk，若存在一個(gè)輸入

52、符號a，對于任意兩個(gè)不等的qi和qj使得（1）T(qi ,a)=s和T(qj ,a)=t不在當(dāng)前劃分的任何一個(gè)狀態(tài)子集中，（2）或者其中T(qi ,a)和T(qj ,a)的任何一個(gè)沒有定義則可以據(jù)此把Ij一分為二：其中的一部分Ij1是從Ij的狀態(tài)讀入a之后進(jìn)入包含s狀態(tài)子集的狀態(tài)，Ij2=Ij Ij1。這樣，在劃分中用Ij1和Ij2取代Ij，就形成一個(gè)新的劃分。編譯原理與技術(shù)692.4 有限自動(dòng)機(jī)可以根據(jù)Ij中每個(gè)qi的T(qi ,a)來執(zhí)行K分裂：若T(qi ,a)落在劃分的K個(gè)不同的狀態(tài)子集中，則可以把Ij劃分成K個(gè)不相交的組，使得每組的狀態(tài)都落入的同一子集中。重復(fù)這個(gè)劃分，直到?jīng)]有可以分

53、裂的狀態(tài)子集為止，得到最終的劃分。選擇每組中的一個(gè)狀態(tài)作為代表，刪除其它一切等價(jià)的狀態(tài)，所有這些狀態(tài)代表就構(gòu)成了化簡了的DFA狀態(tài)集合。每個(gè)狀態(tài)組之間的連線轉(zhuǎn)移就是每個(gè)狀態(tài)代表之間的轉(zhuǎn)移，同時(shí)去掉不可達(dá)狀態(tài)和無用狀態(tài)。含有原來初態(tài)的等價(jià)狀態(tài)組就是化簡了的DFA的起始狀態(tài)。包含了原來終結(jié)狀態(tài)的等價(jià)狀態(tài)組就是化簡了的DFA的終結(jié)狀態(tài)。 編譯原理與技術(shù)702.4 有限自動(dòng)機(jī)算法2.2DFA最小化算法輸入： DFA N=輸出： 等價(jià)的具有最少狀態(tài)的DFA M假設(shè) =a1,a2,., an初始化： = F, SF; 標(biāo)記F和SF沒有訪問過 finished = false; 編譯原理與技術(shù)712.4 有

54、限自動(dòng)機(jī)（1）完成劃分；while not finished do if 中不存在未訪問的子集J then finished = true else 把J標(biāo)記“訪問過”；/ Ijq1,q2,.,qk distinguished = false; i = 1; while i n AND not distinguished do if J使得Jai J可區(qū)分的 then distinguished = true;把J 從 中刪除；設(shè)T(qi ,a)落在劃分的K個(gè)不同Ji1,., Jik； 把J劃分成K個(gè)不相交的組并加入到中； else i = i+1; end if; end while; en

55、d if;/ 試算中的下一個(gè)狀態(tài)子集end while;/ 直到的每個(gè)狀態(tài)子集不可劃分為止編譯原理與技術(shù)722.4 有限自動(dòng)機(jī)（2）取的每組中的一個(gè)狀態(tài)作為代表，刪除其它一切等價(jià)的狀態(tài)，所有這些狀態(tài)代表就構(gòu)成了化簡了的DFA狀態(tài)集合；（3）每個(gè)狀態(tài)組之間的連線變成每個(gè)狀態(tài)代表之間的連線，去掉不可達(dá)狀態(tài)和無用狀態(tài)；（4）含有原來初態(tài)的等價(jià)狀態(tài)組就是化簡了的DFA的起始狀態(tài)；（5）包含了原來終結(jié)狀態(tài)的等價(jià)狀態(tài)組就是化簡了的DFA的終結(jié)狀態(tài)；編譯原理與技術(shù)732.4 有限自動(dòng)機(jī)例2.15：圖2.13所示的DFA的最小化過程如下:初始劃分 = 0,1,2, 3,4,5,6，計(jì)算0,1,2a1,3，它不

56、包含在的任何一個(gè)子集當(dāng)中，所以，可以把0,1,2分解.根據(jù)T(1,a)=3，T(0,a)=T(2,a)=1，把0,1,2分解成兩個(gè)狀態(tài)子集1和0, 2。這時(shí)的 = 1, 0, 2,3,4,5,6。繼續(xù)劃分：由于0, 2b=2,5未包含在當(dāng)前劃分的任何一個(gè)子集中，所以0, 2一分為二，得到新的劃分 = 0, 1,2,3,4,5,6。由于3,4,5,6a=3,4,6，3,4,5,6b=4,5,6都包含在3,4,5,6內(nèi)，不可再劃分。至此，整個(gè)劃分結(jié)束。令狀態(tài)3代表3,4,5,6，把原來進(jìn)入狀態(tài)4、5和6的弧都導(dǎo)入3，刪除狀態(tài)4、5和6，得到最小化的DFA如圖2.15。 編譯原理與技術(shù)742.4 有

57、限自動(dòng)機(jī)例2.15ab34a01bbba256baabbaaab3b01bba2baa最小化圖2.13所示的DFA最小化的DFA編譯原理與技術(shù)752.4 有限自動(dòng)機(jī)例2.16：下圖所示的DFA的最小化過程 ab43 b01bbba2baaa32b1bb0baaaa（1）因?yàn)闋顟B(tài)僅狀態(tài)4是終結(jié)狀態(tài)，首先得劃分4和0,1,2,3。（2）只需對0,1,2,3繼續(xù)劃分：0,1,2,3在面臨字符a時(shí)，每個(gè)狀態(tài)都轉(zhuǎn)換到狀態(tài)1，無法區(qū)分；而在面臨符號b時(shí)，狀態(tài)3進(jìn)入狀態(tài)4，狀態(tài)0、1和2都轉(zhuǎn)換到0,1,2,3內(nèi)得狀態(tài)，所以，可以把0,1,2,3分解成3和0,1,2，從而得到新的劃分包括4、3和0,1,2。（

58、3）可能再分解的是0,1,2：在輸入b時(shí)，T(0, b)2，T(1, b)=3, T(2, b)=2，據(jù)此可以把0,1,2分解成1和0, 2（4）繼續(xù)嘗試分解0, 2：這時(shí)的0, 2a1，0, 2b2，無法區(qū)分，劃分完畢。（5）最小化的狀態(tài)包括0, 2、1、3和4，重新命名、整理后得到右上圖。編譯原理與技術(shù)762.4 有限自動(dòng)機(jī)從正規(guī)式到有限自動(dòng)機(jī) 基于轉(zhuǎn)換規(guī)則的算法，利用轉(zhuǎn)移把單個(gè)的正規(guī)式粘接起來，形成更復(fù)雜的 、識別正規(guī)式表示語言的NFA。 定理2.3：(1) 對字母表上的任何一個(gè)正規(guī)表達(dá)式e都存在一個(gè)接受L(e)的有限自動(dòng)機(jī)M，即L(e)L(M)。(2) 對字母表上的任何一個(gè)有限自動(dòng)機(jī)M

59、都存在一個(gè)接受L(M)正規(guī)表達(dá)式e，即L(M)L(e) 。編譯原理與技術(shù)772.4 有限自動(dòng)機(jī)（1）對應(yīng)于基本正規(guī)式a、的NFAa對應(yīng)于基本正規(guī)式a的NFA是對應(yīng)于基本正規(guī)式的NFA是對應(yīng)于基本正規(guī)式的NFA是編譯原理與技術(shù)782.4 有限自動(dòng)機(jī)（2）選擇替換規(guī)則：e1|e2表示成e2e1構(gòu)造的有限自動(dòng)機(jī)新增加了兩個(gè)狀態(tài)，分別表示開始狀態(tài)和終結(jié)狀態(tài)，然后把新增的起始狀態(tài)與N(e1)和N(e2)的起始狀態(tài)用轉(zhuǎn)移連接起來，把N(e1)和N(e2)的終結(jié)狀態(tài)與新增的終結(jié)狀態(tài)用轉(zhuǎn)移連接來，并且更改N(e1)和N(e2)起始狀態(tài)和終結(jié)狀態(tài)的性質(zhì)。N(e1)接受的任何串s，等價(jià)于s，而它可以被N(e1|e

60、2)接受，即L(e1)L(e1|e2)。同樣，L(e2)L(e1|e2)。反之，所有從N(e1|e2)的開始狀態(tài)，經(jīng)過N(e1)部分到達(dá)終結(jié)狀態(tài)，所接受的語言是 L(e1) L(e1)，或者經(jīng)過N(e2)部分到達(dá)終結(jié)狀態(tài)，所接受的語言是 L(e2) L(e2)，即L(e1|e2) L(e1) L(e2)。所以L(e1|e2) L(e1) L(e2)。 編譯原理與技術(shù)792.4 有限自動(dòng)機(jī)（3）連接替換規(guī)則：e1e2表示成e2e1e1和e2連接成e1e2時(shí)，把N(e1)的終結(jié)狀態(tài)改為非終結(jié)狀態(tài)，然后通過轉(zhuǎn)移與N(e2)的起始狀態(tài)連接起來，N(e1)的起始狀態(tài)成為N(e1e2)的起始狀態(tài)，N(e2