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

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

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

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

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

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

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

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

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

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

10、輸入源程序文本。輸入串一般放在輸入串一般放在一個緩沖區(qū)中，一個緩沖區(qū)中，這個緩沖區(qū)稱輸這個緩沖區(qū)稱輸入緩沖區(qū)。入緩沖區(qū)。單詞符號的識別：超前搜索n關(guān)鍵字識別關(guān)鍵字識別 例例. 在標(biāo)準在標(biāo)準FORTRAN中四個合法句子：中四個合法句子： 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)識符為標(biāo)識符的一部分的一部分單詞符號的識別：超前搜索n標(biāo)識符的識別標(biāo)識符的識別多數(shù)語言的標(biāo)識符是字母開頭的多數(shù)語言的標(biāo)識符是字母開頭的“字母字母/ /數(shù)字數(shù)字”串

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

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

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

14、轉(zhuǎn)換圖的作用n一個狀態(tài)轉(zhuǎn)換圖可用于一個狀態(tài)轉(zhuǎn)換圖可用于接受接受（或（或識別識別）一定的符）一定的符號串。號串。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對于某一符號串對于某一符號串，在狀態(tài)轉(zhuǎn)換圖中，若存在一，在狀態(tài)轉(zhuǎn)換圖中，若存在一條路產(chǎn)生條路產(chǎn)生，則稱狀態(tài)轉(zhuǎn)換圖接受（或識別）該，則稱狀態(tài)轉(zhuǎn)換圖接受（或識別）該符號串符號串，否則稱符號串，否則稱符號串不能被接受。不能被接受。狀態(tài)轉(zhuǎn)換圖所能識別的語言n能被狀態(tài)轉(zhuǎn)換圖能被狀態(tài)轉(zhuǎn)換圖TG接受的符號串的集合記為接受的符號串的集合記為L(TG)，稱它為，稱它為狀態(tài)轉(zhuǎn)換圖所能

15、識別的語言狀態(tài)轉(zhuǎn)換圖所能識別的語言。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ù)程序語言的單詞符號都大多數(shù)程序語言的單詞符號都可以用狀態(tài)轉(zhuǎn)換圖予以識別?？梢杂脿顟B(tài)轉(zhuǎn)換圖予以識別。字母字母其他其他字母或數(shù)字字母或數(shù)字* *（b b）識別標(biāo)識符的轉(zhuǎn)換圖）識別標(biāo)識符的轉(zhuǎn)換圖其他其他數(shù)字數(shù)字數(shù)字數(shù)字* *（c c）識別整數(shù)的轉(zhuǎn)換圖）識別整數(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)字母X XY Y(a)(a)單個符號的轉(zhuǎn)單個符號的轉(zhuǎn)換圖示例換圖示例意味著多讀進了一個

16、不屬于標(biāo)意味著多讀進了一個不屬于標(biāo)識符部分的字符，應(yīng)把它退還識符部分的字符，應(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ù)字數(shù)字.數(shù)字數(shù)字 .數(shù)字數(shù)字其它其它數(shù)字數(shù)字E / DE / D+ / -數(shù)字數(shù)字數(shù)字數(shù)字其它其它數(shù)字數(shù)字*6（d d）識別）識別FORTRANFORTRAN實型常數(shù)的轉(zhuǎn)換圖實型常數(shù)的轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖識別單詞符號的過程Step1. 從初態(tài)開始；從初態(tài)開始；Step2. 從輸入串中讀一個字符；從輸入串中讀一個字符；Step3. 判明讀入字符與從當(dāng)前狀態(tài)出

17、發(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，均不匹配時便告失??；到達終，均不匹配時便告失??；到達終態(tài)時便識別出一個單詞符號。態(tài)時便識別出一個單詞符號。例例. . 設(shè)一小語言所有單詞符號及其內(nèi)部表示形式設(shè)一小語言所有單詞符號及其內(nèi)部表示形式單詞符號單詞符號種別編碼種別編碼助憶符助憶符內(nèi)碼值內(nèi)碼值DIM1$DIM-IF2$IF-DO3$DO-STOP4$STOP-END5$END-標(biāo)識符標(biāo)識符6$ID內(nèi)部字符串內(nèi)部字符串整常數(shù)整常數(shù)7$INT標(biāo)準二進制形式標(biāo)

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

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

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

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

22、段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(); Retract(); value=InsertConst(st

23、rToken); 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(ch=) return($LBRACE,-);else

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

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

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

27、符: iden letter (letter digit)*整常數(shù)整常數(shù): integer digit(digit)* sign +- signedinteger sign integer不帶指數(shù)部分的實常數(shù)不帶指數(shù)部分的實常數(shù): decimal signedinteger . integer signedinteger . sign . Integer帶指數(shù)部分的實常數(shù)帶指數(shù)部分的實常數(shù): exponential (decimal signedinteger) E signedinteger例例. 識別小語言單詞符號的識別小語言單詞符號的 LEX 程序程序AUXILIARY DEFINITI

28、ONS /* 輔助定義輔助定義 */ letter AB . . .Z digit 01 . . . 9RECOGNITION RULES /* 識別規(guī)則識別規(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 (7, getConstTableEntryPoint(

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

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

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

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

33、)函數(shù)，執(zhí)行該函數(shù)即可函數(shù)，執(zhí)行該函數(shù)即可對輸入文本進行詞法分析。如下圖所示：對輸入文本進行詞法分析。如下圖所示：Flex正則表達式nFlex使用表達式規(guī)則來描述詞法規(guī)則，其使用的正則表達式是一種使使用表達式規(guī)則來描述詞法規(guī)則，其使用的正則表達式是一種使用元語言的模式描述，和擴展的用元語言的模式描述，和擴展的POSIX正則表達式基本類似。一些具正則表達式基本類似。一些具有特殊含義的字符列舉如下：有特殊含義的字符列舉如下：字符字符含義含義.匹配換行符n以外的全部單個字符匹配字符集，用表示取反，用-簡寫一段連續(xù)的ASCII字符a-z-jv除j和v以外的小寫字母除用于內(nèi)表取反外，作為模式的第一個字符

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

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

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

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

38、 0-9，L a-zA-Z_）使用使用來引用在聲明區(qū)自定義的模式，如：來引用在聲明區(qū)自定義的模式，如：Newline模式一定要位于一行的開頭且前面不能有縮進模式一定要位于一行的開頭且前面不能有縮進；動作的開頭一定要與對應(yīng)的模式在同一行；動作的開頭一定要與對應(yīng)的模式在同一行Flex規(guī)則描述文件n輔助代碼部分可定義一些分析過程中要用輔助代碼部分可定義一些分析過程中要用到的函數(shù)（當(dāng)然也可以定義到的函數(shù)（當(dāng)然也可以定義main函數(shù)），函數(shù)），這部分的代碼也會被這部分的代碼也會被Flex直接搬到生成的直接搬到生成的掃描器源代碼中掃描器源代碼中n作用域問題：為了保證自己定義的變量和作用域問題：為了保證自己

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

40、x實踐獲取與安裝nLinux下安裝下安裝Flex一般方法：一般方法：n從從http:/ check（檢查編譯結(jié)果，可省略）（檢查編譯結(jié)果，可省略）make install（如遇權(quán)限問題加上（如遇權(quán)限問題加上sudo命令）命令）快速方法：快速方法：n以以Ubuntu的的apt-get為例：進入終端，輸入以下命令為例：進入終端，輸入以下命令apt-get install built-essential（更新（更新gcc等編譯工具，可省略）等編譯工具，可省略）apt-get install flex（下載并安裝（下載并安裝Flex）安裝完畢后使用安裝完畢后使用flex -version命令打印版本號

41、驗證安裝命令打印版本號驗證安裝nWindows下使用下使用Flex查閱網(wǎng)上相關(guān)開源項目，需借助查閱網(wǎng)上相關(guān)開源項目，需借助Cygwin（略）（略）Flex實踐編譯與運行n將之前編寫完的將之前編寫完的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；n鍵入鍵入./myscanner運行掃描器，運行掃

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

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

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

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

46、則 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, 說明n運算符運算符 ”| |”讀為讀為”或或”； ”. .”讀為讀為”連接連接” ”* *”讀為讀為”閉包閉包”。 一般地，連接符一般地，連接符”. .”可省略不寫，在不引起混淆的情可省略不寫，在不引起混淆的情況下，括號可省去。況下，括號可省去。n正規(guī)式運算符的正規(guī)式運算符的優(yōu)先順序優(yōu)先順序為：

47、為：”* *”最高最高, ,”. .”次之次之, ,”| |”最低。最低。n若兩個正規(guī)式所表示的正規(guī)集相同，則認為二者等價，記若兩個正規(guī)式所表示的正規(guī)集相同，則認為二者等價，記為為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,baa,baaa,上所有以上所有以b為首后跟任意多個

48、為首后跟任意多個a的的字的集合。字的集合。正規(guī)式正規(guī)式a(a|b)*(a|b)*(aa|bb)(a|b)*正規(guī)集正規(guī)集上所有以上所有以a a為首的字集為首的字集上所有含有兩個相繼上所有含有兩個相繼a a或兩個相繼或兩個相繼b b的字集的字集例例2. C語言中語言中“標(biāo)識符標(biāo)識符”全體的正規(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ī)式的運算律n令令U、V和和W均為正規(guī)式，則：均為正規(guī)式，則： （1）

49、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運算律證明-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 )運算律證明-2（3）結(jié)合律）結(jié)合律: U(VW)=(UV)W 證明證明: L(U

50、(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*) 自動機n什么是自動機？什么是自動機？具有離散輸入輸出的數(shù)學(xué)模型。具有離散輸入輸出的數(shù)學(xué)模型。自動機接受一定的輸入，執(zhí)行一定的動作，產(chǎn)

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

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

53、限控制器有限控制器+ +字符輸入帶字符輸入帶示例q0q1q2q3Start01101100輸入（字符串）輸入（字符串）： 0 0 1 000 10控制器確定有限自動機（DFA）nDFA是一個五元組是一個五元組 M=(S, ,s0,F)S: 有限的狀態(tài)集合，每個元素稱為一個有限的狀態(tài)集合，每個元素稱為一個狀態(tài)狀態(tài)； : 有限的輸入字母表，每個元素稱為一個有限的輸入字母表，每個元素稱為一個輸入字符輸入字符；: 轉(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 ；狀態(tài)轉(zhuǎn)換矩陣n一個一個DFA可用一個矩陣表示，該矩

54、陣的行表示狀態(tài)，列表可用一個矩陣表示，該矩陣的行表示狀態(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 對應(yīng)的狀態(tài)轉(zhuǎn)換矩陣對應(yīng)的狀態(tài)轉(zhuǎn)換矩陣 狀態(tài)狀態(tài)ab012132213333DFA與狀態(tài)轉(zhuǎn)換圖n一個一個DFA可以表示成一張（確定的）狀態(tài)轉(zhuǎn)換圖?？梢员硎境梢粡垼ù_定的）狀態(tài)轉(zhuǎn)換圖。假定假定DFA M含有含有m個狀態(tài)和個狀態(tài)和n個輸入字符，那么，狀態(tài)圖必含有個輸入字

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

56、定義: (s, a)=( (s,),a)n對于對于DFA: (s,a)=( (s, ),a)=(s,a)即對于單個字符時即對于單個字符時和和是相等的。是相等的。擴展轉(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輸入（字符串）輸入（字符串）： 0 0 1 000 10

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

58、。可被接受。 設(shè)計DFAn例例. 構(gòu)造自動機，識別所有由奇數(shù)個構(gòu)造自動機，識別所有由奇數(shù)個a和奇數(shù)個和奇數(shù)個b組成的字符串。組成的字符串。n關(guān)鍵：不需要記住所看到的整個字符串，只需記住至此所看到的關(guān)鍵：不需要記住所看到的整個字符串，只需記住至此所看到的a、b個數(shù)是偶數(shù)還是奇數(shù)。個數(shù)是偶數(shù)還是奇數(shù)。q偶偶a偶偶bq奇奇a偶偶bq偶偶a奇奇bq奇奇a奇奇bStartbaabaabb非確定的有限自動機n修改修改DFA的模型的模型,使之在某個狀態(tài)使之在某個狀態(tài), 對應(yīng)一個輸入對應(yīng)一個輸入,可以有多個轉(zhuǎn)移可以有多個轉(zhuǎn)移, 到達不到達不 同同的狀態(tài)的狀態(tài), 即：即：具有在同一情況下可有不同選擇的能力。具有

59、在同一情況下可有不同選擇的能力。則稱為非確定的有限則稱為非確定的有限自動機。自動機。r0r11r211p0p11p311p21s011接受長度為接受長度為3 3的倍的倍數(shù)的輸入字符串?dāng)?shù)的輸入字符串接受長度為接受長度為4 4的倍的倍數(shù)的輸入字符串?dāng)?shù)的輸入字符串接受長接受長度為度為3 3或或4 4的的倍數(shù)的倍數(shù)的輸入字輸入字符串符串非確定的有限自動機n一個非確定的有限自動機（一個非確定的有限自動機（NFA）M 是一個五元組是一個五元組: M = ( S, , , S0, F )，其中，其中: （1）S和和 的定義同前；的定義同前； （2）: S 2S（狀態(tài)子集）；（狀態(tài)子集）； 對于某個狀態(tài)對于某

60、個狀態(tài)s S 和一個輸入字母和一個輸入字母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)換矩陣中的每一項都是一個集合。注：狀態(tài)轉(zhuǎn)換矩陣中的每一項都是一個集合。含空集含空集，即對于某些狀態(tài)與輸入字母的組合可能，即對于某些狀態(tài)與輸入字母的組合可能沒有動作。沒有動作。NFA和DFA的比較例例. 構(gòu)造構(gòu)造NFA，可識別，可識別0,1上的語言上的語言 L=x000y | x,y0.1