詞法及詞法程序

1、12詞法分析程序設(shè)計的流程1、各類單詞表示成不同的正規(guī)文法Gi2、求正規(guī)文法Gi對應(yīng)的正規(guī)表達式3、由各個正規(guī)表達式構(gòu)造對應(yīng)的-NFA4、由各個-NFA組合成一個大的-NFA5、大的-NFA確定化、最小化得到DFA M6、DFA M就是構(gòu)造詞法分析程序的流程圖7、按照DFA M編寫詞法分析程序3主要內(nèi)容3.1 3.2 3.3 3.4 3.5 4詞法分析的任務(wù)詞法分析的任務(wù) 掃描輸入串中的字符，從中識別出具有獨立意義的基本掃描輸入串中的字符，從中識別出具有獨立意義的基本語法單位：單詞，生成單詞序列。語法單位：單詞，生成單詞序列。 剝?nèi)ピ闯绦蛑械淖⑨專▔K、行）和剝?nèi)ピ闯绦蛑械淖⑨專▔K、行）和“空白

2、空白”符符 預(yù)處理預(yù)處理宏處理與文件包含宏處理與文件包含詞法分析程序亦稱為掃描器設(shè)計和實現(xiàn)掃描器的相關(guān)問題： 描述語言中各種單詞的結(jié)構(gòu)：描述語言中各種單詞的結(jié)構(gòu)：3型文法及其正規(guī)式型文法及其正規(guī)式 識別源程序中的各個單詞：狀態(tài)轉(zhuǎn)換圖或有限自動機識別源程序中的各個單詞：狀態(tài)轉(zhuǎn)換圖或有限自動機5掃描器的功能詞法分析器語法分析器get_next_token編譯器其它階段符號表高級語言源程序字符流token單詞（流）6程序語言的單詞（1）單詞詞文模式關(guān)鍵字WHILEwhilewhileFORforfor標(biāo)識符IDtemp, i,max字母開頭的字母數(shù)字串常數(shù)NUM3.14100數(shù)字串.數(shù)字串單詞：同類

3、詞文的總稱詞文：源程序中能匹配某一記號的字符串模式：描述用字符串構(gòu)成單詞的規(guī)則7程序語言的單詞（2）單詞詞文模式運算符MUL*GT界符,串常量STRING“hello”there雙（單）引號中間的字符串（不包括引號本身）83.1 3.1.1 詞法分析的兩種處理方式n將詞法分析納入到語法分析中進行將詞法分析納入到語法分析中進行n詞法分析與語法分析分開來進行詞法分析與語法分析分開來進行描述單詞結(jié)構(gòu)比描述語法結(jié)構(gòu)簡單，僅用描述單詞結(jié)構(gòu)比描述語法結(jié)構(gòu)簡單，僅用3 3型文法就夠了；型文法就夠了；將單詞識別從語法分析中分離出來，可采用更有效的工將單詞識別從語法分析中分離出來，可采用更有效的工具（狀態(tài)轉(zhuǎn)移圖

4、、有限自動機等）實現(xiàn)；具（狀態(tài)轉(zhuǎn)移圖、有限自動機等）實現(xiàn)；有些語言（如有些語言（如FORTRANFORTRAN）的單詞識別與前后文相關(guān)，將詞）的單詞識別與前后文相關(guān)，將詞法分析獨立出來，有利于實現(xiàn)統(tǒng)一的語法分析；法分析獨立出來，有利于實現(xiàn)統(tǒng)一的語法分析；使編譯程序各部分獨立出來，有利于設(shè)計、調(diào)試和維護使編譯程序各部分獨立出來，有利于設(shè)計、調(diào)試和維護n邏輯上的劃分，不是指編譯程序的執(zhí)行流程邏輯上的劃分，不是指編譯程序的執(zhí)行流程9n詞法分析作為單獨的一遍（詞法分析作為單獨的一遍（多遍掃描多遍掃描） 大部分編譯時間花在掃描字符上，獨立出來便于集大部分編譯時間花在掃描字符上，獨立出來便于集中處理中處理

5、. . 單詞的詞法規(guī)則簡單，可建立特別適用于這種文法單詞的詞法規(guī)則簡單，可建立特別適用于這種文法的有效技術(shù)，實現(xiàn)詞法分析的自動生成的有效技術(shù)，實現(xiàn)詞法分析的自動生成. . 整個編譯程序結(jié)構(gòu)簡單，清晰，產(chǎn)生中間文件，占整個編譯程序結(jié)構(gòu)簡單，清晰，產(chǎn)生中間文件，占內(nèi)存內(nèi)存. .n詞法分析作為一個獨立的子程序，供語法分析程序調(diào)詞法分析作為一個獨立的子程序，供語法分析程序調(diào)用用 （單遍掃描單遍掃描） 語法分析調(diào)用時，返回一個單詞符號語法分析調(diào)用時，返回一個單詞符號. . 無中間文件，省內(nèi)存，編譯效率高無中間文件，省內(nèi)存，編譯效率高. . 兩種具體的實現(xiàn)方式兩種具體的實現(xiàn)方式103.1.2 3.1.2

6、單詞符號的內(nèi)部表示單詞符號的內(nèi)部表示 詞法分析器的輸出形式詞法分析器的輸出形式(1) (1) 單詞符號的種類單詞符號的種類 保留字保留字：如：如beginbegin，end,doend,do等用戶不能使用等用戶不能使用 標(biāo)識符標(biāo)識符：由用戶定義：由用戶定義 無符號整數(shù)無符號整數(shù)：如：如124124 單字符分界符單字符分界符：+ +，* *，/ / ，；， （ ，），： 雙字符分界符雙字符分界符：/，/ /* *，* */ /，: := =等等11 (2)(2)單詞符號的表示形式單詞符號的表示形式二元組二元組 二元組：（單詞類別，單詞自身值）二元組：（單詞類別，單詞自身值） 單詞類別單詞類別：說

7、明單詞屬于哪一類，常用助記符或：說明單詞屬于哪一類，常用助記符或 整數(shù)編碼表示整數(shù)編碼表示. . 例：標(biāo)識符用例：標(biāo)識符用4 4 表示表示 + + 用用8 8表示表示 * * 用用1010表示表示單詞自身值單詞自身值 一種類只有一個單詞，不必給出單詞自身值一種類只有一個單詞，不必給出單詞自身值. .因為因為 根據(jù)類別編碼能完全確定根據(jù)類別編碼能完全確定. . 一種類含有多個單詞，必須給出單詞自身值予以一種類含有多個單詞，必須給出單詞自身值予以 區(qū)別。區(qū)別。12 一般：一般： 保留字、運算符和分界符都是一個符號一保留字、運算符和分界符都是一個符號一種類別，不需單詞自身值種類別，不需單詞自身值.

8、. 如如 + + 類別類別8, 8, + + 的二元組的二元組 （8 8，- -） 標(biāo)識符整體作為一個類別,其單詞自身值采用自身的字符串編碼表示. 如標(biāo)識符類別為如標(biāo)識符類別為5 5，ABAB的二元組的二元組(5(5，ABAB） 常數(shù)按類型分類別：單詞自身值采用自身常數(shù)按類型分類別：單詞自身值采用自身 的的二進制二進制形式形式. . 如整數(shù)類別為如整數(shù)類別為2020，整數(shù)，整數(shù)4 4的二元組的二元組(20(20，100100）133.1.3 3.1.3 識別標(biāo)識符的若干約定和策略識別標(biāo)識符的若干約定和策略n約定：約定：(1)(1)標(biāo)識符中的字符個數(shù)超過最大允許長度，截去尾部標(biāo)識符中的字符個數(shù)超

9、過最大允許長度，截去尾部. .(2)(2)不超過最大長度的標(biāo)識符，則按不超過最大長度的標(biāo)識符，則按“盡可能長盡可能長”的原的原則匹配則匹配. .如：如果標(biāo)識符最大長度為如：如果標(biāo)識符最大長度為6,6,則則identifieridentifier識別為識別為identiidenti，而不是，而不是identifier;identifier; 而而NO23ANO23A可識別出可識別出NO23ANO23A標(biāo)識符標(biāo)識符, ,而不是而不是NONO、2323和和A A14n禁止關(guān)鍵字作為標(biāo)識符的前綴的語言系統(tǒng)（如禁止關(guān)鍵字作為標(biāo)識符的前綴的語言系統(tǒng)（如標(biāo)準(zhǔn)標(biāo)準(zhǔn)FORTRANFORTRAN和和PASCALP

10、ASCAL） DO10I會識別為DO 10 I，而不是將之識別為一個標(biāo)識符。n若允許關(guān)鍵字作為標(biāo)識符的前綴（非標(biāo)準(zhǔn)若允許關(guān)鍵字作為標(biāo)識符的前綴（非標(biāo)準(zhǔn)FORTRANFORTRAN） DO99K=1DO99K=1, ,10 DO10 DO循環(huán)語句循環(huán)語句 DO99K=1DO99K=1. .10 10 變量賦值變量賦值 IF(5IF(5.EQ.EQ.M)X=5 IFM)X=5 IF語句語句 IF(5)IF(5)= =55 55 函數(shù)賦值函數(shù)賦值15單詞符號的識別單詞符號的識別超前掃描技術(shù)超前掃描技術(shù)n超前掃描技術(shù)：在無法判別和識別當(dāng)前單詞時，先向超前掃描技術(shù)：在無法判別和識別當(dāng)前單詞時，先向前掃描

11、若干個字符，直到可以進行判斷和識別為止。前掃描若干個字符，直到可以進行判斷和識別為止。n嵌套括號的分層 由外向內(nèi)編號：第一層，第二層，n語句內(nèi)容的分層 按包含它的括號層次確定 不被括號包含的語句內(nèi)容稱為屬于第零層 不被括號包含的等號和逗號分別稱為零層等號和零層逗號n利用超前掃描到的零層等號和零層逗號來識別單詞符號16超前掃描技術(shù)示例超前掃描技術(shù)示例 DO99K=1DO99K=1, ,10 DO10 DO循環(huán)語句循環(huán)語句 DO99K=1DO99K=1. .10 10 變量賦值變量賦值 IF(5IF(5.EQ.EQ.M)X=5 IFM)X=5 IF語句語句 IF(5)IF(5)= =55 55 函

12、數(shù)賦值函數(shù)賦值n包含零層等號的語句：賦值語句、包含零層等號的語句：賦值語句、DODO語句、函數(shù)定語句、函數(shù)定義語句以及某些邏輯義語句以及某些邏輯IFIF語句語句n既包含零層等號，也包含零層逗號的語句：既包含零層等號，也包含零層逗號的語句：DODO語句語句n如，函數(shù)或數(shù)組賦值語句如，函數(shù)或數(shù)組賦值語句 f(a1,a2,f(a1,a2,an)=e,an)=e函數(shù)語句：函數(shù)語句： f f不出現(xiàn)在數(shù)組說明符中不出現(xiàn)在數(shù)組說明符中數(shù)組賦值語句：數(shù)組賦值語句： f f出現(xiàn)在數(shù)組說明符中出現(xiàn)在數(shù)組說明符中n再如，掃描到字符再如，掃描到字符,還需繼續(xù)向前掃描還需繼續(xù)向前掃描,（左移）（左移）,=,=,=,=（

13、復(fù)合賦值）（復(fù)合賦值）17回退字符n在超前掃描結(jié)束后，還要“回退”字符，即將超前掃描的字符退回輸入緩沖區(qū)。n實現(xiàn)回退的數(shù)據(jù)結(jié)構(gòu)：堆棧 回退：將要回退的字符依次壓入堆棧。 掃描：檢查堆棧是否為空，如果不為空，則從棧頂讀取后續(xù)字符，否則從輸入字符串讀取。n書中 程序給出了使用堆棧實現(xiàn)多字符回退的算法。183.1.4 3.1.4 源程序的輸入及預(yù)處理源程序的輸入及預(yù)處理 n緩沖輸入：將磁盤上的源程序分批送入緩沖緩沖輸入：將磁盤上的源程序分批送入緩沖區(qū)，等待掃描器處理?？梢蕴岣咦x盤效率和區(qū)，等待掃描器處理?？梢蕴岣咦x盤效率和方便掃描器工作。方便掃描器工作。n輸入系統(tǒng)：一組完成源程序輸入的函數(shù)或者輸入系

14、統(tǒng)：一組完成源程序輸入的函數(shù)或者子程序，支持讀盤、超前搜索、多字符回退子程序，支持讀盤、超前搜索、多字符回退等操作等操作nLexLex中的掃描緩沖區(qū)實例：中的掃描緩沖區(qū)實例：P46,P46,圖圖3-23-2n預(yù)處理預(yù)處理: :消除無用空白、回車、換行、制表、消除無用空白、回車、換行、制表、注釋、區(qū)分標(biāo)號區(qū)、續(xù)行號（注釋、區(qū)分標(biāo)號區(qū)、續(xù)行號（FORTRANFORTRAN）等）等. .1920n程序設(shè)計語言的單詞都能用正規(guī)文法描述，例如，標(biāo)識符可定義為：n若把字母、數(shù)字視為終結(jié)符，則上述產(chǎn)生式為左線性文法，是正規(guī)文法。n若我們用d表示0-9間的數(shù)字，則C語言的的文法是右線性文法，也是正規(guī)文法（見P

15、48）21由一組矢線連接的有限個結(jié)點所組成的有向圖。每個結(jié)點代表在識別分析過程中掃描器所處的狀態(tài)，其中含有一個初始狀態(tài)和若干個終態(tài)。在圖中，狀態(tài)用圓圈表示，終態(tài)用雙層圓圈表示。狀態(tài)之間可用有向邊連接，其上標(biāo)記一字符a，表示從有向邊的射出狀態(tài)出發(fā)，識別一字符a后，將進入箭頭所指狀態(tài)（結(jié)點）n凡能用正規(guī)文法描述的語言，均可由某種有限狀態(tài)算法進行分析。22設(shè)設(shè)G=(VN,VT,P,S)是一右線性文法，并設(shè)是一右線性文法，并設(shè)|VN|=k,則所要構(gòu)造的狀態(tài)轉(zhuǎn)換圖共有則所要構(gòu)造的狀態(tài)轉(zhuǎn)換圖共有k+1個狀態(tài)個狀態(tài)(結(jié)結(jié)點點)。用。用VN中的每個符號分別標(biāo)記其中的中的每個符號分別標(biāo)記其中的k個個結(jié)點，且令結(jié)

16、點，且令G的開始符的開始符S為初態(tài)結(jié)點；余下為初態(tài)結(jié)點；余下的一個結(jié)點作為終態(tài)結(jié)點，用的一個結(jié)點作為終態(tài)結(jié)點，用F( VN)標(biāo)記。標(biāo)記。23A狀態(tài)轉(zhuǎn)換圖的構(gòu)造原則狀態(tài)轉(zhuǎn)換圖的構(gòu)造原則G G的每一個非終結(jié)符號代表一結(jié)點的每一個非終結(jié)符號代表一結(jié)點( (狀態(tài)狀態(tài)) ) 開始符號開始符號S S作為初始狀態(tài)作為初始狀態(tài) 設(shè)一符號設(shè)一符號F F不屬于不屬于V V作為終止?fàn)顟B(tài)作為終止?fàn)顟B(tài) 形如形如AaBAaB的規(guī)則的規(guī)則 a a 形如形如AaAa的規(guī)則的規(guī)則 a a 特別特別:A :A 未曾在未曾在A A的射出弧中的射出弧中 出現(xiàn)過的終結(jié)符號出現(xiàn)過的終結(jié)符號 某些情況下也可考慮直接將某些情況下也可考慮直接

17、將A A作為終態(tài)作為終態(tài)BSFBAAFAFA24例例:GZ:GZ:Z0UZ0U 1V1VU 1ZU 1Z 1 1V 0ZV 0Z 0 0 25例例:GZ: :GZ: 狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖:Z0UZ0U 1V1VU 1ZU 1Z 1 1 1 V 0ZV 0Z 0 0 0 1 初態(tài)初態(tài) 1 0 0 ZUVF26無符號數(shù)文法舉例0. d | | d1. d | | E | | d2. E | d | d 3. d | d 4. d | + | - | d 5. d | d6. d | d d表示09之間的數(shù)字27無符號數(shù)文法對應(yīng)的狀態(tài)轉(zhuǎn)換圖無符號數(shù)文法對應(yīng)的狀態(tài)轉(zhuǎn)換圖n例如,P48中定義的無符號數(shù)的

18、文法對應(yīng)的狀態(tài)轉(zhuǎn)換圖為(化簡后):n可識別的無符號數(shù)形式：0453126d.dddd.E+|-Edd28對于已給的字符串對于已給的字符串w=a1a2an,ai VT,利用狀態(tài)轉(zhuǎn)換圖利用狀態(tài)轉(zhuǎn)換圖對對w 識別的步驟如下識別的步驟如下:(1)從初始狀態(tài)從初始狀態(tài)S出發(fā)出發(fā),自左至右逐個掃描自左至右逐個掃描w的各個字符的各個字符(當(dāng)前為當(dāng)前為a1),此時在結(jié)點此時在結(jié)點S所射出的諸矢線中所射出的諸矢線中,尋找標(biāo)尋找標(biāo)記為記為a1的矢線的矢線(若不存在若不存在,則表明則表明w有語法錯誤有語法錯誤),讀入讀入a1并沿矢線所指方向前進并沿矢線所指方向前進,過渡到下一狀態(tài)過渡到下一狀態(tài)(設(shè)為設(shè)為A1).(2

19、)設(shè)當(dāng)前處在設(shè)當(dāng)前處在Ai狀態(tài)狀態(tài),所掃描的字符為所掃描的字符為ai+1,在結(jié)點在結(jié)點Ai所所射出的諸矢線中射出的諸矢線中,尋找標(biāo)記為尋找標(biāo)記為ai+1的矢線的矢線(若不存在若不存在,則則表明表明w有語法錯誤有語法錯誤),讀入讀入ai+1,并進入狀態(tài)并進入狀態(tài)Ai+1;(3)重復(fù)重復(fù)(2),直到直到w中所有字符被讀完且恰好進入終態(tài)中所有字符被讀完且恰好進入終態(tài)F時時,宣告整個識別結(jié)束宣告整個識別結(jié)束,w可被接受可被接受.29例例:GZ: :GZ: 狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖:Z0UZ0U 1V1VU 1ZU 1Z 1 1 1 V 0ZV 0Z 0 0 0 1 初態(tài)初態(tài) 1 0 0 1 1=01100

20、1=0110012 2=111001=111001ZUVF30n顯然顯然, ,若從若從初態(tài)初態(tài)出發(fā)出發(fā), ,分別沿分別沿一切可能一切可能的的路徑路徑到達到達終態(tài)終態(tài)結(jié)點結(jié)點, ,并將路徑中并將路徑中矢線上所標(biāo)記的字符矢線上所標(biāo)記的字符依次連接起來依次連接起來, ,便得到便得到狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖所能識別的所能識別的全部符號串全部符號串, ,這些符號串這些符號串組成的集合構(gòu)成了該組成的集合構(gòu)成了該識別的語言。識別的語言。31狀態(tài)轉(zhuǎn)換圖與文法推導(dǎo)狀態(tài)轉(zhuǎn)換圖與文法推導(dǎo)n用狀態(tài)轉(zhuǎn)換圖識別符號串w w的過程，就是為w w建立一個推導(dǎo)S S* * w w的過程。n在第一步（在初始狀態(tài)S S下，掃描到a a

21、1 1而過渡到下一狀態(tài)A A1 1），由狀態(tài)轉(zhuǎn)換圖的構(gòu)造規(guī)則可知，GG中必有產(chǎn)生式S Sa a1 1A A1 1;n對于識別過程的后續(xù)步驟，由狀態(tài)A Ai i 識別a ai+1i+1后過渡到A Ai+1i+1恰好對應(yīng)了使用產(chǎn)生式A Ai i a ai+1i+1A Ai+1 i+1 。n最后在狀態(tài)A An-1n-1識別a an n后到達終態(tài)F F，對應(yīng)了使用產(chǎn)生式A A a an n。n整個推導(dǎo)過程：S S a a1 1A A1 1 a a1 1a a2 2A A2 2 a a1 1a a2 2a an-1n-1A An-1n-1 a a1 1a a2 2a an n32例例:GZ: :GZ:

22、狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖:Z0UZ0U 1V1VU 1ZU 1Z 1 1 1 V 0ZV 0Z 0 0 0 1 初態(tài)初態(tài) 1 0 0 例例: =011001: =011001通過狀態(tài)圖可以確定通過狀態(tài)圖可以確定是文法的句子是文法的句子. .此過程是一種推導(dǎo)過程此過程是一種推導(dǎo)過程. .Z=0U=01Z=011V=0110Z=01100U=011001Z=0U=01Z=011V=0110Z=01100U=011001ZUVF33 設(shè)設(shè) 是一是一,是相應(yīng)的是相應(yīng)的,則從前面的討則從前面的討論可以看出如下事實：論可以看出如下事實：(1)在利用在利用對符號串對符號串 進行識別時進行識別時,中每次狀態(tài)的轉(zhuǎn)換

23、都模擬了一中每次狀態(tài)的轉(zhuǎn)換都模擬了一步直接推導(dǎo)步直接推導(dǎo),即識別方法即識別方法(或稱分析方法或稱分析方法) 是是“ ”的的;(2)因因右線性文法右線性文法只有形如只有形如的產(chǎn)生式，所以推導(dǎo)的每一的產(chǎn)生式，所以推導(dǎo)的每一步所得句型只含一個非終結(jié)符，且必出現(xiàn)在句型的最右端，所以步所得句型只含一個非終結(jié)符，且必出現(xiàn)在句型的最右端，所以推導(dǎo)是推導(dǎo)是規(guī)范推導(dǎo)規(guī)范推導(dǎo)，每步所得的句型也必為，每步所得的句型也必為規(guī)范句型規(guī)范句型；(3)對于對于所識別的任一符號串所識別的任一符號串 ,必存在必存在G中的一個推導(dǎo)中的一個推導(dǎo) (即有即有反之反之,對于對于中任一句子中任一句子 ,必存在一條從初態(tài)必存在一條從初態(tài)

24、到終態(tài)到終態(tài)的路徑的路徑,此路徑上各矢線的標(biāo)記依次拼接起來所組成的符號串恰為此路徑上各矢線的標(biāo)記依次拼接起來所組成的符號串恰為34n設(shè)是一左線性文法,構(gòu)造相應(yīng)的狀態(tài)轉(zhuǎn)換圖的方法是: 首先用中的非終結(jié)符標(biāo)記M的結(jié)點，其中，開始符對應(yīng)的結(jié)點為終態(tài)結(jié)點。引入一個新結(jié)點標(biāo)記初態(tài)。矢線的連接規(guī)則為:(1)對于 中形如 的產(chǎn)生式，引矢線且標(biāo)記為 ；(2)對于G中形如 的產(chǎn)生式，引矢，且標(biāo)記為 。35已給文法已給文法G=(S,U,0,1,SS1 |U1, UU0 | 0,S)36例例:GZ:GZ:ZU0ZU0 V1V1U Z1U Z1 1 1V Z0V Z0 0 0狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖: 0初態(tài)初態(tài) 1 1

25、 0 0 1RUVZ(2)(2)狀態(tài)轉(zhuǎn)換圖的使用狀態(tài)轉(zhuǎn)換圖的使用 識別句子識別句子( (單詞符號單詞符號) )例例:100110:100110通過狀態(tài)圖可通過狀態(tài)圖可以確定是文法的句子以確定是文法的句子. . 識別過程對應(yīng)著歸約識別過程對應(yīng)著歸約過程過程 1 10011000110 U0U001100110 Z0Z0110110 V1V11010 Z1Z10 0 U0U0 Z Z37n由構(gòu)造狀態(tài)轉(zhuǎn)換圖的方法可知,從初態(tài)從初態(tài)到下一狀態(tài)到下一狀態(tài)A A的轉(zhuǎn)換的轉(zhuǎn)換, ,對應(yīng)了形如對應(yīng)了形如 的產(chǎn)生式的產(chǎn)生式,即將終結(jié)符 歸約成非終結(jié)符A A;n從狀態(tài)B B轉(zhuǎn)換到狀態(tài) ,對應(yīng)了形如對應(yīng)了形如的產(chǎn)生

26、式的產(chǎn)生式,即將歸約為 ;n如此下去,直到從某狀態(tài) 轉(zhuǎn)換到狀態(tài)(終態(tài)),對應(yīng)了形如對應(yīng)了形如的產(chǎn)生式的產(chǎn)生式,即將歸約為開始符 .此時歸約成功,也恰好進入了終態(tài),即狀態(tài)轉(zhuǎn)換圖識別了(或接受)該符號串.n前面識別的例子對應(yīng)的歸約過程見右圖38n狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖可方便地用于識別單詞.但是,如何讓計算機利用狀態(tài)轉(zhuǎn)換圖來進行詞法分析呢?n一個簡單實用的方法就是將圖以矩陣的形式保存在內(nèi)存中.這就是所謂的狀態(tài)矩陣法狀態(tài)矩陣法.n狀態(tài)矩陣狀態(tài)矩陣 以圖中各個狀態(tài)為行,以各個輸入符號為列,組成一個矩陣 ,其元素指明掃描器此時應(yīng)完成的語義動作和要轉(zhuǎn)換到的下一狀態(tài).其含義是,在狀態(tài)下,掃描到 符時,按序偶查矩

27、陣 ,掃描器根據(jù)的指示,先執(zhí)行相應(yīng)的語義動作,再轉(zhuǎn)換到下個狀態(tài).n若為“”,則說明輸入符號串有誤,拒絕接受.掃描器將調(diào)用出錯處理程序進行處理39 CurStat=0;FlagOfFS=NoneSeen; if(CurChar=EOF) return 0;while (CurChar != EOF) if(Stat=TransMatCurStatCurChar!=NULL) CurStat=Stat; advance( ); if( CurStat 是終態(tài)是終態(tài)) FlagOfFS=HasSeen; / 記下輸入串中當(dāng)前位置及該狀態(tài)相關(guān)聯(lián)的動作記下輸入串中當(dāng)前位置及該狀態(tài)相關(guān)聯(lián)的動作; 40 e

28、lse if(FlagOfFS=NoneSeen) 報告詞法錯誤報告詞法錯誤; 略過當(dāng)前詞文及輸入字符略過當(dāng)前詞文及輸入字符; CurStat=0; else 回退到最近經(jīng)歷的那個終態(tài)的輸入字符位置回退到最近經(jīng)歷的那個終態(tài)的輸入字符位置; 執(zhí)行所記錄的該終態(tài)的相關(guān)動作執(zhí)行所記錄的該終態(tài)的相關(guān)動作; / 41貪心策略n目的是獲得最長匹配單詞（1）若當(dāng)前狀態(tài)對輸入符號有后繼動作，則繼續(xù)進行狀態(tài)轉(zhuǎn)移；（2）若當(dāng)前狀態(tài)為終態(tài)，記下該狀態(tài)和當(dāng)前輸入字符的位置，并繼續(xù)向前掃描；（3）若當(dāng)前狀態(tài)已無后繼狀態(tài)，并且此前經(jīng)歷過終態(tài)，則執(zhí)行曾經(jīng)歷的最近的終態(tài)所對應(yīng)的語義動作；（4）若當(dāng)前狀態(tài)已無后繼狀態(tài)，并且此前

29、沒有經(jīng)歷過終態(tài)，則表明輸入字符串有詞法錯誤，報錯，并略過余下的部分詞文，從狀態(tài)0開始繼續(xù)下一單詞的識別。n狀態(tài)矩陣是稀疏的，應(yīng)該采用緊湊的數(shù)據(jù)結(jié)構(gòu)42識別無符號數(shù)識別無符號數(shù)n功能：把識別出的無符號數(shù)轉(zhuǎn)換成整數(shù)（n無符號數(shù)的輸入形式：可改寫為可改寫為n用分別計錄尾數(shù)、指數(shù)、小數(shù)位及指數(shù)的符號。因此數(shù)值為： n語義加工過程：初值為0， 初值為1； 處理整數(shù)部分時，對于每個 處理小數(shù)部分時，對于每個 處理指數(shù)時， 后若有 號，令；計算指數(shù)值 在出口處，令43無符號數(shù)無符號數(shù)當(dāng) 前 狀態(tài)掃 描 字 符語 義 處 理 操 作 或 接 受 動 作后 繼 狀態(tài)dw =0;n=0;p=0;e=1;w =w

30、*10+d1.w =0;n=0;p=0;e=1;30thererrordw =w *10+d;1.2E41otherreturn ( IC O N = w );enddn+; w =w *10+d;2E42otherreturn (FC O N =w *pow (10,e*p-n) ) ;enddn+;w =w *10+d;23othererrordp=p*10+d;6+5-e=-1;54othererrordp=p*10+d;65othererrordp=p*10+d;66otherreturn (FC O N =w *pow (10,e*p-n) );end44狀態(tài)轉(zhuǎn)換圖實際上是有限自動機

31、的圖形表示453.3.1 確定的有限自動機DFAn抽象地看抽象地看, ,狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖由五個部分組成由五個部分組成: :(1)(1)有限個狀態(tài)之集有限個狀態(tài)之集, ,記作記作K K; ;(2)(2)有限個輸入符號組成的字母表有限個輸入符號組成的字母表, ,記作記作 ; ;(3)(3)從從K K到到K K的的轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù) f: Kf: KK. f(p,a)=qK. f(p,a)=q表示若表示若當(dāng)前狀態(tài)為當(dāng)前狀態(tài)為p p, ,且輸入符號為且輸入符號為a a, ,則進入下一個狀態(tài)為則進入下一個狀態(tài)為q q; ;(4)(4)S S0 0 K K, ,初始初始( (開始開始) )狀態(tài)狀態(tài); ;

32、(5)(5)若干個終態(tài)之集若干個終態(tài)之集: : Z(Z( K)K)由上述五個要素組成的五元式由上述五個要素組成的五元式 M=(K, M=(K, , f,S, f,S0 0,Z ),Z )稱為稱為一個一個確定的有限自動機確定的有限自動機 ( (DFADFA: : D Deterministic eterministic F Finite inite A Automatautomata) )由此可見由此可見, ,DFADFA實際上是狀態(tài)轉(zhuǎn)換圖的形式描述實際上是狀態(tài)轉(zhuǎn)換圖的形式描述( (數(shù)學(xué)定數(shù)學(xué)定義義),),狀態(tài)轉(zhuǎn)換圖是狀態(tài)轉(zhuǎn)換圖是DFADFA的幾何的幾何( (圖形圖形) )表示表示. .46ZU

33、VF2=1001已知已知DFA M=(K, , f,S0,Z )，其中：，其中：K=Z，U，V，F(xiàn)， =0，1，S0=Z，Z=Ff(Z,0)=U,f(Z,1)=V,f(U,0)=Z,f(U,1)=F,f(V,0)=Zf(V,1)=F狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖: :1=0010010初態(tài)初態(tài)011103=11100147nDFA M的接受集 我們把一DFA M所接受的符號串的全體稱為M的接受集或M接受的語言，記為L(M),即 L(M)= x | f(S0,x) Z,x* nM接受(或識別)某符號串x*：從初態(tài)S0出發(fā),經(jīng)一恰好標(biāo)有x 的路徑后可達到某終態(tài)S Z 。用f描述就是: S Z, f(S0,x

34、)=S n將轉(zhuǎn)換函數(shù)f 的定義域拓廣到K* ，可以得到 f: (1) f (s, )=s, s K; (2) f (s,aw)=f ( f(s,a),w), s K,a,w*;n對于x* , f(s,x)=t 的含義是,當(dāng)M從狀態(tài)s出發(fā),依次掃描完x的各個符號后將進入狀態(tài)t.n只要f有定義, f與f的效果是一致的，以后不再區(qū)分。48轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù) f: Kf: KK. K. f(p,af(p,a)=q)=q表示若當(dāng)前狀態(tài)為表示若當(dāng)前狀態(tài)為p,p,且輸入符號且輸入符號為為a,a,則進入下一個狀態(tài)為則進入下一個狀態(tài)為q;q;把把f f拓廣到拓廣到f:f:f(p,f(p,x)=q)=q若若x=ab

35、cd=abcdf(p,af(p,a)=p1,f(p1,b)=p2,)=p1,f(p1,b)=p2,f(pf(p, ,x)=)=f(f(p,a),bcdf(f(p,a),bcd.).)49n確定的FA：在狀態(tài)轉(zhuǎn)換的每一步，根據(jù)FA當(dāng)前的狀態(tài)及掃描的輸入字符，便能唯一地唯一地確定FA的下一狀態(tài)。在轉(zhuǎn)換圖上看，若|=n，則任何結(jié)點所引出的矢線至多有n條，且矢線上的標(biāo)記均不同。n例如，P51圖3-4所對應(yīng)的DFA為 M=(R,U,S,0,1,f,R,S) 其中，f的定義如下：f(R,0)=Uf(U,0)=Uf(U,1)=Sf(S,1)=Sn由DFA與狀態(tài)轉(zhuǎn)換圖的關(guān)系可知，構(gòu)造狀態(tài)轉(zhuǎn)換圖的算法，同樣適用

36、于構(gòu)造DFA。n可以證明， 正規(guī)文法G， DFA M，使L(M)=L(G)，反之亦然。50 在相應(yīng)的狀態(tài)轉(zhuǎn)換圖中，在相應(yīng)的狀態(tài)轉(zhuǎn)換圖中，就會出現(xiàn)這樣的結(jié)點就會出現(xiàn)這樣的結(jié)點U，它具有多條標(biāo)記為同一它具有多條標(biāo)記為同一輸入符號輸入符號a的矢線的矢線在在U狀態(tài)下，輸入符號為狀態(tài)下，輸入符號為a時，時，F(xiàn)A的下一狀態(tài)不唯一，而的下一狀態(tài)不唯一，而是在狀態(tài)集是在狀態(tài)集A,B,C,X中任選其一。具有這種性質(zhì)的中任選其一。具有這種性質(zhì)的FA稱為非確定的稱為非確定的FA（NFA: Nondeterministic FA）51nNFA M 也可用五元式定義：M=(K,f,S0,Z)，其中，K, ,S0,Z的含

37、義同DFA,轉(zhuǎn)換函數(shù)f的定義為 f: K(K),即將(Si,aj)映射到K的一個子集Sk1,Skm n類似地，我們可把f的定義域拓廣到K* ： (1) f(S,)=S; (2) f(S,aw)=f(f(S,a),w) a,w*.52n所有為所有為NFANFA M M所接受的符號串之集稱為所接受的符號串之集稱為NFA MNFA M的接受的接受集（或識別集），記作集（或識別集），記作 L(M).L(M).即即 L(M)L(M)=x x| |f f（S S0 0,x,x） Z Z , x, x* * nx x* * 為為M M所接受：集合所接受：集合f(Sf(S0 0,x),x)中含有中含有Z Z中

38、的元素中的元素（終態(tài)），即至少存在一條從初態(tài)（終態(tài)），即至少存在一條從初態(tài)S S0 0到某一終態(tài)的路到某一終態(tài)的路徑，此路徑上的符號之連接恰為徑，此路徑上的符號之連接恰為x x。例例3.13.1 給定給定M=(S,A,B,C, M=(S,A,B,C, a,b,f,S,C),a,b,f,S,C),其狀態(tài)轉(zhuǎn)其狀態(tài)轉(zhuǎn)換圖見右。由圖可知換圖見右。由圖可知M M是一是一NFANFA。53識別符號串識別符號串a(chǎn)babbababb的路徑的路徑 注意注意，NFANFA識別輸入符號串時有一個試探過程，為了能識別輸入符號串時有一個試探過程，為了能走到終態(tài)，往往要走許多彎路（走到終態(tài)，往往要走許多彎路（帶回溯帶回溯

39、），這影響了），這影響了FAFA的效率。的效率。n符號串符號串a(chǎn)babbababb的識別路徑的識別路徑S(S(a a) )A(A(b b) )B(B(a a) )A(A(b b) )B(B(b b) )C C( (接受接受) )。 ( (參見書中參見書中P60P60) )543.3.3 n可將可將DFA看作看作NFA的特殊情況的特殊情況,即即DFA所接受所接受的語言類包含在的語言類包含在NFA所接受的語言類中。因所接受的語言類中。因此，要證明此，要證明NFA與與DFA的等價性，只需證明的等價性，只需證明每一個每一個NFA都可以確定化。都可以確定化。n確定化：對任意確定化：對任意NFA M，構(gòu)造

40、一個，構(gòu)造一個DFA M，使得使得L(M)=L(M)。n思路：令思路：令M的某個狀態(tài)與的某個狀態(tài)與M的某個狀態(tài)子集的某個狀態(tài)子集相對應(yīng)，并使得在相對應(yīng)，并使得在M掃描與掃描與M相同的輸入符相同的輸入符號時，保持對號時，保持對M的狀態(tài)進行跟蹤（能根據(jù)的狀態(tài)進行跟蹤（能根據(jù)M的狀態(tài)確定的狀態(tài)確定M的狀態(tài)）。的狀態(tài)）。55證明 對于字母表對于字母表 上的任一上的任一NFA M，必存，必存在與在與M等價的等價的DFA M 。 設(shè)設(shè) M=(K,M=(K, ,f,S,f,S0 0,Z),Z) 是是 上的上的NFANFA，現(xiàn)構(gòu)造，現(xiàn)構(gòu)造 上上DFADFA M M=（K, , ,f,S0,Z).方法如下：方法

41、如下：1.1.K= (K).為表示方便為表示方便,如如K某子集為某子集為S1,S2,Si,記相應(yīng)的狀態(tài)為記相應(yīng)的狀態(tài)為S1,S2,Si.特別地特別地,令令S0=S0.2.映射映射f的定義的定義: f(S1,S2,Si,a)=R1,R2,Rj iff f(S1,S2,Si,a)=R1,R2,Rj3.M的終態(tài)集的終態(tài)集Z=Sp,Sq,Sr|Sp,Sq,Sr K并且并且Sp,Sq,Sr Z56現(xiàn)在現(xiàn)在,證明證明M與與M等價的等價性等價的等價性.為此為此,對輸入符號串對輸入符號串|x|=n的長度進行的長度進行歸納歸納,以證明如下論斷以證明如下論斷: f(S0,x)= S1,S2,Si f(S0,x)=

42、S1,S2,Si (S0=S0)當(dāng)當(dāng)|x|=0 (即即x= )時時,由于總有由于總有 f(S0, )=S0, f(S0, )=S0 ,即即f(S0, )=S0,故論斷成立故論斷成立.設(shè)對于長度小于或等于設(shè)對于長度小于或等于m的任何輸入串的任何輸入串x論斷均成立論斷均成立,即即f(S0,x)=S1,S2,Sif(S0,x)=S1,S2,Si現(xiàn)證明對于輸入串現(xiàn)證明對于輸入串xa,其中其中,|x|=m,a 論斷也成立論斷也成立,即即 f(S0,xa)=R1,R2,Rj f(S0,xa)=R1,R2,Rj57f(S0,xa)= f(f(S0,x),a)=f(S1,S2,Si,a) =R1,R2,Rjf

43、(S0,xa)=f(f(S0,x),a)=f(S1,Si,a) (歸納假設(shè)歸納假設(shè)) =R1,Rj (f的構(gòu)造定義的構(gòu)造定義) 最后最后,若若 f(S0,x) Z 及由及由Z的定義的定義,f(S0,x) Z.即即 x L(M) x L(M) 得證。由于得證。由于NFA與與DFA是等價的是等價的,今后統(tǒng)稱今后統(tǒng)稱FA. 還應(yīng)指出，確定化時所得的還應(yīng)指出，確定化時所得的DFA的狀態(tài)數(shù)是很大的，的狀態(tài)數(shù)是很大的，往往有許多無用狀態(tài)（往往有許多無用狀態(tài)（即那些從初態(tài)即那些從初態(tài)S0不可達的狀態(tài)不可達的狀態(tài)或那些從其出發(fā)不能到達終態(tài)的狀態(tài)或那些從其出發(fā)不能到達終態(tài)的狀態(tài)），這些狀態(tài)可），這些狀態(tài)可從從D

44、FA中刪除。中刪除。58例例3.23.2 M=(S0,S1,a,b,f,S0,S1)構(gòu)造構(gòu)造M的的DFA M=(K,a,b,f,S0,Z), 其中其中 K=S0,S1,S0,S1, f(S0,a)=S0,S1 f(S0,b)=S1f(S1,a)= f(S1,b)=S0,S1因為因為 f(S0,S1,a)= f(S0,a) f(S1,a)= S0,S1 f(S0,S1,b)= f(S0,b) f(S1,b)= S0,S1所以所以 f(S0,S1,a)= f(S0,S1,b)=S0,S1_f_|_a_ b_S0 |S0,S1 S1S1 | S0,S159f(,a)= f(,b)= f | a b

45、| new state | | S0 | S0,S1 S1 | 1S1 | S0,S1 | 2S0,S1| S0,S1 S0,S1 | 3Z= S1,S0,S1M=(K,a,b,f,S0, S1,S0,S1)603.3.4 n若在一若在一FAFA中中, ,允許對允許對 也作狀也作狀態(tài)轉(zhuǎn)移態(tài)轉(zhuǎn)移, ,則這樣的則這樣的FAFA稱為具有稱為具有 動作的動作的FA.n右圖就是一個具有具有 動作的動作的FA。其中其中, ,有的矢線上標(biāo)記有的矢線上標(biāo)記為為（在此看作一個符號在此看作一個符號）。標(biāo)記為 的矢線對識別符號串無影響,但卻改變了當(dāng)前的狀態(tài)狀態(tài).例如,上圖的FA中,從狀態(tài)0到狀態(tài)3存在路徑: 0(a

46、)0(a)0()2(c)2(c)2()3,即M識別了aacc=aacc.61 定義為定義為 M=(K,f,S0,Z),其中,f定義為 f:K()(K).n在在中中, 視為一個視為一個輸入符號輸入符號, ,在矩陣表在矩陣表示中示中, ,也有相應(yīng)的列也有相應(yīng)的列。例如，對于前面例如，對于前面的的FAFA，相應(yīng)的狀態(tài)轉(zhuǎn)換矩陣如，相應(yīng)的狀態(tài)轉(zhuǎn)換矩陣如P63P63表表3-23-2所示。所示。n同理可以定義同理可以定義f:K*(K). f(S,x)是由這是由這樣的狀態(tài)樣的狀態(tài)q組成組成,存在從存在從S到到q的路徑的路徑,該路徑上矢線該路徑上矢線的標(biāo)記組成的符號串恰好為的標(biāo)記組成的符號串恰好為x, 標(biāo)記中可

47、以包含若標(biāo)記中可以包含若干個干個 。62狀態(tài)S的-閉包：-CLOSURE(S)n狀態(tài)S的 -閉包閉包：記為-CLOSURE(S),它是從S出發(fā)經(jīng)過若干標(biāo)記為的矢線所能達到的全部狀態(tài)之集，其歸納定義如下： (1)S-CLOSURE(S); (2)設(shè)Sj-CLOSURE(S),且Sj Sk,則Sk-CLOSURE(S); (3)重復(fù)使用規(guī)則（2）所得的集合為-CLOSURE(S).n-CLOSURE還可定義在狀態(tài)集上，設(shè)QK，則QSSCLOSUREQCLOSURE)()(63-CLOSURE示例n例例如如，對于右圖的NFA， -CLOSURE(0)=0,1,2,3；-CLOSURE(1)=1；-C

48、LOSURE(2)=2,3；-CLOSURE(3)=3.64轉(zhuǎn)換函數(shù)f和f 的拓廣n利用-CLOSURE(S)，可定義f如下： RqRqwSfqwqfwRfaqfaRfKRKRKKfKKfffaqfawSffPPCLOSUREwaSfSCLOSURESfwaKS),(),()4(),(),(3)(:)2(),(),(,);(),()2();(),()1 (,*),(*）（有：）（）。對（）（）和（）（）（定義分別拓廣到的及將。其中65f與f的區(qū)別n由f的定義可知，f(S,a) 與f(S,a) 不同，f(S,a)是從S出發(fā)經(jīng)過路徑a所達的狀態(tài)集（可走若干步）；而f(S,a)是從S出發(fā)經(jīng)過矢線a所

49、達的狀態(tài)集（只走一步）n顯然，f(S,a) 只走一步只走一步a矢線矢線 -CLOSURE(f(S,a) 多步，第一步必須走多步，第一步必須走a矢線矢線 f(S,a) 路徑路徑a ：第一步可以是第一步可以是 矢線矢線n-NFA的接受集的接受集： L(M)=w|f(S0,w) Z66f與f的計算示例n例如，在右圖的NFA中， f(0, )=1,2; f(0,a)=0 是輸入符號是輸入符號 f(0, )= -CLOSURE(0)=0,1,2,3; 是符號串是符號串 f(0,a)= -CLOSURE(f(f(0, ),a)= -CLOSURE(f(0,1,2,3,a) = -CLOSURE(f(0,a

50、) f(3,a)= -CLOSURE(0)=0,1,2,3 f(0,ac)= -CLOSURE(f(f(0,a),c)= -CLOSURE(f(0,1,2,3,c) = -CLOSURE(f(0,c) f(3,c)= -CLOSURE(2)=2,367 -NFA的用途：構(gòu)造更復(fù)雜的的用途：構(gòu)造更復(fù)雜的FAn有了-NFA，就可把識別各種不同單詞的FA用矢線（并連）連接起來，組成一個單一的NFA，經(jīng)確定化后可得識別所有單詞的DFA，由此可設(shè)計編譯程序的詞法分析器。n例如，某語言的單詞有： 1.BEGIN 2.END3.IF 4.THEN5.ELSE 6.標(biāo)識符7.無符號整數(shù) 8. 9. = 10.

51、 =11. 12. 13.= 可分別構(gòu)造出識別各類單詞的FA,然后將其合并為一個大FA,如書中P65圖3-11所示。68n為具有為具有 動作的動作的NFA M=(K, ,f,S0,Z)構(gòu)造相應(yīng)的構(gòu)造相應(yīng)的DFA M=(K, ,f,q0,Z)n基本思路：從基本思路：從M的初始狀態(tài)的初始狀態(tài)S0出發(fā)，僅經(jīng)過任意條出發(fā)，僅經(jīng)過任意條矢線所能到達的狀態(tài)集合作為矢線所能到達的狀態(tài)集合作為M的初態(tài)的初態(tài)q0 ；然后從；然后從q0出發(fā)，將對輸入符號出發(fā)，將對輸入符號a進行狀態(tài)轉(zhuǎn)移所能到達進行狀態(tài)轉(zhuǎn)移所能到達的狀態(tài)（包括轉(zhuǎn)移后再經(jīng)過的狀態(tài)（包括轉(zhuǎn)移后再經(jīng)過 矢線所能到達的狀態(tài)）矢線所能到達的狀態(tài)）所組成的集合

52、作為所組成的集合作為M的狀態(tài)，如此反復(fù)，直到無新的狀態(tài)，如此反復(fù)，直到無新狀態(tài)產(chǎn)生為止。狀態(tài)產(chǎn)生為止。69構(gòu)造構(gòu)造K,f和和Z的遞歸過程的遞歸過程1. 令令 K= -CLOSURE(S0); f= ;2. 對對K中尚未被標(biāo)記的狀態(tài)中尚未被標(biāo)記的狀態(tài)qi=Si1,Si2,Sim:(1)標(biāo)記標(biāo)記qi;(2)對于每個對于每個a,令令Ta=f(Si1,Si2,Sim,a); 對對a轉(zhuǎn)移轉(zhuǎn)移 令令 qj= -CLOSURE(Ta); 進行進行 矢線轉(zhuǎn)移矢線轉(zhuǎn)移(3)若若qj K,則令則令K=K qj ;(4)令令f=f f(qi ,a)= qj ;3. 重復(fù)重復(fù)2.,直到直到K中無未標(biāo)記的狀態(tài)中無未標(biāo)記

53、的狀態(tài);4. 令令Z=qj | qj Z (這里把這里把qj 視為集合視為集合)70確定化具有確定化具有 動作的動作的NFANFA的例子的例子例例3.4 考慮右圖具有考慮右圖具有 動作的動作的NFA1.q0 = -CLOSURE(0) =0,1,2,3=K;2.q0未標(biāo)記未標(biāo)記,故故 (1)標(biāo)記標(biāo)記q0; (2)f(q0,a)= -CLOSURE(f(0,1,2,3,a) = -CLOSURE(0) = q0; f(q0,b)= -CLOSURE(f(0,1,2,3,b) = -CLOSURE(1,3) = 1,3= q1 =K; f(q0,c)= -CLOSURE(f(0,1,2,3,c)

54、= -CLOSURE(2) = 2,3= q2 =K;71確定化具有確定化具有 動作的動作的NFANFA的例子的例子( (續(xù)續(xù)) )3. K=q0,q1, q2,q1,q2 沒有標(biāo)記，沒有標(biāo)記， (1) 標(biāo)記標(biāo)記q1; (2) f(q1,a)= -CLOSURE(f(1,3,a)= f(q1,b)=q1; f(q1,c)= ;4. q2 沒標(biāo)記沒標(biāo)記, (1) 標(biāo)記標(biāo)記q2; (2) f(q2,a)= -CLOSURE(f(2,3,a)=； f(q2,b)=;f(q2,c)=q2; K不再增大，且所有的狀態(tài)都已被標(biāo)記，不再增大，且所有的狀態(tài)都已被標(biāo)記，Z=q0,q1,q2，最后的最后的DFA

55、M 如下所示：如下所示：q1q0q2abbcc72n需要說明的是需要說明的是,上述算法也適合于不含上述算法也適合于不含 產(chǎn)生式的產(chǎn)生式的NFA的確定化的確定化. 對于書中圖對于書中圖3-11所示的所示的NFA利用上述算法所得利用上述算法所得的的DFA如如 P67圖圖3-13所示所示. 其中其中,圓圈中的數(shù)字是原圓圈中的數(shù)字是原NFA的狀態(tài)編號的狀態(tài)編號,在圖在圖3-13中中, q0=0,1,7,11,14,19,24,26,28,30,33,35,40. 標(biāo)有標(biāo)有“#”的狀態(tài)為特殊狀態(tài)的狀態(tài)為特殊狀態(tài),在該狀態(tài)下在該狀態(tài)下,若遇非弧若遇非弧線上出現(xiàn)的字符線上出現(xiàn)的字符,則轉(zhuǎn)到狀態(tài)則轉(zhuǎn)到狀態(tài)25

56、.733.3.6 DFA狀態(tài)數(shù)的最小化n對于一對于一DFA來說來說,其狀態(tài)數(shù)可能并不是最小的其狀態(tài)數(shù)可能并不是最小的.原因是原因是DFA中有些狀態(tài)是中有些狀態(tài)是“等價等價”的的.為得到高效率的為得到高效率的DFA,需需將這些將這些“等價等價”狀態(tài)合并狀態(tài)合并,這就是這就是DFA的最小化的最小化.nDFA M的最小化的最小化: 構(gòu)造等價的構(gòu)造等價的DFA MDFA M其狀態(tài)數(shù)達到最其狀態(tài)數(shù)達到最小小. .n可區(qū)分狀態(tài)可區(qū)分狀態(tài): 設(shè)設(shè)s,t K, s,t由某由某w*所區(qū)分所區(qū)分 iff ( f(s,w) Z f(t,w) Z ) ( f(s,w) Z f(t,w) Z ) 若若 w*, f(s,

57、w) Z f(t,w) Z,則則 s與與 t不可區(qū)分，稱不可區(qū)分，稱二者等價。二者等價。n確定了等價狀態(tài)，就可以對其進行合并。確定了等價狀態(tài)，就可以對其進行合并。74DFA最小化算法n基本思想: 將M的狀態(tài)集K逐步地進行劃分,以期將K劃分為滿足等價關(guān)系的等價類：使得在同一類中的狀態(tài)不可區(qū)分;在不同類中的狀態(tài)可區(qū)分.算法如下:1. 先將狀態(tài)集K按終態(tài)和非終態(tài)劃分為兩個子集Z Z和K-K-Z Z,顯然分屬于這兩個集合的狀態(tài)是可(被 )區(qū)分的.記 =Z,K-Z.=Z,K-Z.2. 設(shè)當(dāng)前的劃分 中已含有mm個子集: =I=I1 1,I ,I2 2, ,I ,Imm ,其中,屬于不同子集I Ii i和

58、I Ij j (ij)的狀態(tài)是可區(qū)分的,而屬于同一子集I Ii i中的狀態(tài)是待區(qū)分的.現(xiàn)對每個子集I Ii i=S=Si i1 1,S,Si i2 2, ,S,Si in n 中的各狀態(tài)S Si ir r(S(Si ir r K,1K,1 r r n )n )進行考查,看其是否可區(qū)分.75DFA最小化算法(續(xù)) 對于S Si ip p, S, Si iq q I Ii i ,若存在a a,使得f(Sf(Si ip p,a)=S,a)=Su u I Ij j, f(S, f(Si iq q,a) ,a) =S=Sv v I Ik k（即經(jīng)過a a轉(zhuǎn)換后落在不同的等價類中），則根據(jù) S Su u和

59、S Sv v被某個w w所區(qū)分可知,S Si ip p 和S Si iq q 可被awaw 區(qū)分: f(Sf(Si ip p,aw)=f(S,aw)=f(Su u ,w) ,w)，而f(Sf(Si iq q,aw)= f(S,aw)= f(Sv v ,w) ,w)，且且S Su u與S Sv v可區(qū)分.將I Ii i細(xì)分,使其落入不同的更小的子集中.得到新劃分 new.new. （細(xì)分I Ii i的方法見下頁）。3.若 newnew. 不等于,則令 = = new.new. 轉(zhuǎn)2.4.對于最終的 ，從每個劃分塊I Ii i中任選一狀態(tài)為代表，構(gòu)成KK。若I Ii i中含有初態(tài)，則其代表也為初態(tài)

60、；若I Ii i Z Z，則I Ii i 的代表 ZZ。刪除非代表狀態(tài)，將引入非代表狀態(tài)的矢線引向代表狀態(tài).76細(xì)分劃分塊的方法.),(,),(),(,21中同一子集落入使得個更小的子集分為則將個不同的子集中的狀態(tài)分別落入若令對每個子集aIfIIIpIpIaSfaIfIaIjpiiiiiiaiISiaii.),(,),(,可區(qū)分有意義的狀態(tài)它任何使與其則無意義使得若某狀態(tài)iiIqaqfpapfIp77DFA最小化的例子1. =0,1,2,3,4 0,1,2,3a=1 未區(qū)分未區(qū)分; 0,1,2b=2,3, 3b=4, 所以所以3與與 0,1,2 可區(qū)分可區(qū)分; =0,1,2, 3,42. 0,