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

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

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

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

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

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

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

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

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

10、輸入源程序文本。輸入串一般放在輸入串一般放在一個緩沖區中，一個緩沖區中，這個緩沖區稱輸這個緩沖區稱輸入緩沖區。入緩沖區。單詞符號的識別：超前搜索n關鍵字識別關鍵字識別 例例. 在標準在標準FORTRAN中四個合法句子：中四個合法句子： 1、DO99K = 1,10 2、IF(5.EQ.M)I = 10 3、DO99K = 1.10 4、IF(5) = 55其中的其中的DODO、IFIF為關鍵字為關鍵字其中的其中的DODO、IFIF為標識符為標識符的一部分的一部分單詞符號的識別：超前搜索n標識符的識別標識符的識別多數語言的標識符是字母開頭的多數語言的標識符是字母開頭的“字母字母/ /數字數字”串

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

12、如：描述。如： 字母字母| 字母字母| 數字數字 數字數字| 數字數字 +|+| | | ; |, |( | )|; |, |( | )|n利用這些規則識別單詞符號的過程可用一張稱為利用這些規則識別單詞符號的過程可用一張稱為狀態轉換狀態轉換圖圖的有限方向圖來表示，而狀態轉換圖識別單詞符號的過的有限方向圖來表示，而狀態轉換圖識別單詞符號的過程又可以方便地用程序實現程又可以方便地用程序實現。狀態轉換圖定義n轉換圖：是一個有限方向圖。轉換圖：是一個有限方向圖。結點代表狀態，用圓圈表示。結點代表狀態，用圓圈表示。n初態：一張轉換圖的啟動條件，通常有一個初態：一張轉換圖的啟動條件，通常有一個, ,用圓圈

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

14、轉換圖的作用n一個狀態轉換圖可用于一個狀態轉換圖可用于接受接受（或（或識別識別）一定的符）一定的符號串。號串。n路路: :在狀態轉換圖中從在狀態轉換圖中從初始狀態初始狀態到到某一終止狀態某一終止狀態的的弧上的弧上的標記序列標記序列。n對于某一符號串對于某一符號串，在狀態轉換圖中，若存在一，在狀態轉換圖中，若存在一條路產生條路產生，則稱狀態轉換圖接受（或識別）該，則稱狀態轉換圖接受（或識別）該符號串符號串，否則稱符號串，否則稱符號串不能被接受。不能被接受。狀態轉換圖所能識別的語言n能被狀態轉換圖能被狀態轉換圖TG接受的符號串的集合記為接受的符號串的集合記為L(TG)，稱它為，稱它為狀態轉換圖所能

15、識別的語言狀態轉換圖所能識別的語言。L(TG)= 0，1，00，01，11，001，010，L(TG)= a，b，ab，ba，aaa，bbb，aab，bba，狀態轉換圖示例n大多數程序語言的單詞符號都大多數程序語言的單詞符號都可以用狀態轉換圖予以識別。可以用狀態轉換圖予以識別。2 20 01 1字母字母其他其他字母或數字字母或數字* *（b b）識別標識符的轉換圖）識別標識符的轉換圖其他其他2 20 01 1數字數字數字數字* *（c c）識別整數的轉換圖）識別整數的轉換圖初態初態終態終態從從0 0狀態到狀態到1 1狀態狀態可能出現字母可能出現字母1 1X XY Y(a)(a)單個符號的轉單個

16、符號的轉換圖示例換圖示例2 23 3意味著多讀進了一個不屬于標意味著多讀進了一個不屬于標識符部分的字符，應把它退還識符部分的字符，應把它退還給輸入串給輸入串 a. .b a .b E (或或D)d a.b(a,b,d 為整數常數為整數常數) a.Ed .b Ed a.bE d aEd0123457數字數字.數字數字 .數字數字其它其它數字數字E / DE / D+ / -數字數字數字數字其它其它數字數字*6（d d）識別）識別FORTRANFORTRAN實型常數的轉換圖實型常數的轉換圖狀態轉換圖識別單詞符號的過程Step1. 從初態開始；從初態開始；Step2. 從輸入串中讀一個字符；從輸入串

17、中讀一個字符；Step3. 判明讀入字符與從當前狀態出發的哪條弧上判明讀入字符與從當前狀態出發的哪條弧上 的標記相匹配，便轉到相應匹配的那條弧所指的標記相匹配，便轉到相應匹配的那條弧所指向的狀態；向的狀態；Step4. 重復重復Step3，均不匹配時便告失敗；到達終，均不匹配時便告失敗；到達終態時便識別出一個單詞符號。態時便識別出一個單詞符號。例例. . 設一小語言所有單詞符號及其內部表示形式設一小語言所有單詞符號及其內部表示形式單詞符號單詞符號種別編碼種別編碼助憶符助憶符內碼值內碼值DIM1$DIM-IF2$IF-DO3$DO-STOP4$STOP-END5$END-標識符標識符6$ID內部

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

19、111213數字數字數字數字非數字非數字=+*非非*，()其它其它*狀態轉換圖實現中的變量和過程ch：字符變量：字符變量 功能：存放當前讀入字符功能：存放當前讀入字符strToken：字符數組：字符數組 功能：存放單詞的字符串功能：存放單詞的字符串GetChar：取字符過程：取字符過程 功能：取下一字符到功能：取下一字符到ch ；搜；搜 索指針索指針+1GetBC：濾除空字符過程：濾除空字符過程 功能：判功能：判ch =空空? 若是若是,則則調用調用GetCharConcat：子程序過程：子程序過程 功能：把功能：把ch中的字符拼入中的字符拼入strToken IsLetter, IsDigi

20、t：布爾函數：布爾函數 功能：功能： ch中為字母、數字時返中為字母、數字時返回回.T.Reserve：整型函數：整型函數 功能：按功能：按strToken中字符串查保中字符串查保留字表；查到返回保留字留字表；查到返回保留字編碼編碼;否則返回否則返回0Retract：子程序過程：子程序過程 功能：搜索指針回退一字符功能：搜索指針回退一字符InsertId：函數：函數 功能：將標識符插入符號表，返功能：將標識符插入符號表，返回符號表指針回符號表指針InsertConst函數函數 功能：功能： 將常數插入常數表，返回將常數插入常數表，返回常數表指針常數表指針程序段n不含回路的分叉結點對應的程序段可

21、表示為不含回路的分叉結點對應的程序段可表示為 GetChar(); if (IsLetter() 狀態狀態j的對應程序段的對應程序段 else if (IsDigit()狀態狀態k的對應程序段的對應程序段 else if(ch=/) 狀態狀態l的對應程序段的對應程序段 else錯誤處理錯誤處理ijkl字母字母數字數字/程序段n終態結點對應一條語句終態結點對應一條語句 return(code,value);ij字母或字母或數字數字其它其它in含回路的狀態結點對應的程序段可表示為含回路的狀態結點對應的程序段可表示為 GetChar(); While(IsLetter() or IsDigit()

22、GetChar(); 狀態狀態j的對應程序段的對應程序段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正規表達式與有限自動機正規表達式與有限自動機n詞法分析器的自動生成詞法分析器的自動生成FA正規表達式與有限自動機正規式正規式DFANFA正規文法正規文法子集法子集法狀態消去法狀態消去法DFA化簡化簡Thompson算法算法內容線索對于詞法分析器的要求對于詞法分析器的要求詞法分析器的設計詞法分析器的設計正規表達式與有限自動機正規表達式與有限自動機n詞法分析器的自

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

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

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

28、 LEX 程序程序AUXILIARY DEFINITIONS /* 輔助定義輔助定義 */ letter AB . . .Z digit 01 . . . 9RECOGNITION RULES /* 識別規則識別規則 */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, _ )正規式正規式LEX 的實現n方法方法由由LEX 編譯程序將編譯程序將 LEX 源程序改造為一個詞法分析器，即構造源程序改造為一個詞法分析器，即構造相應的相應的 DFAn步驟步驟對每條識別規則對每條識別規則Pi構造一個相應的構造一個相應的 NFA Mi引入一個新的初態引

30、入一個新的初態X, 連接成連接成 NFA M用子集法將其確定化并化簡用子集法將其確定化并化簡將將 DFA 轉換為詞法分析程序轉換為詞法分析程序n注意注意匹配最長子串匹配最長子串(最長匹配原則最長匹配原則)多個最長子串匹配多個最長子串匹配Pi, 以前面的以前面的Pi為準為準(優先匹配原則優先匹配原則)XM2P1 . . .M1MnP2Pn例例. LEX 程序程序: a abb a*bb* NFA M:012345678aabbabb 0137aa*bb*abb247875868bbbaabbba abba*bb*狀態狀態ab識別單詞識別單詞 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總結正規式正規式DFANFA正規文法正規文法子集法子集法狀態消去法狀態消去法DFA化簡化簡Thompson算法算法詞法分詞法分析程序析程序正規定義式正規定義式識別規則識別規則作業nP636 （4）（）（5）8（1）（）（2）（）（7）7 （1）（）（2）912Flex簡介nFlex是一款是一款Unix下用于自動生成詞法分析器（下用于自動生成詞法分析器（lexical analyzer）的開源工具。詞法分）的開源工具。詞法分析器又稱作掃描器（析器又稱作

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

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

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

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

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

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

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

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

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

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

42、n鍵入鍵入./myscanner運行掃描器，運行掃描器，yylex()函數默函數默認以認以stdin為輸入文件流，鍵入程序片段測試為輸入文件流，鍵入程序片段測試掃描器，按掃描器，按ctrl+d輸入輸入eof終止。終止。Flex實踐運行結果輸入的程序片段為i = 0IF i=0 i=1共計三個標識符（都是i），三個常數（0,0,1），代碼共2行，根據打印結果驗證程序基本正確參考資料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.正規表達式與有限自動機n為了更好地使用狀態轉換圖構造詞法分析器，和討論詞法為了更好地使用狀態轉換圖構造詞法分析器，和討論詞法分析器的自動生成，還需要將轉換圖的概念形式化。分析器的自動生成，還需要將轉換圖的概念形式化。正規式與正規集正規式與正規集確定有限自

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

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

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

47、n正規式運算符的正規式運算符的優先順序優先順序為：為：”* *”最高最高, ,”. .”次之次之, ,”| |”最低。最低。n若兩個正規式所表示的正規集相同，則認為二者等價，記若兩個正規式所表示的正規集相同，則認為二者等價，記為為U=V。例例1. 令令 a,b， 上的正規式和相應的正規集有上的正規式和相應的正規集有正規式正規式(a|b)(a|b)正規集正規集 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為首后跟任意多個為首后跟任意多個a的的字的集合。字的集合。正規式正規式a(a|b)*(a|b)*(aa|bb)(a|b)*正規集正規集上所有以上所有以a a為首的字集為首的字集上所有含有兩個相繼上所有含有兩個相繼a a或兩個相繼或兩個相繼b b的字集的字集例例2. C語言中語言中“標識符標識符”全體的正規式為：全體的正規式為：(A| B | Z | a | b | z)( A | B | Z | a |b|z|0|1|9)*例例3. “整數整數”全體的正規式：全體的正規式：(0 | 1 | 2 | 9 |)(0 | 1 | 2 | 9)*正規式的運算律n令令U

49、、V和和W均為正規式，則：均為正規式，則： （1）U|V=V|U交換律交換律 （2）U|(V|W)=(U|V)|W結合律結合律 （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）結合律）結合律: 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）結合律）結

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*) 自動機n什么是自動機？什么是自動機？具有離散輸入輸出的數學模型。具有離散輸入輸出的

51、數學模型。自動機接受一定的輸入，執行一定的動作，產生一定的結果。使用狀態自動機接受一定的輸入，執行一定的動作，產生一定的結果。使用狀態遷移描述整個工作過程。遷移描述整個工作過程。n狀態：一個標識，能區分自動機在不同時刻的狀況。有限狀態系統具有任意狀態：一個標識，能區分自動機在不同時刻的狀況。有限狀態系統具有任意有限數目的內部有限數目的內部“狀態狀態”n為什么叫自動機？為什么叫自動機？可能的狀態、運行的規則都是事先確定的。一旦開始運行，就按照事先可能的狀態、運行的規則都是事先確定的。一旦開始運行，就按照事先確定的規則工作，因此叫確定的規則工作，因此叫“自動機自動機”。n自動機的本質？自動機的本質

52、？根據狀態、輸入和規則決定下一個狀態根據狀態、輸入和規則決定下一個狀態狀態狀態 輸入輸入 規則規則 狀態遷移狀態遷移有限自動機的定義n有限自動機（有限自動機（FA，Finite Automata）有限狀態機（有限狀態機（FSM，Finite State Machine）一個機器或一種控制結構，設計它的目的是為一個機器或一種控制結構，設計它的目的是為了自動仿效一個事先確定的操作序列或響應一了自動仿效一個事先確定的操作序列或響應一條已編碼的指令。條已編碼的指令。FA的模型nFA可以理解成一個控制器，它讀一條輸入帶上的字符。可以理解成一個控制器，它讀一條輸入帶上的字符。a b c d d e e f

53、 g . 控制器輸入帶有限自動機有限自動機= =有限控制器有限控制器+ +字符輸入帶字符輸入帶示例q0q1q2q3Start01101100輸入（字符串）輸入（字符串）： 0 0 1 000 10控制器確定有限自動機（DFA）nDFA是一個五元組是一個五元組 M=(S, ,s0,F)S: 有限的狀態集合，每個元素稱為一個有限的狀態集合，每個元素稱為一個狀態狀態； : 有限的輸入字母表，每個元素稱為一個有限的輸入字母表，每個元素稱為一個輸入字符輸入字符；: 轉換函數轉換函數(狀態轉移集合狀態轉移集合): S S ；s0: 初始狀態，初始狀態， s0 S ；F: 終止狀態集終止狀態集, F S ；

54、狀態轉換矩陣n一個一個DFA可用一個矩陣表示，該矩陣的行表示狀態，列表可用一個矩陣表示，該矩陣的行表示狀態，列表示輸入字符，矩陣元素表示示輸入字符，矩陣元素表示(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 對應的狀態轉換矩陣對應的狀態轉換矩陣 狀態狀態ab012132213333DFA與狀態轉換圖n一個一個DFA可以表示成一張（確定的）狀態轉換圖。可以表示成一張（確定的）狀態轉換圖。假定假定DFA M含有含有m個狀態

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

56、個字符串是一個字符串, a是一個字符是一個字符定義定義: (s, a)=( (s,),a)n對于對于DFA: (s,a)=( (s, ),a)=(s,a)即對于單個字符時即對于單個字符時和和是相等的。是相等的。擴展轉移函數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接受的語言n被被DFA接收的字符串接收的字符串: 輸入結束后使輸入結束后使DFA的狀態到達終止的狀態到達終止狀態。否則該字符串不能被狀態。否則該字符串不能被DFA接收接收.nDFA接收的語言接收的語言: 被被DFA接收的字符串的集合接收的字符串的集合. L(M) = ( s0 , ) F 對任一輸入字符串對任一輸入字符串 *，若存在一條從初態結點，若存在一條從初態結點s0到某到某一終態結點的通路一終態結點的通路, 且這條通路上所有弧的標記連接成的且這條通路上所有弧的標記連接成的字等于字等于,則稱則稱可以被可以被DFA M所識別所識別(讀出

58、、接受）讀出、接受）。 若若s0F, 則則可被接受。可被接受。 設計DFAn例例. 構造自動機，識別所有由奇數個構造自動機，識別所有由奇數個a和奇數個和奇數個b組成的字符串。組成的字符串。n關鍵：不需要記住所看到的整個字符串，只需記住至此所看到的關鍵：不需要記住所看到的整個字符串，只需記住至此所看到的a、b個數是偶數還是奇數。個數是偶數還是奇數。q偶偶a偶偶bq奇奇a偶偶bq偶偶a奇奇bq奇奇a奇奇bStartbaabaabb非確定的有限自動機n修改修改DFA的模型的模型,使之在某個狀態使之在某個狀態, 對應一個輸入對應一個輸入,可以有多個轉移可以有多個轉移, 到達不到達不 同同的狀態的狀態,

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

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