編譯原理-第三章

1、2022-3-4TJNU-COCIE-WJW1編譯原理編譯原理第三章第三章 詞法分析詞法分析王金偉計算機與信息工程學院天津師范大學TJNU-COCIE-WJW2 22022-3-42022-3-4第三章第三章 詞法分析詞法分析n3.1 對于詞法分析器的要求對于詞法分析器的要求n3.2 詞法分析器的設(shè)計詞法分析器的設(shè)計n3.3 正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機n3.4 詞法分析器的自動產(chǎn)生（詞法分析器的自動產(chǎn)生（LEX）TJNU-COCIE-WJW3 32022-3-42022-3-4n詞法分析的任務(wù)詞法分析的任務(wù)從左至右逐個字符的對源程序進行掃描，產(chǎn)生從左至右逐個字符的對源程序進行

2、掃描，產(chǎn)生一個個的單詞符號，把作為字符串的源程序改一個個的單詞符號，把作為字符串的源程序改造成為由單詞符號串組成的程序造成為由單詞符號串組成的程序n詞法分析器：詞法分析器：執(zhí)行詞法分析的程序執(zhí)行詞法分析的程序輸入：源程序輸入：源程序輸出：單詞符號輸出：單詞符號n詞法分析器的構(gòu)造方法詞法分析器的構(gòu)造方法手工方法手工方法：根據(jù)詞法直接編程序：根據(jù)詞法直接編程序(有限自動機有限自動機)自動方法自動方法：利用一些工具：利用一些工具LexTJNU-COCIE-WJW4 42022-3-42022-3-43.1 對詞法分析器的要求對詞法分析器的要求源程序源程序 詞法分析器詞法分析器 單詞符號單詞符號1.單

3、詞符號概念單詞符號概念指語言中具有獨立意義的最小的語法符號指語言中具有獨立意義的最小的語法符號：C = A * 3.14 + 5單詞：單詞： C，A 變量變量 3.14, 5 常數(shù)常數(shù) = ，*，+ 算符算符一、一、詞法分析器的功能和輸出形式詞法分析器的功能和輸出形式TJNU-COCIE-WJW5 52022-3-42022-3-42.單詞的種類單詞的種類（1）基本字（保留字，關(guān)鍵字）基本字（保留字，關(guān)鍵字）由程序語言定義的具有固定意義的標識符。由程序語言定義的具有固定意義的標識符。用戶不能用來表示變量名，函數(shù)名等標識符用戶不能用來表示變量名，函數(shù)名等標識符：C語言中的語言中的“if” “el

4、se” “while” （2）標識符標識符用戶使用的，用來表示各種名字，變量名，函數(shù)用戶使用的，用來表示各種名字，變量名，函數(shù)名等名等TJNU-COCIE-WJW6 62022-3-42022-3-42.單詞的種類（續(xù)）單詞的種類（續(xù)）（3）常數(shù)常數(shù)整型、實型、邏輯、字符整型、實型、邏輯、字符例：例：1000，3.14，TRUE，“Abcd”（4）運算符運算符+、-、*、/ （5）界符界符， ； （）（）TJNU-COCIE-WJW7 72022-3-42022-3-4詞法分析器輸出的單詞符號常常用詞法分析器輸出的單詞符號常常用二元式二元式來表示：來表示：二、二、單詞的表示形式單詞的表示形式T

5、JNU-COCIE-WJW8 82022-3-42022-3-41. 單詞種別單詞種別通常用通常用整數(shù)編碼整數(shù)編碼來表示來表示（1）關(guān)鍵字，運算符，界符關(guān)鍵字，運算符，界符n一字一種編碼（處理起來比較方便）一字一種編碼（處理起來比較方便）：if，else，(，+，（2）常數(shù)常數(shù)n按類型分別給出編碼按類型分別給出編碼：整型，實型，布爾型，：整型，實型，布爾型，（3）標識符標識符n統(tǒng)歸一種，只給一個編碼統(tǒng)歸一種，只給一個編碼：變量名，函數(shù)名等都是一種編碼：變量名，函數(shù)名等都是一種編碼TJNU-COCIE-WJW9 92022-3-42022-3-41. 單詞種別（續(xù)）單詞種別（續(xù)）：(1)若一個種

6、別只包含一個單詞符號（一種一字），若一個種別只包含一個單詞符號（一種一字），對于該單詞符號，種別編碼就可以代表它自身了。對于該單詞符號，種別編碼就可以代表它自身了。：關(guān)鍵字，運算符，界符：關(guān)鍵字，運算符，界符(2)若一個種別包含有多個單詞符號（一種多字），若一個種別包含有多個單詞符號（一種多字），對于該種別的每個單詞符號，除了給出種別編碼，對于該種別的每個單詞符號，除了給出種別編碼，還需給出單詞符號的屬性值還需給出單詞符號的屬性值：整型常數(shù)，實型常數(shù)，布爾常數(shù)，標識符：整型常數(shù)，實型常數(shù)，布爾常數(shù)，標識符TJNU-COCIE-WJW10102022-3-42022-3-42.單詞符號的屬性信息

7、單詞符號的屬性信息單詞符號的屬性單詞符號的屬性：指單詞符號的特性或特征：指單詞符號的特性或特征單詞符號的屬性值單詞符號的屬性值：反映單詞特性或特征的值：反映單詞特性或特征的值TJNU-COCIE-WJW11112022-3-42022-3-42.單詞符號的屬性信息（續(xù)）單詞符號的屬性信息（續(xù)）屬性值的表示方法屬性值的表示方法：（1）基本字，運算符，界符（一字一種）基本字，運算符，界符（一字一種）n只給其種別編碼，不給出它的屬性值只給其種別編碼，不給出它的屬性值：基本字：基本字while表示成：表示成： （2）常數(shù)常數(shù)n表示成標準的二進制形式表示成標準的二進制形式：1024表示成：表示成： （3

8、）標識符標識符n用字符串編碼或?qū)?yīng)的符號表項地址用字符串編碼或?qū)?yīng)的符號表項地址：name表示成：表示成：或或TJNU-COCIE-WJW12122022-3-42022-3-4：FORTRAN編譯程序的詞法分析器，在掃描輸編譯程序的詞法分析器，在掃描輸入串：入串： IF （5. EQ .M） GOTO 100輸出的單詞如下：輸出的單詞如下：單詞符號單詞符號 nIFn左括號左括號n整常數(shù)整常數(shù)n等號等號n標識符標識符n右括號右括號nGOTOn標號標號三、三、例子例子TJNU-COCIE-WJW13132022-3-42022-3-4：考慮下面：考慮下面C+的一段代碼：的一段代碼：while (

9、 i = j) i-;經(jīng)詞法分析器處理后，將被轉(zhuǎn)換成如下單詞符號序列：經(jīng)詞法分析器處理后，將被轉(zhuǎn)換成如下單詞符號序列：單詞符號單詞符號 nwhilen(nin= ，- njn)ni n-n；TJNU-COCIE-WJW14142022-3-42022-3-43.2 詞法分析器的設(shè)計詞法分析器的設(shè)計源程序源程序預處理預處理子程序子程序輸入輸入緩沖區(qū)緩沖區(qū)掃描器掃描器掃描緩沖區(qū)掃描緩沖區(qū)輸入輸入列表列表單詞符號單詞符號一、一、詞法分析器的結(jié)構(gòu)詞法分析器的結(jié)構(gòu)TJNU-COCIE-WJW15152022-3-42022-3-41. 輸入緩沖區(qū)、預處理子程序輸入緩沖區(qū)、預處理子程序（1）輸入源程序文本

10、，放入輸入緩沖區(qū)中，詞）輸入源程序文本，放入輸入緩沖區(qū)中，詞法分析工作可在這個輸入緩沖區(qū)中工作法分析工作可在這個輸入緩沖區(qū)中工作（2）剔除無用的空白，跳格）剔除無用的空白，跳格(TAB)，回車，換行，回車，換行等編輯性字符；若空白符號為單詞符號的界符，等編輯性字符；若空白符號為單詞符號的界符，就將若干空白和并為就將若干空白和并為1個個（3）剔除注釋行，比如）剔除注釋行，比如/*/（4）如果是）如果是FORTRAN語言，區(qū)分標號區(qū)、續(xù)語言，區(qū)分標號區(qū)、續(xù)行區(qū)和給出句末符行區(qū)和給出句末符（5）源程序的出錯列表打?。┰闯绦虻某鲥e列表打?。?）將預處理好的子程序放到掃描緩沖區(qū)中）將預處理好的子程序放到

11、掃描緩沖區(qū)中TJNU-COCIE-WJW16162022-3-42022-3-42.掃描緩沖區(qū)、掃描器掃描緩沖區(qū)、掃描器（1）掃描緩沖區(qū)）掃描緩沖區(qū)n設(shè)兩個半?yún)^(qū)，可互補使用設(shè)兩個半?yún)^(qū)，可互補使用n設(shè)兩個指針設(shè)兩個指針起點指針：指出正在識別單詞起點位置起點指針：指出正在識別單詞起點位置搜索指針：向前搜索以尋找單詞終點搜索指針：向前搜索以尋找單詞終點（2）掃描器：掃描緩沖區(qū)，直接進行單詞的識別）掃描器：掃描緩沖區(qū)，直接進行單詞的識別前半?yún)^(qū)前半?yún)^(qū)后半?yún)^(qū)后半?yún)^(qū)起點指針起點指針搜索指針搜索指針TJNU-COCIE-WJW17172022-3-42022-3-4源程序源程序預處理預處理子程序子程序輸入輸入

12、緩沖區(qū)緩沖區(qū)掃描器掃描器掃描緩沖區(qū)掃描緩沖區(qū)輸入輸入列表列表單詞符號單詞符號二、二、詞法分析器的工作過程詞法分析器的工作過程TJNU-COCIE-WJW18182022-3-42022-3-41. 超前搜索超前搜索(1)關(guān)鍵字的識別關(guān)鍵字的識別前提：允許用戶使用基本字（關(guān)鍵字）前提：允許用戶使用基本字（關(guān)鍵字）：試分析下面：試分析下面FORTRAN的幾個語句的幾個語句（1） DO99K=1，10（2） IF(S.EQ.M) GOTO 55（3） DO99K=1.10（4） IF(S)=55超前掃描很多字符，直到掃描到可以肯定詞性的超前掃描很多字符，直到掃描到可以肯定詞性的地方為止地方為止 PR

13、OGRAM SUM S=0 DO 99 I=1,100 S=S+I 99 CONTINUE END 三、三、單詞符號的識別單詞符號的識別TJNU-COCIE-WJW19192022-3-42022-3-41. 超前搜索法（續(xù)超前搜索法（續(xù)1）(2) 標識符的識別標識符的識別一般是以一般是以字母字母開頭后跟開頭后跟數(shù)字數(shù)字/字母字母的字符串，后邊的字符串，后邊一般都有算符和界符，比較好識別一般都有算符和界符，比較好識別(3)常數(shù)的識別常數(shù)的識別：對于：對于FORTRAN5.EQ.M（5=M）5.E08（5*108)直到超前掃描到字母直到超前掃描到字母Q時才能確定時才能確定5的詞性的詞性3HABC

14、（“ABC”）3H是詞頭，代表長度為是詞頭，代表長度為3的字符串常數(shù)的字符串常數(shù)TJNU-COCIE-WJW20202022-3-42022-3-41. 超前搜索法（續(xù)超前搜索法（續(xù)2）(4) 算符和界符的識別算符和界符的識別應(yīng)將那些由多個字符復合成的算符和界符拼成一個應(yīng)將那些由多個字符復合成的算符和界符拼成一個單詞符號單詞符號：+ - =TJNU-COCIE-WJW21212022-3-42022-3-42. 直接分析法直接分析法（1）基本思想基本思想根據(jù)讀來的第一個字符的種類分別轉(zhuǎn)到各種根據(jù)讀來的第一個字符的種類分別轉(zhuǎn)到各種子程序處理。這些子程序功能就是識別以相子程序處理。這些子程序功能就

15、是識別以相應(yīng)字符開頭的各種單詞。應(yīng)字符開頭的各種單詞。（2）方法方法以以FORTRAN語言為例，分成幾種情況語言為例，分成幾種情況以字母開頭的以字母開頭的基本字、標識符、格式說明符，基本字、標識符、格式說明符，nIFnWHILETJNU-COCIE-WJW22222022-3-42022-3-42. 直接分析法（續(xù)直接分析法（續(xù)1）以小數(shù)點開頭的以小數(shù)點開頭的n.34 .EQ. .TRUE. .FALSE. 等等以數(shù)字開頭的以數(shù)字開頭的n常數(shù)、格式語句、重復說明常數(shù)、格式語句、重復說明nWRITE(6,10) X,Y10 FORMAT(2X, F10.4, F9.3)以以*開頭的開頭的：* *

16、除此之外除此之外：都是一個基本字符表示一個單詞：都是一個基本字符表示一個單詞TJNU-COCIE-WJW23232022-3-42022-3-4子子程程序序1子子程程序序2子子程程序序3子子程程序序4子子程程序序5下一個語句下一個語句字符是否讀來字符是否讀來該字符是什么該字符是什么讀讀一一個個符符號號字母字母數(shù)字數(shù)字*其他其他出口出口否否是是2. 直接分析法（續(xù)直接分析法（續(xù)2）分析流程圖分析流程圖TJNU-COCIE-WJW24242022-3-42022-3-43. 狀態(tài)轉(zhuǎn)換圖法狀態(tài)轉(zhuǎn)換圖法(1)狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖：一張有限方向圖：一張有限方向圖(2)狀態(tài)轉(zhuǎn)換圖的功能狀態(tài)轉(zhuǎn)換圖的功能識別

17、（接受）一定的符號串（單詞）識別（接受）一定的符號串（單詞）TJNU-COCIE-WJW25252022-3-42022-3-43. 狀態(tài)轉(zhuǎn)換圖法（續(xù)狀態(tài)轉(zhuǎn)換圖法（續(xù)1）(3)狀態(tài)轉(zhuǎn)換圖的結(jié)構(gòu)狀態(tài)轉(zhuǎn)換圖的結(jié)構(gòu)結(jié)點結(jié)點：代表狀態(tài)，用圓圈表示：代表狀態(tài)，用圓圈表示箭弧箭?。籂顟B(tài)之間用箭弧連接：狀態(tài)之間用箭弧連接箭弧上的標記箭弧上的標記：代表在射出節(jié)點下可能出現(xiàn)的：代表在射出節(jié)點下可能出現(xiàn)的字符或字符串字符或字符串：一個完整的狀態(tài)轉(zhuǎn)換圖有：一個完整的狀態(tài)轉(zhuǎn)換圖有n個狀態(tài)，其中有個狀態(tài)，其中有一個初態(tài)，至少要有一個終態(tài)一個初態(tài)，至少要有一個終態(tài)(用雙圓圈表示用雙圓圈表示)TJNU-COCIE-WJW2

18、6262022-3-42022-3-43. 狀態(tài)轉(zhuǎn)換圖法（續(xù)狀態(tài)轉(zhuǎn)換圖法（續(xù)2）(4)舉例舉例：構(gòu)造一個識別標識符的狀態(tài)轉(zhuǎn)換圖：構(gòu)造一個識別標識符的狀態(tài)轉(zhuǎn)換圖解：解：其中其中“*”表示在該狀態(tài)下多讀進一個字符表示在該狀態(tài)下多讀進一個字符識別：識別：name1TJNU-COCIE-WJW27272022-3-42022-3-43. 狀態(tài)轉(zhuǎn)換圖法（續(xù)狀態(tài)轉(zhuǎn)換圖法（續(xù)3）：構(gòu)造一個識別整數(shù)的狀態(tài)轉(zhuǎn)換圖，說說識：構(gòu)造一個識別整數(shù)的狀態(tài)轉(zhuǎn)換圖，說說識別別256過程過程解：解：TJNU-COCIE-WJW28282022-3-42022-3-43. 狀態(tài)轉(zhuǎn)換圖法（續(xù)狀態(tài)轉(zhuǎn)換圖法（續(xù)4）： 識別識別FORT

19、RAN實型常數(shù)的狀態(tài)轉(zhuǎn)換圖實型常數(shù)的狀態(tài)轉(zhuǎn)換圖解：解：實數(shù)：小數(shù)形式：實數(shù)：小數(shù)形式：3.413.4 34. 指數(shù)形式：指數(shù)形式：3E+05 即即 3X105TJNU-COCIE-WJW29292022-3-42022-3-4四、四、綜合例子綜合例子用狀態(tài)轉(zhuǎn)換圖法，構(gòu)造一個識別某一個簡單語用狀態(tài)轉(zhuǎn)換圖法，構(gòu)造一個識別某一個簡單語言（言（SL）的所有單詞符號的詞法分析器）的所有單詞符號的詞法分析器TJNU-COCIE-WJW30302022-3-42022-3-4單詞符號單詞符號種別編碼種別編碼助記符號助記符號內(nèi)碼值內(nèi)碼值DIMIFDOSTOPEND標識符標識符常數(shù)（整型）常數(shù)（整型）=+*,（

20、）1234567891011121314$DIM$IF$DO$STOP$END$ID$INT$ASSIGN$PLUS$STAR$POWER$COMMA$LPAR$RPAR-內(nèi)部字符串內(nèi)部字符串標準二進制標準二進制-1、SL的單詞符號及其內(nèi)部表示（的單詞符號及其內(nèi)部表示（P42)TJNU-COCIE-WJW31312022-3-42022-3-42.為了討論方便，對為了討論方便，對SL加三點限制加三點限制（1）所有基本字都規(guī)定為保留字（用戶不能）所有基本字都規(guī)定為保留字（用戶不能用它們來定義標識符的，避免超前搜索用它們來定義標識符的，避免超前搜索 ）（2）對基本字只構(gòu)造一個基本字表，不構(gòu)造）對基

21、本字只構(gòu)造一個基本字表，不構(gòu)造其狀態(tài)轉(zhuǎn)換圖（只要識別出是一個標識符，其狀態(tài)轉(zhuǎn)換圖（只要識別出是一個標識符，就去查基本字表看看是否是基本字）就去查基本字表看看是否是基本字）（3）對基本字，標識符和常數(shù)之間要留有間）對基本字，標識符和常數(shù)之間要留有間隔符（避免超前搜索）隔符（避免超前搜索）TJNU-COCIE-WJW32322022-3-42022-3-43.構(gòu)造能夠識別構(gòu)造能夠識別SL單詞單詞的狀態(tài)轉(zhuǎn)換圖的狀態(tài)轉(zhuǎn)換圖(P43)TJNU-COCIE-WJW33332022-3-42022-3-44. 狀態(tài)轉(zhuǎn)換圖的程序?qū)崿F(xiàn)狀態(tài)轉(zhuǎn)換圖的程序?qū)崿F(xiàn)思路思路：為每個狀態(tài)結(jié)點都編寫一個子程序：為每個狀態(tài)結(jié)點都

22、編寫一個子程序首先，設(shè)以下一些變量或過程首先，設(shè)以下一些變量或過程ch:字符變量字符變量,存放最新讀進的源程序字符存放最新讀進的源程序字符strToken:字符數(shù)組字符數(shù)組,存放構(gòu)成單詞符號的字符串存放構(gòu)成單詞符號的字符串GetChar:子程序過程子程序過程,將下一輸入字符讀到將下一輸入字符讀到ch中中,搜索指搜索指示器前移一字符位置示器前移一字符位置GetBC:子程序過程子程序過程,檢查檢查ch中的字符是否為空白中的字符是否為空白,若是若是,則調(diào)用則調(diào)用GetChar直至直至ch中進入一個非空白字符中進入一個非空白字符Concat:子程序過程子程序過程,將將ch中的字符連接到中的字符連接到s

23、trToken之之后后.例如例如,假定假定strToken原來的值為原來的值為“AB”,而而ch中存放著中存放著C,經(jīng)調(diào)用經(jīng)調(diào)用Concat后后,strToken的值就變?yōu)榈闹稻妥優(yōu)椤癆BC”TJNU-COCIE-WJW34342022-3-42022-3-4IsLetter和和IsDigit:布爾函數(shù)過程布爾函數(shù)過程,他們分別判斷他們分別判斷ch中的字符是否為字母和數(shù)字中的字符是否為字母和數(shù)字Reserve:整型函數(shù)過程整型函數(shù)過程,對對strToken中的字符串中的字符串查找保留字表查找保留字表,若它是一個保留字則返回它的編碼，若它是一個保留字則返回它的編碼，否則返回否則返回0值（假定值（

24、假定0不是保留字的編碼）不是保留字的編碼）Retract:子程序過程子程序過程,將搜索指示器回調(diào)一個字位將搜索指示器回調(diào)一個字位置，將置，將ch置為空白字符置為空白字符InsertId:整型函數(shù)過程整型函數(shù)過程,將將strToken中的標識符插中的標識符插入符號表入符號表,返回符號表指針。返回符號表指針。InsertConst:整型函數(shù)過程整型函數(shù)過程,將將strToken中的常數(shù)中的常數(shù)插入到常數(shù)符號表插入到常數(shù)符號表,放回常數(shù)表針放回常數(shù)表針TJNU-COCIE-WJW35352022-3-42022-3-4然后，對每個狀態(tài)編寫一個對應(yīng)的程序然后，對每個狀態(tài)編寫一個對應(yīng)的程序(1)對于不含

25、回路的狀態(tài)結(jié)點，采用分叉法對于不含回路的狀態(tài)結(jié)點，采用分叉法：GetChar();If(IsLetter()狀態(tài)狀態(tài)j對應(yīng)的程序段對應(yīng)的程序段Else if(IsDigit()狀態(tài)狀態(tài)k對應(yīng)的程序段對應(yīng)的程序段Else if(ch=/)狀態(tài)狀態(tài)l對應(yīng)的程序段對應(yīng)的程序段Else錯誤處理錯誤處理TJNU-COCIE-WJW36362022-3-42022-3-4(2)對于含有回路的狀態(tài)結(jié)點，對應(yīng)一個對于含有回路的狀態(tài)結(jié)點，對應(yīng)一個while語句語句：(3)對于終態(tài)結(jié)點，用對于終態(tài)結(jié)點，用 return(code,value) 其中，其中，code是單詞的種別編碼，是單詞的種別編碼，value是單

26、詞符是單詞符號的屬性值，或無定義。號的屬性值，或無定義。GetChar();while(IsLetter() or IsDigit() GetChar();狀態(tài)狀態(tài)j對應(yīng)的程序段對應(yīng)的程序段TJNU-COCIE-WJW37372022-3-42022-3-45.狀態(tài)轉(zhuǎn)換圖對應(yīng)的詞法分析程序偽代碼狀態(tài)轉(zhuǎn)換圖對應(yīng)的詞法分析程序偽代碼（P45 - 46）TJNU-COCIE-WJW38382022-3-42022-3-4第第1次上機作業(yè)次上機作業(yè)根據(jù)根據(jù)編譯原理編譯原理P45-46頁的詞法分析程序偽代頁的詞法分析程序偽代碼，用碼，用C語言實現(xiàn)，要求語言實現(xiàn)，要求：輸入輸入：由：由P43頁表頁表3.1

27、中的單詞，按詞法規(guī)則組成中的單詞，按詞法規(guī)則組成的語句序列（或用文件存儲，相當于源程序）的語句序列（或用文件存儲，相當于源程序） 例如：例如：IF i0 i=1輸出輸出：打印單詞的種別（用表：打印單詞的種別（用表3.1中的助記符）中的助記符）和單詞的屬性值（表和單詞的屬性值（表3.1中的內(nèi)碼值）中的內(nèi)碼值） 每行一詞，格式每行一詞，格式單詞單詞1：單詞單詞2： 例如：例如：IF:TJNU-COCIE-WJW39392022-3-42022-3-43.3 正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機為了更好地使用狀態(tài)圖構(gòu)造詞法分析程序，為了為了更好地使用狀態(tài)圖構(gòu)造詞法分析程序，為了 討論詞法分析

28、程序的自動生成，需要將狀態(tài)轉(zhuǎn)換討論詞法分析程序的自動生成，需要將狀態(tài)轉(zhuǎn)換圖的概念形式化圖的概念形式化詞法分析器的構(gòu)造的基本思路：詞法分析器的構(gòu)造的基本思路：程序語言的描述程序語言的描述詞法規(guī)則詞法規(guī)則正規(guī)表達式正規(guī)表達式有限自動機有限自動機詞法分析程序詞法分析程序TJNU-COCIE-WJW40402022-3-42022-3-41.字母表字母表（基本字符集）（基本字符集）一個非空的由有限元素組成的集合，每個元素稱一個非空的由有限元素組成的集合，每個元素稱為一個符號，為一個符號，一般用一般用表示表示： = a , b , c = a , b , c 元素：元素：a a，b b，c c: :不同

29、語言有不同的字母表不同語言有不同的字母表：C C語言的字母表中包含：字母語言的字母表中包含：字母AZ,azAZ,az，數(shù)字，數(shù)字0909，標點，標點,.+-,.+-* */ /等等一、一、基本概念基本概念TJNU-COCIE-WJW41412022-3-42022-3-42.字母表字母表上的一個上的一個符號串（字）符號串（字）由字母表由字母表中的符號所構(gòu)成的一個有窮序列，一中的符號所構(gòu)成的一個有窮序列，一般用小寫字母般用小寫字母x, y表示表示：aa，ab，abc，：(1)符號的順序不同代表不同的符號串符號的順序不同代表不同的符號串例如例如ab ba(2)不包含任何字符的序列稱為空字，用不包含

30、任何字符的序列稱為空字，用來表示來表示TJNU-COCIE-WJW42422022-3-42022-3-43.字字(符號串符號串)的連接的連接設(shè)設(shè)x和和y是兩個字是兩個字(符號串符號串)，則定義，則定義xy為他們的連接為他們的連接：ab和和ba連接是連接是abba: (1)是連結(jié)運算的恒等元素是連結(jié)運算的恒等元素x = x= x (2)字字(符號串符號串)的的n次連接次連接xn = xxxx n個個 規(guī)定規(guī)定x0 = x1= x，x2=xx，x3= xxx：x=ab，則，則x0 = ，x1= ab，x2=abab，x3= abababTJNU-COCIE-WJW43432022-3-42022

31、-3-44.集合的集合的(連接連接)積積設(shè)設(shè)U和和V是兩個是兩個“字字(符號串符號串)的集合的集合”，則定義則定義UV為他們的為他們的(連接連接)積積 UV=xy|xU且且yV：設(shè)：設(shè)U=a, ab, V=b, ba, 則則UV=ab, aba, abb, abba：(1)集合的集合的(連接連接)積不滿足交換率積不滿足交換率UVVU (2)集合的集合的(連接連接)積滿足結(jié)合率積滿足結(jié)合率(UV)W = U(VW)TJNU-COCIE-WJW44442022-3-42022-3-45.集合集合V的的n次次(連接連接)積記為：積記為： Vn = V V VV n個個 規(guī)定規(guī)定 V0= ：設(shè)：設(shè)V=

32、a, b，那么，那么V0= V1= a,bV2=VV=aa,ab,ba,bbV3=VVV=V2V=aaa,aba,baa,bba,aab,abb,bab,bbbV4= VVVV=V3V=TJNU-COCIE-WJW45452022-3-42022-3-46.閉包閉包設(shè)設(shè)V是一個字（符號串）的集合，是一個字（符號串）的集合，則則V的閉包定義為的閉包定義為V* *， V* * = V0V1V2：閉包閉包V* * 中的每個字都是由中的每個字都是由V中的字經(jīng)過中的字經(jīng)過有限次連接而成的有限次連接而成的7.正則閉包正則閉包V+ +的定義為的定義為V+ + = VV* * TJNU-COCIE-WJW46

33、462022-3-42022-3-48. *定義（定義（ 的閉包）的閉包）用用*來表示來表示上所有字的全體，空字上所有字的全體，空字也包括在其中也包括在其中* * = 012：設(shè)：設(shè)=a，b，求，求* =,a,b,aa,ab,ba,bb,aaa, :(1)用用來表示不含任何元素的集合，稱為空集，即來表示不含任何元素的集合，稱為空集，即 (2) ， ，之間的區(qū)別之間的區(qū)別：空字；：空字； ：空集；：空集；：僅含有空字的集合：僅含有空字的集合TJNU-COCIE-WJW47472022-3-42022-3-4詞法分析器需要識別語言中具有不同特征的字詞法分析器需要識別語言中具有不同特征的字 識別識別

34、“標識符標識符”、識別、識別“數(shù)數(shù)” ，等等。，等等。我們可以把具有相同特征的字放在一起組成一個集我們可以把具有相同特征的字放在一起組成一個集合，即所謂的合，即所謂的正規(guī)集正規(guī)集然后使用一種形式化的方法來表示正規(guī)集，即所謂然后使用一種形式化的方法來表示正規(guī)集，即所謂的的正規(guī)式正規(guī)式：正規(guī)式是描述單詞結(jié)構(gòu)的一種形式；正規(guī)式是描述單詞結(jié)構(gòu)的一種形式；正規(guī)集是該類單詞的全集。正規(guī)集是該類單詞的全集。二、二、正規(guī)式與正規(guī)集正規(guī)式與正規(guī)集TJNU-COCIE-WJW48482022-3-42022-3-41.正規(guī)式正規(guī)式與與正規(guī)集正規(guī)集的定義（遞歸的定義方法）的定義（遞歸的定義方法）(1)和和是是上的正

35、規(guī)式上的正規(guī)式,它們所表示的正規(guī)集分別為它們所表示的正規(guī)集分別為和和(2)任何任何a,是是上的一個正規(guī)式上的一個正規(guī)式,他所表示的正規(guī)集為他所表示的正規(guī)集為 a (3)假定假定U和和V都是都是上的正規(guī)式，他們所表示的正規(guī)集分別記為上的正規(guī)式，他們所表示的正規(guī)集分別記為L(U)和和L(V)，那么，那么(a) (U|V)是正規(guī)式，所表示的正規(guī)集為是正規(guī)式，所表示的正規(guī)集為L(U)L(V)(b) (UV)是正規(guī)式，所表示的正規(guī)集為是正規(guī)式，所表示的正規(guī)集為L(U) L(V)（連接積）（連接積）(c) (U)*是正規(guī)式，所表示的正規(guī)集為是正規(guī)式，所表示的正規(guī)集為 (L(U)*（閉包）（閉包）僅由有限次

36、使用僅由有限次使用(1)(2)(3)所得到的表達式才是所得到的表達式才是上的正規(guī)式，上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是僅由這些正規(guī)式所表示的字集才是上的正規(guī)集。上的正規(guī)集。：|(或或)、 (連接連接)、*(閉包閉包,任意有限次的自重復連接任意有限次的自重復連接) 運算的優(yōu)先級為：運算的優(yōu)先級為：“ * ” “ ” “ | ”TJNU-COCIE-WJW49492022-3-42022-3-42.舉例舉例 . 令令=a, b正規(guī)式正規(guī)式正規(guī)集正規(guī)集aba|b ab (a|b)(a|b)a*(a|b)*ba*a(a|b)*(a|b)*(aa|bb)(a|b)* a b a,b ab aa,

37、ab,ba,bb , a, aa, 任意個任意個a的串的串, a, b, aa, ab, 所有所有a,b組成的串組成的串b, ba, baa, baaa, 上以上以a為首的字的全體為首的字的全體上含有上含有aa或或bb的字的全體的字的全體TJNU-COCIE-WJW50502022-3-42022-3-4. 令令=A，B, 0, 1正規(guī)式正規(guī)式正規(guī)集正規(guī)集AB0 1A|B 0|1 (A|B|0|1)(A|B|0|1)*(A|B)(A|B|0|1)* (0|1)(0|1)* A B 0 1 A, B 0, 1 A,B,0,1 上字的全體，包含空字上字的全體，包含空字上上“標識符標識符”的全體的全

38、體上上“數(shù)數(shù)”的全體的全體(不包含空字不包含空字)TJNU-COCIE-WJW51512022-3-42022-3-43.兩個正規(guī)式的等價兩個正規(guī)式的等價若兩個正規(guī)式若兩個正規(guī)式U和和V所表示的正規(guī)集相同，則認為所表示的正規(guī)集相同，則認為二者等價，記為：二者等價，記為：U = V：證明：證明b(ab)* = (ba)*b證明：因為，證明：因為，L(b(ab)*)=L(b)L(ab)*) =b ,ab, abab, =b, bab, babab, 又因為，又因為， L(ba)*b)=L(ba)*) L(b)=, ba, baba, b=b, bab, babab, 因此，因此， L(b(ab)*

39、)= L(ba)*b)所以，所以， b(ab)*=(ba)*b(證畢）證畢）TJNU-COCIE-WJW52522022-3-42022-3-44.正規(guī)式的性質(zhì)正規(guī)式的性質(zhì)設(shè)設(shè)U，V，W是上的是上的正規(guī)式，則正規(guī)式，則(1) U | V = V | U或的交換律或的交換律(2) U | ( V|W ) = ( U|V ) | W或的結(jié)合律或的結(jié)合律(3) U ( VW ) = ( UV ) W連接積的結(jié)合律連接積的結(jié)合律(4) U ( V | W ) = ( UV ) | ( UW ) 分配律分配律 ( V | W ) U = VU | WU (5) U = U = UTJNU-COCIE-W

40、JW53532022-3-42022-3-4(1) U | V = V | U或的交換律或的交換律證明：因為，證明：因為，L(U|V) = L(U)L(V) 又因為，又因為，L(V|U) = L(V)L(U) = L(U)L(V) 因為，因為， L(U|V) = L(V|U) 所以，所以，U | V = V | UTJNU-COCIE-WJW54542022-3-42022-3-4(2) U | ( V|W ) = ( U|V ) | W或的結(jié)合律或的結(jié)合律證明：證明：因為，因為，L(U|(V|W)=L(U)L(V|W)=L(U)L(V)L(W)又因為，又因為，L( U|V ) | W) =

41、L(U|V)L(W)= L(U)L(V)L(W)因此，因此， L(U|(V|W) = L( U|V ) | W) 所以，所以， U | ( V|W ) = ( U|V ) | W(3)(4)(5) 留給同學們課下證明留給同學們課下證明TJNU-COCIE-WJW55552022-3-42022-3-4下面，我們把狀態(tài)轉(zhuǎn)換圖再形式化一下下面，我們把狀態(tài)轉(zhuǎn)換圖再形式化一下及所謂的及所謂的有限自動機有限自動機有兩種：有兩種：l確定的有限自動機（確定的有限自動機（DFA）（Deterministic Finite Automata)l非確定的有限自動機（非確定的有限自動機（NFA）（Non-deter

42、ministic Finite Automata)TJNU-COCIE-WJW56562022-3-42022-3-41.定義定義：一個確定有限自動機（：一個確定有限自動機（DFA）M是一個五元式：是一個五元式：M = (S, , f, s0, F)，其中，其中S是一個有限的狀態(tài)集合，它的每個元素我們稱為是一個有限的狀態(tài)集合，它的每個元素我們稱為一個狀態(tài)一個狀態(tài)是一個有窮的輸入符號的字母表，它的每個元素是一個有窮的輸入符號的字母表，它的每個元素我們稱為一個輸入字符我們稱為一個輸入字符f是從是從 S S的單值部分映射的單值部分映射s0是是S的一個元素，為初始狀態(tài)，它是唯一的的一個元素，為初始狀態(tài)

43、，它是唯一的1)狀態(tài)集合狀態(tài)集合F是終止狀態(tài)的集合，它是是終止狀態(tài)的集合，它是S的子集的子集(可空可空)三、三、確定的有限自動機（確定的有限自動機（DFA） （Deterministic Finite Automata)TJNU-COCIE-WJW57572022-3-42022-3-4：所謂的自動機不是指一臺實際的機器，而是一所謂的自動機不是指一臺實際的機器，而是一種數(shù)學模型（集合，函數(shù)，序列種數(shù)學模型（集合，函數(shù)，序列），利用它），利用它模擬計算機識別的功能模擬計算機識別的功能所謂確定性是指，所謂確定性是指，f(s, a) = s 是單值函數(shù)。是單值函數(shù)。 對對任何狀態(tài)任何狀態(tài)sS，和輸入

44、符號，和輸入符號 a ， f(s, a) 唯唯一的確定下一個狀態(tài)一的確定下一個狀態(tài)所謂有限性是指，所謂有限性是指，S是一個有限的狀態(tài)集合，并是一個有限的狀態(tài)集合，并且且是一個有限的輸入符號的字母表是一個有限的輸入符號的字母表1)用上述用上述5條，來定義一個條，來定義一個DFA，來完成識別一個，來完成識別一個序列是否被機器所接受序列是否被機器所接受TJNU-COCIE-WJW58582022-3-42022-3-4：設(shè)一個奇偶校驗器，其功能是，用來識別由：設(shè)一個奇偶校驗器，其功能是，用來識別由1和和0組成組成的序列是否含有奇數(shù)個的序列是否含有奇數(shù)個1。解：設(shè)解：設(shè)DFA M = (S, , f,

45、 s0, F)來表示奇偶校驗器，其中來表示奇偶校驗器，其中1) S：EVEN， ODD2) ：0，13) f: f(EVEN, 0) = EVENf(EVEN, 1) = ODDf(ODD, 0) = ODDf(ODD, 1) = EVEN4) s0: EVEN5) F: ODD ：如果一個序列使自動機從開始狀態(tài)出發(fā)，最后達：如果一個序列使自動機從開始狀態(tài)出發(fā)，最后達到一個終態(tài)，那么該輸入序列就被該自動解接受到一個終態(tài)，那么該輸入序列就被該自動解接受（識別，讀出），否則將被拒絕。（識別，讀出），否則將被拒絕。TJNU-COCIE-WJW59592022-3-42022-3-4：1 1 0 1

46、1 1 0EVENODDEVENEVENODDEVENODDODDf: f(EVEN, 0) = EVENf(EVEN, 1) = ODDf(ODD, 0) = ODDf(ODD, 1) = EVEN1101110TJNU-COCIE-WJW60602022-3-42022-3-42.DFA M的表示方法的表示方法狀態(tài)轉(zhuǎn)換矩陣表示法狀態(tài)轉(zhuǎn)換矩陣表示法(用一個用一個“表表”來表示來表示)設(shè)矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素設(shè)矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素是是f（s，a）的值）的值：設(shè)：設(shè)DFA M = (0,1,2,3,a, b, f, 0, 3)，其中其中f: f(0, a

47、) = 1,f(0, b) = 2 f(1, a) = 3,f(1, b) = 2 f(2, a) = 1,f(2, b) = 3 f(3, a) = 3,f(3, b) = 3輸入字符輸入字符狀態(tài)狀態(tài)ab012313132233TJNU-COCIE-WJW61612022-3-42022-3-4(2) 用狀態(tài)轉(zhuǎn)換圖來表示用狀態(tài)轉(zhuǎn)換圖來表示：設(shè)：設(shè)DFA M = (0,1,2,3,a, b, f, 0, 3)，其中，其中f: f(0, a) = 1,f(0, b) = 2 f(1, a) = 3,f(1, b) = 2 f(2, a) = 1,f(2, b) = 3 f(3, a) = 3,f

48、(3, b) = 3TJNU-COCIE-WJW62622022-3-42022-3-43.DFA M的識別功能的識別功能對于對于*中任何字中任何字，如果存在一條從初態(tài)結(jié)點到，如果存在一條從初態(tài)結(jié)點到某個終態(tài)結(jié)點的道路，這條路上所有的標識符某個終態(tài)結(jié)點的道路，這條路上所有的標識符連成的字等于連成的字等于 ，則，則可被可被DFA M所識別所識別(接受，接受，讀出讀出)：*=aa, bb, ab, baa, aba, bbb, bba, TJNU-COCIE-WJW63632022-3-42022-3-4：(1)若若M的初態(tài)結(jié)點同時又是終態(tài)節(jié)點，則空字可的初態(tài)結(jié)點同時又是終態(tài)節(jié)點，則空字可被被M識

49、別識別(2)DFA M所能識別的字的全體記為所能識別的字的全體記為L(M)(3)如果一個如果一個DFA M的輸入字母表為的輸入字母表為，則我們稱，則我們稱M是是上的一個上的一個DFA(4)若若V是是上的一個正規(guī)集，當且僅當存在一個上的一個正規(guī)集，當且僅當存在一個上的上的DFA M，使得，使得V = L(M)TJNU-COCIE-WJW64642022-3-42022-3-41.定義定義:一個非確定有限自動機（一個非確定有限自動機（NFA）M是一個五元式是一個五元式M = (S, , f, S0, F)，其中，其中S是一個有限的狀態(tài)集合，它的每個元素我們是一個有限的狀態(tài)集合，它的每個元素我們稱為

50、一個狀態(tài)稱為一個狀態(tài)是一個有限的輸入符號的字母表，它的每個是一個有限的輸入符號的字母表，它的每個元素我們稱為一個輸入字符元素我們稱為一個輸入字符f是從是從S*2S 的部分映射，其中，的部分映射，其中，2S表示表示S的冪集合（所有的冪集合（所有S的子集組成的集合）的子集組成的集合）（f是非單值的是非單值的M是非確定）是非確定）狀態(tài)集合狀態(tài)集合S0是初始狀態(tài)集合，它是是初始狀態(tài)集合，它是S的子集的子集1)狀態(tài)集合狀態(tài)集合F是終止狀態(tài)的集合，它是是終止狀態(tài)的集合，它是S的子集的子集四、四、非確定的有限自動機非確定的有限自動機(NFA)（Non-deterministic Finite Automat

51、a)TJNU-COCIE-WJW65652022-3-42022-3-42.NFA M表示方法表示方法(1) 用狀態(tài)矩陣表示用狀態(tài)矩陣表示：設(shè)：設(shè)NFA M = (0,1,2,a, b, f, 0, 1,2)，其中，其中f: f(0, aa) =1,f(0, bb) = 2 f(0, a) = 0,f(0, b) = 0 f(1, a) = 1,f(1, b) = 1 f(2, a) = 2,f(2, b) = 2字字狀態(tài)狀態(tài)aabbab0121-2-012012TJNU-COCIE-WJW66662022-3-42022-3-4(2) 用狀態(tài)轉(zhuǎn)換圖表示用狀態(tài)轉(zhuǎn)換圖表示：設(shè)：設(shè)NFA M =

52、(0,1,2,a, b, f, 0, 1,2)，其中，其中f: f(0, aa) = 1,f(0, bb) =2 f(0, a) = 0,f(0, b) = 0 f(1, a) = 1,f(1, b) = 1 f(2, a) = 2,f(2, b) = 2TJNU-COCIE-WJW67672022-3-42022-3-43.NFA M識別條件識別條件對于對于*中的任何字中的任何字若存在一條從某一個初態(tài)若存在一條從某一個初態(tài)到某一個終態(tài)的通路且這條路上所有弧的標記到某一個終態(tài)的通路且這條路上所有弧的標記字連接成的字等于字連接成的字等于 ，則，則可被可被NFA M識別識別(讀出，接受讀出，接受)

53、4.有限自動機的等價有限自動機的等價對任何兩個有限的自動機對任何兩個有限的自動機M1和和M2，若有，若有L(M1)=L(M2)，則稱，則稱M1與與M2等價。等價。 TJNU-COCIE-WJW68682022-3-42022-3-4: (1) 若若M的某些結(jié)點既是初態(tài)結(jié)點又是終態(tài)結(jié)的某些結(jié)點既是初態(tài)結(jié)點又是終態(tài)結(jié)點，或者存在一條從某初態(tài)結(jié)點到某個終態(tài)結(jié)點，或者存在一條從某初態(tài)結(jié)點到某個終態(tài)結(jié)點的點的通路，那么空字通路，那么空字可為可為M所識別所識別(2) DFA是是NFA的一個特例，對于每個的一個特例，對于每個NFA M存在一個存在一個DFA M使得使得L(M) = L(M)，也就是說，也就是

54、說M和和M是等價的是等價的TJNU-COCIE-WJW69692022-3-42022-3-4定理定理1：對于任何：對于任何上上NFA M都可構(gòu)造一個都可構(gòu)造一個上的正上的正規(guī)式規(guī)式V，使得，使得 L(V) = L(M) 其中，其中，L(M)是是上上NFA M所能識別的字的全體，所能識別的字的全體，L(V)是是上的正規(guī)集上的正規(guī)集五、五、正規(guī)式與有限自動機的等價性正規(guī)式與有限自動機的等價性TJNU-COCIE-WJW70702022-3-42022-3-4問題問題：如何由一個：如何由一個NFA M，構(gòu)造一個正規(guī)式，構(gòu)造一個正規(guī)式V方法：方法：(1)在在M轉(zhuǎn)換圖上加進轉(zhuǎn)換圖上加進X結(jié)點和結(jié)點和Y

55、結(jié)點，從結(jié)點，從X結(jié)點用結(jié)點用弧弧連接連接M的所有初態(tài)結(jié)點，的所有初態(tài)結(jié)點，M的所有終態(tài)結(jié)的所有終態(tài)結(jié)點用弧點用弧連接到連接到Y(jié)，得到一個，得到一個NFA M，且，且L(M) = L(M)(2)使用替換規(guī)則逐步消去使用替換規(guī)則逐步消去M的所有結(jié)點，直到只的所有結(jié)點，直到只剩下剩下X結(jié)點和結(jié)點和Y結(jié)點，在消去過程中，逐步使結(jié)點，在消去過程中，逐步使用正規(guī)式來標記箭弧用正規(guī)式來標記箭弧TJNU-COCIE-WJW71712022-3-42022-3-4替換規(guī)則：替換規(guī)則：TJNU-COCIE-WJW72722022-3-42022-3-4：對于一個：對于一個上的上的NFA M，構(gòu)造一個正規(guī)式，構(gòu)造

56、一個正規(guī)式V，使得使得L(M)=L(V)TJNU-COCIE-WJW73732022-3-42022-3-4第二步第二步，消去結(jié)點，消去結(jié)點1第三步第三步，消去結(jié)點，消去結(jié)點0第一步第一步：加入：加入X結(jié)點和結(jié)點和Y結(jié)點得到一個結(jié)點得到一個M，且，且L(M)=L(M)TJNU-COCIE-WJW74742022-3-42022-3-4定理定理2. 對于對于上的每一個正規(guī)式上的每一個正規(guī)式V，存在一個，存在一個上上的的DFA M，使得，使得L(M) = L(V) 問題問題：如何由一個正規(guī)式：如何由一個正規(guī)式V，構(gòu)造一個，構(gòu)造一個DFA M思路思路：分兩步走：分兩步走1.根據(jù)根據(jù)V，構(gòu)造一個，構(gòu)造

57、一個NFA M，使得，使得L(M) = L(V)2.將將M確定化，變?yōu)榇_定化，變?yōu)镈FA MTJNU-COCIE-WJW75752022-3-42022-3-4方法方法：第一步第一步，在，在上構(gòu)造一個上構(gòu)造一個NFA M(1)構(gòu)造一個拓廣的轉(zhuǎn)換圖構(gòu)造一個拓廣的轉(zhuǎn)換圖TJNU-COCIE-WJW76762022-3-42022-3-4(2)使用分裂規(guī)則對使用分裂規(guī)則對V進行分裂，加進新結(jié)點，直到進行分裂，加進新結(jié)點，直到把圖轉(zhuǎn)換成每條弧上標識為把圖轉(zhuǎn)換成每條弧上標識為上的一個字符或上的一個字符或最后得到一個最后得到一個NFA M且且L(M) = L(V)TJNU-COCIE-WJW7777202

58、2-3-42022-3-4第二步第二步，把，把M確定化確定化定義定義1 某個狀態(tài)集某個狀態(tài)集I的的(空字空字)閉包：閉包：_CLOSURE( I ) 是一個狀態(tài)集，由兩部分組成是一個狀態(tài)集，由兩部分組成:n狀態(tài)集狀態(tài)集I中的所有狀態(tài)。中的所有狀態(tài)。n從從I中的狀態(tài)出發(fā)經(jīng)過任意條中的狀態(tài)出發(fā)經(jīng)過任意條弧，所能到達的狀態(tài)的全體?；?，所能到達的狀態(tài)的全體。定義定義2 某個狀態(tài)集某個狀態(tài)集I的的a弧轉(zhuǎn)換：弧轉(zhuǎn)換：move( I, a ) 是一個狀態(tài)集，是從是一個狀態(tài)集，是從I中的狀態(tài)出發(fā)經(jīng)過一條中的狀態(tài)出發(fā)經(jīng)過一條a弧到達的弧到達的狀態(tài)的全體。狀態(tài)的全體。定義定義3 Ia =_CLOSURE( mov

59、e( I, a ) )是一個狀態(tài)集。是一個狀態(tài)集。TJNU-COCIE-WJW78782022-3-42022-3-4：有如下一個：有如下一個NFA N的狀態(tài)轉(zhuǎn)換圖的狀態(tài)轉(zhuǎn)換圖假定假定 I=1, 2，求，求Ia = ？解：解： move( I, a ) = Ia=_CLOSURE(J) = 1a a5438267a aa a4,5,35,6,2,4,7,3,8a aa aa a5436278J =TJNU-COCIE-WJW79792022-3-42022-3-4：有如下一個狀態(tài)轉(zhuǎn)換圖：有如下一個狀態(tài)轉(zhuǎn)換圖已知已知K=5, 4, 1求求Ka ， Kb 解：求解：求Ka J=5, 3 Ka =_

60、CLOSURE(J) = 5, 3, 1求求KbJ=5, 2, 4Kb =_CLOSURE(J) = 5, 2, 4, 1, 6, YX12a a56b ba ab b43a aa ab bb bYTJNU-COCIE-WJW80802022-3-42022-3-4(1) 基本思想基本思想:把把NFA的一些狀態(tài)，即狀態(tài)子集，合并為的一些狀態(tài)，即狀態(tài)子集，合并為DFA的一個狀態(tài)。的一個狀態(tài)。子集法子集法TJNU-COCIE-WJW81812022-3-42022-3-4(2) 具體做法：具體做法：假設(shè)有一個假設(shè)有一個NFA N，=a1ak ，初始狀態(tài)集是，初始狀態(tài)集是S0，用子集法把用子集法把N