編譯原理-劉善梅-第3章 詞法分析4ppt課件

1、第三章第三章 詞法分析詞法分析n對(duì)于詞法分析器的要求對(duì)于詞法分析器的要求n詞法分析器的設(shè)計(jì)詞法分析器的設(shè)計(jì)n正規(guī)表達(dá)式與有窮自動(dòng)機(jī)正規(guī)表達(dá)式與有窮自動(dòng)機(jī)n詞法分析器的自動(dòng)產(chǎn)生詞法分析器的自動(dòng)產(chǎn)生-LEX-LEX詞法分析詞法分析n詞法分析的任務(wù)：從左至右逐個(gè)字符地詞法分析的任務(wù)：從左至右逐個(gè)字符地對(duì)源程序進(jìn)行掃描，產(chǎn)生一個(gè)個(gè)單詞符對(duì)源程序進(jìn)行掃描，產(chǎn)生一個(gè)個(gè)單詞符號(hào)。號(hào)。n詞法分析器詞法分析器(Lexical Analyzer) (Lexical Analyzer) 又稱掃又稱掃描器描器(Scanner)(Scanner)：執(zhí)行詞法分析的程序：執(zhí)行詞法分析的程序3.13.1 對(duì)于詞法分析器的要求

2、對(duì)于詞法分析器的要求一、詞法分析器的功能和輸出形式一、詞法分析器的功能和輸出形式功能功能: :輸入源程序、輸出單詞符號(hào)輸入源程序、輸出單詞符號(hào)單詞符號(hào)的種類：?jiǎn)卧~符號(hào)的種類：基本字：如基本字：如 begin begin，repeatrepeat，標(biāo)識(shí)符標(biāo)識(shí)符表示各種名字：如變量名、數(shù)表示各種名字：如變量名、數(shù)組名和過(guò)程名組名和過(guò)程名常數(shù)：各種類型的常數(shù)常數(shù)：各種類型的常數(shù)運(yùn)算符：運(yùn)算符：+ +，- -，* *，/ /，界符：逗號(hào)、分號(hào)、括號(hào)和空白界符：逗號(hào)、分號(hào)、括號(hào)和空白n輸出的單詞符號(hào)的表示形式輸出的單詞符號(hào)的表示形式: :n( (單詞種別，單詞自身的值單詞種別，單詞自身的值) )n單詞種

3、別通常用整數(shù)編碼表示。單詞種別通常用整數(shù)編碼表示。n若一個(gè)種別只有一個(gè)單詞符號(hào)，則種別編若一個(gè)種別只有一個(gè)單詞符號(hào)，則種別編碼就代表該單詞符號(hào)。假定基本字、運(yùn)算碼就代表該單詞符號(hào)。假定基本字、運(yùn)算符和界符都是一符一種。符和界符都是一符一種。n若一個(gè)種別有多個(gè)單詞符號(hào)，則對(duì)于每個(gè)若一個(gè)種別有多個(gè)單詞符號(hào)，則對(duì)于每個(gè)單詞符號(hào)，給出種別編碼和自身的值。單詞符號(hào)，給出種別編碼和自身的值。n標(biāo)識(shí)符單列一種；標(biāo)識(shí)符自身的值表示成標(biāo)識(shí)符單列一種；標(biāo)識(shí)符自身的值表示成按機(jī)器字節(jié)劃分的內(nèi)部碼。按機(jī)器字節(jié)劃分的內(nèi)部碼。n常數(shù)按類型分種；常數(shù)的值則表示成標(biāo)準(zhǔn)常數(shù)按類型分種；常數(shù)的值則表示成標(biāo)準(zhǔn)的二進(jìn)制形式。的二進(jìn)制

4、形式。例例 FORTRAN FORTRAN程序程序nIF (5.EQ.M) GOTO 100IF (5.EQ.M) GOTO 100n輸出單詞符號(hào)：輸出單詞符號(hào)：n邏輯邏輯IFIF(34(34，-)-)n左括號(hào)左括號(hào)(2(2，-)-)n整常數(shù)整常數(shù)(20(20， 5 5的二進(jìn)制的二進(jìn)制) )n等號(hào)等號(hào)(6(6，-)-)n標(biāo)識(shí)符標(biāo)識(shí)符(26(26， M) M)n右括號(hào)右括號(hào)(16(16，-)-)nGOTOGOTO(30(30，-)-)n標(biāo)號(hào)標(biāo)號(hào)(19(19， 100 100的二進(jìn)制的二進(jìn)制) )n助憶符：直接用編碼表示不便于記憶，因此用助憶助憶符：直接用編碼表示不便于記憶，因此用助憶符來(lái)表示編碼

5、。符來(lái)表示編碼。例：例：IFIF(34(34，-) (IF-) (IF，-) -) 左括號(hào)左括號(hào)(2(2，-) (-) (，-) -) 等號(hào)等號(hào)(6(6，-) (=-) (=，-) -) 例例 C C程序程序n while (i=j) i-;n輸出單詞符號(hào)：輸出單詞符號(hào)：nnnn=, - nnnnn二、詞法分析器作為一個(gè)獨(dú)立子程序二、詞法分析器作為一個(gè)獨(dú)立子程序n詞法分析是作為一個(gè)獨(dú)立的階段，是否詞法分析是作為一個(gè)獨(dú)立的階段，是否應(yīng)當(dāng)將其處理為一遍呢？應(yīng)當(dāng)將其處理為一遍呢？n作為獨(dú)立階段的優(yōu)點(diǎn)：結(jié)構(gòu)簡(jiǎn)潔、清晰作為獨(dú)立階段的優(yōu)點(diǎn)：結(jié)構(gòu)簡(jiǎn)潔、清晰和條理化，有利于集中考慮詞法分析一和條理化，有利于集

6、中考慮詞法分析一些枝節(jié)問(wèn)題。些枝節(jié)問(wèn)題。n不作為一遍：將其處理為一個(gè)子程序。不作為一遍：將其處理為一個(gè)子程序。詞法分析器詞法分析器詞法分詞法分析器析器語(yǔ)法分語(yǔ)法分析器析器符號(hào)表符號(hào)表源程序源程序單詞符號(hào)單詞符號(hào)取下一單詞取下一單詞.詞法分析器的結(jié)構(gòu)詞法分析器的結(jié)構(gòu)預(yù)處理預(yù)處理子程序子程序掃描器掃描器輸入緩沖區(qū)輸入緩沖區(qū)掃描緩沖區(qū)掃描緩沖區(qū)單詞符號(hào)單詞符號(hào)輸入輸入3.2 詞法分析器的設(shè)計(jì)刪除無(wú)用的空白、跳格、回刪除無(wú)用的空白、跳格、回車和換行等編輯性字符車和換行等編輯性字符區(qū)分標(biāo)號(hào)區(qū)、捻接續(xù)行和給區(qū)分標(biāo)號(hào)區(qū)、捻接續(xù)行和給出句末符等出句末符等 WhatALongWord WhatALongWord

7、 WhatALongWord WhatALongWon掃描緩沖區(qū)掃描緩沖區(qū) 起點(diǎn)起點(diǎn) 搜索搜索指示器指示器 指示器指示器一、掃描緩沖區(qū)一、掃描緩沖區(qū) 二、單詞符號(hào)的識(shí)別二、單詞符號(hào)的識(shí)別: :超前搜索超前搜索以基本字的識(shí)別為例：以基本字的識(shí)別為例：例如例如:DO99K=1，10 DO 99 K = 1，10 IF(5.EQ.M)GOTO55 IF (5.EQ.M) GOTO 55DO99K=1.10IF(5)=55需要超前搜索才能確定哪些是基本字需要超前搜索才能確定哪些是基本字幾點(diǎn)限制幾點(diǎn)限制不必使用超前搜索不必使用超前搜索n所有基本字都是保留字；用戶不能用它們作自己所有基本字都是保留字；用戶

8、不能用它們作自己的標(biāo)識(shí)符；的標(biāo)識(shí)符；n 基本字作為特殊的標(biāo)識(shí)符來(lái)處理基本字作為特殊的標(biāo)識(shí)符來(lái)處理;不用特殊的狀不用特殊的狀態(tài)圖來(lái)識(shí)別，只要查保留字表。態(tài)圖來(lái)識(shí)別，只要查保留字表。n如果基本字、標(biāo)識(shí)符和常數(shù)或標(biāo)號(hào)之間沒(méi)有如果基本字、標(biāo)識(shí)符和常數(shù)或標(biāo)號(hào)之間沒(méi)有確定的運(yùn)算符或界符作間隔，則必須使用一個(gè)空確定的運(yùn)算符或界符作間隔，則必須使用一個(gè)空白符作間隔白符作間隔三、狀態(tài)轉(zhuǎn)換圖三、狀態(tài)轉(zhuǎn)換圖1 1 概念概念狀態(tài)轉(zhuǎn)換圖是一張有限方向圖。狀態(tài)轉(zhuǎn)換圖是一張有限方向圖。213a數(shù)字?jǐn)?shù)字結(jié)點(diǎn)代表狀態(tài)，用圓圈表示。結(jié)點(diǎn)代表狀態(tài)，用圓圈表示。狀態(tài)之間用箭弧連結(jié)，箭弧狀態(tài)之間用箭弧連結(jié)，箭弧上的標(biāo)記上的標(biāo)記( (字

9、符字符) )代表射出結(jié)代表射出結(jié)狀態(tài)下可能出現(xiàn)的輸入字符狀態(tài)下可能出現(xiàn)的輸入字符或字符類?；蜃址悺Ｒ粡堔D(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)為初態(tài)，至少要有一個(gè)終態(tài)。有一個(gè)為初態(tài)，至少要有一個(gè)終態(tài)。識(shí)別標(biāo)識(shí)符的狀態(tài)轉(zhuǎn)換圖識(shí)別標(biāo)識(shí)符的狀態(tài)轉(zhuǎn)換圖123字母字母其他其他字母或數(shù)字字母或數(shù)字*識(shí)別整常數(shù)的狀態(tài)轉(zhuǎn)換圖識(shí)別整常數(shù)的狀態(tài)轉(zhuǎn)換圖123數(shù)字?jǐn)?shù)字其他其他數(shù)字?jǐn)?shù)字*n一個(gè)狀態(tài)轉(zhuǎn)換圖可用于識(shí)別一個(gè)狀態(tài)轉(zhuǎn)換圖可用于識(shí)別( (或接受或接受) )一定一定的字符串。的字符串。詞法分析器設(shè)計(jì)流程詞法分析器設(shè)計(jì)流程 某程序設(shè)計(jì)語(yǔ)言的某程序設(shè)計(jì)語(yǔ)言的單詞符號(hào)串集單詞符號(hào)串集 分析詞法規(guī)

10、則分析詞法規(guī)則 畫出識(shí)別單詞的狀態(tài)圖畫出識(shí)別單詞的狀態(tài)圖 根據(jù)狀態(tài)圖寫詞法分析器程序根據(jù)狀態(tài)圖寫詞法分析器程序單單 詞詞 符符 號(hào)號(hào) 種種 別別 編編 碼碼 助助 憶憶 符符 內(nèi)內(nèi) 碼碼 值值 D DI IM M 1 1 $ $D DI IM M - - I IF F 2 2 $ $I IF F - - D DO O 3 3 $ $D DO O - - S ST TO OP P 4 4 $ $S ST TO OP P - - E EN ND D 5 5 $ $E EN ND D - - 標(biāo)標(biāo) 識(shí)識(shí) 符符 6 6 $ $I ID D 內(nèi)內(nèi) 部部 字字 符符 串串 常常 數(shù)數(shù) ( (數(shù)數(shù) ) )

11、7 7 $ $I IN NT T 標(biāo)標(biāo) 準(zhǔn)準(zhǔn) 二二 進(jìn)進(jìn) 制制 形形 式式 = = 8 8 $ $A AS SS SI IG GN N - - _ _ 9 9 $ $P PL LU US S - - * * 1 10 0 $ $S ST TA AR R - - * * * 1 11 1 $ $P PO OW WE ER R - - ， 1 12 2 $ $C CO OM MM MA A - - ( ( 1 13 3 $ $L LP PA AR R - - ) ) 1 14 4 $ $R RP PA AR R - - 1 12 23 34 45 56 67 78 89 9101011111212

12、13130 0空白空白字母字母字母或數(shù)字字母或數(shù)字非字母與數(shù)字非字母與數(shù)字?jǐn)?shù)字?jǐn)?shù)字非數(shù)字非數(shù)字?jǐn)?shù)字?jǐn)?shù)字= =+ +* *非非* *, ,( () )其它其它* * * * *3 狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)思想：每個(gè)狀態(tài)結(jié)對(duì)應(yīng)一小段程序。思想：每個(gè)狀態(tài)結(jié)對(duì)應(yīng)一小段程序。做法做法:1)對(duì)不含回路的分叉結(jié)，可用一個(gè)對(duì)不含回路的分叉結(jié)，可用一個(gè)CASE語(yǔ)句語(yǔ)句或一組或一組IF-THEN-ELSE語(yǔ)句實(shí)現(xiàn)語(yǔ)句實(shí)現(xiàn)GetChar( );if (IsLetter( ) 狀態(tài)狀態(tài)j的對(duì)應(yīng)程序段的對(duì)應(yīng)程序段;else if (IsDigit( ) 狀態(tài)狀態(tài)k的對(duì)應(yīng)程序段的對(duì)應(yīng)程序段;else if (ch

13、=/) 狀態(tài)狀態(tài)l的對(duì)應(yīng)程序段的對(duì)應(yīng)程序段;else 錯(cuò)誤處理錯(cuò)誤處理;ijkl字母字母數(shù)字?jǐn)?shù)字/3 狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)2)對(duì)含回路的狀態(tài)結(jié)，可對(duì)應(yīng)一段由對(duì)含回路的狀態(tài)結(jié)，可對(duì)應(yīng)一段由WHILE語(yǔ)句構(gòu)成的程序語(yǔ)句構(gòu)成的程序.i字母或數(shù)字字母或數(shù)字其它其它jGetChar( );while (IsLetter( ) or IsDigit( )GetChar( );狀態(tài)狀態(tài)j的對(duì)應(yīng)程序段的對(duì)應(yīng)程序段3 狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)3)終態(tài)結(jié)表示識(shí)別出某種單詞符號(hào)，因此，終態(tài)結(jié)表示識(shí)別出某種單詞符號(hào)，因此，對(duì)應(yīng)語(yǔ)句為對(duì)應(yīng)語(yǔ)句為 RETURN (C，VAL) 其中，其中，C為單詞種別

14、，為單詞種別，VAL為單詞自身值為單詞自身值.n全局變量與過(guò)程全局變量與過(guò)程n1)ch 字符變量、存放最新讀入的源程字符變量、存放最新讀入的源程序字符序字符n2)strToken 字符數(shù)組，存放構(gòu)成單詞字符數(shù)組，存放構(gòu)成單詞符號(hào)的字符串符號(hào)的字符串n3)GetChar 子程序過(guò)程，把下一個(gè)字子程序過(guò)程，把下一個(gè)字符讀入到符讀入到 ch 中中n4)GetBC 子程序過(guò)程，跳過(guò)空白符，直子程序過(guò)程，跳過(guò)空白符，直至至 ch 中讀入一非空白符中讀入一非空白符n5)Concat 子程序，把子程序，把ch中的字符連接中的字符連接到到 strToken 6)IsLetter和和 IsDisgital 布爾

15、函數(shù)，布爾函數(shù)，判斷判斷ch中字符是否為字母和數(shù)字中字符是否為字母和數(shù)字7) Reserve 整型函數(shù)，對(duì)于整型函數(shù)，對(duì)于 strToken 中的字符串查找保留字表，若它是保留字中的字符串查找保留字表，若它是保留字則給出它的編碼，否則回送則給出它的編碼，否則回送08) Retract 子程序，把搜索指針回調(diào)一子程序，把搜索指針回調(diào)一個(gè)字符位置個(gè)字符位置9)InsertId 整型函數(shù)，將整型函數(shù)，將strToken中中的標(biāo)識(shí)符插入符號(hào)表，返回符號(hào)表指針的標(biāo)識(shí)符插入符號(hào)表，返回符號(hào)表指針10)InsertConst 整型函數(shù)過(guò)程，將整型函數(shù)過(guò)程，將strToken中的常數(shù)插入常數(shù)表，返回常中的常數(shù)

16、插入常數(shù)表，返回常數(shù)表指針。數(shù)表指針。 int code, value;strToken := “ ”; /*置置strToken為空串為空串*/GetChar(); GetBC();if (IsLetter()beginwhile (IsLetter() or IsDigit()beginConcat(); GetChar(); endRetract();/搜索指針回調(diào)搜索指針回調(diào)code := Reserve(); /判斷是否為保留字判斷是否為保留字if (code = 0) /標(biāo)識(shí)符標(biāo)識(shí)符beginvalue := InsertId(strToken);return ($ID, valu

17、e);endelsereturn (code, -); /保留字保留字endelse if (IsDigit()begin while (IsDigit() begin Concat( ); GetChar( ); endRetract();value := InsertConst(strToken);return($INT, value);endelse if (ch =) return ($ASSIGN, -);else if (ch =+) return ($PLUS, -);5=*6*+else if (ch =*)beginGetChar();if (ch =*) return ($

18、POWER, -);Retract(); return ($STAR, -);endelse if (ch =;) return ($SEMICOLON, -);else if (ch =() return ($LPAR, -);else if (ch =) return ($RPAR, -);else ProcError( );/* 錯(cuò)誤處理錯(cuò)誤處理*/將狀態(tài)圖的代碼一般化將狀態(tài)圖的代碼一般化n變量變量curState用于保存現(xiàn)有的狀態(tài)用于保存現(xiàn)有的狀態(tài)n用二維數(shù)組表示狀態(tài)圖：用二維數(shù)組表示狀態(tài)圖：n stateTransstatecharcurState=初態(tài)初態(tài)GetChar();Whi

19、le(stateTranscurStatech有定義有定義)/存在后繼狀態(tài)，讀入，拼接存在后繼狀態(tài)，讀入，拼接Contact();/轉(zhuǎn)入下一狀態(tài)，讀入下一字符轉(zhuǎn)入下一狀態(tài)，讀入下一字符curState=stateTranscurStatech；If curState是終態(tài)是終態(tài) then 返回返回strToken中的單詞中的單詞GetChar(); FA正規(guī)集正規(guī)集正規(guī)式正規(guī)式DFANFA正規(guī)文法正規(guī)文法3.3.13.3.23.3.33.3.43.3.5DFA3.3.63.3 3.3 正規(guī)表達(dá)式與有限自動(dòng)機(jī)正規(guī)表達(dá)式與有限自動(dòng)機(jī)3.3 3.3 正規(guī)表達(dá)式與有限自動(dòng)機(jī)正規(guī)表達(dá)式與有限自動(dòng)機(jī)n幾個(gè)

20、概念幾個(gè)概念: :n考慮一個(gè)有窮考慮一個(gè)有窮 字母表字母表 字符集字符集n其中每一個(gè)元素稱為一個(gè)字符其中每一個(gè)元素稱為一個(gè)字符n上的字上的字( (也叫字符串也叫字符串) ) 是指由是指由中的字中的字符所構(gòu)成的一個(gè)有窮序列符所構(gòu)成的一個(gè)有窮序列n不包含任何字符的序列稱為空字，記為不包含任何字符的序列稱為空字，記為n用用* *表示表示上的所有字的全體上的所有字的全體, ,包含空字包含空字n例如例如: : 設(shè)設(shè) =a =a， b b，那么，那么 * *=,a,b,aa,ab,ba,bb,aaa,.=,a,b,aa,ab,ba,bb,aaa,.n*的子集的子集U和和V的連接積定義為的連接積定義為nUV

21、 | U & V nV自身的自身的 n次積記為次積記為nVn=VVVn規(guī)定規(guī)定V0=，令，令n V*=V0V1V2V3 n稱稱V*是是V的閉包的閉包;n記記 VVV* ，稱，稱V+是是V的正規(guī)閉包。的正規(guī)閉包。3.3.1 正規(guī)式和正規(guī)集正規(guī)式和正規(guī)集n正規(guī)集可以用正規(guī)表達(dá)式簡(jiǎn)稱正規(guī)式正規(guī)集可以用正規(guī)表達(dá)式簡(jiǎn)稱正規(guī)式表示。表示。n正規(guī)表達(dá)式是表示正規(guī)集一種方法。一正規(guī)表達(dá)式是表示正規(guī)集一種方法。一個(gè)字集合是正規(guī)集當(dāng)且僅當(dāng)它能用正規(guī)個(gè)字集合是正規(guī)集當(dāng)且僅當(dāng)它能用正規(guī)式表示。式表示。n正規(guī)式和正規(guī)集的遞歸定義：正規(guī)式和正規(guī)集的遞歸定義：n對(duì)給定的字母表對(duì)給定的字母表n1)1) 和和都是都是上

22、的正規(guī)式，它們所表上的正規(guī)式，它們所表示的正規(guī)集為示的正規(guī)集為 和和; ;n2) 2) 任何任何a a ，a a是是上的正規(guī)式，它上的正規(guī)式，它所表示的正規(guī)集為所表示的正規(guī)集為a ;a ;3) 假定假定e1和和e2都是都是 上的正規(guī)式，它們所表示上的正規(guī)式，它們所表示的正規(guī)集為的正規(guī)集為L(zhǎng)(e1)和和L(e2)，那么，那么i) (e1|e2)為正規(guī)式，它所表示的正規(guī)集為為正規(guī)式，它所表示的正規(guī)集為L(zhǎng)(e1)L(e2)，ii) (e1.e2)為正規(guī)式，它所表示的正規(guī)集為為正規(guī)式，它所表示的正規(guī)集為L(zhǎng)(e1)L(e2)(連接積連接積)，iii) (e1)*為正規(guī)式，它所表示的正規(guī)集為為正規(guī)式，它所

23、表示的正規(guī)集為(L(e1)*（閉包，即任意有限次的自重復(fù)連（閉包，即任意有限次的自重復(fù)連接），接），僅由有限次使用上述三步驟而定義的表達(dá)式才僅由有限次使用上述三步驟而定義的表達(dá)式才是是 上的正規(guī)式，僅由這些正規(guī)式表示的字集上的正規(guī)式，僅由這些正規(guī)式表示的字集才是才是 上的正規(guī)集。上的正規(guī)集。n所有詞法結(jié)構(gòu)一般都可以用正規(guī)式描述。所有詞法結(jié)構(gòu)一般都可以用正規(guī)式描述。n若兩個(gè)正規(guī)式所表示的正規(guī)集相同，則稱若兩個(gè)正規(guī)式所表示的正規(guī)集相同，則稱這兩個(gè)正規(guī)式等價(jià)。如這兩個(gè)正規(guī)式等價(jià)。如nb(ab)b(ab)* *=(ba)=(ba)* *b b(a(a* *b b* *) )* *=(a|b)=(a|b

24、)* *n L( (ba)*b) = L(ba)*) L(b)= (L(ba)*L(b) = (L(b)L(a)* L(b) = ba* b = , ba, baba, bababa, b= b, bab, babab, bababab, L(b(ab)*) = L(b)L(ab)*) = L(b) (L(ab)*= L(b) (L(a)L(b)*=b ab* = b , ab, abab, ababab, = b, bab, babab, bababab, L(b(ab)*)= L( (ba)*b) b(ab)*=(ba)*bn對(duì)正規(guī)式，下列等價(jià)成立：對(duì)正規(guī)式，下列等價(jià)成立：ne1|e2 =

25、 e2|e1 交換律交換律ne1 |(e2|e3) = (e1|e2)|e3 結(jié)合律結(jié)合律ne1(e2e3) = (e1e2)e3 結(jié)合律結(jié)合律ne1(e2|e3) = e1e2|e1e3 分配律分配律n(e2|e3)e1 = e2e1|e3 e1分配律分配律ne = e = e e1e2 e2 e1 L(e1|e2) = L(e1 ) L(e2)= L(e2 ) L(e1)= L(e2|e1)FA正規(guī)集正規(guī)集正規(guī)式正規(guī)式DFANFA3.3.13.3.23.3.33.3.2 確定有限自動(dòng)機(jī)確定有限自動(dòng)機(jī)(DFA)n對(duì)狀態(tài)圖進(jìn)行形式化，則可以下定義：對(duì)狀態(tài)圖進(jìn)行形式化，則可以下定義：n自動(dòng)機(jī)自動(dòng)

26、機(jī)M M是一個(gè)五元式是一個(gè)五元式M=(S, M=(S, , f, S0, F), f, S0, F),其中：其中：n1. S: 1. S: 有窮狀態(tài)集，有窮狀態(tài)集，n2. 2. ：輸入字母表：輸入字母表( (有窮有窮) )，n3. f: 3. f: 狀態(tài)轉(zhuǎn)換函數(shù)，為狀態(tài)轉(zhuǎn)換函數(shù)，為S SS S的單值部的單值部分映射，分映射，f(sf(s，a)=sa)=s表示：當(dāng)現(xiàn)行狀態(tài)為表示：當(dāng)現(xiàn)行狀態(tài)為s s，輸入字符為輸入字符為a a時(shí)，將狀態(tài)轉(zhuǎn)換到下一狀態(tài)時(shí)，將狀態(tài)轉(zhuǎn)換到下一狀態(tài)s s。我們把我們把s s稱為稱為s s的一個(gè)后繼狀態(tài)。的一個(gè)后繼狀態(tài)。n4. S04. S0S S是唯一的一個(gè)初態(tài)；是唯一的

27、一個(gè)初態(tài)； n5 F5 FS S ：終態(tài)集：終態(tài)集( (可空可空) )。n例如：例如：DFA M=(0，1，2，3，a，b，f，0，3)， 其中：其中：f定義如下：定義如下：nf(0，a)=1f(0，b)=2nf(1，a)=3 f(1，b)=2nf(2，a)=1f(2，b)=3nf(3，a)=3 f(3，b)=3ab012132213333狀態(tài)轉(zhuǎn)換矩陣狀態(tài)轉(zhuǎn)換矩陣0312aaaa狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖bbbbn對(duì)于對(duì)于 * *中的任何字符串中的任何字符串，若存在一條從，若存在一條從初態(tài)到某一終態(tài)的道路，且這條路上所有初態(tài)到某一終態(tài)的道路，且這條路上所有弧上的標(biāo)記符連接成的字符串等于弧上的標(biāo)記符連

28、接成的字符串等于，則，則稱稱為為DFA MDFA M所識(shí)別所識(shí)別( (接納接納) )。nDFA MDFA M所識(shí)別的字符串的全體記為所識(shí)別的字符串的全體記為L(zhǎng)(M)L(M)。142300011011練習(xí)練習(xí)下圖下圖DFADFA識(shí)別的識(shí)別的L(M)L(M)是什么？是什么？A.L(M)=A.L(M)=以以aaaa或或bbbb開(kāi)頭的字符串開(kāi)頭的字符串B.L(M)=B.L(M)=含含aaaa或或bbbb的字符串的字符串C.L(M)=C.L(M)=以以aaaa或或bbbb結(jié)尾的字符串結(jié)尾的字符串答案：答案：B B0312aaaaDFADFAbbbb3.3.3 3.3.3 非確定有限自動(dòng)機(jī)非確定有限自動(dòng)機(jī)

29、(NFA) (NFA) 1976年圖靈獎(jiǎng)年圖靈獎(jiǎng) For their joint paper“Finite automata and their decision problemswhich introduced the idea of nondeterministic machines，which has proved to be an enormously valuable concept. Their classic paper has been a continuous source of inspiration for subsequent work in this field.3.

30、3.3 3.3.3 非確定有限自動(dòng)機(jī)非確定有限自動(dòng)機(jī)(NFA) (NFA) n定義：一個(gè)非確定有限自動(dòng)機(jī)定義：一個(gè)非確定有限自動(dòng)機(jī)(NFA) M(NFA) M是是一個(gè)五元式一個(gè)五元式M=(S, M=(S, , f, S0, F), f, S0, F)，其中：，其中：n1 S: 1 S: 有窮狀態(tài)集；有窮狀態(tài)集；n2 2 ：輸入字母表：輸入字母表( (有窮有窮) )；n3 f: 3 f: 狀態(tài)轉(zhuǎn)換函數(shù)，為狀態(tài)轉(zhuǎn)換函數(shù)，為S S* *2S2S的的部分映射部分映射( (非單值非單值) )；n4 S04 S0S S是非空的初態(tài)集；是非空的初態(tài)集；n5 F 5 F S S ：終態(tài)集：終態(tài)集( (可空可空

31、) )。n從狀態(tài)圖可看出從狀態(tài)圖可看出NFA 和和DFA的區(qū)別：的區(qū)別：n 1 可有多個(gè)初態(tài)可有多個(gè)初態(tài)n 2 弧上的標(biāo)記可以是弧上的標(biāo)記可以是 *中的一個(gè)字甚至可中的一個(gè)字甚至可以是一個(gè)正規(guī)式），而不一定是單個(gè)字符；以是一個(gè)正規(guī)式），而不一定是單個(gè)字符；n 3 同一個(gè)字可能出現(xiàn)在同狀態(tài)射出的多條弧同一個(gè)字可能出現(xiàn)在同狀態(tài)射出的多條弧上。上。nDFA是是NFA的特例。的特例。021 aaa|bb*cabNFADFAn對(duì)于對(duì)于 * *中的任何字中的任何字，若存在一條從初態(tài)，若存在一條從初態(tài)到某一終態(tài)的道路，且這條路上所有弧上到某一終態(tài)的道路，且這條路上所有弧上的標(biāo)記符連接成的字等于的標(biāo)記符連接成

32、的字等于（忽略那些標(biāo)（忽略那些標(biāo)記為記為的?。瑒t稱的?。?，則稱為為NFA MNFA M所識(shí)別所識(shí)別( (接接納納) )nNFA MNFA M所識(shí)別的字符串的全體記為所識(shí)別的字符串的全體記為L(zhǎng)(M)L(M)。021 a|baaa|bbba|b012abab識(shí)別所有含相繼兩個(gè)識(shí)別所有含相繼兩個(gè)a a或相繼兩個(gè)或相繼兩個(gè)b b的字的字ambn | m，n1NFA示例示例n定義：對(duì)于任何兩個(gè)有限自動(dòng)機(jī)定義：對(duì)于任何兩個(gè)有限自動(dòng)機(jī)M和和M，如果如果L(M)=L(M)，則稱，則稱M與與M等價(jià)。等價(jià)。n自動(dòng)機(jī)理論中一個(gè)重要的結(jié)論：判定兩自動(dòng)機(jī)理論中一個(gè)重要的結(jié)論：判定兩個(gè)自動(dòng)機(jī)等價(jià)性的算法是存在的。個(gè)自動(dòng)

33、機(jī)等價(jià)性的算法是存在的。n對(duì)于每個(gè)對(duì)于每個(gè)NFA M存在一個(gè)存在一個(gè)DFA M，使得，使得 L(M)=L(M)。亦即。亦即DFA與與NFA描述能力描述能力相同。相同。NFA與與DFA1. 假定假定NFA M=，我們對(duì)，我們對(duì)NFA M的狀態(tài)轉(zhuǎn)換圖進(jìn)行以下改造：的狀態(tài)轉(zhuǎn)換圖進(jìn)行以下改造： 1) 引進(jìn)新的初態(tài)結(jié)點(diǎn)引進(jìn)新的初態(tài)結(jié)點(diǎn)X和終態(tài)結(jié)點(diǎn)和終態(tài)結(jié)點(diǎn)Y，X,YS， 從從X到到S0中任意狀態(tài)結(jié)點(diǎn)連一條中任意狀態(tài)結(jié)點(diǎn)連一條箭弧，箭弧， 從從F中任意狀態(tài)結(jié)點(diǎn)連一條中任意狀態(tài)結(jié)點(diǎn)連一條箭弧到箭弧到Y(jié)。 2) 按以下按以下3條規(guī)則對(duì)條規(guī)則對(duì)NFA M的狀態(tài)轉(zhuǎn)換圖進(jìn)一的狀態(tài)轉(zhuǎn)換圖進(jìn)一步施行替換，直到把這個(gè)圖轉(zhuǎn)

34、變?yōu)槊織l弧只步施行替換，直到把這個(gè)圖轉(zhuǎn)變?yōu)槊織l弧只標(biāo)記為標(biāo)記為 上的一個(gè)字符或上的一個(gè)字符或；其中；其中k是新引入是新引入的狀態(tài)。的狀態(tài)。NFA轉(zhuǎn)換為等價(jià)的轉(zhuǎn)換為等價(jià)的DFA代之為代之為ikABjijAB代之為代之為ijA|BijBA代之為代之為ijA*ik jA按下面的按下面的3條規(guī)則對(duì)箭弧進(jìn)行分裂條規(guī)則對(duì)箭弧進(jìn)行分裂:n例：識(shí)別所有含相繼兩個(gè)例：識(shí)別所有含相繼兩個(gè)a或相繼兩個(gè)或相繼兩個(gè)b的字的字XY 514236ab ababab5126ab abaabb2. 把上述把上述NFA確定化確定化采用子集法采用子集法.設(shè)設(shè)I是是NFA的狀態(tài)集的一個(gè)子集，定義的狀態(tài)集的一個(gè)子集，定義I的的-閉包閉

35、包-closure(I)為為: i) 若若sI，則，則s-closure(I)； ii) 若若sI，則從，則從s出發(fā)經(jīng)過(guò)任意條出發(fā)經(jīng)過(guò)任意條弧弧而能到達(dá)的任何狀態(tài)而能到達(dá)的任何狀態(tài)s都屬于都屬于-closure(I) 即即 -closure(I)=Is|從某個(gè)從某個(gè)sI出發(fā)經(jīng)過(guò)任出發(fā)經(jīng)過(guò)任意條意條弧能到達(dá)弧能到達(dá)sn設(shè)設(shè)a是是中的一個(gè)字符，定義中的一個(gè)字符，定義nIa= -closure(J)n 其中，其中，J為為I中的某個(gè)狀態(tài)出發(fā)經(jīng)過(guò)一條中的某個(gè)狀態(tài)出發(fā)經(jīng)過(guò)一條a弧而到達(dá)的狀態(tài)集合?；《竭_(dá)的狀態(tài)集合。IIaaIJaK n -closure(1)=1，2=I n J=5，4，3n Ia= -

36、closure(J)= -closure(5，4，3)n =5，4，3，6，2，7，861a 234578aa n設(shè)設(shè)a是是中的一中的一個(gè)字符，定義個(gè)字符，定義nIa= -closure(J)n 其中，其中，J為為I中的中的某個(gè)狀態(tài)出發(fā)經(jīng)某個(gè)狀態(tài)出發(fā)經(jīng)過(guò)一條過(guò)一條a弧而到弧而到達(dá)的狀態(tài)集合。達(dá)的狀態(tài)集合。Ia=？n確定化的過(guò)程確定化的過(guò)程: :n 不失一般性，設(shè)字母表只包含兩個(gè)不失一般性，設(shè)字母表只包含兩個(gè)a a和和b b，我們構(gòu)造一張表，我們構(gòu)造一張表: :IIaIb -C losure(X )u首先，置第首先，置第1行第行第1列為列為-closure(X)求出這一列的求出這一列的Ia，Ib

37、；u然后，檢查這兩個(gè)然后，檢查這兩個(gè)Ia，Ib，看，看它們是否已在表中的第一列中出它們是否已在表中的第一列中出現(xiàn)，把未曾出現(xiàn)的填入后面的空現(xiàn)，把未曾出現(xiàn)的填入后面的空行的第行的第1列上，求出每行第列上，求出每行第2，3列列上的集合上的集合.u重復(fù)上述過(guò)程，知道所有第重復(fù)上述過(guò)程，知道所有第2，3列子集全部出現(xiàn)在第一列為止。列子集全部出現(xiàn)在第一列為止。IIaIbX,5,15,3,15,4,15,3,15,2,3,1,6,Y5,4,15,4,15,3,15,2,4,1,6,Y5,2,3,1,6,Y5,2,3,1,6,Y5,4,6,1,Y5,4,6,1,Y5,3,6,1,Y5,2,4,1,6,Y5,

38、2,4,1,6,Y5,3,6,1,Y5,2,4,1,6,Y5,3,6,1,Y5,2,3,1,6,Y5,4,6,1,YXY 514236ab abababn現(xiàn)在把這張表看成一個(gè)狀態(tài)轉(zhuǎn)換矩陣，把其中的每個(gè)子現(xiàn)在把這張表看成一個(gè)狀態(tài)轉(zhuǎn)換矩陣，把其中的每個(gè)子集看成一個(gè)狀態(tài)。集看成一個(gè)狀態(tài)。n這張表唯一刻劃了一個(gè)確定的有限自動(dòng)機(jī)這張表唯一刻劃了一個(gè)確定的有限自動(dòng)機(jī)M，它的初態(tài)，它的初態(tài)是是-closure(X) ，它的終態(tài)是含有原終態(tài)，它的終態(tài)是含有原終態(tài)Y的子集。的子集。n不難看出，這個(gè)不難看出，這個(gè)DFA M與與M等價(jià)。等價(jià)。IIaIbX,5,15,3,15,4,15,3,15,2,3,1,6,Y5

39、,4,15,4,15,3,15,2,4,1,6,Y5,2,3,1,6,Y5,2,3,1,6,Y5,4,6,1,Y5,4,6,1,Y5,3,6,1,Y5,2,4,1,6,Y5,2,4,1,6,Y5,3,6,1,Y5,2,4,1,6,Y5,3,6,1,Y5,2,3,1,6,Y5,4,6,1,YIIaIbX,5,15,3,15,4,15,3,15,2,3,1,6,Y5,4,15,4,15,3,15,2,4,1,6,Y5,2,3,1,6,Y5,2,3,1,6,Y5,4,6,1,Y5,4,6,1,Y5,3,6,1,Y5,2,4,1,6,Y5,2,4,1,6,Y5,3,6,1,Y5,2,4,1,6,Y5,

40、3,6,1,Y5,2,3,1,6,Y5,4,6,1,YIab012132214334465565634Iab0121322143344655656340123546aabbbabaabababFA正規(guī)集正規(guī)集正規(guī)式正規(guī)式DFANFA3.3.13.3.23.3.33.3.53.3.5 正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性n定理：定理：n 1. 對(duì)任何對(duì)任何FA M，都存在一個(gè)正規(guī)式，都存在一個(gè)正規(guī)式r，使得使得L(r)=L(M)。n 2. 對(duì)任何正規(guī)式對(duì)任何正規(guī)式r，都存在一個(gè)，都存在一個(gè)FA M，使得使得L(M)=L(r)。n對(duì)轉(zhuǎn)換圖概念拓廣，令每條弧可用一個(gè)對(duì)轉(zhuǎn)換圖概念拓廣，

41、令每條弧可用一個(gè)正規(guī)式作標(biāo)記。正規(guī)式作標(biāo)記。(對(duì)一類輸入符號(hào)對(duì)一類輸入符號(hào))n證明：證明： n 1 1 對(duì)對(duì) 上任一上任一NFA MNFA M，構(gòu)造一個(gè)，構(gòu)造一個(gè) 上的正規(guī)上的正規(guī)式式r r，使得，使得L(r)=L(M)L(r)=L(M)。n首先，在首先，在M M的轉(zhuǎn)換圖上加進(jìn)兩個(gè)狀態(tài)的轉(zhuǎn)換圖上加進(jìn)兩個(gè)狀態(tài)X X和和Y Y，從從X X用用弧連接到弧連接到M M的所有初態(tài)結(jié)點(diǎn)，從的所有初態(tài)結(jié)點(diǎn)，從M M的所有終態(tài)結(jié)點(diǎn)用的所有終態(tài)結(jié)點(diǎn)用弧連接到弧連接到Y(jié) Y，從而形，從而形成一個(gè)新的成一個(gè)新的NFANFA，記為，記為M M，它只有一個(gè)初態(tài)，它只有一個(gè)初態(tài)X X和一個(gè)終態(tài)和一個(gè)終態(tài)Y Y，顯然，顯然

42、L(M)=L(ML(M)=L(M) )。n然后，反復(fù)使用下面的一條規(guī)則，逐步消然后，反復(fù)使用下面的一條規(guī)則，逐步消去的所有結(jié)點(diǎn)，直到只剩下去的所有結(jié)點(diǎn)，直到只剩下X X和和Y Y為止；為止；代之為代之為ijr1r2kikr1r2代之為代之為ijr1|r2ijr2r1代之為代之為ikr1r2*r3ijr1r3kr212354U1V1U2V2W2W11254V1(U1|U2)*W1V1(U1|U2)*W2V2(U1|U2)*W2V2(U1|U2)*W1q最后，最后，X到到Y(jié)的弧上標(biāo)記的正規(guī)式即為的弧上標(biāo)記的正規(guī)式即為所構(gòu)造的正規(guī)式所構(gòu)造的正規(guī)式rq顯然顯然L(r)=L(M)=L(M)XYrn定理：

43、定理：n 1. 對(duì)任何對(duì)任何FA M，都存在一個(gè)正規(guī)式，都存在一個(gè)正規(guī)式r，使得，使得L(r)=L(M)。n 2. 對(duì)任何正規(guī)式對(duì)任何正規(guī)式r，都存在一個(gè)，都存在一個(gè)FA M，使得，使得L(M)=L(r)。n證明證明2: 對(duì)于對(duì)于 上的正規(guī)式上的正規(guī)式r，構(gòu)造一個(gè)，構(gòu)造一個(gè)NFA M，使，使L(M)=L(r)，并且，并且M只有一個(gè)只有一個(gè)終態(tài)，而且沒(méi)有從該終態(tài)出發(fā)的箭弧。終態(tài)，而且沒(méi)有從該終態(tài)出發(fā)的箭弧。n 下面使用關(guān)于下面使用關(guān)于r中運(yùn)算符數(shù)目的歸納法中運(yùn)算符數(shù)目的歸納法證明上述結(jié)論。證明上述結(jié)論。n(1) 若若r具有零個(gè)運(yùn)算符，則具有零個(gè)運(yùn)算符，則r=或或r=或或r=a，其中，其中a。此時(shí)

44、下圖所示的三個(gè)有。此時(shí)下圖所示的三個(gè)有限自動(dòng)機(jī)顯然符合上述要求。限自動(dòng)機(jī)顯然符合上述要求。q0q0qfaq0qf(2) 假設(shè)結(jié)論對(duì)于少于假設(shè)結(jié)論對(duì)于少于k(k1)個(gè)運(yùn)算符的正個(gè)運(yùn)算符的正規(guī)式成立。規(guī)式成立。 當(dāng)當(dāng)r中含有中含有k個(gè)運(yùn)算符時(shí)，個(gè)運(yùn)算符時(shí)，r有三種情形：有三種情形：情形情形1：r=r1|r2，r1,r2中運(yùn)算符個(gè)數(shù)少于中運(yùn)算符個(gè)數(shù)少于k。從而，由歸納假設(shè)，對(duì)從而，由歸納假設(shè)，對(duì)ri存在存在Mi=，使得，使得L(Mi)=L(ri)，并且，并且Mi沒(méi)沒(méi)有從終態(tài)出發(fā)的箭弧有從終態(tài)出發(fā)的箭弧i=1,2）。不妨設(shè)）。不妨設(shè)S1S2=，在，在S1 S2中加入兩個(gè)新?tīng)顟B(tài)中加入兩個(gè)新?tīng)顟B(tài)q0，f0

45、。 令令M=，其中，其中定義如下：定義如下：(a) (q0, )=q1,q2(b) (q,a)= 1(q,a), 當(dāng)當(dāng)qS1-f1, a1(c) (q,a)= 2(q,a), 當(dāng)當(dāng)qS2-f2, a2(d) (f1,)=(f2,)=f0。 M的狀態(tài)轉(zhuǎn)換如右圖所示。的狀態(tài)轉(zhuǎn)換如右圖所示。 L(M)=L(M1)L(M2) =L(r1)L(r2)=L(r) q0f0M1q1f1M2q2f2 l情形情形2：r=r1r2, 設(shè)設(shè)Mi同情形同情形1(i=1,2)。l 令令M=，其中其中定義如下：定義如下：l(a) (q,a)= 1(q,a), 當(dāng)當(dāng)qS1-f1, a1l(b) (q,a)= 2(q,a),

46、 當(dāng)當(dāng)qS2, a2l(c) (f1,)=q2l M的狀態(tài)轉(zhuǎn)換如右圖所示。的狀態(tài)轉(zhuǎn)換如右圖所示。l L(M)=L(M1)L(M2)l =L(r1)L(r2)=L(r)。 M1q1f1M2q2f2l情形情形3：r=r1*。設(shè)。設(shè)M1同情形同情形1。l令令M=，其，其中中q0, f0S1，定義如下：定義如下：l(a) (q0,)=(f1,)=q1, f0l(b) (q,a)= 1(q, a), 當(dāng)當(dāng)qS1-f1, a1。lM的狀態(tài)轉(zhuǎn)換如右圖所示。的狀態(tài)轉(zhuǎn)換如右圖所示。lL(M) = L(M1)* = L(r1)* = L(r)l至此，結(jié)論至此，結(jié)論2獲證。獲證。 M1q1f1q0f0 1) 1)

47、構(gòu)造構(gòu)造 上的上的NFA M NFA M 使得使得 L(V)=L(M) L(V)=L(M)首先，把首先，把V V表示成表示成XYV上述證明過(guò)程實(shí)質(zhì)上是一個(gè)將正規(guī)表達(dá)式上述證明過(guò)程實(shí)質(zhì)上是一個(gè)將正規(guī)表達(dá)式轉(zhuǎn)換為有限自動(dòng)機(jī)的算法。轉(zhuǎn)換為有限自動(dòng)機(jī)的算法。代之為代之為ijV1V2kikV1V2代之為代之為ijV1|V2ijV2V1代之為代之為ikV1*ij kV1然后，按下面的三條規(guī)則對(duì)然后，按下面的三條規(guī)則對(duì)V進(jìn)行分裂進(jìn)行分裂n逐步把這個(gè)圖轉(zhuǎn)變?yōu)槊織l弧只標(biāo)記為逐步把這個(gè)圖轉(zhuǎn)變?yōu)槊織l弧只標(biāo)記為 上的上的一個(gè)字符或一個(gè)字符或，最后得到一個(gè)，最后得到一個(gè)NFA M，顯，顯然然L(M)=L(V)n(a|b

48、)*(aa|bb)(a|b)*XY(a|b)*(aa|bb)(a|b)*XY 514236ab abababIIaIbX,5,15,3,15,4,15,3,15,2,3,1,6,Y5,4,15,4,15,3,15,2,4,1,6,Y5,2,3,1,6,Y5,2,3,1,6,Y5,4,6,1,Y5,4,6,1,Y5,3,6,1,Y5,2,4,1,6,Y5,2,4,1,6,Y5,3,6,1,Y5,2,4,1,6,Y5,3,6,1,Y5,2,3,1,6,Y5,4,6,1,YXY 514236ab abababIab0121322143344655656340123546aabbbabaabababF

49、A正規(guī)集正規(guī)集正規(guī)式正規(guī)式DFANFA3.3.13.3.23.3.33.3.5DFA3.3.63.3.6 確定有限自動(dòng)機(jī)的化簡(jiǎn)確定有限自動(dòng)機(jī)的化簡(jiǎn)n對(duì)對(duì)DFA M的化簡(jiǎn)的化簡(jiǎn):尋找一個(gè)狀態(tài)數(shù)比尋找一個(gè)狀態(tài)數(shù)比M少少的的DFA M，使得，使得L(M)=L(M)n假設(shè)假設(shè)s和和t為為M的兩個(gè)狀態(tài)，稱的兩個(gè)狀態(tài)，稱s和和t等價(jià)等價(jià):如果從狀態(tài)如果從狀態(tài)s出發(fā)能讀出某個(gè)字出發(fā)能讀出某個(gè)字而停止而停止于終態(tài)，那么同樣，從于終態(tài)，那么同樣，從t出發(fā)也能讀出出發(fā)也能讀出而停止于終態(tài)；反之亦然。而停止于終態(tài)；反之亦然。n兩個(gè)狀態(tài)不等價(jià)，則稱它們是可區(qū)別的。兩個(gè)狀態(tài)不等價(jià)，則稱它們是可區(qū)別的。n對(duì)一個(gè)對(duì)一個(gè)DF

50、A M最少化的基本思想最少化的基本思想:n 把把M的狀態(tài)集劃分為一些不相交的子集，的狀態(tài)集劃分為一些不相交的子集，使得任何兩個(gè)不同子集的狀態(tài)是可區(qū)別使得任何兩個(gè)不同子集的狀態(tài)是可區(qū)別的，而同一子集的任何兩個(gè)狀態(tài)是等價(jià)的，而同一子集的任何兩個(gè)狀態(tài)是等價(jià)的。最后，讓每個(gè)子集選出一個(gè)代表，的。最后，讓每個(gè)子集選出一個(gè)代表，同時(shí)消去其他狀態(tài)。同時(shí)消去其他狀態(tài)。n具體做法具體做法: 對(duì)對(duì)M的狀態(tài)集進(jìn)行劃分的狀態(tài)集進(jìn)行劃分n首先，把首先，把S劃分為終態(tài)和非終態(tài)兩個(gè)子集，劃分為終態(tài)和非終態(tài)兩個(gè)子集，形成基本劃分形成基本劃分。 n假定到某個(gè)時(shí)候，假定到某個(gè)時(shí)候，已含已含m個(gè)子集，記個(gè)子集，記為為=I(1)，I

51、(2)，I(m)，檢查，檢查中中的每個(gè)子集看是否能進(jìn)一步劃分的每個(gè)子集看是否能進(jìn)一步劃分:n對(duì)某個(gè)對(duì)某個(gè)I(i)，令，令I(lǐng)(i)=s1,s2, ,sk，若存，若存在一個(gè)輸入字符在一個(gè)輸入字符a使得使得Ia(i) 不會(huì)包含在現(xiàn)不會(huì)包含在現(xiàn)行行的某個(gè)子集的某個(gè)子集I(j)中即，中即， Ia(i)中的元中的元素分布在現(xiàn)行劃分的多個(gè)子集中），則素分布在現(xiàn)行劃分的多個(gè)子集中），則至少應(yīng)把至少應(yīng)把I(i)分為兩個(gè)部分。分為兩個(gè)部分。n例如，假定狀態(tài)例如，假定狀態(tài)s1和和s2經(jīng)經(jīng)a弧分別到達(dá)弧分別到達(dá)t1和和t2，而，而t1和和t2屬于現(xiàn)行屬于現(xiàn)行中的兩個(gè)不同中的兩個(gè)不同子集，說(shuō)明有一個(gè)字子集，說(shuō)明有一個(gè)字

52、， t1讀出讀出后到后到達(dá)終態(tài)，而達(dá)終態(tài)，而t2讀出讀出后不能到達(dá)終態(tài)，或后不能到達(dá)終態(tài)，或者反之，那么對(duì)于字者反之，那么對(duì)于字a ， s1讀出讀出a后后到達(dá)終態(tài)，而到達(dá)終態(tài)，而s2讀出讀出a不能到達(dá)終態(tài)，不能到達(dá)終態(tài)，或者反之，所以或者反之，所以s1和和s2不等價(jià)。不等價(jià)。s1t1as2t2a j in則將則將I(i)分成兩半，使得一半含有分成兩半，使得一半含有s1 :n I(i1)=s|sI(i)且且s經(jīng)經(jīng)a弧到達(dá)弧到達(dá)t, n 且且t與與t1屬于現(xiàn)行屬于現(xiàn)行中的同一子集中的同一子集n 另一半含有另一半含有s2 : I(i2)=I(i)-I(i1)s1t1as2t2a j in一般地，對(duì)某

53、個(gè)一般地，對(duì)某個(gè)a和和I(i)，若，若Ia(i) 落入現(xiàn)行落入現(xiàn)行中中 N個(gè)不同子集，則應(yīng)把個(gè)不同子集，則應(yīng)把I(i)劃分成劃分成N個(gè)不相個(gè)不相交的組，使得每個(gè)組交的組，使得每個(gè)組J的的Ja都落入的都落入的同一同一子集。這樣構(gòu)成新的劃分。子集。這樣構(gòu)成新的劃分。n重復(fù)上述過(guò)程，直到重復(fù)上述過(guò)程，直到所含子集數(shù)不再增長(zhǎng)。所含子集數(shù)不再增長(zhǎng)。n對(duì)于上述最后劃分對(duì)于上述最后劃分中的每個(gè)子集，我們選中的每個(gè)子集，我們選取每個(gè)子集取每個(gè)子集I中的一個(gè)狀態(tài)代表其他狀態(tài)，中的一個(gè)狀態(tài)代表其他狀態(tài)，則可得到化簡(jiǎn)后的則可得到化簡(jiǎn)后的DFA M。n若若I含有原來(lái)的初態(tài)，則其代表為新的初態(tài)，含有原來(lái)的初態(tài)，則其代表

54、為新的初態(tài)，若若I含有原來(lái)的終態(tài)，則其代表為新的終態(tài)。含有原來(lái)的終態(tài)，則其代表為新的終態(tài)。0123546aabbbabaabababI(1)=0, 1, 2 I(2)=3, 4, 5, 6 Ia(1) =1, 3 I(11) =0, 2 I(12) =1I(2)=3, 4, 5, 6 I(11) =0, 2Ia(11) =1 Ib(11) =2, 5 I(111) =0 I(112) =2 I(12) =1 I(2)=3, 4, 5, 6 Ia(2) =3, 6 Ib(2) =4, 5 0123546aabbbabaababab0123aabbbaabFA正規(guī)集正規(guī)集正規(guī)式正規(guī)式DFANFA3

55、.3.13.3.23.3.33.3.5DFA3.3.685一一. .原理原理 單詞的詞法規(guī)則用正規(guī)式描述單詞的詞法規(guī)則用正規(guī)式描述 正規(guī)式正規(guī)式 NFA NFA DFA DFA min DFAmin DFALEXLEX編譯器編譯器LEXLEX源程序源程序lex.1lex.1詞法分析程序詞法分析程序Lex.yy.c二二. .用用LEXLEX建立詞法分析程序的過(guò)程建立詞法分析程序的過(guò)程3.4 詞法分析器的自動(dòng)產(chǎn)生詞法分析器的自動(dòng)產(chǎn)生-LEXC編譯器編譯器詞法分析程序詞法分析程序Lex.yy.c詞法分析程序詞法分析程序Lex.out或或lex.exe 詞法分析程序詞法分析程序L L單詞符號(hào)單詞符號(hào)輸

56、入串輸入串狀態(tài)轉(zhuǎn)換矩陣狀態(tài)轉(zhuǎn)換矩陣控制執(zhí)行程序控制執(zhí)行程序3.4 詞法分析器的自動(dòng)產(chǎn)生詞法分析器的自動(dòng)產(chǎn)生-LEX3.4 詞法分析器的自動(dòng)產(chǎn)生詞法分析器的自動(dòng)產(chǎn)生-LEXlexlex源程序源程序 lex lex源程序由三部分組成源程序由三部分組成聲明聲明% % 識(shí)別規(guī)則識(shí)別規(guī)則( (翻譯規(guī)則）翻譯規(guī)則）%輔助過(guò)程輔助過(guò)程 聲明包括變量，符號(hào)常量和正規(guī)定義式。聲明包括變量，符號(hào)常量和正規(guī)定義式。正規(guī)定義式是形式如下的一系列定義：正規(guī)定義式是形式如下的一系列定義： d1 d1 r1 r1 d2 d2 r2 r2 dn dn rn rn其中，其中， di di 表示不同的名字，表示不同的名字， ri ri 是正規(guī)式是正規(guī)式識(shí)別規(guī)則翻譯規(guī)則的形式為：識(shí)別規(guī)則翻譯規(guī)則的形式為： p1 p1 動(dòng)作動(dòng)作1 1 p2 p2 動(dòng)作動(dòng)作22 p n p n 動(dòng)作動(dòng)作nn 每個(gè)每個(gè)pi是一個(gè)正規(guī)式，稱為詞形。是一個(gè)正規(guī)式，稱為詞形。 每個(gè)每個(gè)動(dòng)作動(dòng)