詞法分析及詞法分析程序

1、12詞法分析程序設(shè)計(jì)的流程1、各類單詞表示成不同的正規(guī)文法Gi2、求正規(guī)文法Gi對(duì)應(yīng)的正規(guī)表達(dá)式3、由各個(gè)正規(guī)表達(dá)式構(gòu)造對(duì)應(yīng)的-NFA4、由各個(gè)-NFA組合成一個(gè)大的-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ù) 掃描輸入串中的字符，從中識(shí)別出具有獨(dú)立意義的基本掃描輸入串中的字符，從中識(shí)別出具有獨(dú)立意義的基本語法單位：?jiǎn)卧~，生成單詞序列。語法單位：?jiǎn)卧~，生成單詞序列。 剝?nèi)ピ闯绦蛑械淖⑨專▔K、行）和剝?nèi)ピ闯绦蛑械淖⑨專▔K、行）和“空白

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

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

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

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

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

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

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

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

10、ASCAL） DO10I會(huì)識(shí)別為DO 10 I，而不是將之識(shí)別為一個(gè)標(biāo)識(shí)符。n若允許關(guān)鍵字作為標(biāo)識(shí)符的前綴（非標(biāo)準(zhǔn)若允許關(guān)鍵字作為標(biāo)識(shí)符的前綴（非標(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單詞符號(hào)的識(shí)別單詞符號(hào)的識(shí)別超前掃描技術(shù)超前掃描技術(shù)n超前掃描技術(shù)：在無法判別和識(shí)別當(dāng)前單詞時(shí)，先向超前掃描技術(shù)：在無法判別和識(shí)別當(dāng)前單詞時(shí)，先向前掃描

11、若干個(gè)字符，直到可以進(jìn)行判斷和識(shí)別為止。前掃描若干個(gè)字符，直到可以進(jìn)行判斷和識(shí)別為止。n嵌套括號(hào)的分層 由外向內(nèi)編號(hào)：第一層，第二層，n語句內(nèi)容的分層 按包含它的括號(hào)層次確定 不被括號(hào)包含的語句內(nèi)容稱為屬于第零層 不被括號(hào)包含的等號(hào)和逗號(hào)分別稱為零層等號(hào)和零層逗號(hào)n利用超前掃描到的零層等號(hào)和零層逗號(hào)來識(shí)別單詞符號(hào)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包含零層等號(hào)的語句：賦值語句、包含零層等號(hào)的語句：賦值語句、DODO語句、函數(shù)定語句、函數(shù)定義語句以及某些邏輯義語句以及某些邏輯IFIF語句語句n既包含零層等號(hào)，也包含零層逗號(hào)的語句：既包含零層等號(hào)，也包含零層逗號(hào)的語句：DODO語句語句n如，函數(shù)或數(shù)組賦值語句如，函數(shù)或數(shù)組賦值語句 f(a1,a2,an)=ef(a1,a2,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ù)向前掃描,（左移）（左移）,=,=,=,=（復(fù)

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

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

15、21由一組矢線連接的有限個(gè)結(jié)點(diǎn)所組成的有向圖。每個(gè)結(jié)點(diǎn)代表在識(shí)別分析過程中掃描器所處的狀態(tài)，其中含有一個(gè)初始狀態(tài)和若干個(gè)終態(tài)。在圖中，狀態(tài)用圓圈表示，終態(tài)用雙層圓圈表示。狀態(tài)之間可用有向邊連接，其上標(biāo)記一字符a，表示從有向邊的射出狀態(tài)出發(fā)，識(shí)別一字符a后，將進(jìn)入箭頭所指狀態(tài)（結(jié)點(diǎn)）n凡能用正規(guī)文法描述的語言，均可由某種有限狀態(tài)算法進(jìn)行分析。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個(gè)狀態(tài)個(gè)狀態(tài)(結(jié)結(jié)點(diǎn)點(diǎn))。用。用VN中的每個(gè)符號(hào)分別標(biāo)記其中的中的每個(gè)符號(hào)分別標(biāo)記其中的k個(gè)個(gè)結(jié)點(diǎn)，且令結(jié)點(diǎn)，且

16、令G的開始符的開始符S為初態(tài)結(jié)點(diǎn)；余下為初態(tài)結(jié)點(diǎn)；余下的一個(gè)結(jié)點(diǎn)作為終態(tài)結(jié)點(diǎn)，用的一個(gè)結(jié)點(diǎn)作為終態(tài)結(jié)點(diǎn)，用F( VN)標(biāo)記。標(biāo)記。23A狀態(tài)轉(zhuǎn)換圖的構(gòu)造原則狀態(tài)轉(zhuǎn)換圖的構(gòu)造原則G G的每一個(gè)非終結(jié)符號(hào)代表一結(jié)點(diǎn)的每一個(gè)非終結(jié)符號(hào)代表一結(jié)點(diǎn)( (狀態(tài)狀態(tài)) ) 開始符號(hào)開始符號(hào)S S作為初始狀態(tài)作為初始狀態(tài) 設(shè)一符號(hào)設(shè)一符號(hào)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é)符號(hào)出現(xiàn)過的終結(jié)符號(hào) 某些情況下也可考慮直接將某些情況下也可考慮直接將A

17、A作為終態(tài)作為終態(tài)BSFBAAFAFA24例例:GZ:GZ:Z0U1VZ0U1VU 1Z1U 1Z1V 0Z0V 0Z0 25例例:GZ: :GZ: 狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖:Z0U1VZ0U1VU 1Z1U 1Z1 1 V 0Z0V 0Z0 0 1 初態(tài)初態(tài) 1 0 0 ZUVF26無符號(hào)數(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無符號(hào)數(shù)文法對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖無符號(hào)數(shù)文法對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖n例如,P48中定義的無符號(hào)數(shù)的文法對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖為(化

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

19、狀態(tài)狀態(tài),所掃描的字符為所掃描的字符為ai+1,在結(jié)點(diǎn)在結(jié)點(diǎn)Ai所所射出的諸矢線中射出的諸矢線中,尋找標(biāo)記為尋找標(biāo)記為ai+1的矢線的矢線(若不存在若不存在,則則表明表明w有語法錯(cuò)誤有語法錯(cuò)誤),讀入讀入ai+1,并進(jìn)入狀態(tài)并進(jìn)入狀態(tài)Ai+1;(3)重復(fù)重復(fù)(2),直到直到w中所有字符被讀完且恰好進(jìn)入終態(tài)中所有字符被讀完且恰好進(jìn)入終態(tài)F時(shí)時(shí),宣告整個(gè)識(shí)別結(jié)束宣告整個(gè)識(shí)別結(jié)束,w可被接受可被接受.29例例:GZ: :GZ: 狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖:Z0U1VZ0U1VU 1Z1U 1Z1 1 V 0Z0V 0Z0 0 1 初態(tài)初態(tài) 1 0 0 1 1=011001=0110012 2=111001

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

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

22、VU 1Z1U 1Z1 1 V 0Z0V 0Z0 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)的,則從前面的討則從前面的討論可以看出如下事實(shí)：論可以看出如下事實(shí)：(1)在利用在利用對(duì)符號(hào)串對(duì)符號(hào)串 進(jìn)行識(shí)別時(shí)進(jìn)行識(shí)別時(shí),中每次狀態(tài)的轉(zhuǎn)換都模擬了一中每次狀態(tài)的轉(zhuǎn)換都模擬了一步直接推導(dǎo)步直

23、接推導(dǎo),即識(shí)別方法即識(shí)別方法(或稱分析方法或稱分析方法) 是是“ ”的的;(2)因因右線性文法右線性文法只有形如只有形如的產(chǎn)生式，所以推導(dǎo)的每一的產(chǎn)生式，所以推導(dǎo)的每一步所得句型只含一個(gè)非終結(jié)符，且必出現(xiàn)在句型的最右端，所以步所得句型只含一個(gè)非終結(jié)符，且必出現(xiàn)在句型的最右端，所以推導(dǎo)是推導(dǎo)是規(guī)范推導(dǎo)規(guī)范推導(dǎo)，每步所得的句型也必為，每步所得的句型也必為規(guī)范句型規(guī)范句型；(3)對(duì)于對(duì)于所識(shí)別的任一符號(hào)串所識(shí)別的任一符號(hào)串 ,必存在必存在G中的一個(gè)推導(dǎo)中的一個(gè)推導(dǎo) (即有即有反之反之,對(duì)于對(duì)于中任一句子中任一句子 ,必存在一條從初態(tài)必存在一條從初態(tài) 到終態(tài)到終態(tài)的路徑的路徑,此路徑上各矢線的標(biāo)記依次

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

25、使用 識(shí)別句子識(shí)別句子( (單詞符號(hào)單詞符號(hào)) )例例:100110:100110通過狀態(tài)圖可通過狀態(tài)圖可以確定是文法的句子以確定是文法的句子. . 識(shí)別過程對(duì)應(yīng)著歸約識(shí)別過程對(duì)應(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)換, ,對(duì)應(yīng)了形如對(duì)應(yīng)了形如 的產(chǎn)生式的產(chǎn)生式,即將終結(jié)符 歸約成非終結(jié)符A A;n從狀態(tài)B B轉(zhuǎn)換到狀態(tài) ,對(duì)應(yīng)了形如對(duì)應(yīng)了形如的產(chǎn)生式的產(chǎn)生式,即將歸約為 ;n如此下去,直到從某狀態(tài) 轉(zhuǎn)換到狀

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

27、態(tài).n若為“”,則說明輸入符號(hào)串有誤,拒絕接受.掃描器將調(diào)用出錯(cuò)處理程序進(jìn)行處理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)作記下輸入串中當(dāng)前位置及該狀態(tài)相關(guān)聯(lián)的動(dòng)作; 40 else if(FlagOfFS=NoneSeen) 報(bào)告詞法

28、錯(cuò)誤報(bào)告詞法錯(cuò)誤; 略過當(dāng)前詞文及輸入字符略過當(dāng)前詞文及輸入字符; CurStat=0; else 回退到最近經(jīng)歷的那個(gè)終態(tài)的輸入字符位置回退到最近經(jīng)歷的那個(gè)終態(tài)的輸入字符位置; 執(zhí)行所記錄的該終態(tài)的相關(guān)動(dòng)作執(zhí)行所記錄的該終態(tài)的相關(guān)動(dòng)作; / 41貪心策略n目的是獲得最長(zhǎng)匹配單詞（1）若當(dāng)前狀態(tài)對(duì)輸入符號(hào)有后繼動(dòng)作，則繼續(xù)進(jìn)行狀態(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)所對(duì)應(yīng)的語義動(dòng)作；（4）若當(dāng)前狀態(tài)已無后繼狀態(tài)，并且此前沒有經(jīng)歷過終態(tài)，則表明輸入字符串有詞法錯(cuò)誤，報(bào)錯(cuò)，并略過余下

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

30、errordw =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)換圖實(shí)際上是有限自動(dòng)機(jī)的圖形表示453.3.1 確定的有限自動(dòng)機(jī)DFAn抽象地看抽

31、象地看, ,狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖由五個(gè)部分組成由五個(gè)部分組成: :(1)(1)有限個(gè)狀態(tài)之集有限個(gè)狀態(tài)之集, ,記作記作K K; ;(2)(2)有限個(gè)輸入符號(hào)組成的字母表有限個(gè)輸入符號(hào)組成的字母表, ,記作記作 ; ;(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, ,且輸入符號(hào)為且輸入符號(hào)為a a, ,則進(jìn)入下一個(gè)狀態(tài)為則進(jìn)入下一個(gè)狀態(tài)為q q; ;(4)(4)S S0 0 K K, ,初始初始( (開始開始) )狀態(tài)狀態(tài); ;(5)(5)若干個(gè)終態(tài)之集若干個(gè)終態(tài)之集: : Z(Z( K

32、)K)由上述五個(gè)要素組成的五元式由上述五個(gè)要素組成的五元式 M=(K, M=(K, , f,S, f,S0 0,Z ),Z )稱為稱為一個(gè)一個(gè)確定的有限自動(dòng)機(jī)確定的有限自動(dòng)機(jī) ( (DFADFA: : D Deterministic eterministic F Finite inite A Automatautomata) )由此可見由此可見, ,DFADFA實(shí)際上是狀態(tài)轉(zhuǎn)換圖的形式描述實(shí)際上是狀態(tài)轉(zhuǎn)換圖的形式描述( (數(shù)學(xué)定數(shù)學(xué)定義義),),狀態(tài)轉(zhuǎn)換圖是狀態(tài)轉(zhuǎn)換圖是DFADFA的幾何的幾何( (圖形圖形) )表示表示. .46ZUVF2=1001已知已知DFA M=(K, , f,S0,Z

33、 )，其中：，其中：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所接受的符號(hào)串的全體稱為M的接受集或M接受的語言，記為L(zhǎng)(M),即 L(M)= x | f(S0,x) Z,x* nM接受(或識(shí)別)某符號(hào)串x*：從初態(tài)S0出發(fā),經(jīng)一恰好標(biāo)有x 的路徑后可達(dá)到某終態(tài)S Z 。用f描述就是: S Z, f(S0,x)=S n將轉(zhuǎn)換函數(shù)f 的定義域拓廣到K* ，可以得到 f:

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

35、p,a)=p1,f(p1,b)=p2,f(p,f(p,x)=f(f(p,a),bcd.)=f(f(p,a),bcd.)49n確定的FA：在狀態(tài)轉(zhuǎn)換的每一步，根據(jù)FA當(dāng)前的狀態(tài)及掃描的輸入字符，便能唯一地唯一地確定FA的下一狀態(tài)。在轉(zhuǎn)換圖上看，若|=n，則任何結(jié)點(diǎn)所引出的矢線至多有n條，且矢線上的標(biāo)記均不同。n例如，P51圖3-4所對(duì)應(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)換圖的算法，同樣適用于構(gòu)造DFA。n可以證明， 正規(guī)文法G， DFA M，使L(M)

36、=L(G)，反之亦然。50 在相應(yīng)的狀態(tài)轉(zhuǎn)換圖中，在相應(yīng)的狀態(tài)轉(zhuǎn)換圖中，就會(huì)出現(xiàn)這樣的結(jié)點(diǎn)就會(huì)出現(xiàn)這樣的結(jié)點(diǎn)U，它具有多條標(biāo)記為同一它具有多條標(biāo)記為同一輸入符號(hào)輸入符號(hào)a的矢線的矢線在在U狀態(tài)下，輸入符號(hào)為狀態(tài)下，輸入符號(hào)為a時(shí)，時(shí)，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的含義同DFA,轉(zhuǎn)換函數(shù)f的定義為 f: K(K),即將(Si,aj

37、)映射到K的一個(gè)子集Sk1,Skm n類似地，我們可把f的定義域拓廣到K* ： (1) f(S,)=S; (2) f(S,aw)=f(f(S,a),w) a,w*.52n所有為所有為NFANFA M M所接受的符號(hào)串之集稱為所接受的符號(hào)串之集稱為NFA MNFA M的接受的接受集（或識(shí)別集），記作集（或識(shí)別集），記作 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中的元素中的元素（終態(tài)），即至少存在一條從初態(tài)（終態(tài)），即至少存

38、在一條從初態(tài)S S0 0到某一終態(tài)的路到某一終態(tài)的路徑，此路徑上的符號(hào)之連接恰為徑，此路徑上的符號(hào)之連接恰為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識(shí)別符號(hào)串識(shí)別符號(hào)串a(chǎn)babbababb的路徑的路徑 注意注意，NFANFA識(shí)別輸入符號(hào)串時(shí)有一個(gè)試探過程，為了能識(shí)別輸入符號(hào)串時(shí)有一個(gè)試探過程，為了能走到終態(tài)，往往要走許多彎路（走到終態(tài)，往往要走許多彎路（帶回溯帶回溯），這影響了），這影響了FAFA的效率。的效率。n符號(hào)串符號(hào)串

39、ababbababb的識(shí)別路徑的識(shí)別路徑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的等價(jià)性，只需證明的等價(jià)性，只需證明每一個(gè)每一個(gè)NFA都可以確定化。都可以確定化。n確定化：對(duì)任意確定化：對(duì)任意NFA M，構(gòu)造一個(gè)，構(gòu)造一個(gè)DFA M，使得使得L(M)=L(M)。n思路：

40、令思路：令M的某個(gè)狀態(tài)與的某個(gè)狀態(tài)與M的某個(gè)狀態(tài)子集的某個(gè)狀態(tài)子集相對(duì)應(yīng)，并使得在相對(duì)應(yīng)，并使得在M掃描與掃描與M相同的輸入符相同的輸入符號(hào)時(shí)，保持對(duì)號(hào)時(shí)，保持對(duì)M的狀態(tài)進(jìn)行跟蹤（能根據(jù)的狀態(tài)進(jìn)行跟蹤（能根據(jù)M的狀態(tài)確定的狀態(tài)確定M的狀態(tài)）。的狀態(tài)）。55證明 對(duì)于字母表對(duì)于字母表 上的任一上的任一NFA M，必存，必存在與在與M等價(jià)的等價(jià)的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).方法如下：方法如下：1.1.K= (K).為表示方便為表示方便,如如K某子集

41、為某子集為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等價(jià)的等價(jià)性等價(jià)的等價(jià)性.為此為此,對(duì)輸入符號(hào)串對(duì)輸入符號(hào)串|x|=n的長(zhǎng)度進(jìn)行的長(zhǎng)度進(jìn)行歸納歸納,以證明如下論斷以證明如下論斷: f(S0,x)= S1,S2,Si f(S0,x)=S1,S2,Si (S0=S0)當(dāng)當(dāng)|x|=0 (即即x= )

42、時(shí)時(shí),由于總有由于總有 f(S0, )=S0, f(S0, )=S0 ,即即f(S0, )=S0,故論斷成立故論斷成立.設(shè)對(duì)于長(zhǎng)度小于或等于設(shè)對(duì)于長(zhǎng)度小于或等于m的任何輸入串的任何輸入串x論斷均成立論斷均成立,即即f(S0,x)=S1,S2,Sif(S0,x)=S1,S2,Si現(xiàn)證明對(duì)于輸入串現(xiàn)證明對(duì)于輸入串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(S0,xa)=f(f(S0,x),a)=f(S1,Si,a)

43、 (歸納假設(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是等價(jià)的是等價(jià)的,今后統(tǒng)稱今后統(tǒng)稱FA. 還應(yīng)指出，確定化時(shí)所得的還應(yīng)指出，確定化時(shí)所得的DFA的狀態(tài)數(shù)是很大的，的狀態(tài)數(shù)是很大的，往往有許多無用狀態(tài)（往往有許多無用狀態(tài)（即那些從初態(tài)即那些從初態(tài)S0不可達(dá)的狀態(tài)不可達(dá)的狀態(tài)或那些從其出發(fā)不能到達(dá)終態(tài)的狀態(tài)或那些從其出發(fā)不能到達(dá)終態(tài)的狀態(tài)），這些狀態(tài)可），這些狀態(tài)可從從DFA中刪除。中刪除。58例例3.23.2 M=(S0,S1,a

44、,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因?yàn)橐驗(yàn)?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 | new state | | S0 | S0,S1 S1 |

45、 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中中, ,允許對(duì)允許對(duì) 也作狀也作狀態(tài)轉(zhuǎn)移態(tài)轉(zhuǎn)移, ,則這樣的則這樣的FAFA稱為具有稱為具有 動(dòng)作的動(dòng)作的FA.n右圖就是一個(gè)具有具有 動(dòng)作的動(dòng)作的FA。其中其中, ,有的矢線上標(biāo)記有的矢線上標(biāo)記為為（在此看作一個(gè)符號(hào)在此看作一個(gè)符號(hào)）。標(biāo)記為 的矢線對(duì)識(shí)別符號(hào)串無影響,但卻改變了當(dāng)前的狀態(tài)狀態(tài).例如,上圖的FA中,從狀態(tài)0到狀態(tài)3存在路徑: 0(a)0(a)0()2(c)2(c)2()3,即M識(shí)別了aacc=

46、aacc.61 定義為定義為 M=(K,f,S0,Z),其中,f定義為 f:K()(K).n在在中中, 視為一個(gè)視為一個(gè)輸入符號(hào)輸入符號(hào), ,在矩陣表在矩陣表示中示中, ,也有相應(yīng)的列也有相應(yīng)的列。例如，對(duì)于前面例如，對(duì)于前面的的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)記組成的符號(hào)串恰好為的標(biāo)記組成的符號(hào)串恰好為x, 標(biāo)記中可以包含若標(biāo)記中可以包含若干個(gè)干個(gè) 。62狀態(tài)S的-閉包：-CL

47、OSURE(S)n狀態(tài)S的 -閉包閉包：記為-CLOSURE(S),它是從S出發(fā)經(jīng)過若干標(biāo)記為的矢線所能達(dá)到的全部狀態(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例如例如，對(duì)于右圖的NFA， -CLOSURE(0)=0,1,2,3；-CLOSURE(1)=1；-CLOSURE(2)=2,3；-CLOSURE(3)=3.64轉(zhuǎn)

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

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

50、(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，就可把識(shí)別各種不同單詞的FA用矢線（并連）連接起來，組成一個(gè)單一的NFA，經(jīng)確定化后可得識(shí)別所有單詞的DFA，由此可設(shè)計(jì)編譯程序的詞法分析器。n例如，某語言的單詞有： 1.BEGIN 2.END3.IF 4.THEN5.ELSE 6.標(biāo)識(shí)符7.無符號(hào)整數(shù) 8. 9. = 10. =11. 12. 13.= 可分別構(gòu)造出識(shí)別各類單詞的FA,

51、然后將其合并為一個(gè)大FA,如書中P65圖3-11所示。68n為具有為具有 動(dòng)作的動(dòng)作的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)過任意條矢線所能到達(dá)的狀態(tài)集合作為矢線所能到達(dá)的狀態(tài)集合作為M的初態(tài)的初態(tài)q0 ；然后從；然后從q0出發(fā)，將對(duì)輸入符號(hào)出發(fā)，將對(duì)輸入符號(hào)a進(jìn)行狀態(tài)轉(zhuǎn)移所能到達(dá)進(jìn)行狀態(tài)轉(zhuǎn)移所能到達(dá)的狀態(tài)（包括轉(zhuǎn)移后再經(jīng)過的狀態(tài)（包括轉(zhuǎn)移后再經(jīng)過 矢線所能到達(dá)的狀態(tài)）矢線所能到達(dá)的狀態(tài)）所組成的集合作為所組成的集合作為M的狀態(tài)，如此反復(fù)，直到無新的狀態(tài)，如此反

52、復(fù)，直到無新狀態(tài)產(chǎn)生為止。狀態(tài)產(chǎn)生為止。69構(gòu)造構(gòu)造K,f和和Z的遞歸過程的遞歸過程1. 令令 K= -CLOSURE(S0); f= ;2. 對(duì)對(duì)K中尚未被標(biāo)記的狀態(tài)中尚未被標(biāo)記的狀態(tài)qi=Si1,Si2,Sim:(1)標(biāo)記標(biāo)記qi;(2)對(duì)于每個(gè)對(duì)于每個(gè)a,令令Ta=f(Si1,Si2,Sim,a); 對(duì)對(duì)a轉(zhuǎn)移轉(zhuǎn)移 令令 qj= -CLOSURE(Ta); 進(jìn)行進(jìn)行 矢線轉(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)記的狀態(tài);4. 令令Z=qj | qj Z (這里把這里把qj

53、視為集合視為集合)70確定化具有確定化具有 動(dòng)作的動(dòng)作的NFANFA的例子的例子例例3.4 考慮右圖具有考慮右圖具有 動(dòng)作的動(dòng)作的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) = -CLOSURE(2) = 2,3= q2 =K;71確定

54、化具有確定化具有 動(dòng)作的動(dòng)作的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 M 如下所示：如下所示：q1q0q2abbcc72n需要說明的

55、是需要說明的是,上述算法也適合于不含上述算法也適合于不含 產(chǎn)生式的產(chǎn)生式的NFA的確定化的確定化. 對(duì)于書中圖對(duì)于書中圖3-11所示的所示的NFA利用上述算法所得利用上述算法所得的的DFA如如 P67圖圖3-13所示所示. 其中其中,圓圈中的數(shù)字是原圓圈中的數(shù)字是原NFA的狀態(tài)編號(hào)的狀態(tài)編號(hào),在圖在圖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.733.3.6 DFA狀態(tài)數(shù)的最小化n對(duì)于一對(duì)于一DFA來說

56、來說,其狀態(tài)數(shù)可能并不是最小的其狀態(tài)數(shù)可能并不是最小的.原因是原因是DFA中有些狀態(tài)是中有些狀態(tài)是“等價(jià)等價(jià)”的的.為得到高效率的為得到高效率的DFA,需需將這些將這些“等價(jià)等價(jià)”狀態(tài)合并狀態(tài)合并,這就是這就是DFA的最小化的最小化.nDFA M的最小化的最小化: 構(gòu)造等價(jià)的構(gòu)造等價(jià)的DFA MDFA M其狀態(tài)數(shù)達(dá)到最其狀態(tài)數(shù)達(dá)到最小小. .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,w) Z f(t,w) Z,則則 s與與 t不可區(qū)分，稱不可區(qū)

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

58、的狀態(tài)是待區(qū)分的.現(xiàn)對(duì)每個(gè)子集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 )進(jìn)行考查,看其是否可區(qū)分.75DFA最小化算法(續(xù)) 對(duì)于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)換后落在不同的等價(jià)類中），則根據(jù) S Su u和S Sv v被某個(gè)w w所區(qū)分可知,S Si ip p 和S Si iq

59、 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的方法見下頁(yè)）。3.若 newnew. 不等于,則令 = = new.new. 轉(zhuǎn)2.4.對(duì)于最終的 ，從每個(gè)劃分塊I Ii i中任選一狀態(tài)為代表，構(gòu)成KK。若I Ii i中含有初態(tài)，則其代表也為初態(tài)；若I Ii i Z Z，則I Ii i 的代表 ZZ。刪除非代表狀態(tài)，

60、將引入非代表狀態(tài)的矢線引向代表狀態(tài).76細(xì)分劃分塊的方法.),(,),(),(,21中同一子集落入使得個(gè)更小的子集分為則將個(gè)不同的子集中的狀態(tài)分別落入若令對(duì)每個(gè)子集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,1,2a=1, 未區(qū)分未區(qū)分; 0,2b=2,1b=3, 1與與0,2可