編譯原理課程設(shè)計之-第二章-詞法分析

1、mcy1w課程內(nèi)容課程內(nèi)容第一章第一章 概論概論第二章第二章 詞法分析詞法分析第三章第三章上下文無關(guān)文法及分析上下文無關(guān)文法及分析第四章第四章自上而下的語法分析自上而下的語法分析第五章第五章自下而上的語法分析自下而上的語法分析第六章第六章語義分析語義分析第七章第七章運行時環(huán)境運行時環(huán)境第八章第八章代碼生成代碼生成mcy2第第2 2章章 詞法分析詞法分析2.1 詞法分析器的作用詞法分析器的作用2.2 正規(guī)表達式正規(guī)表達式 2.3 有窮自動機有窮自動機2.4 從正規(guī)表達式到從正規(guī)表達式到DFA 2.5 用代碼實現(xiàn)有窮自動機用代碼實現(xiàn)有窮自動機2.6 利用利用lex自動生成詞法分析自動生成詞法分析程

2、序程序單詞的描單詞的描述工具述工具單詞單詞的識的識別系統(tǒng)別系統(tǒng)設(shè)計和設(shè)計和實現(xiàn)詞實現(xiàn)詞法分析法分析程序程序作業(yè)作業(yè)課程設(shè)計課程設(shè)計1 1 mcy32.1 2.1 詞法分析器的作用詞法分析器的作用 詞法分析器詞法分析器( (詞法分析程序詞法分析程序) )的任務(wù)的任務(wù)：從源從源代碼中讀取輸入字符，產(chǎn)生單詞序列代碼中讀取輸入字符，產(chǎn)生單詞序列(生生成獨立的有意義的邏輯單元稱作單詞成獨立的有意義的邏輯單元稱作單詞(token)，提交給語法分析使用。，提交給語法分析使用。mcy4任務(wù)任務(wù)：逐個讀入源程序字符并按照：逐個讀入源程序字符并按照構(gòu)詞規(guī)則構(gòu)詞規(guī)則切分切分成一系列單詞。單詞是語言中具有獨立意義的成

3、一系列單詞。單詞是語言中具有獨立意義的最小單位，包括保留字、標識符、運算符、標最小單位，包括保留字、標識符、運算符、標點符號和常量等。點符號和常量等。w識別出源程序中的單詞；識別出源程序中的單詞；w刪除無用的空白字符及注釋（空格、回車刪除無用的空白字符及注釋（空格、回車 等），這些信等），這些信息僅增加了源程序的可讀性，便于程序員閱讀和維護程息僅增加了源程序的可讀性，便于程序員閱讀和維護程序，而對于語法分析是完全無用的。序，而對于語法分析是完全無用的。w進行詞法檢查，能夠檢測出輸入中不能形成進行詞法檢查，能夠檢測出輸入中不能形成源語言任何源語言任何單詞的錯誤字符串單詞的錯誤字符串。mcy5Th

4、e big elephant ate the peanut.The big elephant ate the peanut. big 詞法分析的結(jié)果：詞法分析的結(jié)果： mcy6 token表示的字符串表示的字符串（串值或詞義串值或詞義）：）： if , y, ,3,then,x,=,0 token的的類型（詞法）類型（詞法）： 關(guān)鍵字（關(guān)鍵字（if, else, for,int,return） 操作符（操作符（+ , -, ） 數(shù)字數(shù)字 （3, 45,） 標示符（標示符（x, y, ）詞法分析器的輸出詞法分析器的輸出: : token序列序列mcy7if y3 then x=0 LT, 詞法分

5、析器詞法分析器例如：例如：C源代碼源代碼:if y3 then x=0,詞法詞法分析器的輸出是？分析器的輸出是？ mcy8定義邏輯項定義邏輯項token的數(shù)據(jù)類型的數(shù)據(jù)類型： typedef struct union char *stringval; int numval; attribute; TokenRecord; TokenType tokenval;Token類型類型Token詞義詞義mcy9詞法分析程序的函數(shù)接口：詞法分析程序的函數(shù)接口： TokenRecord getToken(void);TokengetToken()源程序源程序詞法分析程序詞法分析程序語法分析程序語法分析程序

6、符號表符號表mcy10第第2 2章章 詞法分析詞法分析2.1 詞法分析器的作用詞法分析器的作用2.2 正規(guī)表達式正規(guī)表達式 2.3 有窮自動機有窮自動機2.4 從正規(guī)表達式到從正規(guī)表達式到DFA 2.5 用代碼實現(xiàn)有窮自動機用代碼實現(xiàn)有窮自動機2.6 利用利用lex自動生成詞法分析自動生成詞法分析程序程序記號的描記號的描述工具述工具記號的識記號的識別系統(tǒng)別系統(tǒng)設(shè)計和設(shè)計和實現(xiàn)詞實現(xiàn)詞法分析法分析程序程序作業(yè)作業(yè)課程設(shè)計課程設(shè)計1 1 mcy11正規(guī)表達式的引入：正規(guī)表達式的引入： 對自動生成詞法分析程序而言，正規(guī)表達對自動生成詞法分析程序而言，正規(guī)表達 式也是非常有用的工具。式也是非常有用的工

7、具。 所謂所謂正規(guī)表達式正規(guī)表達式就是用特定的就是用特定的運算符運算符及及運算運算對象對象按某種規(guī)則構(gòu)造的表達式。例如：按某種規(guī)則構(gòu)造的表達式。例如：c-語語言的詞法言的詞法。 正規(guī)表達式用來描述單詞正規(guī)表達式用來描述單詞結(jié)構(gòu)結(jié)構(gòu)( (定義單詞定義單詞) )。mcy122.2.1 基本概念和術(shù)語基本概念和術(shù)語2.2.2 正規(guī)表達式的定義正規(guī)表達式的定義2.2.3 正規(guī)表達式基本等價關(guān)系正規(guī)表達式基本等價關(guān)系2.2.4 正規(guī)表達式的擴展正規(guī)表達式的擴展2.2.5 單詞的正規(guī)表達式舉例單詞的正規(guī)表達式舉例2.22.2正規(guī)表達式正規(guī)表達式 單詞的描述工具單詞的描述工具mcy132.2.1 2.2.1

8、 基本概念和術(shù)語基本概念和術(shù)語字母表（符號表、符號集）字母表（符號表、符號集） 由若干元素由若干元素（符號、字母）組成的有限非空集合。（符號、字母）組成的有限非空集合。不同的語言可以有不同的字母表，例如不同的語言可以有不同的字母表，例如漢語的字母表中包括漢字、數(shù)字及標點漢語的字母表中包括漢字、數(shù)字及標點符號等。符號等。mcy14 符號串符號串 由字母表中的符號組成的任何有由字母表中的符號組成的任何有窮序列稱為符號串窮序列稱為符號串:例如例如00 11 10 是字母表是字母表 =0，1上上的符號串。的符號串。字母表字母表A=a，b，c上的符號串有：上的符號串有： a，b，c，ab，aaca。在符

9、號串中，符號的順序是很重要的，符在符號串中，符號的順序是很重要的，符號串號串a(chǎn)b就不同于就不同于ba，abca和和aabc也不同。也不同。mcy15符號串的長度符號串的長度 如果某符號串如果某符號串x x中有中有m m個符號，個符號，則稱其長度為則稱其長度為m m，表示為表示為x x=m=m，如如001110001110的長度是的長度是6 6?？辗柎辗柎?，即不包含任何符號的符號串，用，即不包含任何符號的符號串，用表示，其長度為表示，其長度為0 0，即，即=0=0。mcy16w符號串的連接符號串的連接：設(shè)：設(shè)x和和y是符號串，它們的連是符號串，它們的連接接xy是把是把y的符號寫在的符號寫在

10、x的符號之后得到的符的符號之后得到的符號串。號串。 例如例如 x=ST，y=abu，則它們的連接則它們的連接 xy=STabu，x=2，y=3，xy=5由于由于的含義，顯然有的含義，顯然有x=x=x。w符號串的方冪符號串的方冪：符號串自身連接符號串自身連接n次得到的符次得到的符號串號串xn 定義為定義為 xxxx； n個個x x1=x, x2=xx且且x0=mcy17例；若例；若x=x=abab 則則: : x x0 0 = = x x1 1 = =abab x x2 2 = = abababab x x3 3 = = abababababab x xn n = xx= xxn-1 n-1 =

11、 x= xn-1n-1x (n0)x (n0)mcy18符號串集合符號串集合：若集合若集合A A中所有元素都是中所有元素都是某字母表某字母表 上的符號串，則稱上的符號串，則稱A A為字母表為字母表 上的符號串集合。上的符號串集合。符號串集合的和與積符號串集合的和與積設(shè)設(shè)A A，B B為兩個符號串集合，定義為兩個符號串集合，定義和和 A A+B(+B(或或A A B)B) =w|w =w|w A A，或或w w BB積積AB=AB=xy|xxy|x A,yA,y B B mcy19v若用若用表示空集，則有：表示空集，則有： A+ = +A = A A = A = A = A = Av 例：若集合

12、例：若集合A= = ab,cde ，集合集合B = B = 0,1 ，則則AB = ab1,ab0,cde0,cde1 ；mcy20的閉包：的閉包：用用 * *表示表示 上的一切符號串（包括上的一切符號串（包括）組成的集合，組成的集合，* *稱為稱為的閉包的閉包。例如例如：=a,ba,b * *=,a,b,aa,ab,ba,bb,aaa,aab,a,b,aa,ab,ba,bb,aaa,aab, , 的正閉包：的正閉包： 上上除除外的所有符號串組成的外的所有符號串組成的集合記為集合記為 + + ，+ +稱為稱為的正閉包的正閉包。例如例如：=a,ba,b + +=a,b,aa,ab,ba,bb,a

13、aa,aaba,b,aa,ab,ba,bb,aaa,aab, , mcy212.2.1 基本概念和術(shù)語基本概念和術(shù)語2.2.2 正規(guī)表達式的定義正規(guī)表達式的定義2.2.3 正規(guī)表達式基本等價關(guān)系正規(guī)表達式基本等價關(guān)系2.2.4 正規(guī)表達式的擴展正規(guī)表達式的擴展2.2.5 單詞的正規(guī)表達式舉例單詞的正規(guī)表達式舉例2.22.2正規(guī)表達式正規(guī)表達式mcy22w正規(guī)表達式正規(guī)表達式(也稱正則表達式也稱正則表達式)就是用特定的就是用特定的運算運算符符及及運算對象運算對象按某種規(guī)則構(gòu)造的表達式。按某種規(guī)則構(gòu)造的表達式。w每個正規(guī)表達式代表一個每個正規(guī)表達式代表一個字符串的集合字符串的集合，我們，我們把其稱

14、為正規(guī)集。把其稱為正規(guī)集。w語言語言(Language)是字符串組成的集合，我們也可是字符串組成的集合，我們也可以把正規(guī)表達式表示的以把正規(guī)表達式表示的正規(guī)集正規(guī)集稱為該正規(guī)表達稱為該正規(guī)表達式表示的式表示的語言語言。2.2.22.2.2正規(guī)表達式的定義正規(guī)表達式的定義mcy23w正規(guī)表達式和它所表示的正規(guī)集正規(guī)表達式和它所表示的正規(guī)集(字符串的集字符串的集合合)的遞歸定義如下的遞歸定義如下： 設(shè)有字母表為設(shè)有字母表為，輔助字母表輔助字母表=, | , . , * , ( , ) mcy24(1)和和是是上的正規(guī)式，它們所表示的正規(guī)集上的正規(guī)式，它們所表示的正規(guī)集分別為分別為和和;(2) 若若

15、a，則則a是是上的正規(guī)式，它所表示的上的正規(guī)式，它所表示的正規(guī)集為正規(guī)集為a;(3)若若r和和s都是都是上的上的正規(guī)式正規(guī)式，且它們所表示，且它們所表示的的正規(guī)集正規(guī)集分別為分別為L(r)和和L(s)，那么：那么：mcy25 r|s 是是正規(guī)式正規(guī)式，表示的，表示的正規(guī)集正規(guī)集為為 L(r|s)=L(r)L(s) ； rs 是是正規(guī)式正規(guī)式，表示的，表示的正規(guī)集正規(guī)集為為 L(rs)=L(r)L(s) ； r *是是正規(guī)式正規(guī)式，表示的，表示的正規(guī)集正規(guī)集為為(L(r)*。 (r) 是是正規(guī)式正規(guī)式，表示的，表示的正規(guī)集正規(guī)集為為L(r)；“.”運算符運算符常省略常省略mcy26(4)僅由有限

16、次使用上述三步驟而定義的表僅由有限次使用上述三步驟而定義的表達式才是達式才是上的上的正規(guī)式正規(guī)式，僅由這些正規(guī)式僅由這些正規(guī)式所表示的符號串集合才是所表示的符號串集合才是上的上的正規(guī)集。正規(guī)集。注：算符的優(yōu)先級為先注：算符的優(yōu)先級為先“ * ”，再，再“ . ”最后最后“ | ” ,都是左結(jié)合的，它們滿足結(jié)合都是左結(jié)合的，它們滿足結(jié)合律。律。舉例：舉例： C-語言的詞法語言的詞法mcy27例例1，令，令 =a，b， 上的正規(guī)式和相應(yīng)的正規(guī)集的例子：上的正規(guī)式和相應(yīng)的正規(guī)集的例子：正規(guī)式正規(guī)式 正規(guī)集正規(guī)集aaa bab(a b)(a b)a a,babaa,ab,ba,bb ,a,aa, 任意

17、個任意個a的串的串(a b) a,b*即即,a,b,aa,ab,ba,bb,mcy28例例2，正規(guī)式，正規(guī)式(a)| (b) * (c)它所表示的正規(guī)集為：它所表示的正規(guī)集為： 根據(jù)運算符的優(yōu)先級，上述正規(guī)式可以表示根據(jù)運算符的優(yōu)先級，上述正規(guī)式可以表示成成 a|b*ca|b*c所表示的正規(guī)集為：字符串所表示的正規(guī)集為：字符串a(chǎn)以及由零個以及由零個或多個或多個b后跟一個后跟一個c 形成的字符串的集合形成的字符串的集合或?qū)懗苫驅(qū)懗蒐(a|b*c)=a bnc | 其中其中n是大于或等是大于或等于于0的整數(shù)的整數(shù)mcy29給定一個正規(guī)式給定一個正規(guī)式, ,它唯一確定一個正規(guī)集；它唯一確定一個正規(guī)集

18、；反之不成立。即一個正規(guī)集可由多個不同反之不成立。即一個正規(guī)集可由多個不同的正規(guī)式表示。的正規(guī)式表示。aaaa a,aa, aaa,任意個任意個a的串的串a(chǎn)|aaa|aa a,aa, aaa,任意個任意個a的串的串例如：例如：mcy30若若二正規(guī)式二正規(guī)式描述同一正規(guī)集，則稱二式描述同一正規(guī)集，則稱二式等等價價( (相等相等) )。判斷下列正規(guī)表達式判斷下列正規(guī)表達式e e1 1和和e e2 2是否等價？是否等價？e1= (a b)， e2 = b ae1= b(ab) ,e2 =(ba) be1= (a b) , e2 =(a b ) mcy31w正規(guī)表達式正規(guī)表達式是表示模式的一種重要方法

19、，每是表示模式的一種重要方法，每個模式匹配一個字符串集合個模式匹配一個字符串集合(即正規(guī)集即正規(guī)集)。w正規(guī)集正規(guī)集是正規(guī)表達式所定義的語言。是正規(guī)表達式所定義的語言。w正規(guī)表達式正規(guī)表達式可以作為字符串集合可以作為字符串集合(即正規(guī)集即正規(guī)集)的名字。的名字。mcy322.2.1 基本概念和術(shù)語基本概念和術(shù)語2.2.2 正規(guī)表達式的定義正規(guī)表達式的定義2.2.3 正規(guī)表達式基本等價關(guān)系正規(guī)表達式基本等價關(guān)系2.2.4 正規(guī)表達式的擴展正規(guī)表達式的擴展2.2.5 單詞的正規(guī)表達式舉例單詞的正規(guī)表達式舉例2.22.2正規(guī)表達式正規(guī)表達式mcy33A1. r|s=s|r A2. r|r=rA3.

20、r| =rA4. (r|s)|t=r|(s|t)A5. (rs)t=r(st)A6. r(s|t)=rs|rtA7. (s|t)r=sr|trA8. r = r= A9. r = r=rA10. r*=( |r)*= |rr* 2.2.3 2.2.3 正規(guī)式基本等價關(guān)系正規(guī)式基本等價關(guān)系mcy342.2.1 基本概念和術(shù)語基本概念和術(shù)語2.2.2 正規(guī)表達式的定義正規(guī)表達式的定義2.2.3 正規(guī)表達式基本等價關(guān)系正規(guī)表達式基本等價關(guān)系2.2.4 正規(guī)表達式的擴展正規(guī)表達式的擴展2.2.5 單詞的正規(guī)表達式舉例單詞的正規(guī)表達式舉例2.22.2正規(guī)表達式正規(guī)表達式mcy352.2.4 2.2.4

21、正規(guī)表達式的擴展正規(guī)表達式的擴展w1.一個或多個重復(fù)（一個或多個重復(fù)（+，*）：）： 假設(shè)假設(shè)r是正則表達式是正則表達式，r的重復(fù)是通過使用標準的閉包運算來描述，的重復(fù)是通過使用標準的閉包運算來描述，寫作寫作r*。它允許它允許r被重復(fù)被重復(fù)0次或更多次次或更多次。用用r +表示表示r 被重復(fù)被重復(fù)1次或更多次次或更多次。因此有：。因此有： (0|1)+=(0|1)(0|1)*mcy362.任意字符（任意字符（.）: 句點句點“ .”表示可以匹配除換行符之外的任意單個符。表示可以匹配除換行符之外的任意單個符。利用這個字符就可為利用這個字符就可為所有包含至少一個所有包含至少一個b 的串的串寫出寫出

22、一個一個正則表達式正則表達式，如下所示：，如下所示： .*b .*3.引號引號“ ”，引號中的字符串表示文本字符，引號中的字符串表示文本字符串本身。例如：串本身。例如：“.”表示要匹配表示要匹配.字符本身。字符本身。mcy374.字符字符范圍范圍：表示法表示法a|b|z 表示所有小寫字母；表示所有小寫字母；0|1|9表示表示0到到9間的所有數(shù)字；間的所有數(shù)字；常見的表示法是利用常見的表示法是利用方括號方括號和和一個連字符一個連字符，如，如a-z是指所有小寫字母，是指所有小寫字母，0-9則指數(shù)字。則指數(shù)字。第二種表示法還可用作表示單個的解，第二種表示法還可用作表示單個的解，a|b|c可寫成可寫成

23、abc，它還可用于多個范圍，它還可用于多個范圍，如如 a - z A - Z 代表所有的大小寫字母。代表所有的大小寫字母。mcy385. 正規(guī)表達式的正規(guī)表達式的名字名字為較長的正則表達式提供一個簡化的名字很有用為較長的正則表達式提供一個簡化的名字很有用處，這樣就不用每次使用正則表達式書寫較長的處，這樣就不用每次使用正則表達式書寫較長的表達式本身了；表達式本身了；如要寫一個正則表達式如要寫一個正則表達式: a - z A - Z ( a - z A - Z 0-9 ) 它定義的正規(guī)集為：以字母打頭后跟若干字母或它定義的正規(guī)集為：以字母打頭后跟若干字母或數(shù)字組成的符號串的集合數(shù)字組成的符號串的集

24、合。mcy39上述正規(guī)式上述正規(guī)式定義的是程序設(shè)計語言定義的是程序設(shè)計語言標識符標識符的的詞法詞法規(guī)則規(guī)則，通過為，通過為正規(guī)表達式提供一個簡化的名字，正規(guī)表達式提供一個簡化的名字，上述正規(guī)表達式可寫作：上述正規(guī)表達式可寫作： letter= a - z A - Z digit=0-9 r=letter(letter digit) mcy40例：寫出正則表達式例：寫出正則表達式signedNatnat=0-9+signedNat=nat|+ nat|- nat對應(yīng)的正規(guī)集？對應(yīng)的正規(guī)集？mcy416.可選的子表達式（可選的子表達式（？）：）：w如果在特定的串中包括既可能出現(xiàn)又可能不出現(xiàn)如果在特

25、定的串中包括既可能出現(xiàn)又可能不出現(xiàn)的可選部分。例如，的可選部分。例如， nat=0-9+ signedNat=nat|+nat|-natw我們可以引入問號我們可以引入問號?來表示來表示r 匹配的串是可選的；上面的匹配的串是可選的；上面的例子可寫成：例子可寫成：nat=0-9 +signedNat=(+|-)？natmcy422.2.1 基本概念和術(shù)語基本概念和術(shù)語2.2.2 正規(guī)表達式的定義正規(guī)表達式的定義2.2.3 正規(guī)表達式基本等價關(guān)系正規(guī)表達式基本等價關(guān)系2.2.4 正規(guī)表達式的擴展正規(guī)表達式的擴展2.2.5 單詞的正規(guī)表達式舉例單詞的正規(guī)表達式舉例2.22.2正規(guī)表達式正規(guī)表達式mcy

26、432.2.5 2.2.5 單詞的正規(guī)表達式舉例單詞的正規(guī)表達式舉例每一種程序設(shè)計語言都有自己的字符集每一種程序設(shè)計語言都有自己的字符集( (字母表字母表) ) 。語言中的各個語言中的各個單詞單詞或是或是 上的單個字符上的單個字符( (如運算符、如運算符、分隔符等分隔符等) )，或是，或是 上的字符串上的字符串( (如常數(shù)、表示符和關(guān)如常數(shù)、表示符和關(guān)鍵字等鍵字等) )。程序設(shè)計語言的程序設(shè)計語言的單詞單詞都能用都能用正規(guī)式正規(guī)式來定義來定義. .由正規(guī)式由正規(guī)式描述的描述的單詞類單詞類也稱為也稱為正規(guī)集正規(guī)集。 例如：例如：C-語言的詞法語言的詞法mcy441.1.數(shù)：數(shù)： nat= 0-9

27、+signedNat=(+|-)? natnumber=signedNat(“.”nat)?(“E” signedNat)?例如：例如：3, 3.5, 2.71E-22.2.保留字：保留字：reserved=else|if |int|return|void|while mcy453.3.標示符：標示符：letter=a-zA-Zdigit=0-9identifier=letter(letter|digit)*mcy46 包含單詞詞法描述的包含單詞詞法描述的語言手冊語言手冊是編譯是編譯器的程序員最常見的。在下面的示例器的程序員最常見的。在下面的示例中，被匹配的串是漢語描述，其任務(wù)中，被匹配的串是

28、漢語描述，其任務(wù)是將描述是將描述翻譯為正則表達式翻譯為正則表達式。mcy471)在字母表在字母表 = a, b, c中，考慮在這個字中，考慮在這個字母表上的母表上的僅包括一個僅包括一個b 的所有串的集合的所有串的集合，這個集合所對應(yīng)的正則表達式為：這個集合所對應(yīng)的正則表達式為： 串串b、abc、abaca、baaaac、ccbaca和和ccccccb等都是滿要求的等都是滿要求的符號串。符號串。(a|c)*b(a|c)*mcy482)在字母表在字母表 = a, b, c中，中，如果字符串集合是如果字符串集合是包括最包括最多一個多一個b 的所有串的所有串，則這個集合的正則表達式為：，則這個集合的正

29、則表達式為：僅包括一個僅包括一個b 的串的集合對應(yīng)的正則表達式的串的集合對應(yīng)的正則表達式 (a|c)*b(a|c)*不包括不包括b 的串的集合對應(yīng)的正則表達式的串的集合對應(yīng)的正則表達式 (a|c)*故所求表達式為：故所求表達式為：(a|c)* | (a|c)*b(a|c)*或者為或者為:(a|c)*(b| )(a|c)*mcy493)在在字母表字母表 = a, b上串上串S的集合是由一個的集合是由一個b及及在其前后有相同數(shù)目的在其前后有相同數(shù)目的a 組成：組成： S = b, aba, aabaa, aaabaaa, . . . = anban | n0 正則表達式并不能描述這個集合正則表達式

30、并不能描述這個集合，其原因在于重復(fù)運，其原因在于重復(fù)運算只有閉包運算算只有閉包運算*一種，它允許有任意次的重復(fù)。因此一種，它允許有任意次的重復(fù)。因此如要寫出表達式如要寫出表達式a*ba*，就不能保證在，就不能保證在b 前后的前后的a 的數(shù)的數(shù)量是否相等了。量是否相等了。mcy50w并非用簡單術(shù)語描述的所有串都可由并非用簡單術(shù)語描述的所有串都可由 正則表正則表達式產(chǎn)生，因此為了與其他集合相區(qū)分，作達式產(chǎn)生，因此為了與其他集合相區(qū)分，作為正則表達式描述的串集合稱作正規(guī)集為正則表達式描述的串集合稱作正規(guī)集(regular set)。w非正規(guī)集偶爾也作為串出現(xiàn)在需要由掃描程非正規(guī)集偶爾也作為串出現(xiàn)在需

31、要由掃描程序識別的程序設(shè)計語言中。序識別的程序設(shè)計語言中。mcy51第第2 2章章 詞法分析詞法分析2.1 詞法分析器的作用詞法分析器的作用2.2 正規(guī)表達式正規(guī)表達式 2.3 有窮自動機有窮自動機2.4 從正規(guī)表達式到從正規(guī)表達式到DFA 2.5 用代碼實現(xiàn)有窮自動機用代碼實現(xiàn)有窮自動機2.6 利用利用lex自動生成詞法分析程序自動生成詞法分析程序記號的描記號的描述工具述工具記號的識記號的識別系統(tǒng)別系統(tǒng)設(shè)計和設(shè)計和實現(xiàn)詞實現(xiàn)詞法分析法分析程序程序作業(yè)作業(yè)課程設(shè)計課程設(shè)計1 1 mcy522.3.1有窮自動機的引入有窮自動機的引入2.3.2確定性有窮自動機確定性有窮自動機(DFA)的定義的定義

32、2.3.3非確定性有窮自動機非確定性有窮自動機(NFA) 2.32.3有窮自動機有窮自動機mcy532.3.1 2.3.1 有窮自動機的引入有窮自動機的引入有窮自動機有窮自動機( (也稱有限自動機也稱有限自動機) )作為一種數(shù)學(xué)模作為一種數(shù)學(xué)模型型，它能準確地識別正規(guī)集，即識別正規(guī)式所它能準確地識別正規(guī)集，即識別正規(guī)式所表示的集合。表示的集合。有窮自動機是有窮自動機是設(shè)計和實現(xiàn)詞法分析器設(shè)計和實現(xiàn)詞法分析器的有效的有效工具，其直觀圖是一種狀態(tài)轉(zhuǎn)換圖。工具，其直觀圖是一種狀態(tài)轉(zhuǎn)換圖。引入有窮自動機理論，也是為詞法分析程序引入有窮自動機理論，也是為詞法分析程序的自動構(gòu)造尋找方法和工具。的自動構(gòu)造尋

33、找方法和工具。mcy54有窮自動機有窮自動機( (Finite Automata,or finite-state machines) )有窮自動機分為兩類：有窮自動機分為兩類：確定的有窮自動機確定的有窮自動機( (Deterministic Finite Automata) )。不確定的有窮自動機不確定的有窮自動機( (Nondeterministic Finite Automata) )。mcy55在程序設(shè)計語言中，用正規(guī)式在程序設(shè)計語言中，用正規(guī)式定義定義的標示符的標示符如下：如下： letter=a-zA-Zdigit=0-9identifier=letter(letter|digit)

34、* 該正規(guī)式匹配的標示符是以一個字母開頭且該正規(guī)式匹配的標示符是以一個字母開頭且其后為任意字母、數(shù)字序列形成的字符串。其后為任意字母、數(shù)字序列形成的字符串。mcy5612letterletterdigit標示符的有窮自動機標示符的有窮自動機變量變量xtempxtemp 識別為標示符的過程可表示為：識別為標示符的過程可表示為：1x2t2e2m2p2 標示符模式的標示符模式的識別識別過程：過程：mcy572.3.1有窮自動機的引入有窮自動機的引入2.3.2確定性有窮自動機確定性有窮自動機(DFA)的定義的定義2.3.3非確定性有窮自動機非確定性有窮自動機(NFA) 2.32.3有窮自動機有窮自動機

35、mcy582.3.22.3.2確定性有窮自動機（確定性有窮自動機（DFADFA）的定義的定義DFA(DFA(確定性有窮自動機確定性有窮自動機) )有五個部分組成：有五個部分組成：(1)(1)有限個輸入符號組成的字母表有限個輸入符號組成的字母表, ,記作記作 ; ;(2)(2)有限個狀態(tài)的集合有限個狀態(tài)的集合, ,記作記作S S; ;(3)(3)轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù)T T T: T: S S S S 即：即：T(s,c)= sT(s,c)= s 其中其中s s S S，s s S S， c c上述轉(zhuǎn)換函數(shù)表示若當前狀態(tài)為上述轉(zhuǎn)換函數(shù)表示若當前狀態(tài)為s s, ,且當前識別的輸入且當前識別的輸入符號為符

36、號為c c, ,識別識別c c后進入的下一個狀態(tài)為后進入的下一個狀態(tài)為s s ; ;mcy59(4)(4)初始狀態(tài)初始狀態(tài)s s0 0 S S; ;指示識別符號串的開始狀態(tài)指示識別符號串的開始狀態(tài); ;(5)(5)若干個若干個識別符號串的識別符號串的接受狀態(tài)接受狀態(tài)( (或稱為終止狀或稱為終止狀 態(tài)態(tài)) )的集合的集合 A A S S ; ;( (由上述五個要素組成的五元式由上述五個要素組成的五元式M=(S;M=(S; ;T;s;T;s0 0;A);A)稱為一稱為一個確定的有限自動機個確定的有限自動機 ( (DFADFA: : D Deterministic eterministic F Fi

37、nite inite A Automatautomata) )。mcy60DFA MDFA M= =（ss1 1,s,s2 2 ,s,s3 3 ,s,s4 4,a,b,T,s,a,b,T,s1 1,s,s4 4 ）其中其中轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù)T T定義為：定義為：T(s1,a)= s2 T(s3,a)=s2 T(s1,b)=s3 T(s3,b)=s4T(s2,a)=s4 T(s4,a)=s4T(s2,b)=s3 T(s4 ,b)=s4一個一個DFA DFA 的例子：的例子：有限個狀有限個狀態(tài)的集合態(tài)的集合s s字母表字母表 初始狀態(tài)初始狀態(tài)接受狀接受狀態(tài)的集合態(tài)的集合A Amcy61狀態(tài)轉(zhuǎn)換圖狀態(tài)

38、轉(zhuǎn)換圖一個一個DFADFA可以表示成一個狀態(tài)圖可以表示成一個狀態(tài)圖( (或稱或稱狀狀態(tài)轉(zhuǎn)換圖態(tài)轉(zhuǎn)換圖) )。狀態(tài)轉(zhuǎn)換圖是由一組矢線。狀態(tài)轉(zhuǎn)換圖是由一組矢線連結(jié)的有限個結(jié)點所組成的有向圖。連結(jié)的有限個結(jié)點所組成的有向圖。例如：例如：s s0 0s s2 20s s1 110mcy62假定假定DFA MDFA M含有含有m m個狀態(tài)，那么這個狀態(tài)圖個狀態(tài)，那么這個狀態(tài)圖就含有就含有m m個結(jié)點；結(jié)點用小圓圈表示，個結(jié)點；結(jié)點用小圓圈表示，圓圈圓圈中標入狀態(tài)的名字中標入狀態(tài)的名字或編號?；蚓幪?。為了醒目起見，用為了醒目起見，用箭頭指示初始狀箭頭指示初始狀態(tài)，用雙圓圈表示終止轉(zhuǎn)態(tài)。態(tài)，用雙圓圈表示終止

39、轉(zhuǎn)態(tài)。s s結(jié)點結(jié)點s s0 0初始狀態(tài)初始狀態(tài)s sn n接受狀態(tài)接受狀態(tài)mcy63s sas s狀態(tài)轉(zhuǎn)換的圖形表示狀態(tài)轉(zhuǎn)換的圖形表示w若若 T(s,a)=s ，則從狀態(tài)結(jié)點則從狀態(tài)結(jié)點s到狀態(tài)結(jié)點到狀態(tài)結(jié)點s畫標記為畫標記為a的矢線。的矢線。表示當詞法分析器處于該矢線的結(jié)點所指示的表示當詞法分析器處于該矢線的結(jié)點所指示的狀態(tài)狀態(tài)s時，可能要識別的輸入字符為時，可能要識別的輸入字符為a，而矢線而矢線進入的結(jié)點進入的結(jié)點s則指示識別相應(yīng)的輸入字符則指示識別相應(yīng)的輸入字符a后后進入的下一個狀態(tài)。進入的下一個狀態(tài)。mcy64 例：例： M=(s0 0, s1 1, s2 2, 0,1, T, s0

40、 0, s2 2) 其其中中, ,T的定義如下：的定義如下： T(s0 0,0)= s1 1 T(s1 1,0)= s1 1 T(s1 1,1)= s2 2 s s0 0s s2 20s s1 110狀態(tài)轉(zhuǎn)換圖舉例狀態(tài)轉(zhuǎn)換圖舉例上述上述DFADFA對應(yīng)的狀態(tài)轉(zhuǎn)換圖：對應(yīng)的狀態(tài)轉(zhuǎn)換圖：mcy65w在狀態(tài)轉(zhuǎn)換圖中，從一個結(jié)點可以同時引出若干在狀態(tài)轉(zhuǎn)換圖中，從一個結(jié)點可以同時引出若干條矢線到有向圖中的其余結(jié)點條矢線到有向圖中的其余結(jié)點(也可從一結(jié)點引矢也可從一結(jié)點引矢線到其自身線到其自身)；w每一矢線上均標記一個字符或字符類記號，表示每一矢線上均標記一個字符或字符類記號，表示當詞法分析器處于該矢線的

41、結(jié)點所指示的狀態(tài)時，當詞法分析器處于該矢線的結(jié)點所指示的狀態(tài)時，可能要識別的輸入字符，而矢線進入的結(jié)點則指可能要識別的輸入字符，而矢線進入的結(jié)點則指示識別相應(yīng)的輸入字符后進入的下一個狀態(tài)。示識別相應(yīng)的輸入字符后進入的下一個狀態(tài)。mcy66DFADFA的接受集的接受集( (即識別的字符串集合即識別的字符串集合) )DFA識別的字符串識別的字符串c c1 1 c c2 2 c cn n的集合的集合滿足如下滿足如下條件：每個條件：每個c ci i ，且存在狀態(tài)，且存在狀態(tài) s1= T(s0 ，c1), s2= T(s1 ，c2), , sn= T(sn-1 ，cn), 其中其中s0 是初態(tài)，是初態(tài)，

42、 sn 是終態(tài)。是終態(tài)。mcy67s s0 0c c1 1s s1 1c c2 2s s2 2s sn-1n-1c cn ns sn nc c3 3c cn-1n-1v字符串字符串c c1 1 c c2 2 c cn n若被若被DFA識別，則在狀態(tài)識別，則在狀態(tài)轉(zhuǎn)換圖中存在一條從初態(tài)到終態(tài)的有向路經(jīng)，轉(zhuǎn)換圖中存在一條從初態(tài)到終態(tài)的有向路經(jīng)，該路徑上所有該路徑上所有矢線上方的字符連接在一起即是矢線上方的字符連接在一起即是字符串字符串c c1 1 c c2 2 c cn nvDFA M識別的字符串的集合識別的字符串的集合 記作記作L(M)mcy68bs1s2s3s4abba | baa例：證明字符

43、串序列例：證明字符串序列baabbaab被下圖的被下圖的DFADFA所接受。所接受。任意列出它接受的另外兩個輸入串？任意列出它接受的另外兩個輸入串？任意列出它拒絕接受的兩個輸入串？任意列出它拒絕接受的兩個輸入串？mcy69證明：由于存在證明：由于存在T(sT(s1 1,b,b）= s= s3 3T(sT(s3 3,a,a）= s= s2 2T(sT(s2 2,a,a）= s= s4 4T(sT(s4 4,b,b）= s= s4 4s s4 4屬于終態(tài)，得證。屬于終態(tài)，得證。mcy70(1).狀態(tài)轉(zhuǎn)換圖中的狀態(tài)轉(zhuǎn)換圖中的狀態(tài)狀態(tài)可以使用可以使用任何標識任何標識系統(tǒng)系統(tǒng)來標識來標識(2).狀態(tài)轉(zhuǎn)換

44、圖中的狀態(tài)轉(zhuǎn)換圖中的轉(zhuǎn)換轉(zhuǎn)換可以使用可以使用字符集合字符集合的名字的名字標出標出關(guān)于關(guān)于DFADFA的狀態(tài)轉(zhuǎn)換圖的的狀態(tài)轉(zhuǎn)換圖的2 2點說明點說明startin_idletterletterdigitmcy7112digitdigit例例1：自然數(shù)的集合自然數(shù)的集合被下圖所示的被下圖所示的DFA接受。接受。注：注：digit=0-9DFADFA的示例的示例mcy72例例2：字母表字母表 = a, b, c上上有且僅有一個有且僅有一個b構(gòu)成構(gòu)成的字符串集合的字符串集合被下圖所示的被下圖所示的DFA接受。接受。12bnotbnotb注：注：notb= a, cmcy73例例3：字母表字母表 = a

45、, b, c上上包含最多一個包含最多一個b構(gòu)構(gòu)成的字符串的集合成的字符串的集合被下圖所示的被下圖所示的DFA接受。接受。2bnotbnotb1注：注：notb= a, cmcy74例例4：有：有C風(fēng)格注釋的風(fēng)格注釋的DFA15/other12*3*4*/other2注：注：other1other1表示除表示除* *之外的所有字符的集合的名字；之外的所有字符的集合的名字； other2 other2表示除表示除* *,/,/之外的所有字符的集合的名字。之外的所有字符的集合的名字。mcy752.3.1有窮自動機的引入有窮自動機的引入2.3.2確定性有窮自動機確定性有窮自動機(DFA)的定義的定義2

46、.3.3非確定性有窮自動機非確定性有窮自動機(NFA) 2.32.3有窮自動機有窮自動機mcy762.3.32.3.3非確定性有窮自動機（非確定性有窮自動機（NFANFA）下圖是識別下圖是識別 = =、, , 字符串的一個字符串的一個有窮自動機，對于輸入符號有窮自動機，對于輸入符號,在狀態(tài)在狀態(tài)0 0上上存在不止一種轉(zhuǎn)換。存在不止一種轉(zhuǎn)換。 153024mcy77w有窮自動機對于某個輸入符號，如果有窮自動機對于某個輸入符號，如果在同一個狀態(tài)上存在不止一種轉(zhuǎn)換，在同一個狀態(tài)上存在不止一種轉(zhuǎn)換，我們稱該有窮自動機為不確定的有窮我們稱該有窮自動機為不確定的有窮自動機。自動機。w在給出非確定性有窮自動

47、機的定義之在給出非確定性有窮自動機的定義之前先引入前先引入 - -轉(zhuǎn)換轉(zhuǎn)換的概念。的概念。mcy78 - -轉(zhuǎn)換轉(zhuǎn)換是無需考慮輸入串就有可能發(fā)生的是無需考慮輸入串就有可能發(fā)生的轉(zhuǎn)換。它可看作是一個空串轉(zhuǎn)換。它可看作是一個空串 的的“匹配匹配”， - -轉(zhuǎn)換的圖形表示為：轉(zhuǎn)換的圖形表示為：0 0 1 1 - -轉(zhuǎn)換的引入轉(zhuǎn)換的引入 - -轉(zhuǎn)換轉(zhuǎn)換可以清晰地描述出空串的匹配：可以清晰地描述出空串的匹配：0 0 1 1mcy790 - -轉(zhuǎn)換轉(zhuǎn)換可以通過添加一個新的初始狀態(tài)來鏈接各個可以通過添加一個新的初始狀態(tài)來鏈接各個自動機，從而將它們合并為一個自動機。自動機，從而將它們合并為一個自動機。將識別數(shù)

48、字將識別數(shù)字和字符的兩個和字符的兩個DFADFA和并為一個非確定的有窮自動機：和并為一個非確定的有窮自動機：letterletterletterletterDONE2DONE2START2START2START1START1digitdigitdigitdigitDONE1DONE1mcy800 123: := =675 = =89= =通過通過 - -轉(zhuǎn)換將識別轉(zhuǎn)換將識別:=:=、=、= =的的DFADFA合并為：合并為：mcy81NFA( (非確定性有窮自動機非確定性有窮自動機) )有五個部分組成：有五個部分組成：(1)(1)有限個輸入符號組成的字母表有限個輸入符號組成的字母表, ,記作記

49、作 ; ;(2)(2)有限個狀態(tài)的集合有限個狀態(tài)的集合, ,記作記作S S; ;(3)(3)轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù)T T; ; T: T: S S ( ( )(S)(S), , T(s,c)= s T(s,c)= sk1, s skm 表示若當前狀態(tài)為表示若當前狀態(tài)為s s S S, ,且要識別的輸入符號為且要識別的輸入符號為c c , , 識識別別c c后進入的狀態(tài)是后進入的狀態(tài)是S S的一個狀態(tài)的一個狀態(tài)子集子集ssk1, s skm ; ;2.3.22.3.2非確定性有窮自動機（非確定性有窮自動機（NFANFA）的定義的定義mcy82(4)(4)初始狀態(tài)初始狀態(tài)s s0 0 S S; ;(5)

50、(5)若干個接受狀態(tài)的集合若干個接受狀態(tài)的集合: : A A S S 由上述五個要素組成的五元式由上述五個要素組成的五元式 M=(SM=(S； ； T T； s s0 0 ； A )A )稱為一個非確定的有限稱為一個非確定的有限自動機自動機 ( (NFANFA: : Nondeterministicondeterministic F Finite inite A Automatautomata),),由上述定義由上述定義可以看出，可以看出，DFADFA是是NFANFA的一個的一個特例。特例。mcy83一個一個NFA NFA 的例子：的例子：NFA M=NFA M=（SS，P P，ZZ，00，1

51、1，T T，SS，ZZ）其中其中 T T（S S，0 0）=P; =P; T T（Z Z，0 0）=P;=P; T T（P P，1 1）=Z; T=Z; T（Z Z，1 1）=P;=P; T T（S S，1 1）=S=S，Z;Z;mcy84NFANFA的狀態(tài)轉(zhuǎn)換圖的狀態(tài)轉(zhuǎn)換圖例：例：M=( , = , 0，1，2，3，4，5 , T, 0, 2，4，5 ) 其中其中T的定義如下：的定義如下：T(0,) = 4 153024mcy85NFA M 的的接受集接受集記作記作L(M)L(M)L(M)定義為定義為字符串字符串c c1 1c c2 2 c cn n的集合的集合，其中每個，其中每個c ci

52、i ，且存在：，且存在：s s1 1 T(T(s s0 0 , ,c c1 1) ), ,s s2 2 T(T(s s1 1, ,c c2 2),), ,s sn n T(T(s sn-1 n-1 , ,c cn n),),其中其中s s0 0是初態(tài)，是初態(tài)， s sn n是終態(tài)集中的一個元素。是終態(tài)集中的一個元素。NFANFA的接受集的接受集mcy86例：考慮下面的例：考慮下面的NFA圖。圖。231a aa ab b4 這個這個NFA接受集與正接受集與正則表達式則表達式ab+|ab*|b*對應(yīng)的對應(yīng)的正規(guī)集相同。正規(guī)集相同。列舉兩個轉(zhuǎn)換序列都可接受串列舉兩個轉(zhuǎn)換序列都可接受串a(chǎn)bb？1a2b

53、4 2b41a3 4 2b4 2b4mcy87第第2 2章章 詞法分析詞法分析2.1 詞法分析器的作用詞法分析器的作用2.2 正規(guī)表達式正規(guī)表達式 2.3 有窮自動機有窮自動機2.4 從正規(guī)表達式到從正規(guī)表達式到DFA 2.5 用代碼實現(xiàn)有窮自動機用代碼實現(xiàn)有窮自動機2.6 利用利用lex自動生成詞法分析自動生成詞法分析程序程序記號的描記號的描述工具述工具記號的識記號的識別系統(tǒng)別系統(tǒng)設(shè)計和設(shè)計和實現(xiàn)詞實現(xiàn)詞法分析法分析程序程序作業(yè)作業(yè)課程設(shè)計課程設(shè)計1 1 mcy882.42.4從正規(guī)表達式到從正規(guī)表達式到DFADFA正規(guī)表達式正規(guī)表達式DFA詞法分析程序詞法分析程序NFA正規(guī)式正規(guī)式是單詞的

54、一種描述工具。由于正規(guī)是單詞的一種描述工具。由于正規(guī)式的簡潔性，趨向于先用式的簡潔性，趨向于先用正規(guī)式來描述單正規(guī)式來描述單詞詞，然后，然后構(gòu)造等價的有限自動機構(gòu)造等價的有限自動機。有限自動機有限自動機可以描述輸入串被識別的過可以描述輸入串被識別的過程，我們可以根據(jù)有限自動機程，我們可以根據(jù)有限自動機構(gòu)造構(gòu)造我們的我們的詞法分析程序詞法分析程序。mcy89正規(guī)式正規(guī)式和和有限自動機有限自動機之間可以之間可以相互轉(zhuǎn)換相互轉(zhuǎn)換，也就是說它們之間存在著也就是說它們之間存在著等價性等價性，即，即：1)1)對于對于上的上的NFA M，可以構(gòu)造一個可以構(gòu)造一個上的上的正規(guī)式正規(guī)式R，使得：使得：L(R)=

55、L(M)2)2)對于對于上的每個正規(guī)式上的每個正規(guī)式R，可以構(gòu)造一個可以構(gòu)造一個上的上的NFA M，使得：使得：L(M)=L(R)mcy902.4.1 從正規(guī)表達式到從正規(guī)表達式到NFA2.4.2 從從NFA 到到DFA2.4.3 將將DFA中的狀態(tài)數(shù)最小化中的狀態(tài)數(shù)最小化2.42.4從正規(guī)表達式到從正規(guī)表達式到DFADFAmcy912.4.1 2.4.1 從正規(guī)表達式到從正規(guī)表達式到NFANFA從正規(guī)表達式到從正規(guī)表達式到NFA的轉(zhuǎn)化方法按正規(guī)式的運算的轉(zhuǎn)化方法按正規(guī)式的運算指引構(gòu)造過程，指引構(gòu)造過程，將正規(guī)式分解為一系列子表達式，將正規(guī)式分解為一系列子表達式，然后將子表達式對應(yīng)的然后將子表

56、達式對應(yīng)的NFA依次連接而成依次連接而成，正規(guī)正規(guī)式式R轉(zhuǎn)化為轉(zhuǎn)化為NFA M 的基本步驟：的基本步驟：mcy92(b)對正規(guī)式對正規(guī)式，等價的等價的NFA為：為： 0 0 1 1 (a)對正規(guī)式對正規(guī)式，等價的等價的NFA為：為： 0 01 1(c)對正規(guī)式對正規(guī)式a，等價的等價的NFA為：為： 0 0a a1 11. 基本正規(guī)式轉(zhuǎn)換為基本正規(guī)式轉(zhuǎn)換為NFA M的方法：的方法： mcy930 0R R1 12. 復(fù)合正規(guī)式復(fù)合正規(guī)式R轉(zhuǎn)換為轉(zhuǎn)換為NFA M的方法：首先將復(fù)的方法：首先將復(fù)合正規(guī)表達式表示成如下合正規(guī)表達式表示成如下拓廣的狀態(tài)轉(zhuǎn)換圖拓廣的狀態(tài)轉(zhuǎn)換圖，然后按照正規(guī)式的運算然后按照

57、正規(guī)式的運算(以下以下(a),(b),(c),(d)四種四種情況情況)遞歸生成遞歸生成NFA Mmcy94(b)若若R=rs,則將則將 代之以代之以 0 01 1rsrs0 01 1r r2 2s s(a)若若R=r|s,則將則將 代之以代之以 0 01 1r|sr|s0 01 1r rs smcy95(c)若若R=r*,則將則將 代之以代之以 0 01 1r r*0 01 12 2 r r(d)正規(guī)式正規(guī)式R=（r）的的NFA同正規(guī)式同正規(guī)式 R=r的的NFA相同相同mcy96例例1 1, ,設(shè)有正規(guī)表達式設(shè)有正規(guī)表達式R=ab|a, ,試構(gòu)造試構(gòu)造NFA M，使使L(R)=L(M)。（1

58、1）0 0ab|aab|a1 1（2 2）0 0abab1 1a a（3 3）0 01 1a a2 2a ab bmcy97例例2 2，設(shè)有正規(guī)表達式，設(shè)有正規(guī)表達式letter(letter|digit)letter(letter|digit)* *, ,試構(gòu)造與之等試構(gòu)造與之等價的價的NFANFA。（1 1）0 0letter(letter|digit)letter(letter|digit)* *1 1（2 2）0 0(letter|digit)(letter|digit)* *1 1letterletter2 2mcy98（3 3）0 0(letter|digit)(letter|di

59、git)1 1letterletter2 2 3 3（4 4）0 0letterletter1 1letterletter2 2 3 3digitdigitmcy992.4.1 從正規(guī)表達式到從正規(guī)表達式到NFA2.4.2 從從NFA 到到DFA2.4.3 將將DFA中的狀態(tài)數(shù)最小化中的狀態(tài)數(shù)最小化2.42.4從正規(guī)表達式到從正規(guī)表達式到DFADFAmcy1002.4.2 2.4.2 從從NFANFA 到到DFADFAw對任一對任一NFA M，總可構(gòu)造一個總可構(gòu)造一個DFA M，使使 L(M)=L(M)成立。這就是成立。這就是NFA與與DFA的等價性。的等價性。w定理定理 對于字母表對于字母表

60、 上的任一上的任一NFA M，必存在與必存在與M等等價的價的DFA M (即有即有 L(M)=L(M) 成立成立) 。在給出具體的構(gòu)造算法之前先引入在給出具體的構(gòu)造算法之前先引入狀態(tài)狀態(tài)s和狀態(tài)和狀態(tài)集合集合S的的 -閉包的概念：閉包的概念：mcy101（1）狀態(tài)狀態(tài)s的的 -閉包閉包：定義為從：定義為從s出發(fā)可由一系出發(fā)可由一系列的零個或多個列的零個或多個 -轉(zhuǎn)換轉(zhuǎn)換能達到能達到的狀態(tài)的集合，的狀態(tài)的集合，并將這個集合記為并將這個集合記為（2）狀態(tài)集合）狀態(tài)集合S的的 -閉包閉包:定義為定義為S中各個狀態(tài)中各個狀態(tài)的的 -閉包的并集閉包的并集s s- -mcy1021 14 42 2a a