編譯原理-第三章

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

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

3、詞符號(hào)概念單詞符號(hào)概念指語言中具有獨(dú)立意義的最小的語法符號(hào)指語言中具有獨(dú)立意義的最小的語法符號(hào)：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)鍵字）由程序語言定義的具有固定意義的標(biāo)識(shí)符。由程序語言定義的具有固定意義的標(biāo)識(shí)符。用戶不能用來表示變量名，函數(shù)名等標(biāo)識(shí)符用戶不能用來表示變量名，函數(shù)名等標(biāo)識(shí)符：C語言中的語言中的“if” “el

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

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

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

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

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

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

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

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

12、緩沖區(qū)緩沖區(qū)掃描器掃描器掃描緩沖區(qū)掃描緩沖區(qū)輸入輸入列表列表單詞符號(hào)單詞符號(hào)二、二、詞法分析器的工作過程詞法分析器的工作過程TJNU-COCIE-WJW18182022-3-42022-3-41. 超前搜索超前搜索(1)關(guān)鍵字的識(shí)別關(guān)鍵字的識(shí)別前提：允許用戶使用基本字（關(guān)鍵字）前提：允許用戶使用基本字（關(guān)鍵字）：試分析下面：試分析下面FORTRAN的幾個(gè)語句的幾個(gè)語句（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 三、三、單詞符號(hào)的識(shí)別單詞符號(hào)的識(shí)別TJNU-COCIE-WJW19192022-3-42022-3-41. 超前搜索法（續(xù)超前搜索法（續(xù)1）(2) 標(biāo)識(shí)符的識(shí)別標(biāo)識(shí)符的識(shí)別一般是以一般是以字母字母開頭后跟開頭后跟數(shù)字?jǐn)?shù)字/字母字母的字符串，后邊的字符串，后邊一般都有算符和界符，比較好識(shí)別一般都有算符和界符，比較好識(shí)別(3)常數(shù)的識(shí)別常數(shù)的識(shí)別：對(duì)于：對(duì)于FORTRAN5.EQ.M（5=M）5.E08（5*108)直到超前掃描到字母直到超前掃描到字母Q時(shí)才能確定時(shí)才能確定5的詞性的詞性3HABC

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

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

16、除此之外除此之外：都是一個(gè)基本字符表示一個(gè)單詞：都是一個(gè)基本字符表示一個(gè)單詞TJNU-COCIE-WJW23232022-3-42022-3-4子子程程序序1子子程程序序2子子程程序序3子子程程序序4子子程程序序5下一個(gè)語句下一個(gè)語句字符是否讀來字符是否讀來該字符是什么該字符是什么讀讀一一個(gè)個(gè)符符號(hào)號(hào)字母字母數(shù)字?jǐn)?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)換圖的功能識(shí)別

17、（接受）一定的符號(hào)串（單詞）識(shí)別（接受）一定的符號(hào)串（單詞）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é)點(diǎn)結(jié)點(diǎn)：代表狀態(tài)，用圓圈表示：代表狀態(tài)，用圓圈表示箭弧箭弧：狀態(tài)之間用箭弧連接：狀態(tài)之間用箭弧連接箭弧上的標(biāo)記箭弧上的標(biāo)記：代表在射出節(jié)點(diǎn)下可能出現(xiàn)的：代表在射出節(jié)點(diǎn)下可能出現(xiàn)的字符或字符串字符或字符串：一個(gè)完整的狀態(tài)轉(zhuǎn)換圖有：一個(gè)完整的狀態(tài)轉(zhuǎn)換圖有n個(gè)狀態(tài)，其中有個(gè)狀態(tài)，其中有一個(gè)初態(tài)，至少要有一個(gè)終態(tài)一個(gè)初態(tài)，至少要有一個(gè)終態(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)造一個(gè)識(shí)別標(biāo)識(shí)符的狀態(tài)轉(zhuǎn)換圖：構(gòu)造一個(gè)識(shí)別標(biāo)識(shí)符的狀態(tài)轉(zhuǎn)換圖解：解：其中其中“*”表示在該狀態(tài)下多讀進(jìn)一個(gè)字符表示在該狀態(tài)下多讀進(jìn)一個(gè)字符識(shí)別：識(shí)別：name1TJNU-COCIE-WJW27272022-3-42022-3-43. 狀態(tài)轉(zhuǎn)換圖法（續(xù)狀態(tài)轉(zhuǎn)換圖法（續(xù)3）：構(gòu)造一個(gè)識(shí)別整數(shù)的狀態(tài)轉(zhuǎn)換圖，說說識(shí)：構(gòu)造一個(gè)識(shí)別整數(shù)的狀態(tài)轉(zhuǎn)換圖，說說識(shí)別別256過程過程解：解：TJNU-COCIE-WJW28282022-3-42022-3-43. 狀態(tài)轉(zhuǎn)換圖法（續(xù)狀態(tài)轉(zhuǎn)換圖法（續(xù)4）： 識(shí)別識(shí)別FORT

19、RAN實(shí)型常數(shù)的狀態(tài)轉(zhuǎn)換圖實(shí)型常數(shù)的狀態(tài)轉(zhuǎn)換圖解：解：實(shí)數(shù)：小數(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)造一個(gè)識(shí)別某一個(gè)簡單語用狀態(tài)轉(zhuǎn)換圖法，構(gòu)造一個(gè)識(shí)別某一個(gè)簡單語言（言（SL）的所有單詞符號(hào)的詞法分析器）的所有單詞符號(hào)的詞法分析器TJNU-COCIE-WJW30302022-3-42022-3-4單詞符號(hào)單詞符號(hào)種別編碼種別編碼助記符號(hào)助記符號(hào)內(nèi)碼值內(nèi)碼值DIMIFDOSTOPEND標(biāo)識(shí)符標(biāo)識(shí)符常數(shù)（整型）常數(shù)（整型）=+*,（

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

21、本字只構(gòu)造一個(gè)基本字表，不構(gòu)造其狀態(tài)轉(zhuǎn)換圖（只要識(shí)別出是一個(gè)標(biāo)識(shí)符，其狀態(tài)轉(zhuǎn)換圖（只要識(shí)別出是一個(gè)標(biāo)識(shí)符，就去查基本字表看看是否是基本字）就去查基本字表看看是否是基本字）（3）對(duì)基本字，標(biāo)識(shí)符和常數(shù)之間要留有間）對(duì)基本字，標(biāo)識(shí)符和常數(shù)之間要留有間隔符（避免超前搜索）隔符（避免超前搜索）TJNU-COCIE-WJW32322022-3-42022-3-43.構(gòu)造能夠識(shí)別構(gòu)造能夠識(shí)別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)思路思路：為每個(gè)狀態(tài)結(jié)點(diǎn)都編寫一個(gè)子程序：為每個(gè)狀態(tài)結(jié)點(diǎn)都

22、編寫一個(gè)子程序首先，設(shè)以下一些變量或過程首先，設(shè)以下一些變量或過程ch:字符變量字符變量,存放最新讀進(jìn)的源程序字符存放最新讀進(jìn)的源程序字符strToken:字符數(shù)組字符數(shù)組,存放構(gòu)成單詞符號(hào)的字符串存放構(gòu)成單詞符號(hào)的字符串GetChar:子程序過程子程序過程,將下一輸入字符讀到將下一輸入字符讀到ch中中,搜索指搜索指示器前移一字符位置示器前移一字符位置GetBC:子程序過程子程序過程,檢查檢查ch中的字符是否為空白中的字符是否為空白,若是若是,則調(diào)用則調(diào)用GetChar直至直至ch中進(jìn)入一個(gè)非空白字符中進(jìn)入一個(gè)非空白字符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ù)過程,對(duì)對(duì)strToken中的字符串中的字符串查找保留字表查找保留字表,若它是一個(gè)保留字則返回它的編碼，若它是一個(gè)保留字則返回它的編碼，否則返回否則返回0值（假定值（

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

25、回路的狀態(tài)結(jié)點(diǎn)，采用分叉法對(duì)于不含回路的狀態(tài)結(jié)點(diǎ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=/)狀態(tài)狀態(tài)l對(duì)應(yīng)的程序段對(duì)應(yīng)的程序段Else錯(cuò)誤處理錯(cuò)誤處理TJNU-COCIE-WJW36362022-3-42022-3-4(2)對(duì)于含有回路的狀態(tài)結(jié)點(diǎn)，對(duì)應(yīng)一個(gè)對(duì)于含有回路的狀態(tài)結(jié)點(diǎn)，對(duì)應(yīng)一個(gè)while語句語句：(3)對(duì)于終態(tài)結(jié)點(diǎn)，用對(duì)于終態(tài)結(jié)點(diǎn)，用 return(code,value) 其中，其中，code是單詞的種別編碼，是單詞的種別編碼，value是單

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

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

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

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

30、任何字符的序列稱為空字，用來表示來表示TJNU-COCIE-WJW42422022-3-42022-3-43.字字(符號(hào)串符號(hào)串)的連接的連接設(shè)設(shè)x和和y是兩個(gè)字是兩個(gè)字(符號(hào)串符號(hào)串)，則定義，則定義xy為他們的連接為他們的連接：ab和和ba連接是連接是abba: (1)是連結(jié)運(yùn)算的恒等元素是連結(jié)運(yùn)算的恒等元素x = x= x (2)字字(符號(hào)串符號(hào)串)的的n次連接次連接xn = xxxx n個(gè)個(gè) 規(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是兩個(gè)是兩個(gè)“字字(符號(hào)串符號(hào)串)的集合的集合”，則定義則定義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個(gè)個(gè) 規(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是一個(gè)字（符號(hào)串）的集合，是一個(gè)字（符號(hào)串）的集合，則則V的閉包定義為的閉包定義為V* *， V* * = V0V1V2：閉包閉包V* * 中的每個(gè)字都是由中的每個(gè)字都是由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詞法分析器需要識(shí)別語言中具有不同特征的字詞法分析器需要識(shí)別語言中具有不同特征的字 識(shí)別識(shí)別

34、“標(biāo)識(shí)符標(biāo)識(shí)符”、識(shí)別、識(shí)別“數(shù)數(shù)” ，等等。，等等。我們可以把具有相同特征的字放在一起組成一個(gè)集我們可以把具有相同特征的字放在一起組成一個(gè)集合，即所謂的合，即所謂的正規(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,是是上的一個(gè)正規(guī)式上的一個(gè)正規(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)所得到的表達(dá)式才是所得到的表達(dá)式才是上的正規(guī)式，上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是僅由這些正規(guī)式所表示的字集才是上的正規(guī)集。上的正規(guī)集。：|(或或)、 (連接連接)、*(閉包閉包,任意有限次的自重復(fù)連接任意有限次的自重復(fù)連接) 運(yùn)算的優(yōu)先級(jí)為：運(yùn)算的優(yōu)先級(jí)為：“ * ” “ ” “ | ”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, 任意個(gè)任意個(gè)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 上字的全體，包含空字上字的全體，包含空字上上“標(biāo)識(shí)符標(biāo)識(shí)符”的全體的全

38、體上上“數(shù)數(shù)”的全體的全體(不包含空字不包含空字)TJNU-COCIE-WJW51512022-3-42022-3-43.兩個(gè)正規(guī)式的等價(jià)兩個(gè)正規(guī)式的等價(jià)若兩個(gè)正規(guī)式若兩個(gè)正規(guī)式U和和V所表示的正規(guī)集相同，則認(rèn)為所表示的正規(guī)集相同，則認(rèn)為二者等價(jià)，記為：二者等價(jià)，記為：U = V：證明：證明b(ab)* = (ba)*b證明：因?yàn)椋C明：因?yàn)?，L(b(ab)*)=L(b)L(ab)*) =b ,ab, abab, =b, bab, babab, 又因?yàn)?，又因?yàn)椋?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或的交換律或的交換律證明：因?yàn)椋C明：因?yàn)?，L(U|V) = L(U)L(V) 又因?yàn)?，又因?yàn)?，L(V|U) = L(V)L(U) = L(U)L(V) 因?yàn)?，因?yàn)椋?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é)合律證明：證明：因?yàn)?，因?yàn)椋琇(U|(V|W)=L(U)L(V|W)=L(U)L(V)L(W)又因?yàn)?，又因?yàn)?，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) 留給同學(xué)們課下證明留給同學(xué)們課下證明TJNU-COCIE-WJW55552022-3-42022-3-4下面，我們把狀態(tài)轉(zhuǎn)換圖再形式化一下下面，我們把狀態(tài)轉(zhuǎn)換圖再形式化一下及所謂的及所謂的有限自動(dòng)機(jī)有限自動(dòng)機(jī)有兩種：有兩種：l確定的有限自動(dòng)機(jī)（確定的有限自動(dòng)機(jī)（DFA）（Deterministic Finite Automata)l非確定的有限自動(dòng)機(jī)（非確定的有限自動(dòng)機(jī)（NFA）（Non-deter

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

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

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

45、 s0, F)來表示奇偶校驗(yàn)器，其中來表示奇偶校驗(yàn)器，其中1) S：EVEN， ODD2) ：0，13) f: f(EVEN, 0) = EVENf(EVEN, 1) = ODDf(ODD, 0) = ODDf(ODD, 1) = EVEN4) s0: EVEN5) F: ODD ：如果一個(gè)序列使自動(dòng)機(jī)從開始狀態(tài)出發(fā)，最后達(dá)：如果一個(gè)序列使自動(dòng)機(jī)從開始狀態(tài)出發(fā)，最后達(dá)到一個(gè)終態(tài)，那么該輸入序列就被該自動(dòng)解接受到一個(gè)終態(tài)，那么該輸入序列就被該自動(dòng)解接受（識(shí)別，讀出），否則將被拒絕。（識(shí)別，讀出），否則將被拒絕。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)換矩陣表示法(用一個(gè)用一個(gè)“表表”來表示來表示)設(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的識(shí)別功能的識(shí)別功能對(duì)于對(duì)于*中任何字中任何字，如果存在一條從初態(tài)結(jié)點(diǎn)到，如果存在一條從初態(tài)結(jié)點(diǎn)到某個(gè)終態(tài)結(jié)點(diǎn)的道路，這條路上所有的標(biāo)識(shí)符某個(gè)終態(tài)結(jié)點(diǎn)的道路，這條路上所有的標(biāo)識(shí)符連成的字等于連成的字等于 ，則，則可被可被DFA M所識(shí)別所識(shí)別(接受，接受，讀出讀出)：*=aa, bb, ab, baa, aba, bbb, bba, TJNU-COCIE-WJW63632022-3-42022-3-4：(1)若若M的初態(tài)結(jié)點(diǎn)同時(shí)又是終態(tài)節(jié)點(diǎn)，則空字可的初態(tài)結(jié)點(diǎn)同時(shí)又是終態(tài)節(jié)點(diǎn)，則空字可被被M識(shí)

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

50、一個(gè)狀態(tài)稱為一個(gè)狀態(tài)是一個(gè)有限的輸入符號(hào)的字母表，它的每個(gè)是一個(gè)有限的輸入符號(hào)的字母表，它的每個(gè)元素我們稱為一個(gè)輸入字符元素我們稱為一個(gè)輸入字符f是從是從S*2S 的部分映射，其中，的部分映射，其中，2S表示表示S的冪集合（所有的冪集合（所有S的子集組成的集合）的子集組成的集合）（f是非單值的是非單值的M是非確定）是非確定）狀態(tài)集合狀態(tài)集合S0是初始狀態(tài)集合，它是是初始狀態(tài)集合，它是S的子集的子集1)狀態(tài)集合狀態(tài)集合F是終止?fàn)顟B(tài)的集合，它是是終止?fàn)顟B(tài)的集合，它是S的子集的子集四、四、非確定的有限自動(dòng)機(jī)非確定的有限自動(dòng)機(jī)(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識(shí)別條件識(shí)別條件對(duì)于對(duì)于*中的任何字中的任何字若存在一條從某一個(gè)初態(tài)若存在一條從某一個(gè)初態(tài)到某一個(gè)終態(tài)的通路且這條路上所有弧的標(biāo)記到某一個(gè)終態(tài)的通路且這條路上所有弧的標(biāo)記字連接成的字等于字連接成的字等于 ，則，則可被可被NFA M識(shí)別識(shí)別(讀出，接受讀出，接受)

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

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

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

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

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

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

59、e( I, a ) )是一個(gè)狀態(tài)集。是一個(gè)狀態(tài)集。TJNU-COCIE-WJW78782022-3-42022-3-4：有如下一個(gè)：有如下一個(gè)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：有如下一個(gè)狀態(tài)轉(zhuǎn)換圖：有如下一個(gè)狀態(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的一個(gè)狀態(tài)。的一個(gè)狀態(tài)。子集法子集法TJNU-COCIE-WJW81812022-3-42022-3-4(2) 具體做法：具體做法：假設(shè)有一個(gè)假設(shè)有一個(gè)NFA N，=a1ak ，初始狀態(tài)集是，初始狀態(tài)集是S0，用子集法把用子集法把N