第三章-詞法分析

1、概述v 本章引入詞法分析器（掃描器）的構(gòu)造原理和實(shí)現(xiàn)技術(shù)v 掃描器的任務(wù)2022-6-201v 討論掃描器的設(shè)計(jì)需求和實(shí)現(xiàn)機(jī)制v 介紹單詞的內(nèi)部表示，引入單詞的描述工具正規(guī)式v 描述識別單詞的轉(zhuǎn)換圖和有限自動(dòng)機(jī)的概念和應(yīng)用v 先討論掃描器的手工構(gòu)造，然后引入自動(dòng)構(gòu)造原理2022-6-202Contents詞法分析器的手工構(gòu)造1正規(guī)表達(dá)式2有限自動(dòng)機(jī)3詞法分析器的自動(dòng)生成4編譯階段詞法分析2022-6-203編譯階段詞法分析v將源程序分解為單詞符號串2022-6-205詞法分析器v詞法分析的任務(wù) 自左至右逐個(gè)字符地對源程序進(jìn)行掃描，產(chǎn)生一個(gè)個(gè)的單詞符號，把作為字符串的源程序改造成為單詞符號串的中

2、間程序。v詞法分析器的構(gòu)造 手工構(gòu)造 自動(dòng)生成Lex：詞法規(guī)則（正規(guī)式）有限自動(dòng)機(jī)2022-6-2063.1 對詞法分析器的要求功能v詞法分析器的功能 功能從數(shù)據(jù)輸入到輸出的一個(gè)變換過程或函數(shù)說明該過程（或函數(shù)）需要做什么，而非如何做 掃描器的輸入是代表源程序的字符串 輸出是單詞符號（token）的內(nèi)部中間表示 過程是掃描輸入的字符流，按詞法規(guī)則識別出單詞2022-6-207對詞法分析器的要求輸出形式v單詞符號的種類 關(guān)鍵字由語言定義、具有固定含義的標(biāo)識符如，main, if, while, for 等通常不作為程序員自定義的名字使用（保留字，基本字） 標(biāo)識符用于表示各種名字如，變量名、數(shù)組名

3、、類名，函數(shù)名和過程名等 常數(shù)具有某種數(shù)據(jù)類型的不變量常見的類型有整型、實(shí)型、布爾型、文字型等如，100、3.14159、TRUE 、 example 運(yùn)算符，用于表示操作如，+、-、*、/ 等 界符，用于區(qū)分各種不同的語法單位如，“,”、“;”、“(”、“)”、“/*”、“*/” 等對詞法分析器的要求輸出形式v單詞符號的輸出形式 二元式 （單詞種別，單詞符號的屬性值）單詞種別：通常用整數(shù)編碼表示，不能唯一確定單詞時(shí)，需用屬性值：通常是指向符號表的指針（入口地址） 實(shí)現(xiàn)上，如何劃分單詞種別和編碼純屬技術(shù)性考慮如關(guān)鍵字、運(yùn)算符和界符通常作為一符一種處理關(guān)鍵字、運(yùn)算符和界符由語言定義，個(gè)數(shù)是固定的

4、種別的整數(shù)編碼可唯一確定該單詞，無須屬性值標(biāo)識符常作為一種來處理，常數(shù)則可按類型分種需用屬性值來區(qū)分不同單詞的特征這些特征信息存放于相關(guān)的符號表項(xiàng)或常數(shù)表項(xiàng)中單詞種別：用整數(shù)編碼2022-6-208詞法分析器的輸出示例2022-6-209v例，C+代碼段：while (i = j) i-; 將被轉(zhuǎn)換為 while, (, id, =, =, id, ) , id, -, ; , 2022-6-2010詞法分析器的組織v將詞法分析器作為一個(gè)獨(dú)立階段 任務(wù)相對獨(dú)立、簡單，有高效的工具進(jìn)行處理 與編譯過程的其它工作分開造就良設(shè)計(jì)的軟件架構(gòu)結(jié)構(gòu)簡潔、清晰、條理化v是否將詞法分析器作為獨(dú)立的一遍？ 沒有

5、必要，而且低效v與語法分析器通信的其他方式 最常用的：作為一個(gè)子程序，由語法分析器在需要單詞符號時(shí)調(diào)用 詞法分析器和語法分析器作為兩個(gè)并發(fā)的過程通過pipe通信詞法分析器的組織示例v作為獨(dú)立階段（一遍）v作為獨(dú)立的子程序3.2 詞法分析器的設(shè)計(jì)問題v語言對程序格式的要求 自由格式大部分語言不規(guī)定某個(gè)單詞必須出現(xiàn)在程序行中的什么位置 固定格式如早期的FORTRAN語言規(guī)定輸入行的前6個(gè)字符是標(biāo)號，最后的字符（7280列）是注釋，以C開頭的是注釋行，等等 空白（空格和tab）大多數(shù)PL，空白是有意義的FORTRAN和Algol60，空白可以加在任何地方提高可讀性2022-6-2012詞法分析器的設(shè)

6、計(jì)問題v緩沖區(qū) 是編譯器中唯一需要處理每個(gè)字符的階段 設(shè)計(jì)不合理會成為最費(fèi)時(shí)和低效的階段 不能從輸入文件中逐個(gè)字符讀入，一次讀入大塊文本放入一個(gè)緩沖區(qū)，由緩沖區(qū)給詞法分析器提供字符 詞法分析器需要向前掃描時(shí)，緩沖區(qū)也有用處v關(guān)鍵字 保留字：用戶不能使用關(guān)鍵字作為標(biāo)識符 PL/l 的關(guān)鍵字不是保留字，詞法分析器要區(qū)分2022-6-2013詞法分析器的設(shè)計(jì)錯(cuò)誤處理v詞法分析中遇到了錯(cuò)誤怎么處理？ 應(yīng)急式（panic）跳過字符，直到發(fā)現(xiàn)一個(gè)結(jié)構(gòu)良好的單詞符號 替換替換一個(gè)不正確的字符 刪除刪除一個(gè)不正確的字符 插入插入一個(gè)缺失的字符 調(diào)換調(diào)換兩個(gè)字符的位置2022-6-20143.2.1 輸入、預(yù)處

7、理v輸入緩沖區(qū) 為了提高效率，掃描器并非直接逐個(gè)字符地讀源文件每次從源文件中讀出一定長度的字符串將輸入的字符串放入一個(gè)輸入緩沖區(qū)中v預(yù)處理 對多數(shù)PL，用于正文編輯的字符一般沒有實(shí)際意義如，空格、跳格、回車和換行符只是在文字常數(shù)中有意義注解的出現(xiàn)對程序的功能也無任何意義為了方便識別工作，編輯性字符和注解應(yīng)事先刪除 有些PL將一個(gè)或相繼多個(gè)空格用作單詞之間的界符此時(shí)應(yīng)事先將相繼多個(gè)空格合并為一個(gè)空格 預(yù)處理即在識別開始前，刪去輸入緩沖區(qū)中的無用字符2022-6-2015輸入、預(yù)處理v預(yù)處理子程序 可設(shè)計(jì)一個(gè)由掃描器調(diào)用的子程序當(dāng)調(diào)用時(shí)，處理出長度為 N 的字符串，并裝入掃描緩沖區(qū)使識別工作可在此

8、緩沖區(qū)上直接進(jìn)行v掃描緩沖區(qū)的結(jié)構(gòu) 通常采用一個(gè)長度為 2N 的雙半?yún)^(qū)（雙緩沖區(qū)）設(shè)計(jì)掃描器需維護(hù)兩個(gè)指示器一個(gè)指向正在掃描單詞的首字符，一個(gè)向前搜索其終點(diǎn)若單詞被半?yún)^(qū)邊界截?cái)?，則再裝入N個(gè)字符到另半?yún)^(qū)單詞的長度 N，故語言通常限制標(biāo)識符和常數(shù)的長度2022-6-2016掃描緩沖區(qū)的結(jié)構(gòu)2022-6-2017詞法分析器的結(jié)構(gòu)2022-6-2018預(yù)處理子程序掃描緩沖區(qū)掃描器輸入緩沖區(qū)輸入列表單詞符號2022-6-2019 3.2.2 單詞符號的識別：超前搜索v識別單詞通常需要超前搜索 為了識別當(dāng)前單詞，需要掃描后繼的若干個(gè)字符v關(guān)鍵字的識別 如FORTRAN，關(guān)鍵字和用戶字無區(qū)別；單詞之間無界

9、符1 DO99K = 1, 10 循環(huán)語句：DO 關(guān)鍵字 99 結(jié)束行標(biāo)號3 DO99K = 1. 10 賦值語句： DO99K 為用戶定義的變量名必須超前搜索至第一個(gè)界符,或.才能確定單詞的種別單詞符號的識別：超前搜索v標(biāo)識符的識別 一般為字母開頭的字母/數(shù)字序列，讀到其它符號時(shí)可識別v常數(shù)的識別 各種類型的常數(shù)一般容易識別，但有些語言需超前搜索如FORTRAN，5 .EQ. M 和 5.E08的前綴相同v算符和界符的識別 有些語言需要超前搜索如C+，Java中，+，+=，-，=等2022-6-20202022-6-20213.2.3 狀態(tài)轉(zhuǎn)換圖v如何利用轉(zhuǎn)換圖手工（非形式）實(shí)現(xiàn)掃描器 轉(zhuǎn)換

10、圖的作用：詞法規(guī)則 轉(zhuǎn)換圖 掃描器詞法規(guī)則的一種圖形描述工具描述掃描器動(dòng)作 如，標(biāo)識符可非形式地描述為字母開頭的字母/數(shù)字序列其轉(zhuǎn)換圖為 （其中0表示初始狀態(tài)，雙圈表示終止?fàn)顟B(tài)）01字母2其它字母或數(shù)字*狀態(tài)轉(zhuǎn)換圖v轉(zhuǎn)換圖是一張有限方向圖 結(jié)點(diǎn)：狀態(tài) 箭弧 標(biāo)記：射出結(jié)點(diǎn)狀態(tài)下可能出現(xiàn)的輸入字符或字符類 初態(tài)和終態(tài)2022-6-202201字母2其它字母或數(shù)字*轉(zhuǎn)換狀態(tài)初態(tài)終態(tài)輸入字符狀態(tài)轉(zhuǎn)換圖v 掃描器可利用轉(zhuǎn)換圖識別（接受）一定的字符串（單詞） 狀態(tài) S0 對應(yīng)于單詞識別的開始位置 在 Si，若存在有向邊 (Si，Sj), 其上標(biāo)記與輸入字符匹配則狀態(tài)轉(zhuǎn)換到 Sj，并將搜索指示器+1，否則

11、失敗 在終止?fàn)顟B(tài)，表示識別出一個(gè)單詞 在終止?fàn)顟B(tài), 若多讀了一個(gè)字符，應(yīng)退給輸入串，標(biāo)記為*2022-6-2023狀態(tài)轉(zhuǎn)換圖示例2022-6-20242022-6-2025狀態(tài)轉(zhuǎn)換圖作用v一個(gè)狀態(tài)轉(zhuǎn)換圖可以用于識別（或接受）一定的字符串v大多數(shù)程序設(shè)計(jì)語言的單詞符號都可以用轉(zhuǎn)換圖予以識別v狀態(tài)轉(zhuǎn)換圖是設(shè)計(jì)詞法分析器的有效工具 給出識別單詞符號的狀態(tài)轉(zhuǎn)換圖 實(shí)現(xiàn)狀態(tài)轉(zhuǎn)換圖 每個(gè)狀態(tài)結(jié)點(diǎn)對應(yīng)一段程序 不含回路的分叉結(jié)點(diǎn)對應(yīng)switch或if-else語句 含回路的狀態(tài)結(jié)點(diǎn)對應(yīng)while和if構(gòu)成的程序段狀態(tài)轉(zhuǎn)換圖實(shí)現(xiàn)示例2022-6-2026狀態(tài)轉(zhuǎn)換圖實(shí)現(xiàn)代碼 1狀態(tài)轉(zhuǎn)換圖實(shí)現(xiàn)代碼 2狀態(tài)轉(zhuǎn)換圖實(shí)

12、現(xiàn)代碼 3狀態(tài)轉(zhuǎn)換圖綜合應(yīng)用v 構(gòu)造識別一個(gè)簡單語言所有單詞符號的轉(zhuǎn)換圖2022-6-2030狀態(tài)轉(zhuǎn)換圖綜合應(yīng)用v 詞法處理約定1. 除標(biāo)識符，常數(shù)外，均為一符一種2. 關(guān)鍵字均為保留字，不可用作用戶字3. 設(shè)保留字表，識別出標(biāo)識符時(shí)，查表確定是否為關(guān)鍵字4. 相鄰單詞之間至少存在一個(gè)界符、算符或空格按此約定，無須使用超前搜索，也無須設(shè)關(guān)鍵字轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖綜合應(yīng)用v設(shè)計(jì)思想狀態(tài)轉(zhuǎn)換圖綜合應(yīng)用狀態(tài)轉(zhuǎn)換圖綜合應(yīng)用v 變量與過程1. ch， 字符變量，存放最新讀入的字符2. strToken，字符數(shù)組，存放組成單詞的字符串3. GetChar(), 讀入當(dāng)前字符，搜索指示器指向下一輸入字符4. G

13、etBC(), 若 ch = , 則反復(fù)調(diào)用GetChar()直至ch 5. Concat(), strToken := strToken | ch6. isletter/isDigit, 若 ch = letter/digit, 則返回 true, 否 false7. int Reserve(), 若strToken = 保留字, 則返回編碼，否 08. Retract(),搜索指示器回調(diào)一個(gè)字符，ch := 9. int InsertId(), 將strToken插入符號表，返回符號表指針10.int InsertConst(),將strToken插入常數(shù)表，返回常數(shù)表指針Nextv手工構(gòu)

14、造詞法分析器 非形式的詞法規(guī)則轉(zhuǎn)換圖掃描器v接下來討論如何形式化上述過程 其目的在于能夠自動(dòng)化（機(jī)械化）該過程，即詞法的形式規(guī)則 形式狀態(tài)轉(zhuǎn)換圖 掃描器 其中：描述詞法的形式規(guī)則是 正規(guī)式 正規(guī)文法 描述轉(zhuǎn)換圖的形式工具是 有限自動(dòng)機(jī) 形式化也使得可以用數(shù)學(xué)方法保證結(jié)果的正確性自動(dòng)自動(dòng)2022-6-20363.3 正規(guī)表達(dá)式與有限自動(dòng)機(jī)正規(guī)式與正規(guī)集1DFA和NFA2正規(guī)文法3等價(jià)性證明43.3.1 正規(guī)式與正規(guī)集v 正規(guī)集已知任何形式語言均為*的一個(gè)子集程序語言的單詞一般均屬于*的一個(gè)特殊子集 正規(guī)集已知正規(guī)集上的字符串（字）可以使用正規(guī)文法描述正規(guī)式是一種比文法更為簡單、高效的方法2022

15、-6-20372022-6-2038正規(guī)式與正規(guī)集定義v設(shè)字母表，正規(guī)式與其所表示的正規(guī)集可遞歸定義為1.和都是上的正規(guī)式，它們所表示的正規(guī)集分別為和;2.任何a，a都是上的一個(gè)正規(guī)式，它所表示的正規(guī)集為a；3.假定U和V都是上的正規(guī)式，它們所表示的正規(guī)集分別記為L(U)和L(V)，那么(U|V)、(UV)和(U)*也都是正規(guī)式，它們所表示的正規(guī)集分別是L(U)L(V)、 L(U)L(V)（連接積）和(L(U)*（閉包）。僅由有限次使用上述三個(gè)步驟而得到的表達(dá)式才是上的正規(guī)式僅由這些正規(guī)式所表示的字集才是上的正規(guī)集v正規(guī)式運(yùn)算符（優(yōu)先級從高到低）* （閉包） （連接） |（或）正規(guī)式與正規(guī)集例

16、v例 設(shè)字母表=a，b，部分上的正規(guī)式和正規(guī)集如下：正規(guī)式正規(guī)集aaa|ba，bab ab(a|b)(a|b)aa，ab，ba，bba*，a，aa， 任意個(gè)a的串ba*b(a)* = b, ba, baa,a(a|b)*a(a, b)* = a*, 上所有以a開頭的字(a|b)*(aa|bb)(a|b)* *aa, bb*, 上所有包含aa或bb的字2022-6-2039正規(guī)式與正規(guī)集例v 例 令 = A, B, 0, 1(A|B)(A|B|0|1)* 上標(biāo)識符的全體(0|1)(0|1)*上數(shù)的全體v 例 令r = letter( letter|digit )*，則其正規(guī)式表示的語言 L(r)

17、 = L(letter) ( L(letter)L(digit) )* =A，Z，a，z(A，Z，a，z，0，9)*v 例 令L(x)=a，b,L(y)=c，d且r1=x|y，r2=y|x，則L(r1)=a，b，c，dL(r2)=a，b，c，dL(r1)= L(r2)正規(guī)式與正規(guī)集等價(jià)性v 正規(guī)式的等價(jià)性若兩個(gè)正規(guī)式所表示的正規(guī)集相同，則認(rèn)為兩者等價(jià)兩個(gè)等價(jià)的正規(guī)式 u 和 v 記為 u = v如，b(ab)* = (ba)*b, (a|b)* = (a*b*)*v 等價(jià)性證明若要證明 u = v，1. 須證明L(u) = L(v)集合相等證明方法2. 使用正規(guī)式的代數(shù)性質(zhì)2022-6-204

18、12022-6-2042正規(guī)式與正規(guī)集正規(guī)式的代數(shù)性質(zhì)連接對 | 是可分配的 是連接的恒等元素性性 質(zhì)質(zhì)描描 述述A|B=B|A| 是可交換的A|(B|C)=(A|B)|C| 是可結(jié)合的A(BC)=(AB)C連接是可結(jié)合的A(B|C)=AB|AC(A|B)C=AC|BC連接對 | 是可分配的 A = AA = A 是連接的恒等元素 A* = (A | )*和之間的關(guān)系A(chǔ)*=A*冪的等價(jià)性正規(guī)式與正規(guī)集等價(jià)性證明v例，證明 b(ab)* = (ba)*b b(ab)*= b(ab)0 | (ab)1 | (ab)2 | )= b | b(ab)1 | b(ab)2 | /分配律= b | (ba

19、)1b | (ba)2b | /結(jié)合律= ( | (ba)1 | (ba)2 | ) b/分配律= (ba)*b2022-6-2043v例，證明 (A*)* = A*, 其中A為任意正規(guī) 需證明 L(A*)*) = L(A*) /注： L(A*)*) = (L(A*)* 首先證明 L(A*)*) L(A*) 顯然有 L(A*)*) = L(A*)0 L(A*)1 L(A*)2 L(A*) 其次證明 L(A*)*) L(A*)設(shè) x L(A*)*) = (L(A*)*若 x = , 則 x L(A*)若 x , 則 x (L(A*)k令 x = x1x2xk 有 xi L(A*) = (L(A)

20、*于是有 xi (L(A)mi （mi 0, i =1, 2, k)則 x = x1x2xk (L(A)m1 (L(A)m2 (L(A)mk = (L(A) m1+ m2 + + mk令 m = m1 + m2 + mk , 有 x (L(A)m (L(A)* 故有 L(A*)*) L(A*)2022-6-2045 3.3.2 確定有限自動(dòng)機(jī)（DFA）v一個(gè)DFA M是一個(gè)五元式M = (S, ,s0,F)，其中1.S = S0, S1, , Sn為有限集，Si S 為狀態(tài)2. 為有限字母表， a 為輸入字符3.: S S 的單值（部分）映射（狀態(tài)轉(zhuǎn)換函數(shù)） (s, a) = s 意為：現(xiàn)行狀

21、態(tài)為 s，輸入字符為 a，則轉(zhuǎn)換到后繼狀態(tài)s 從轉(zhuǎn)換圖來看，相當(dāng)于4.S0 S 為唯一的初態(tài)5.F S 為終態(tài)集（可空）ssa2022-6-2046確定有限自動(dòng)機(jī)DFA的表示v五元式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)=32022-6-2047確定有限自動(dòng)機(jī)DFA的表示v 狀態(tài)轉(zhuǎn)換矩陣 行：狀態(tài) 列：輸入字符 矩陣元素：(s,a)的值01a3b2aaa,bbbv 狀態(tài)轉(zhuǎn)換圖DFA的表示DFA M = (0, 1, 2, 3, a, b, , 0, 3) 映射狀態(tài)矩陣 狀態(tài)轉(zhuǎn)

22、換圖2022-6-20482022-6-2049確定有限自動(dòng)機(jī)DFA M識別的字v對于*上的任何字，若存在一條從初態(tài)結(jié)點(diǎn)到某一終態(tài)結(jié)點(diǎn)的通路，且這條通路上所有弧的標(biāo)記符連接成的字等于，則稱可為DFA M所識別（讀出或接受）。v若M的初態(tài)結(jié)點(diǎn)同時(shí)又是終態(tài)結(jié)點(diǎn)，則空字可為M所識別。vDFA M所識別的字的全體記為L(M)。DFA示例v是DFA嗎？接受什么樣的字符串？2022-6-2050v是DFA嗎？接受什么樣的字符串？DFA示例v自然數(shù)v帶符號的自然數(shù)DFA示例v帶符號的實(shí)數(shù)v浮點(diǎn)數(shù)DFA示例vC語言注釋非確定性vDFA的確定性 映射:SS是單值函數(shù) 任何狀態(tài)sS和輸入符號a, (s,a)唯一地

23、確定了下一個(gè)狀態(tài)。v例，構(gòu)造識別:=, =, =的DFA 構(gòu)造識別三個(gè)運(yùn)算符的DFA 只能用唯一的初始狀態(tài)將它們連接在一起2022-6-2054非確定性2022-6-2055非確定性v如果有兩個(gè)字符串以相同字符開始呢？ 下面的轉(zhuǎn)換圖是DFA嗎？2022-6-2056非確定性v可以用增加新狀態(tài)的方法解決相同符號的沖突 這個(gè)是DFA嗎？與上圖比較有什么優(yōu)劣？2022-6-20572022-6-20583.3.3 非確定有限自動(dòng)機(jī)（NFA）v非確定的有限自動(dòng)機(jī)（NFA） 允許是一個(gè)多值函數(shù) 允許有標(biāo)記的轉(zhuǎn)換：表示沒有輸入字符直接轉(zhuǎn)換狀態(tài)2022-6-2059NFA定義v一個(gè)NFA M是一個(gè)五元式M

24、= (S,S0,F)，其中 S是一個(gè)有限狀態(tài)集 是一個(gè)有窮字母表，是輸入字符集合 是一個(gè)從S*到S的子集的映射，即:S*2S S0 S，是非空初態(tài)集 F S，是一個(gè)終態(tài)集（可空）NFA示例v : S * 2S的含義 其含義為 (s, ) = s | s S 注意： * (* = +a * 與 a 不加區(qū)分，有 | a | = 12S為S的冪集，即由S的所有子集構(gòu)成的集合如，S = 0, 1, 2S = , 0, 1, 0, 1 例，NFA M = (0, 1, 2, a, b, , 0, 1, 2)2022-6-20602022-6-2061NFA和狀態(tài)轉(zhuǎn)換圖v 含有m個(gè)狀態(tài)和n個(gè)輸入字符的N

25、FA可以表示為如下的狀態(tài)轉(zhuǎn)換圖： 該圖有m個(gè)狀態(tài)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)可以射出若干條箭弧與別的結(jié)點(diǎn)相接，每條弧用*中的一個(gè)字作標(biāo)記（輸入字，可以是），整張圖至少含有一個(gè)初態(tài)結(jié)點(diǎn)以及若干個(gè)終態(tài)結(jié)點(diǎn)。aabbb3210NFA示例2022-6-20622022-6-2063NFA識別的字v對于*中的任何一個(gè)字，若存在一條從某一初態(tài)結(jié)點(diǎn)到某一終態(tài)結(jié)點(diǎn)的通路，且這條通路上所有弧的標(biāo)記字依序連接成的字等于，則稱可為NFA M所識別（讀出或接受）。v若M的某些初態(tài)結(jié)點(diǎn)同時(shí)又是終態(tài)結(jié)點(diǎn)，或者存在一條從某個(gè)初態(tài)結(jié)點(diǎn)到某個(gè)終態(tài)結(jié)點(diǎn)的通路，則空字可為M所接受。DFA和NFA的編程實(shí)現(xiàn)v方法一：硬編碼 類似于轉(zhuǎn)換圖的實(shí)現(xiàn) 可

26、以用固定代碼模式2022-6-2064DFA和NFA的實(shí)現(xiàn)v方法二：狀態(tài)轉(zhuǎn)換表驅(qū)動(dòng)的實(shí)現(xiàn) 將狀態(tài)轉(zhuǎn)移用表的方式表示，如下3表示該狀態(tài)不讀取輸入字符空白表示錯(cuò)誤狀態(tài)接受狀態(tài)用標(biāo)記2022-6-2065DFA和NFA的實(shí)現(xiàn)v給定如上的轉(zhuǎn)換表，對任意DFA我們可以編寫下面的程序進(jìn)行詞法分析2022-6-2066DFA和NFA的實(shí)現(xiàn)例C注釋2022-6-2067DFA和NFA的實(shí)現(xiàn)例C注釋DFA和NFA的實(shí)現(xiàn)例C注釋DFA和NFA的實(shí)現(xiàn)例C注釋DFA和NFA的實(shí)現(xiàn)例C注釋正規(guī)式NFADFA詞法分析器v我們的思路1. 用正規(guī)式（RE）描述詞法規(guī)則2. 將正規(guī)式轉(zhuǎn)換為NFA3. 將NFA轉(zhuǎn)換為DFA4.

27、根據(jù)DFA構(gòu)造詞法分析程序v要考慮的問題這些表示方式是否等價(jià)？這一系列轉(zhuǎn)換是否能夠自動(dòng)進(jìn)行（有算法）？v下一步：等價(jià)性證明和構(gòu)造（轉(zhuǎn)換）算法正規(guī)式轉(zhuǎn)換為NFAv每條有向邊上標(biāo)記為或單個(gè)字符2022-6-2073NFA轉(zhuǎn)換為正規(guī)式2022-6-2074NFA和正規(guī)式的等價(jià)性v上述方法說明NFA和正規(guī)式是等價(jià)的 每個(gè)NFA M所識別的字的全體 L(M) 是上的正規(guī)集 每個(gè)上的正規(guī)集L(R)均可被一個(gè)NFA M所識別 L(M) = L(R), 稱為兩者是等價(jià)的 原則上，若程序語言的詞法用正規(guī)式描述，則可自動(dòng)構(gòu)造一個(gè)NFA M來識別該語言的單詞 NFA的非確定性使之不容易用于實(shí)現(xiàn)詞法分析器 若能消除N

28、FA的非確定性，將其轉(zhuǎn)換為DFA，則容易實(shí)現(xiàn)2022-6-2075NFA和DFA的等價(jià)性v有限自動(dòng)機(jī)的等價(jià)性 FA M，F(xiàn)A M，若L(M) = L(M)，則稱兩者是等價(jià)的 DFA與NFA的等價(jià)性是自動(dòng)機(jī)理論的一個(gè)重要定理vDFA和NFA是等價(jià)的1.DFA是NFA的特例即：DFA M，NFA M，使L(M) = L(M)DFA : S SNFA : S * 2S2.需證明，NFA M存在一個(gè)DFA M使 L(M)=L(M)2022-6-2076* , 2S SNFA轉(zhuǎn)換為DFAvNFA M，DFA M，使L(M) = L(M) 設(shè) NFA M = (S, , , S0, F) 將 NFA M

29、改造為 NFA M引入唯一的新初態(tài)結(jié)點(diǎn)X和新終態(tài)結(jié)點(diǎn)YX 到 S0 中所有結(jié)點(diǎn)均用 邊 連接 F 中所有結(jié)點(diǎn)到 Y 也均用 邊 連接反復(fù)使用圖示的替換直至每條有向邊上標(biāo)記為 或單個(gè)字符 顯然，L(M) = L(M)2022-6-2077NFA轉(zhuǎn)換為DFAv基本思想是采用一種“子集構(gòu)造” 算法來確定化 構(gòu)造一個(gè)DFA M，使其每個(gè)狀態(tài)對應(yīng)于NFA M的狀態(tài)集 使得在DFA讀入a1a2an時(shí)，所處的狀態(tài)對應(yīng)于NFA所能到達(dá)的狀態(tài)集如NFA讀入a1a2an到達(dá)狀態(tài) 中的任意一個(gè)，則DFA到達(dá)狀態(tài)集2,3,4，即狀態(tài) 觀察NFA M：可能有 邊，也可能有相同標(biāo)記的邊要構(gòu)造DFA M，必須合并這兩種邊到

30、達(dá)的狀態(tài)2022-6-2078NFA轉(zhuǎn)換為DFAv 子集構(gòu)造方法設(shè) I S，定義 _closure ( I )1. q I, q _closure ( I )2. q I, 從 q 出發(fā)經(jīng)任意條 邊可達(dá)的 q _closure ( I ) 即 _closure ( I ) = I q | q I 旨在合并與狀態(tài)集 I 相關(guān)的 邊可達(dá)狀態(tài)設(shè) I S，a , 定義 Ia = _closure ( J ) q I，從 q 出發(fā)經(jīng) a 邊可達(dá)的q J2022-6-2079NFA轉(zhuǎn)換為DFAv 確定化方法1. 假定 = a1,a2,ak, 我們構(gòu)造一張表S，S有k+1列，依次標(biāo)記為I,Ia1,Ia2,I

31、ak2. 置該表的首行首列為_closure ( X ), X為NFA M 的初態(tài)3. 如果確定了第m（m1,2,）行中第一列的I，則計(jì)算Iax （x1,2,k），并填入m行中對應(yīng)的列即Sm， Iax中4. 檢查m行上的每個(gè)狀態(tài)子集Iax （x1,2,k），如果Iax ，并且它還沒有在表S的第一列中出現(xiàn)，則將其填入到空行的第一列5.重復(fù)3、4，直至所有Iax （x1,2,k）都在第一列上出現(xiàn)該過程一定在有限步內(nèi)終止，因?yàn)镸的子集數(shù) = 2|S| 2022-6-2080NFA轉(zhuǎn)換為DFAv 確定化方法（示例）假設(shè) = a, b, 則定義一張表 S(I, Ia, Ib) 其中，第i行的表元素分別為

32、Si, I, Si, Ia, Si, Ib1. 置S1, I = _closure ( X ), X為NFA M 的初態(tài)2. 若Si, I , 則計(jì)算 Ia, Ib，填入 Si, Ia, Si, Ib3. 檢查第i行的元素，若 Si, Ia 或 Si, Ib 還沒有在第一列出現(xiàn)過 則 將Si, Ia 或 Si, Ib 填入 Sk+, I, （k表示第一個(gè)空行）；i+；返回步驟2否則算法終止2022-6-2081v 例 (a|b)*(aa|bb)(a|b)*2022-6-2082ISIaaIbbX, 5, 105, 3, 11 5, 4, 125, 3, 115, 3, 1, 2, 6, Y3

33、5, 4, 125, 4, 125, 3, 11 5, 4, 1, 2, 6, Y55, 3, 1, 2, 6, Y35, 3, 1, 2, 6, Y3 5, 4, 1, 6, Y45, 4, 1, 6, Y45, 3, 1, 6, Y6 5, 4, 1, 2, 6, Y55, 4, 1, 2, 6, Y55, 3, 1, 6, Y6 5, 4, 1, 2, 6, Y55, 3, 1, 6, Y65, 3, 1, 2, 6, Y3 5, 4, 1, 6, Y4v構(gòu)造 DFA M 所構(gòu)造的S表指定了DFA M的狀態(tài)轉(zhuǎn)換矩陣S表中的每個(gè)狀態(tài)子集為DFA M的一個(gè)狀態(tài)S表中的首行首列為初態(tài)S表中含有

34、終態(tài)的狀態(tài)子集為DFA M的終態(tài)2022-6-20843.3.5 正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性v 證明一FA M，正規(guī)式 r，使得 L(r) = L(M)正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性v證明二正規(guī)式 r, FA M，使得 L(M) = L(r) 用關(guān)于正規(guī)式 r中運(yùn)算符個(gè)數(shù)歸納證明1. 歸納基礎(chǔ)：r中運(yùn)算符數(shù)目為0即 r = 或 r = 或 r = a (a )，則顯然，三個(gè)NFA分別接受的正規(guī)集為, 和a2. 歸納假設(shè)：設(shè)r,如果r中的運(yùn)算符數(shù)目為k，則存在一個(gè)FA M，使得 L(M)=L(r)3. 當(dāng)r中有k+1個(gè)運(yùn)算符時(shí)，r有三種可能：r = r1| r2, r = r1 r2 或 r = r

35、1*； r1和r2 中的運(yùn)算符數(shù)目=k. 根據(jù)歸納假設(shè)，對r1和r2存在FAM1和M2使得 L(M1)=L(r1)L(M2)=L(r2)2022-6-2085則對于r = r1| r2, 構(gòu)造 M 為其中，為M引入新的初態(tài)結(jié)點(diǎn)q0和終態(tài)結(jié)點(diǎn)f0，并從q0引出轉(zhuǎn)換至q1和q2，從 f1和 f2引出轉(zhuǎn)換至f0顯然，有L(M) = L(M1) L(M2) = L(r1) L(r2) = L(r)對于r = r1 r2, 構(gòu)造 M 為其中， q1為新的初態(tài)， f2為終態(tài)，并從f1引出轉(zhuǎn)換至q2顯然，有L(M) = L(M1) L(M2) = L(r1) L(r2) = L(r)對于r = r1*, 構(gòu)

36、造 M 為顯然，有L(M) = L(M1)* = L(r1)* = L(r)2022-6-2086正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性v 基本思想（Thompson 構(gòu)造算法） 對正規(guī)式的各個(gè)部分構(gòu)造NFA 用弧連接起各個(gè)NFA，構(gòu)成完整的自動(dòng)機(jī)2022-6-2087接受正規(guī)式a的NFA接受正規(guī)式的NFA假設(shè)接受正規(guī)式r的NFA如下接受正規(guī)式rs的NFA接受正規(guī)式r|s的NFA接受正規(guī)式r*的NFA正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性例子v 設(shè)正規(guī)式為 r1= 1*， r2 = 01*， r3 = 01* | 12022-6-2088Thompson構(gòu)造算法例子v正規(guī)式ab|a的NFA2022-6-2089Tho

37、mpson構(gòu)造算法例子v正規(guī)式letter(letter|digit)*的NFA正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性v 正規(guī)文法與正規(guī)式 程序語言通常采用正規(guī)文法定義它的詞法規(guī)則 正規(guī)式是自動(dòng)構(gòu)造詞法分析器的有效工具v 正規(guī)（3型）文法 G = (VT, VN, S, P) P: A B, A , A, B VN, VT * （右線性文法） P: A B, A , A, B VN, VT * （左線性文法）v 可等價(jià)變換為 p： A aB， A a A, B VN, a VT （右線性文法） p： A Ba， A a A, B VN, a VT （左線性文法）v 方便起見，右和左線性文法為分別記為GR

38、和GL正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性v 等價(jià)性對正規(guī)文法G和FA M，若L(G)=L(M), 則稱為G和M等價(jià)1. GR或GL，F(xiàn)A M，L(GR) = L(M) 或 L(GL) = L(M) 2. FA M， GR或GL， L(M) = L(GR) = L(GL) v 等價(jià)性證明對右線性文法GR構(gòu)造NFA M，并證明L(M)=L(GR)對左線性文法GL構(gòu)造NFA M，并證明L(M)=L(GL)對DFA M構(gòu)造右線性文法GR，并證明L(GR) =L(M)對DFA M構(gòu)造左線性文法GL，并證明L(GL) =L(M)2022-6-2092正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性v 等價(jià)性證明（從正規(guī)文法構(gòu)造FA

39、）基本思想 設(shè) w = a1a2ak, 分別考慮GR和GL的最左推導(dǎo) GR : S a1B1 a1a2B2 a1a2ak-1Bk-1 a1a2ak GL : S Bk-1ak Bk-2ak-1ak B1a2ak a1a2ak 非終結(jié)符的作用是記住字符個(gè)數(shù)，將其作為狀態(tài)2022-6-2093正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性v 從右線性文法構(gòu)造FA設(shè) GR = (VT, VN, S, P), 其中p： A aB， A a 令 NFA M = (VN F, VT, , S, F)，其中，1. 若AVN, 且a VT, 有A a, 則令 (A, a) = F2. 若AVN, 且a VT, 有A aA1|a

40、A2|aAk,則令 (A, a) = A1,A2, Ak容易證明，該NFA M所識別的語言L(M) = L(GR)2022-6-2094正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性v 從左線性文法構(gòu)造FA設(shè) GL = (VT, VN, S, P), 其中P: A Ba， A a 令 NFA M = (VN q0, VT, , q0, S)，其中，1. 若AVN, 且a VT, 使A a, 則令 (q0, a) = A2. 若AVN, 且a VT, 使A1 Aa, A2 Aa,Ak Aa則令 (A, a) = A1,A2, Ak2022-6-2095正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性v 從DFA中構(gòu)造GR 設(shè)DFA

41、M = (S, , , S0, F), 若S0 F，則令GR = (, S, S0, P), 其中 P為若 則 A aB 或 A a | aB 若S0 F, 則因(S0, ) = S0, 故 L(M), 但 L(GR)引入S0 代替 S0 作為新的開始符號，并增加P：S0 S0 | 容易證明，L(GR) = L(M)v 從DFA中構(gòu)造GL 可用類似的方法，但需逆向構(gòu)造； 若 B Aa 若 A a | S0a2022-6-2096v 例3.4 DFA M GR NFA M GL 1. 設(shè) DFA M = (A, B, C, D, 0, 1, , A, B) 使用FA到正規(guī)式的算法可證明L(M)

42、= 0(10)* GR = (0,1, A, B, C, D, A, P, 其中 P 為A 0 | 0B | 1DB 0D | 1CC 0 | 0B | 1DD 0D | 1D (D為無用產(chǎn)生式）2. 從GR中構(gòu)造NFA M M = (A, B, C, D, F, 0, 1, , A, F)2022-6-20973. 從NFA M構(gòu)造 GL 將 F 作為開始符號，從終態(tài) F 出發(fā)逆向構(gòu)造F 0 | A0 | C0C B1B 0 | A0 | C0D 1 | A1 | C1| D0 | D1| B0 因沒有有向邊射入 A，所以沒有有關(guān) A 的產(chǎn)生式 刪除無用候選式后GL = (0, 1, F,

43、B, C, D, F, P)F 0 | C0C B1B 0 | C0D 1 | C1| D0 | D1| B02022-6-2099等價(jià)性的結(jié)論v正規(guī)文法、正規(guī)式、確定有限自動(dòng)機(jī)和非確定有限自動(dòng)機(jī)在接收語言的能力上是互相等價(jià)的。RG2022-6-20100DFA的化簡vDFA M的化簡 化簡：尋找DFA M，使L(M) = L(M), 且|SM| SM| 最小化：尋找具有最少狀態(tài)數(shù)的M，使L(M) = L(M)v等價(jià)狀態(tài)和可區(qū)別的狀態(tài) M中的不同狀態(tài)s和t是等價(jià)的如果從狀態(tài)s出發(fā)能讀出某個(gè)字w而停于終態(tài)，那么同樣從t出發(fā)也能讀出同樣的字w而停于終態(tài)；反之，若從t出發(fā)能讀出某個(gè)字w而停于終態(tài)，則

44、從s出發(fā)也能讀出同樣的w而停于終態(tài)。2022-6-20101DFA的化簡v 狀態(tài)的等價(jià)關(guān)系() 設(shè) s, t SM, s t, 定義s t, 若w = a1a2ak *, 有v 狀態(tài)的可區(qū)分關(guān)系 s, t SM, s t, 若s，t不等價(jià)，則s，t是可區(qū)分的 據(jù) 關(guān)系，對SM可進(jìn)行等價(jià)劃分 SM = S1S2 Sn, SiSj = , | Si | 1 容易看出, s, t Si, s t, 而 s Si, t Sj, s與 t 是可區(qū)分的 等價(jià)劃分是最大劃分，即這樣劃分 n 為最小 每個(gè)等價(jià)集中元素可讀出相同的w而終止，故可合并為一個(gè)狀態(tài) 最小化算法: 從 SM中尋找 S1, S2,Sn, 使得SiSj = , s, t Si, s