同濟(jì)大學(xué)編譯原理 第三章 詞法分析

1、第三章 詞法分析概括大家的工作n實(shí)現(xiàn)了基本的詞法分析功能實(shí)現(xiàn)了基本的詞法分析功能n緩沖區(qū)的設(shè)置緩沖區(qū)的設(shè)置n字符串的預(yù)讀（超前搜索）字符串的預(yù)讀（超前搜索）n引入了狀態(tài)轉(zhuǎn)換圖模型引入了狀態(tài)轉(zhuǎn)換圖模型n詞法錯(cuò)誤的診斷和定位詞法錯(cuò)誤的診斷和定位內(nèi)容線(xiàn)索n對(duì)于詞法分析器的要求對(duì)于詞法分析器的要求n詞法分析器的設(shè)計(jì)詞法分析器的設(shè)計(jì)n正規(guī)表達(dá)式與有限自動(dòng)機(jī)正規(guī)表達(dá)式與有限自動(dòng)機(jī)n詞法分析器的自動(dòng)生成詞法分析器的自動(dòng)生成詞法分析器的功能源程序掃描器scanner1、關(guān)鍵字2、標(biāo)識(shí)符5、界符4、運(yùn)算符3、常數(shù)由程序語(yǔ)言定義的具有固定意由程序語(yǔ)言定義的具有固定意義的標(biāo)識(shí)符。也可稱(chēng)為保留字義的標(biāo)識(shí)符。也可稱(chēng)為保

2、留字或基本字。例如：或基本字。例如：C C中的中的intint，whilewhile，ifif等。等。它是確定的。它是確定的。界符：如逗號(hào)、分號(hào)、括號(hào)、界符：如逗號(hào)、分號(hào)、括號(hào)、/ /* *，* */ / 等。它是確定的。等。它是確定的。運(yùn)算符：如運(yùn)算符：如+ +、- -、* *、/ / 等。等。它是確定的。它是確定的。常數(shù)的類(lèi)型一般有整型、實(shí)型、常數(shù)的類(lèi)型一般有整型、實(shí)型、布爾型、文字型等。它是不限布爾型、文字型等。它是不限的。的。用來(lái)表示各種名字，如變量名、用來(lái)表示各種名字，如變量名、數(shù)組名、過(guò)程名等。它是不限數(shù)組名、過(guò)程名等。它是不限的。的。單詞符號(hào)單詞符號(hào)單詞符號(hào)表示形式n詞法分析器輸

3、出的單詞符號(hào)常表示成二元組：詞法分析器輸出的單詞符號(hào)常表示成二元組： ( (單詞種別單詞種別, , 單詞符號(hào)的屬性值單詞符號(hào)的屬性值) ) 單詞種別是語(yǔ)法分析需要的信息單詞種別是語(yǔ)法分析需要的信息單詞符號(hào)屬性值則是編譯其它階段需要的信息單詞符號(hào)屬性值則是編譯其它階段需要的信息, ,簡(jiǎn)稱(chēng)單簡(jiǎn)稱(chēng)單詞值。詞值。 例例. . 語(yǔ)句語(yǔ)句const i=25,yes=1const i=25,yes=1，其中，單詞，其中，單詞2525和和1 1的類(lèi)別都是常數(shù)，其值分別為的類(lèi)別都是常數(shù)，其值分別為2525和和1 1；分類(lèi)方法n單詞種別單詞種別: :通常用整數(shù)編碼。通常用整數(shù)編碼。n一個(gè)語(yǔ)言的單詞符號(hào)如何分類(lèi)，

4、分成幾類(lèi)，怎樣編碼取決一個(gè)語(yǔ)言的單詞符號(hào)如何分類(lèi)，分成幾類(lèi)，怎樣編碼取決于處理上的方便。于處理上的方便。標(biāo)識(shí)符標(biāo)識(shí)符一般統(tǒng)歸為一種。一般統(tǒng)歸為一種。常數(shù)常數(shù)則宜按類(lèi)型（整、實(shí)、布爾等）分種。則宜按類(lèi)型（整、實(shí)、布爾等）分種。關(guān)鍵字關(guān)鍵字可視其全體為一種，也可以一字一種。采用一字一種的分可視其全體為一種，也可以一字一種。采用一字一種的分法實(shí)際處理起來(lái)較為方便。法實(shí)際處理起來(lái)較為方便。運(yùn)算符運(yùn)算符可采用一符一種的分法，但也可以把具有一定共性的運(yùn)算可采用一符一種的分法，但也可以把具有一定共性的運(yùn)算符視為一類(lèi)。符視為一類(lèi)。至于至于界符界符一般用一符一種的分法。一般用一符一種的分法。單詞符號(hào)的屬性n單詞

5、符號(hào)的屬性是指單詞符號(hào)的特征或特性。屬單詞符號(hào)的屬性是指單詞符號(hào)的特征或特性。屬性值則是反映特性或特征的值。性值則是反映特性或特征的值。標(biāo)識(shí)符的屬性值是存放它符號(hào)表項(xiàng)的指針或內(nèi)部字符標(biāo)識(shí)符的屬性值是存放它符號(hào)表項(xiàng)的指針或內(nèi)部字符串；串；常數(shù)的屬性值是存放它的常數(shù)表項(xiàng)的指針或二進(jìn)制形常數(shù)的屬性值是存放它的常數(shù)表項(xiàng)的指針或二進(jìn)制形式；式；關(guān)鍵字、運(yùn)算符和界符是一符一種，不需給出其自身關(guān)鍵字、運(yùn)算符和界符是一符一種，不需給出其自身的值。的值。例例. 代碼段代碼段 while (i=j) i-; 詞法分析結(jié)果詞法分析結(jié)果 = , 符號(hào)表符號(hào)表NoIDAddr type 224AF80INT227DF8

6、8INT邏輯邏輯IF （34，_）左括號(hào)左括號(hào) （2，_）整常數(shù)整常數(shù) （20，5的二進(jìn)制表示）的二進(jìn)制表示）等號(hào)等號(hào) （6，_）標(biāo)識(shí)符標(biāo)識(shí)符 （26，M）右括號(hào)右括號(hào) （16，_）GOTO （30，_）標(biāo)號(hào)標(biāo)號(hào) （19，100的二進(jìn)制表示）的二進(jìn)制表示）IFIF為關(guān)鍵字，種別編碼為關(guān)鍵字，種別編碼3434，采用一符一種的編碼方式。采用一符一種的編碼方式。常數(shù)類(lèi)型，種別編碼常數(shù)類(lèi)型，種別編碼2020，單詞自，單詞自身的值為身的值為55的二進(jìn)制表示。的二進(jìn)制表示。(為界符，種別編碼為界符，種別編碼2 2，采，采用一符一種的編碼方式。用一符一種的編碼方式。等號(hào)為運(yùn)算符，種別編碼等號(hào)為運(yùn)算符，種別編

7、碼6 6，采用一符一種的編碼方式。采用一符一種的編碼方式。M M為標(biāo)識(shí)符，種別編碼為標(biāo)識(shí)符，種別編碼2626，單，單詞自身值為詞自身值為MM。)為界符，種別編碼為界符，種別編碼1616，采用一符一種的編碼方式。采用一符一種的編碼方式。GOTOGOTO為關(guān)鍵字，種別編碼為關(guān)鍵字，種別編碼3030，采用一符一種的編碼方式。采用一符一種的編碼方式。100100為標(biāo)號(hào)，種別編碼為標(biāo)號(hào)，種別編碼1919，單詞，單詞內(nèi)部的值用內(nèi)部的值用100100的二進(jìn)制表示。的二進(jìn)制表示。nFORTRAN編譯程序的詞法分析器在掃描輸入串編譯程序的詞法分析器在掃描輸入串 IF (5EQM) GOTO 100 后，它輸出的

8、單詞符號(hào)串是：后，它輸出的單詞符號(hào)串是：FORTRAN編譯實(shí)例詞法分析程序的實(shí)現(xiàn)方式n完全獨(dú)立方式完全獨(dú)立方式：詞法分析程序作為單獨(dú)一遍來(lái)實(shí)：詞法分析程序作為單獨(dú)一遍來(lái)實(shí)現(xiàn)。詞法分析程序讀入整個(gè)源程序，它的輸出作現(xiàn)。詞法分析程序讀入整個(gè)源程序，它的輸出作為語(yǔ)法分析程序的輸入。為語(yǔ)法分析程序的輸入。編譯程序結(jié)構(gòu)簡(jiǎn)潔、清晰和條理化編譯程序結(jié)構(gòu)簡(jiǎn)潔、清晰和條理化n相對(duì)獨(dú)立方式相對(duì)獨(dú)立方式：把詞法分析程序作為語(yǔ)法分析程：把詞法分析程序作為語(yǔ)法分析程序的一個(gè)獨(dú)立子程序。語(yǔ)法分析程序需要新符號(hào)序的一個(gè)獨(dú)立子程序。語(yǔ)法分析程序需要新符號(hào)時(shí)調(diào)用這個(gè)子程序。時(shí)調(diào)用這個(gè)子程序。優(yōu)點(diǎn)：避免了中間文件生成，可以提高效

9、率。優(yōu)點(diǎn)：避免了中間文件生成，可以提高效率。內(nèi)容線(xiàn)索對(duì)于詞法分析器的要求對(duì)于詞法分析器的要求n詞法分析器的設(shè)計(jì)詞法分析器的設(shè)計(jì)n正規(guī)表達(dá)式與有限自動(dòng)機(jī)正規(guī)表達(dá)式與有限自動(dòng)機(jī)n詞法分析器的自動(dòng)生成詞法分析器的自動(dòng)生成詞法分析器的結(jié)構(gòu)預(yù)處理工作包括對(duì)空白符、跳格預(yù)處理工作包括對(duì)空白符、跳格符、回車(chē)符和換行符等編輯性字符、回車(chē)符和換行符等編輯性字符的處理，及刪除注解等。符的處理，及刪除注解等。預(yù)處理子程序預(yù)處理子程序輸入緩沖區(qū)輸入緩沖區(qū)源程序掃描器掃描器單詞符號(hào)單詞符號(hào)掃描緩沖區(qū)掃描緩沖區(qū)起點(diǎn)指起點(diǎn)指示器示器搜索指搜索指示器示器設(shè)定兩個(gè)指示器設(shè)定兩個(gè)指示器緩沖區(qū)一分為二緩沖區(qū)一分為二輸入源程序文本。

10、輸入源程序文本。輸入串一般放在輸入串一般放在一個(gè)緩沖區(qū)中，一個(gè)緩沖區(qū)中，這個(gè)緩沖區(qū)稱(chēng)輸這個(gè)緩沖區(qū)稱(chēng)輸入緩沖區(qū)。入緩沖區(qū)。單詞符號(hào)的識(shí)別：超前搜索n關(guān)鍵字識(shí)別關(guān)鍵字識(shí)別 例例. 在標(biāo)準(zhǔn)在標(biāo)準(zhǔn)FORTRAN中四個(gè)合法句子：中四個(gè)合法句子： 1、DO99K = 1,10 2、IF(5.EQ.M)I = 10 3、DO99K = 1.10 4、IF(5) = 55其中的其中的DODO、IFIF為關(guān)鍵字為關(guān)鍵字其中的其中的DODO、IFIF為標(biāo)識(shí)符為標(biāo)識(shí)符的一部分的一部分單詞符號(hào)的識(shí)別：超前搜索n標(biāo)識(shí)符的識(shí)別標(biāo)識(shí)符的識(shí)別多數(shù)語(yǔ)言的標(biāo)識(shí)符是字母開(kāi)頭的多數(shù)語(yǔ)言的標(biāo)識(shí)符是字母開(kāi)頭的“字母字母/ /數(shù)字?jǐn)?shù)字”串

11、，而串，而且在程序中標(biāo)識(shí)符的出現(xiàn)后都跟著算符或界符。因此，且在程序中標(biāo)識(shí)符的出現(xiàn)后都跟著算符或界符。因此，不難識(shí)別。不難識(shí)別。n常數(shù)的識(shí)別常數(shù)的識(shí)別對(duì)于某些語(yǔ)言的常數(shù)的識(shí)別也需要使用超前搜索。對(duì)于某些語(yǔ)言的常數(shù)的識(shí)別也需要使用超前搜索。FORTRAN中，中，5.E08和和5. EQ.M都是合法的都是合法的n算符和界符的識(shí)別算符和界符的識(shí)別對(duì)于諸如對(duì)于諸如C+C+語(yǔ)言中的語(yǔ)言中的“+ + +”、“- - -”，這種復(fù)合成，這種復(fù)合成的算符，需要超前搜索。的算符，需要超前搜索。狀態(tài)轉(zhuǎn)換圖n大多數(shù)程序設(shè)計(jì)語(yǔ)言中單詞符號(hào)的大多數(shù)程序設(shè)計(jì)語(yǔ)言中單詞符號(hào)的詞法規(guī)則詞法規(guī)則可以用可以用正規(guī)文正規(guī)文法法描述。

12、如：描述。如： 字母字母| 字母字母| 數(shù)字?jǐn)?shù)字 數(shù)字?jǐn)?shù)字| 數(shù)字?jǐn)?shù)字 +|+| | | ; |, |( | )|; |, |( | )|n利用這些規(guī)則識(shí)別單詞符號(hào)的過(guò)程可用一張稱(chēng)為利用這些規(guī)則識(shí)別單詞符號(hào)的過(guò)程可用一張稱(chēng)為狀態(tài)轉(zhuǎn)換狀態(tài)轉(zhuǎn)換圖圖的有限方向圖來(lái)表示，而狀態(tài)轉(zhuǎn)換圖識(shí)別單詞符號(hào)的過(guò)的有限方向圖來(lái)表示，而狀態(tài)轉(zhuǎn)換圖識(shí)別單詞符號(hào)的過(guò)程又可以方便地用程序?qū)崿F(xiàn)程又可以方便地用程序?qū)崿F(xiàn)。狀態(tài)轉(zhuǎn)換圖定義n轉(zhuǎn)換圖：是一個(gè)有限方向圖。轉(zhuǎn)換圖：是一個(gè)有限方向圖。結(jié)點(diǎn)代表狀態(tài)，用圓圈表示。結(jié)點(diǎn)代表狀態(tài)，用圓圈表示。n初態(tài)：一張轉(zhuǎn)換圖的啟動(dòng)條件，通常有一個(gè)初態(tài)：一張轉(zhuǎn)換圖的啟動(dòng)條件，通常有一個(gè), ,用圓圈

13、表示。用圓圈表示。n終態(tài)：一張轉(zhuǎn)換圖的結(jié)束條件，至少有一個(gè)，用雙圈表示。終態(tài)：一張轉(zhuǎn)換圖的結(jié)束條件，至少有一個(gè)，用雙圈表示。狀態(tài)之間用方向弧連接?；∩系臉?biāo)記（字符）代表在出射結(jié)點(diǎn)狀狀態(tài)之間用方向弧連接。弧上的標(biāo)記（字符）代表在出射結(jié)點(diǎn)狀態(tài)下可能出現(xiàn)的輸入字符或字符類(lèi)。態(tài)下可能出現(xiàn)的輸入字符或字符類(lèi)。n狀態(tài)轉(zhuǎn)換圖中只包含有限個(gè)狀態(tài)（結(jié)點(diǎn)）狀態(tài)轉(zhuǎn)換圖中只包含有限個(gè)狀態(tài)（結(jié)點(diǎn)）123XYZW在狀態(tài)在狀態(tài)1下，若輸入字符為下，若輸入字符為X，則讀進(jìn)，則讀進(jìn)X并轉(zhuǎn)換并轉(zhuǎn)換到狀態(tài)到狀態(tài)2；若輸入字符為；若輸入字符為Y則讀進(jìn)則讀進(jìn)Y并轉(zhuǎn)換到狀并轉(zhuǎn)換到狀態(tài)態(tài)3，輸入字符，輸入字符Z，狀態(tài)仍為，狀態(tài)仍為1。狀態(tài)

14、轉(zhuǎn)換圖的作用n一個(gè)狀態(tài)轉(zhuǎn)換圖可用于一個(gè)狀態(tài)轉(zhuǎn)換圖可用于接受接受（或（或識(shí)別識(shí)別）一定的符）一定的符號(hào)串。號(hào)串。n路路: :在狀態(tài)轉(zhuǎn)換圖中從在狀態(tài)轉(zhuǎn)換圖中從初始狀態(tài)初始狀態(tài)到到某一終止?fàn)顟B(tài)某一終止?fàn)顟B(tài)的的弧上的弧上的標(biāo)記序列標(biāo)記序列。n對(duì)于某一符號(hào)串對(duì)于某一符號(hào)串，在狀態(tài)轉(zhuǎn)換圖中，若存在一，在狀態(tài)轉(zhuǎn)換圖中，若存在一條路產(chǎn)生條路產(chǎn)生，則稱(chēng)狀態(tài)轉(zhuǎn)換圖接受（或識(shí)別）該，則稱(chēng)狀態(tài)轉(zhuǎn)換圖接受（或識(shí)別）該符號(hào)串符號(hào)串，否則稱(chēng)符號(hào)串，否則稱(chēng)符號(hào)串不能被接受。不能被接受。狀態(tài)轉(zhuǎn)換圖所能識(shí)別的語(yǔ)言n能被狀態(tài)轉(zhuǎn)換圖能被狀態(tài)轉(zhuǎn)換圖TG接受的符號(hào)串的集合記為接受的符號(hào)串的集合記為L(zhǎng)(TG)，稱(chēng)它為，稱(chēng)它為狀態(tài)轉(zhuǎn)換圖所能

15、識(shí)別的語(yǔ)言狀態(tài)轉(zhuǎn)換圖所能識(shí)別的語(yǔ)言。L(TG)= 0，1，00，01，11，001，010，L(TG)= a，b，ab，ba，aaa，bbb，aab，bba，狀態(tài)轉(zhuǎn)換圖示例n大多數(shù)程序語(yǔ)言的單詞符號(hào)都大多數(shù)程序語(yǔ)言的單詞符號(hào)都可以用狀態(tài)轉(zhuǎn)換圖予以識(shí)別?？梢杂脿顟B(tài)轉(zhuǎn)換圖予以識(shí)別。2 20 01 1字母字母其他其他字母或數(shù)字字母或數(shù)字* *（b b）識(shí)別標(biāo)識(shí)符的轉(zhuǎn)換圖）識(shí)別標(biāo)識(shí)符的轉(zhuǎn)換圖其他其他2 20 01 1數(shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字* *（c c）識(shí)別整數(shù)的轉(zhuǎn)換圖）識(shí)別整數(shù)的轉(zhuǎn)換圖初態(tài)初態(tài)終態(tài)終態(tài)從從0 0狀態(tài)到狀態(tài)到1 1狀態(tài)狀態(tài)可能出現(xiàn)字母可能出現(xiàn)字母1 1X XY Y(a)(a)單個(gè)符號(hào)的轉(zhuǎn)單個(gè)

16、符號(hào)的轉(zhuǎn)換圖示例換圖示例2 23 3意味著多讀進(jìn)了一個(gè)不屬于標(biāo)意味著多讀進(jìn)了一個(gè)不屬于標(biāo)識(shí)符部分的字符，應(yīng)把它退還識(shí)符部分的字符，應(yīng)把它退還給輸入串給輸入串 a. .b a .b E (或或D)d a.b(a,b,d 為整數(shù)常數(shù)為整數(shù)常數(shù)) a.Ed .b Ed a.bE d aEd0123457數(shù)字?jǐn)?shù)字.數(shù)字?jǐn)?shù)字 .數(shù)字?jǐn)?shù)字其它其它數(shù)字?jǐn)?shù)字E / DE / D+ / -數(shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字其它其它數(shù)字?jǐn)?shù)字*6（d d）識(shí)別）識(shí)別FORTRANFORTRAN實(shí)型常數(shù)的轉(zhuǎn)換圖實(shí)型常數(shù)的轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖識(shí)別單詞符號(hào)的過(guò)程Step1. 從初態(tài)開(kāi)始；從初態(tài)開(kāi)始；Step2. 從輸入串中讀一個(gè)字符；從輸入串

17、中讀一個(gè)字符；Step3. 判明讀入字符與從當(dāng)前狀態(tài)出發(fā)的哪條弧上判明讀入字符與從當(dāng)前狀態(tài)出發(fā)的哪條弧上 的標(biāo)記相匹配，便轉(zhuǎn)到相應(yīng)匹配的那條弧所指的標(biāo)記相匹配，便轉(zhuǎn)到相應(yīng)匹配的那條弧所指向的狀態(tài)；向的狀態(tài)；Step4. 重復(fù)重復(fù)Step3，均不匹配時(shí)便告失??；到達(dá)終，均不匹配時(shí)便告失?。坏竭_(dá)終態(tài)時(shí)便識(shí)別出一個(gè)單詞符號(hào)。態(tài)時(shí)便識(shí)別出一個(gè)單詞符號(hào)。例例. . 設(shè)一小語(yǔ)言所有單詞符號(hào)及其內(nèi)部表示形式設(shè)一小語(yǔ)言所有單詞符號(hào)及其內(nèi)部表示形式單詞符號(hào)單詞符號(hào)種別編碼種別編碼助憶符助憶符內(nèi)碼值內(nèi)碼值DIM1$DIM-IF2$IF-DO3$DO-STOP4$STOP-END5$END-標(biāo)識(shí)符標(biāo)識(shí)符6$ID內(nèi)部

18、字符串內(nèi)部字符串整常數(shù)整常數(shù)7$INT標(biāo)準(zhǔn)二進(jìn)制形式標(biāo)準(zhǔn)二進(jìn)制形式=8$ASSIGN-+9$PLUS-*10$STAR-*11$POWER-.12$COMMA-(13$LPAR-)14$RPAR-能識(shí)別小語(yǔ)言所有單詞的狀態(tài)轉(zhuǎn)換能識(shí)別小語(yǔ)言所有單詞的狀態(tài)轉(zhuǎn)換圖圖約定（限制）約定（限制）: : 關(guān)鍵字為保留字關(guān)鍵字為保留字; ; 保留字作為標(biāo)識(shí)符保留字作為標(biāo)識(shí)符處理處理, ,并使用保留字并使用保留字表識(shí)別；表識(shí)別；關(guān)鍵字、標(biāo)識(shí)符、關(guān)鍵字、標(biāo)識(shí)符、常數(shù)間若無(wú)運(yùn)算符常數(shù)間若無(wú)運(yùn)算符或界限符則加一空或界限符則加一空格格0空白空白字母字母1字母或數(shù)字字母或數(shù)字2非字母與數(shù)字非字母與數(shù)字34*5678910

19、111213數(shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字非數(shù)字非數(shù)字=+*非非*，()其它其它*狀態(tài)轉(zhuǎn)換圖實(shí)現(xiàn)中的變量和過(guò)程ch：字符變量：字符變量 功能：存放當(dāng)前讀入字符功能：存放當(dāng)前讀入字符strToken：字符數(shù)組：字符數(shù)組 功能：存放單詞的字符串功能：存放單詞的字符串GetChar：取字符過(guò)程：取字符過(guò)程 功能：取下一字符到功能：取下一字符到ch ；搜；搜 索指針?biāo)髦羔?1GetBC：濾除空字符過(guò)程：濾除空字符過(guò)程 功能：判功能：判ch =空空? 若是若是,則則調(diào)用調(diào)用GetCharConcat：子程序過(guò)程：子程序過(guò)程 功能：把功能：把ch中的字符拼入中的字符拼入strToken IsLetter, IsDigi

20、t：布爾函數(shù)：布爾函數(shù) 功能：功能： ch中為字母、數(shù)字時(shí)返中為字母、數(shù)字時(shí)返回回.T.Reserve：整型函數(shù)：整型函數(shù) 功能：按功能：按strToken中字符串查保中字符串查保留字表；查到返回保留字留字表；查到返回保留字編碼編碼;否則返回否則返回0Retract：子程序過(guò)程：子程序過(guò)程 功能：搜索指針回退一字符功能：搜索指針回退一字符InsertId：函數(shù)：函數(shù) 功能：將標(biāo)識(shí)符插入符號(hào)表，返功能：將標(biāo)識(shí)符插入符號(hào)表，返回符號(hào)表指針回符號(hào)表指針I(yè)nsertConst函數(shù)函數(shù) 功能：功能： 將常數(shù)插入常數(shù)表，返回將常數(shù)插入常數(shù)表，返回常數(shù)表指針常數(shù)表指針程序段n不含回路的分叉結(jié)點(diǎn)對(duì)應(yīng)的程序段可

21、表示為不含回路的分叉結(jié)點(diǎn)對(duì)應(yīng)的程序段可表示為 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ò)誤處理ijkl字母字母數(shù)字?jǐn)?shù)字/程序段n終態(tài)結(jié)點(diǎn)對(duì)應(yīng)一條語(yǔ)句終態(tài)結(jié)點(diǎn)對(duì)應(yīng)一條語(yǔ)句 return(code,value);ij字母或字母或數(shù)字?jǐn)?shù)字其它其它in含回路的狀態(tài)結(jié)點(diǎn)對(duì)應(yīng)的程序段可表示為含回路的狀態(tài)結(jié)點(diǎn)對(duì)應(yīng)的程序段可表示為 GetChar(); While(IsLetter() or IsDigit()

22、GetChar(); 狀態(tài)狀態(tài)j的對(duì)應(yīng)程序段的對(duì)應(yīng)程序段int code,value;strToken=“”;GetChar();GetBC()；If (IsLetter() while(IsLetter() or IsDigit() Concat();GetChar(); Retract(); code=Reserve(); if(code=0) value=InsertId(strToken); return($ID,value); else return(code,-);else if(IsDigit() while(IsDigit() Concat(); GetChar(); Retr

23、act(); value=InsertConst(strToken); return($INT,value);else if (ch=) return($ASSIGN,-);else if (ch=+) return($PLUS,-);else if(ch=“*”) Getchar(); if(ch=*) return($POWER,-); Retract();return($STAR,-);else if(ch=:) return($SEMICOLON,-);else if(ch=() return($LPAR,-);else if(ch=) return($RPAR,-);else if(

24、ch=) return($LBRACE,-);else if(ch=) return($RBRACE,-);else ProcError();掃描器總控程序內(nèi)容線(xiàn)索對(duì)于詞法分析器的要求對(duì)于詞法分析器的要求詞法分析器的設(shè)計(jì)詞法分析器的設(shè)計(jì)n正規(guī)表達(dá)式與有限自動(dòng)機(jī)正規(guī)表達(dá)式與有限自動(dòng)機(jī)n詞法分析器的自動(dòng)生成詞法分析器的自動(dòng)生成FA正規(guī)表達(dá)式與有限自動(dòng)機(jī)正規(guī)式正規(guī)式DFANFA正規(guī)文法正規(guī)文法子集法子集法狀態(tài)消去法狀態(tài)消去法DFA化簡(jiǎn)化簡(jiǎn)Thompson算法算法內(nèi)容線(xiàn)索對(duì)于詞法分析器的要求對(duì)于詞法分析器的要求詞法分析器的設(shè)計(jì)詞法分析器的設(shè)計(jì)正規(guī)表達(dá)式與有限自動(dòng)機(jī)正規(guī)表達(dá)式與有限自動(dòng)機(jī)n詞法分析器的自

25、動(dòng)生成詞法分析器的自動(dòng)生成詞法分析器的自動(dòng)產(chǎn)生LEX詞法分析程序詞法分析程序自動(dòng)產(chǎn)生器自動(dòng)產(chǎn)生器詞法分析器詞法分析器LLEX源程序源程序 詞法分析器詞法分析器L單詞符號(hào)單詞符號(hào)輸入串輸入串狀態(tài)轉(zhuǎn)換表狀態(tài)轉(zhuǎn)換表控制執(zhí)行程序控制執(zhí)行程序nLEX程序由一組正規(guī)式以及與每個(gè)正規(guī)式相應(yīng)的動(dòng)作組成。程序由一組正規(guī)式以及與每個(gè)正規(guī)式相應(yīng)的動(dòng)作組成。動(dòng)作本身是一小段程序代碼，它指出了當(dāng)按正規(guī)式識(shí)別出一個(gè)單詞動(dòng)作本身是一小段程序代碼，它指出了當(dāng)按正規(guī)式識(shí)別出一個(gè)單詞符號(hào)時(shí)應(yīng)采取的行動(dòng)。符號(hào)時(shí)應(yīng)采取的行動(dòng)。語(yǔ)言L(fǎng)EX的一般描述(1) 正規(guī)式輔助定義式正規(guī)式輔助定義式 d1 r1 d2 r2 . dn rn ri

26、為正規(guī)式為正規(guī)式, di為該正規(guī)式的簡(jiǎn)名為該正規(guī)式的簡(jiǎn)名, ri中只允許出現(xiàn)中只允許出現(xiàn) 中的字符和已定義的簡(jiǎn)名中的字符和已定義的簡(jiǎn)名d1, d2, , di-1(2) 識(shí)別規(guī)則：是一串下述形式的識(shí)別規(guī)則：是一串下述形式的LEX語(yǔ)句語(yǔ)句 P1 A1 P2 A2 . Pm AmLEX源程序包括源程序包括: 輔助定義部分輔助定義部分 識(shí)別規(guī)則部分識(shí)別規(guī)則部分 用戶(hù)子程序部分用戶(hù)子程序部分Pi為為d1, d2, . . . ,dn上的正規(guī)式；上的正規(guī)式； Ai 為識(shí)別出為識(shí)別出詞形詞形 Pi后應(yīng)采取的動(dòng)作，是后應(yīng)采取的動(dòng)作，是一小段程序代碼。一小段程序代碼。例例. 正規(guī)式輔助定義式正規(guī)式輔助定義式

27、letter AB Z digit 01 9標(biāo)識(shí)符標(biāo)識(shí)符: iden letter (letter digit)*整常數(shù)整常數(shù): integer digit(digit)* sign +- signedinteger sign integer不帶指數(shù)部分的實(shí)常數(shù)不帶指數(shù)部分的實(shí)常數(shù): decimal signedinteger . integer signedinteger . sign . Integer帶指數(shù)部分的實(shí)常數(shù)帶指數(shù)部分的實(shí)常數(shù): exponential (decimal signedinteger) E signedinteger例例. 識(shí)別小語(yǔ)言單詞符號(hào)的識(shí)別小語(yǔ)言單詞符號(hào)的

28、 LEX 程序程序AUXILIARY DEFINITIONS /* 輔助定義輔助定義 */ letter AB . . .Z digit 01 . . . 9RECOGNITION RULES /* 識(shí)別規(guī)則識(shí)別規(guī)則 */1 DIM RETURN (1, _ )2 IF RETURN (2, _ )3 DO RETURN (3, _ )4 STOP RETURN (4, _ )5 END RETURN (5, _ )6 letter(letter | digit)* RETURN (6, getSymbolTableEntryPoint() )7 digit (digit)* RETURN (

29、7, getConstTableEntryPoint() )8 = RETURN (8, _ )9 + RETURN (9, _ )10 * RETURN (10, _ )11 * RETURN (11, _ )12 , RETURN (12, _ )13 ( RETURN (13, _ )14 ) RETURN (14, _ )正規(guī)式正規(guī)式LEX 的實(shí)現(xiàn)n方法方法由由LEX 編譯程序?qū)⒕幾g程序?qū)?LEX 源程序改造為一個(gè)詞法分析器，即構(gòu)造源程序改造為一個(gè)詞法分析器，即構(gòu)造相應(yīng)的相應(yīng)的 DFAn步驟步驟對(duì)每條識(shí)別規(guī)則對(duì)每條識(shí)別規(guī)則Pi構(gòu)造一個(gè)相應(yīng)的構(gòu)造一個(gè)相應(yīng)的 NFA Mi引入一個(gè)新的初態(tài)引

30、入一個(gè)新的初態(tài)X, 連接成連接成 NFA M用子集法將其確定化并化簡(jiǎn)用子集法將其確定化并化簡(jiǎn)將將 DFA 轉(zhuǎn)換為詞法分析程序轉(zhuǎn)換為詞法分析程序n注意注意匹配最長(zhǎng)子串匹配最長(zhǎng)子串(最長(zhǎng)匹配原則最長(zhǎng)匹配原則)多個(gè)最長(zhǎng)子串匹配多個(gè)最長(zhǎng)子串匹配Pi, 以前面的以前面的Pi為準(zhǔn)為準(zhǔn)(優(yōu)先匹配原則優(yōu)先匹配原則)XM2P1 . . .M1MnP2Pn例例. LEX 程序程序: a abb a*bb* NFA M:012345678aabbabb 0137aa*bb*abb247875868bbbaabbba abba*bb*狀態(tài)狀態(tài)ab識(shí)別單詞識(shí)別單詞 0 1 3 7 2 4 7 8 2 4 7 7 5 8

31、a 8 8a*bb* 7 7 8 5 8 6 8a*bb* 6 8 8abb輸入：輸入：abbbabb輸出：輸出：abbb abba*bb*aFA總結(jié)正規(guī)式正規(guī)式DFANFA正規(guī)文法正規(guī)文法子集法子集法狀態(tài)消去法狀態(tài)消去法DFA化簡(jiǎn)化簡(jiǎn)Thompson算法算法詞法分詞法分析程序析程序正規(guī)定義式正規(guī)定義式識(shí)別規(guī)則識(shí)別規(guī)則作業(yè)nP636 （4）（）（5）8（1）（）（2）（）（7）7 （1）（）（2）912Flex簡(jiǎn)介nFlex是一款是一款Unix下用于自動(dòng)生成詞法分析器（下用于自動(dòng)生成詞法分析器（lexical analyzer）的開(kāi)源工具。詞法分）的開(kāi)源工具。詞法分析器又稱(chēng)作掃描器（析器又稱(chēng)作

32、掃描器（scanner）、標(biāo)記生成器（）、標(biāo)記生成器（tokenizer），能夠識(shí)別文本中的詞法），能夠識(shí)別文本中的詞法規(guī)則。規(guī)則。n大約大約1987年時(shí)，勞倫斯年時(shí)，勞倫斯-伯克利實(shí)驗(yàn)室的伯克利實(shí)驗(yàn)室的Vern Paxson采用采用ratfor語(yǔ)言編寫(xiě)了語(yǔ)言編寫(xiě)了Flex，意，意為為“Fast Lexical Analyzer Generator”，后又翻譯為，后又翻譯為C語(yǔ)言。語(yǔ)言。nFlex程序通過(guò)讀入用戶(hù)編寫(xiě)的規(guī)則描述文件（也稱(chēng)作程序通過(guò)讀入用戶(hù)編寫(xiě)的規(guī)則描述文件（也稱(chēng)作Flex源文件或源文件或Flex腳本，以腳本，以*.l或或*.ll作為后綴名）生成掃描器源文件，其中包含調(diào)用接口作為

33、后綴名）生成掃描器源文件，其中包含調(diào)用接口yylex()函數(shù)，執(zhí)行該函數(shù)即可函數(shù)，執(zhí)行該函數(shù)即可對(duì)輸入文本進(jìn)行詞法分析。如下圖所示：對(duì)輸入文本進(jìn)行詞法分析。如下圖所示：Flex正則表達(dá)式nFlex使用表達(dá)式規(guī)則來(lái)描述詞法規(guī)則，其使用的正則表達(dá)式是一種使使用表達(dá)式規(guī)則來(lái)描述詞法規(guī)則，其使用的正則表達(dá)式是一種使用元語(yǔ)言的模式描述，和擴(kuò)展的用元語(yǔ)言的模式描述，和擴(kuò)展的POSIX正則表達(dá)式基本類(lèi)似。一些具正則表達(dá)式基本類(lèi)似。一些具有特殊含義的字符列舉如下：有特殊含義的字符列舉如下：字符字符含義含義.匹配換行符n以外的全部單個(gè)字符匹配字符集，用表示取反，用-簡(jiǎn)寫(xiě)一段連續(xù)的ASCII字符a-z-jv除j和

34、v以外的小寫(xiě)字母除用于內(nèi)表取反外，作為模式的第一個(gè)字符匹配一行的開(kāi)頭$作為模式的最后一個(gè)字符匹配一行的結(jié)尾指出一個(gè)模式可能出現(xiàn)的次數(shù)，A1,3表示A出現(xiàn)1次或3次轉(zhuǎn)義字符字符字符含義含義*匹配0或多個(gè)該模式+匹配1或多個(gè)該模式?匹配0或1個(gè)該模式|表達(dá)式間的邏輯或，表示能且只能匹配其中的任意一個(gè)“”用”括起的內(nèi)容將無(wú)視其中的特殊字符而被處理為字符串，但其中的轉(zhuǎn)義字符仍然有效()將一系列表達(dá)式分組jokers 匹配jokes或jokerA1,2shis+ 匹配AAshis, Ashis, AAshiss, Ashiss等A(b-e)? 匹配A, Ab, Ac, Ad, AeFlex規(guī)則描述文件n

35、一個(gè)一個(gè)Flex規(guī)則描述文件分為三段，以規(guī)則描述文件分為三段，以%分界，如下所示：分界，如下所示：聲明部分聲明部分%規(guī)則部分規(guī)則部分%輔助代碼輔助代碼n聲明部分包括：聲明部分包括：以以%option開(kāi)頭的開(kāi)頭的Flex配置語(yǔ)句，如配置語(yǔ)句，如%option c+指定生成指定生成c+而非而非c形式的詞法形式的詞法分析器源代碼分析器源代碼用用% %括住的括住的C/C+代碼，這些代碼將直接被代碼，這些代碼將直接被Flex搬到生成的掃描器源代碼搬到生成的掃描器源代碼中，一般為掃描器所要用到的輔助變量聲明及一些初始化語(yǔ)句中，一般為掃描器所要用到的輔助變量聲明及一些初始化語(yǔ)句自定義模式，為一些模式命名，以

36、便重用和維護(hù)，格式如下：自定義模式，為一些模式命名，以便重用和維護(hù)，格式如下：Digit0-9（定義正則表達(dá)式（定義正則表達(dá)式0-9為數(shù)字）為數(shù)字）Lettera-zA-ZNewlinenWhitespace t+Flex規(guī)則描述文件n規(guī)則部分由若干條模式（規(guī)則部分由若干條模式（pattern）和動(dòng)作（）和動(dòng)作（action）組成組成的規(guī)則組的規(guī)則組成，格式如下：成，格式如下：模式模式動(dòng)作動(dòng)作模式即模式即Flex正則表達(dá)式，動(dòng)作即一些正則表達(dá)式，動(dòng)作即一些C/C+語(yǔ)句。模式指出一個(gè)單詞是語(yǔ)句。模式指出一個(gè)單詞是如何構(gòu)成的，當(dāng)分析出一個(gè)符合規(guī)則的單詞時(shí)，就執(zhí)行相應(yīng)的動(dòng)作。如如何構(gòu)成的，當(dāng)分析出一

37、個(gè)符合規(guī)則的單詞時(shí)，就執(zhí)行相應(yīng)的動(dòng)作。如Newline lineno+;（Newline為之前定義的換行模式，遇到換行符時(shí)更新為之前定義的換行模式，遇到換行符時(shí)更新行數(shù)）行數(shù)）又如又如：當(dāng)識(shí)別到/*時(shí)采取以下動(dòng)作：循環(huán)調(diào)用Flex提供的yyinput()繼續(xù)向后讀直到遇上*/為止 C語(yǔ)言風(fēng)格注釋的匹配方法Flex規(guī)則描述文件n規(guī)則部分的一些注意事項(xiàng)：規(guī)則部分的一些注意事項(xiàng)：規(guī)則匹配的優(yōu)先級(jí)按書(shū)寫(xiě)順序排序。寫(xiě)在越靠規(guī)則匹配的優(yōu)先級(jí)按書(shū)寫(xiě)順序排序。寫(xiě)在越靠前的規(guī)則越優(yōu)先匹配，如：前的規(guī)則越優(yōu)先匹配，如：“while”/*優(yōu)先匹配單詞優(yōu)先匹配單詞while*/L(L|D)*/*如上述模式均不匹配，匹

38、配為標(biāo)識(shí)符如上述模式均不匹配，匹配為標(biāo)識(shí)符*/（D 0-9，L a-zA-Z_）使用使用來(lái)引用在聲明區(qū)自定義的模式，如：來(lái)引用在聲明區(qū)自定義的模式，如：Newline模式一定要位于一行的開(kāi)頭且前面不能有縮進(jìn)模式一定要位于一行的開(kāi)頭且前面不能有縮進(jìn)；動(dòng)作的開(kāi)頭一定要與對(duì)應(yīng)的模式在同一行；動(dòng)作的開(kāi)頭一定要與對(duì)應(yīng)的模式在同一行Flex規(guī)則描述文件n輔助代碼部分可定義一些分析過(guò)程中要用輔助代碼部分可定義一些分析過(guò)程中要用到的函數(shù)（當(dāng)然也可以定義到的函數(shù)（當(dāng)然也可以定義main函數(shù)），函數(shù)），這部分的代碼也會(huì)被這部分的代碼也會(huì)被Flex直接搬到生成的直接搬到生成的掃描器源代碼中掃描器源代碼中n作用域問(wèn)題

39、：為了保證自己定義的變量和作用域問(wèn)題：為了保證自己定義的變量和函數(shù)能被規(guī)則部分和輔助代碼部分訪(fǎng)問(wèn)，函數(shù)能被規(guī)則部分和輔助代碼部分訪(fǎng)問(wèn)，應(yīng)將它們正確定義于聲明部分的應(yīng)將它們正確定義于聲明部分的%中中Flex規(guī)則描述文件示例n按照教材按照教材P42表表3.1描述的詞法規(guī)則可編寫(xiě)如下描述的詞法規(guī)則可編寫(xiě)如下Flex規(guī)則描述文件：規(guī)則描述文件：Flex提供了一系列供用戶(hù)操作的接口變量和函數(shù)，如本例中的yytext記錄了當(dāng)前截取的字符內(nèi)容。此外，yyin和yyout指針?lè)謩e指向掃描器的輸入和輸出，默認(rèn)為stdin和stdout；yywrap()函數(shù)必須由用戶(hù)實(shí)現(xiàn)以指定讀到文件尾時(shí)的動(dòng)作，返回1結(jié)束解析，

40、可通過(guò)賦值yyin并返回0來(lái)實(shí)現(xiàn)多文件解析；Flex實(shí)踐獲取與安裝nLinux下安裝下安裝Flex一般方法：一般方法：n從從http:/ check（檢查編譯結(jié)果，可省略）（檢查編譯結(jié)果，可省略）make install（如遇權(quán)限問(wèn)題加上（如遇權(quán)限問(wèn)題加上sudo命令）命令）快速方法：快速方法：n以以Ubuntu的的apt-get為例：進(jìn)入終端，輸入以下命令為例：進(jìn)入終端，輸入以下命令apt-get install built-essential（更新（更新gcc等編譯工具，可省略）等編譯工具，可省略）apt-get install flex（下載并安裝（下載并安裝Flex）安裝完畢后使用安裝

41、完畢后使用flex -version命令打印版本號(hào)驗(yàn)證安裝命令打印版本號(hào)驗(yàn)證安裝nWindows下使用下使用Flex查閱網(wǎng)上相關(guān)開(kāi)源項(xiàng)目，需借助查閱網(wǎng)上相關(guān)開(kāi)源項(xiàng)目，需借助Cygwin（略）（略）Flex實(shí)踐編譯與運(yùn)行n將之前編寫(xiě)完的將之前編寫(xiě)完的Flex腳本保存為腳本保存為scanner.l文文件，轉(zhuǎn)入保存目錄，鍵入件，轉(zhuǎn)入保存目錄，鍵入flex scanner.l，生，生成詞法分析器源文件成詞法分析器源文件lex.yy.c；n使用使用gcc編譯編譯lex.yy.c為可執(zhí)行文件：鍵入為可執(zhí)行文件：鍵入gcc lex.yy.c o myscanner，生成掃描器，生成掃描器myscanner；

42、n鍵入鍵入./myscanner運(yùn)行掃描器，運(yùn)行掃描器，yylex()函數(shù)默函數(shù)默認(rèn)以認(rèn)以stdin為輸入文件流，鍵入程序片段測(cè)試為輸入文件流，鍵入程序片段測(cè)試掃描器，按掃描器，按ctrl+d輸入輸入eof終止。終止。Flex實(shí)踐運(yùn)行結(jié)果輸入的程序片段為i = 0IF i=0 i=1共計(jì)三個(gè)標(biāo)識(shí)符（都是i），三個(gè)常數(shù)（0,0,1），代碼共2行，根據(jù)打印結(jié)果驗(yàn)證程序基本正確參考資料nJohn Levine. Flex & Bison. OReilly, 2009nDoug Brown, John Levine, Tony Mason. Lex & Yacc, 2nd Editio

43、n. OReilly, 1992nhttp:/ M. E. and E. Schmidt 1975. Lex - A Lexical Analyzer Generator. Computing Science Technical Report No. 39, Bell Laboratories, Murray Hill, New Jersey.正規(guī)表達(dá)式與有限自動(dòng)機(jī)n為了更好地使用狀態(tài)轉(zhuǎn)換圖構(gòu)造詞法分析器，和討論詞法為了更好地使用狀態(tài)轉(zhuǎn)換圖構(gòu)造詞法分析器，和討論詞法分析器的自動(dòng)生成，還需要將轉(zhuǎn)換圖的概念形式化。分析器的自動(dòng)生成，還需要將轉(zhuǎn)換圖的概念形式化。正規(guī)式與正規(guī)集正規(guī)式與正規(guī)集確定有限自

44、動(dòng)機(jī)確定有限自動(dòng)機(jī) (DFA)(DFA)非確定有限自動(dòng)機(jī)非確定有限自動(dòng)機(jī)(NFA)(NFA)正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性確定有限自動(dòng)機(jī)的化簡(jiǎn)確定有限自動(dòng)機(jī)的化簡(jiǎn)正規(guī)式與正規(guī)集n字母表字母表上的上的正規(guī)式正規(guī)式和和正規(guī)集正規(guī)集遞歸定義如下：遞歸定義如下： （1）和和 都是都是上的正規(guī)式，它們所表示的正規(guī)集分別上的正規(guī)式，它們所表示的正規(guī)集分別 為為和和 。其中：。其中：為空字符串，為空字符串， 為空集；為空集； （2）任意元素）任意元素a ，a是是上的一個(gè)正規(guī)式，它所表示的上的一個(gè)正規(guī)式，它所表示的 正規(guī)集是正規(guī)集是a; （3）假定）假定U和和V都是都是上的正規(guī)式，它們所

45、表示的正規(guī)集上的正規(guī)式，它們所表示的正規(guī)集 記為記為L(zhǎng)(U)和和L(V)，那么，（，那么，（U|V），（），（UV）和）和(U)*都是都是 正規(guī)式，他們所表示的正規(guī)集分別記為正規(guī)式，他們所表示的正規(guī)集分別記為L(zhǎng)(U)L(V)， L(U)L(V)和和(L(U)*。 （4）僅由有限次使用上述三步而得到的表達(dá)式才是）僅由有限次使用上述三步而得到的表達(dá)式才是上的上的 正規(guī)式，它們所表示的字集才是正規(guī)式，它們所表示的字集才是上的正規(guī)集。上的正規(guī)集。三種運(yùn)算示例例例1. 設(shè)設(shè) L = 001,10,111 , M = , 001 , 則則 L M = , 10, 001, 111 例例2. 設(shè)設(shè) L =

46、001,10,111 , M = , 001 ,則則 LM = 001, 10, 111, 001001, 10001, 111001 例例3. 設(shè)設(shè) L = 0, 11 , 則則 L* = , 0, 11, 00, 011, 110, 1111, 000, 0011, 0110, 01111, 1100, 11011, 11110, 111111, 說(shuō)明n運(yùn)算符運(yùn)算符 ”| |”讀為讀為”或或”； ”. .”讀為讀為”連接連接” ”* *”讀為讀為”閉包閉包”。 一般地，連接符一般地，連接符”. .”可省略不寫(xiě)，在不引起混淆的情可省略不寫(xiě)，在不引起混淆的情況下，括號(hào)可省去。況下，括號(hào)可省去。

47、n正規(guī)式運(yùn)算符的正規(guī)式運(yùn)算符的優(yōu)先順序優(yōu)先順序?yàn)椋簽椋骸? *”最高最高, ,”. .”次之次之, ,”| |”最低。最低。n若兩個(gè)正規(guī)式所表示的正規(guī)集相同，則認(rèn)為二者等價(jià)，記若兩個(gè)正規(guī)式所表示的正規(guī)集相同，則認(rèn)為二者等價(jià)，記為為U=V。例例1. 令令 a,b， 上的正規(guī)式和相應(yīng)的正規(guī)集有上的正規(guī)式和相應(yīng)的正規(guī)集有正規(guī)式正規(guī)式(a|b)(a|b)正規(guī)集正規(guī)集 L(a|b)(a|b)=L(a|b)L(a|b) =(L(a)L(b)(L(a)L(b) =a,ba,b=aa,ab,ba,bbba*L(ba*)=L(b)L(a*)=L(b)(L(a)* =ba*=b,a,aa,aaa, =b,ab,b

48、aa,baaa,上所有以上所有以b為首后跟任意多個(gè)為首后跟任意多個(gè)a的的字的集合。字的集合。正規(guī)式正規(guī)式a(a|b)*(a|b)*(aa|bb)(a|b)*正規(guī)集正規(guī)集上所有以上所有以a a為首的字集為首的字集上所有含有兩個(gè)相繼上所有含有兩個(gè)相繼a a或兩個(gè)相繼或兩個(gè)相繼b b的字集的字集例例2. C語(yǔ)言中語(yǔ)言中“標(biāo)識(shí)符標(biāo)識(shí)符”全體的正規(guī)式為：全體的正規(guī)式為：(A| B | Z | a | b | z)( A | B | Z | a |b|z|0|1|9)*例例3. “整數(shù)整數(shù)”全體的正規(guī)式：全體的正規(guī)式：(0 | 1 | 2 | 9 |)(0 | 1 | 2 | 9)*正規(guī)式的運(yùn)算律n令令U

49、、V和和W均為正規(guī)式，則：均為正規(guī)式，則： （1）U|V=V|U交換律交換律 （2）U|(V|W)=(U|V)|W結(jié)合律結(jié)合律 （3）U(VW)=(UV)W （4）U(V|W)=UV|UW 分配律分配律 （5）(V|W)U=VU|WU （6）U=U=U運(yùn)算律證明-1（1）交換律）交換律: UV=VU 證明證明:L(UV) = L(U)L(V) = L(V)L(U) = L(VU)（2）結(jié)合律）結(jié)合律: U(VW) = (UV)W 證明證明: L(U(VW) = L(U)L(VW) = L(U)(L(V)L(W) = (L(U)L(V)L(W) = L(UV)W )運(yùn)算律證明-2（3）結(jié)合律）結(jié)

50、合律: U(VW)=(UV)W 證明證明: L(U(VW) =L(U)L(VW) =L(U)(L(V)L(W) =L(U)(L(V)L(W) =L(U)(L(V)L(W) =(L(U)L(V)L(W) =L(UV) L(W) =L(UV)W)舉例試證明：試證明： A* = A A*證明：證明： L( AA*) = L()L( AA*) = L()（L( A) L(A*) ） = L()L( A) (L(A)0L(A)1L(A)2.) = L()L(A)1L(A)2L(A)3.) = (L(A)* = L(A*) 自動(dòng)機(jī)n什么是自動(dòng)機(jī)？什么是自動(dòng)機(jī)？具有離散輸入輸出的數(shù)學(xué)模型。具有離散輸入輸出的

51、數(shù)學(xué)模型。自動(dòng)機(jī)接受一定的輸入，執(zhí)行一定的動(dòng)作，產(chǎn)生一定的結(jié)果。使用狀態(tài)自動(dòng)機(jī)接受一定的輸入，執(zhí)行一定的動(dòng)作，產(chǎn)生一定的結(jié)果。使用狀態(tài)遷移描述整個(gè)工作過(guò)程。遷移描述整個(gè)工作過(guò)程。n狀態(tài)：一個(gè)標(biāo)識(shí)，能區(qū)分自動(dòng)機(jī)在不同時(shí)刻的狀況。有限狀態(tài)系統(tǒng)具有任意狀態(tài)：一個(gè)標(biāo)識(shí)，能區(qū)分自動(dòng)機(jī)在不同時(shí)刻的狀況。有限狀態(tài)系統(tǒng)具有任意有限數(shù)目的內(nèi)部有限數(shù)目的內(nèi)部“狀態(tài)狀態(tài)”n為什么叫自動(dòng)機(jī)？為什么叫自動(dòng)機(jī)？可能的狀態(tài)、運(yùn)行的規(guī)則都是事先確定的。一旦開(kāi)始運(yùn)行，就按照事先可能的狀態(tài)、運(yùn)行的規(guī)則都是事先確定的。一旦開(kāi)始運(yùn)行，就按照事先確定的規(guī)則工作，因此叫確定的規(guī)則工作，因此叫“自動(dòng)機(jī)自動(dòng)機(jī)”。n自動(dòng)機(jī)的本質(zhì)？自動(dòng)機(jī)的本質(zhì)

52、？根據(jù)狀態(tài)、輸入和規(guī)則決定下一個(gè)狀態(tài)根據(jù)狀態(tài)、輸入和規(guī)則決定下一個(gè)狀態(tài)狀態(tài)狀態(tài) 輸入輸入 規(guī)則規(guī)則 狀態(tài)遷移狀態(tài)遷移有限自動(dòng)機(jī)的定義n有限自動(dòng)機(jī)（有限自動(dòng)機(jī)（FA，F(xiàn)inite Automata）有限狀態(tài)機(jī)（有限狀態(tài)機(jī)（FSM，F(xiàn)inite State Machine）一個(gè)機(jī)器或一種控制結(jié)構(gòu)，設(shè)計(jì)它的目的是為一個(gè)機(jī)器或一種控制結(jié)構(gòu)，設(shè)計(jì)它的目的是為了自動(dòng)仿效一個(gè)事先確定的操作序列或響應(yīng)一了自動(dòng)仿效一個(gè)事先確定的操作序列或響應(yīng)一條已編碼的指令。條已編碼的指令。FA的模型nFA可以理解成一個(gè)控制器，它讀一條輸入帶上的字符。可以理解成一個(gè)控制器，它讀一條輸入帶上的字符。a b c d d e e f

53、 g . 控制器輸入帶有限自動(dòng)機(jī)有限自動(dòng)機(jī)= =有限控制器有限控制器+ +字符輸入帶字符輸入帶示例q0q1q2q3Start01101100輸入（字符串）輸入（字符串）： 0 0 1 000 10控制器確定有限自動(dòng)機(jī)（DFA）nDFA是一個(gè)五元組是一個(gè)五元組 M=(S, ,s0,F)S: 有限的狀態(tài)集合，每個(gè)元素稱(chēng)為一個(gè)有限的狀態(tài)集合，每個(gè)元素稱(chēng)為一個(gè)狀態(tài)狀態(tài)； : 有限的輸入字母表，每個(gè)元素稱(chēng)為一個(gè)有限的輸入字母表，每個(gè)元素稱(chēng)為一個(gè)輸入字符輸入字符；: 轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù)(狀態(tài)轉(zhuǎn)移集合狀態(tài)轉(zhuǎn)移集合): S S ；s0: 初始狀態(tài)，初始狀態(tài)， s0 S ；F: 終止?fàn)顟B(tài)集終止?fàn)顟B(tài)集, F S ；

54、狀態(tài)轉(zhuǎn)換矩陣n一個(gè)一個(gè)DFA可用一個(gè)矩陣表示，該矩陣的行表示狀態(tài)，列表可用一個(gè)矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示示輸入字符，矩陣元素表示(s,a)的值。的值。例：例：DFA M= ( 0,1,2,3，a,b, , 0, 3) 其中其中(0,a)=1 (0,b)=2 (2,a)=1 (2,b)=3 (1,a)=3 (1,b)=2 (3,a)=3 (3,b)=3 對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換矩陣對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換矩陣 狀態(tài)狀態(tài)ab012132213333DFA與狀態(tài)轉(zhuǎn)換圖n一個(gè)一個(gè)DFA可以表示成一張（確定的）狀態(tài)轉(zhuǎn)換圖。可以表示成一張（確定的）狀態(tài)轉(zhuǎn)換圖。假定假定DFA M含有含有m個(gè)狀態(tài)

55、和個(gè)狀態(tài)和n個(gè)輸入字符，那么，狀態(tài)圖必含有個(gè)輸入字符，那么，狀態(tài)圖必含有m 個(gè)狀態(tài)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)有個(gè)狀態(tài)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)有n條弧射出和別的結(jié)點(diǎn)相連。每條弧上用條弧射出和別的結(jié)點(diǎn)相連。每條弧上用中的一個(gè)不同輸入字符做標(biāo)記。整張圖有唯一的一個(gè)初態(tài)結(jié)點(diǎn)和若中的一個(gè)不同輸入字符做標(biāo)記。整張圖有唯一的一個(gè)初態(tài)結(jié)點(diǎn)和若干終態(tài)結(jié)點(diǎn)。干終態(tài)結(jié)點(diǎn)。狀態(tài)狀態(tài)ab012132213333 0 1 2 3 a b b a a,b a b 擴(kuò)展轉(zhuǎn)移函數(shù)n 函數(shù)函數(shù)接收一個(gè)字符串的狀態(tài)轉(zhuǎn)移函數(shù)。接收一個(gè)字符串的狀態(tài)轉(zhuǎn)移函數(shù)。 : S * S n 對(duì)任何對(duì)任何s S，定義：，定義： 1. (s , ) = s 2. 若若是一

56、個(gè)字符串是一個(gè)字符串, a是一個(gè)字符是一個(gè)字符定義定義: (s, a)=( (s,),a)n對(duì)于對(duì)于DFA: (s,a)=( (s, ),a)=(s,a)即對(duì)于單個(gè)字符時(shí)即對(duì)于單個(gè)字符時(shí)和和是相等的。是相等的。擴(kuò)展轉(zhuǎn)移函數(shù)q0q1q2q3Start01101100 (q0 , 0010) = ( (q0 , 001) ,0)= ( ( (q0 , 00) , 1) ,0)= ( ( ( (q0 , 0) , 0) , 1) ,0)= ( ( ( (q0 , 0) , 0) , 1) ,0)= ( ( (q2, 0) , 1) ,0)= ( (q0, 1) ,0)= (q1, ,0)=q3輸入（

57、字符串）輸入（字符串）： 0 0 1 000 10DFA接受的語(yǔ)言n被被DFA接收的字符串接收的字符串: 輸入結(jié)束后使輸入結(jié)束后使DFA的狀態(tài)到達(dá)終止的狀態(tài)到達(dá)終止?fàn)顟B(tài)。否則該字符串不能被狀態(tài)。否則該字符串不能被DFA接收接收.nDFA接收的語(yǔ)言接收的語(yǔ)言: 被被DFA接收的字符串的集合接收的字符串的集合. L(M) = ( s0 , ) F 對(duì)任一輸入字符串對(duì)任一輸入字符串 *，若存在一條從初態(tài)結(jié)點(diǎn)，若存在一條從初態(tài)結(jié)點(diǎn)s0到某到某一終態(tài)結(jié)點(diǎn)的通路一終態(tài)結(jié)點(diǎn)的通路, 且這條通路上所有弧的標(biāo)記連接成的且這條通路上所有弧的標(biāo)記連接成的字等于字等于,則稱(chēng)則稱(chēng)可以被可以被DFA M所識(shí)別所識(shí)別(讀出

58、、接受）讀出、接受）。 若若s0F, 則則可被接受?？杀唤邮?。 設(shè)計(jì)DFAn例例. 構(gòu)造自動(dòng)機(jī)，識(shí)別所有由奇數(shù)個(gè)構(gòu)造自動(dòng)機(jī)，識(shí)別所有由奇數(shù)個(gè)a和奇數(shù)個(gè)和奇數(shù)個(gè)b組成的字符串。組成的字符串。n關(guān)鍵：不需要記住所看到的整個(gè)字符串，只需記住至此所看到的關(guān)鍵：不需要記住所看到的整個(gè)字符串，只需記住至此所看到的a、b個(gè)數(shù)是偶數(shù)還是奇數(shù)。個(gè)數(shù)是偶數(shù)還是奇數(shù)。q偶偶a偶偶bq奇奇a偶偶bq偶偶a奇奇bq奇奇a奇奇bStartbaabaabb非確定的有限自動(dòng)機(jī)n修改修改DFA的模型的模型,使之在某個(gè)狀態(tài)使之在某個(gè)狀態(tài), 對(duì)應(yīng)一個(gè)輸入對(duì)應(yīng)一個(gè)輸入,可以有多個(gè)轉(zhuǎn)移可以有多個(gè)轉(zhuǎn)移, 到達(dá)不到達(dá)不 同同的狀態(tài)的狀態(tài),

59、 即：即：具有在同一情況下可有不同選擇的能力。具有在同一情況下可有不同選擇的能力。則稱(chēng)為非確定的有限則稱(chēng)為非確定的有限自動(dòng)機(jī)。自動(dòng)機(jī)。r0r11r211p0p11p311p21s011接受長(zhǎng)度為接受長(zhǎng)度為3 3的倍的倍數(shù)的輸入字符串?dāng)?shù)的輸入字符串接受長(zhǎng)度為接受長(zhǎng)度為4 4的倍的倍數(shù)的輸入字符串?dāng)?shù)的輸入字符串接受長(zhǎng)接受長(zhǎng)度為度為3 3或或4 4的的倍數(shù)的倍數(shù)的輸入字輸入字符串符串非確定的有限自動(dòng)機(jī)n一個(gè)非確定的有限自動(dòng)機(jī)（一個(gè)非確定的有限自動(dòng)機(jī)（NFA）M 是一個(gè)五元組是一個(gè)五元組: M = ( S, , , S0, F )，其中，其中: （1）S和和 的定義同前；的定義同前； （2）: S 2

60、S（狀態(tài)子集）；（狀態(tài)子集）； 對(duì)于某個(gè)狀態(tài)對(duì)于某個(gè)狀態(tài)s S 和一個(gè)輸入字母和一個(gè)輸入字母a： (s, a)=S S （3）S0 S為非空初態(tài)集；為非空初態(tài)集； （4）F S為終態(tài)集為終態(tài)集狀態(tài)轉(zhuǎn)換圖和轉(zhuǎn)換矩陣表示的NFAStartpr0, 10q1(1)Startp0, 11qr0, 1(2)pq r0 q q q, r 1pq r0 p r r 1 p, q 注：狀態(tài)轉(zhuǎn)換矩陣中的每一項(xiàng)都是一個(gè)集合。注：狀態(tài)轉(zhuǎn)換矩陣中的每一項(xiàng)都是一個(gè)集合。含空集含空集，即對(duì)于某些狀態(tài)與輸入字母的組合可能，即對(duì)于某些狀態(tài)與輸入字母的組合可能沒(méi)有動(dòng)作。沒(méi)有動(dòng)作。NFA和DFA的比較例例. 構(gòu)造構(gòu)造NFA，可識(shí)別，可識(shí)別0,1