1、編譯原理實踐-詞法分析程序的自動生成器LEX由于各種高級程序設計語言的單詞形式基本上可以用一組正規式來描述，人們就希望能否構造一個自動生成系統，只要給出程序設計語言的各類單詞描述以及識別出各類單詞后應輸出的結果，這種自動系統便能自動產生此程序設計語言的詞法分析程序Lex就是這樣一個工具，他將正規式轉換為一個NFA，進而轉換為相應的DFA，這個DFA可以識別該正規式所表示的語言的句子 LEX簡單的介紹簡單的介紹1 LEX(lexical ananlyzer generator) 一個詞法分析程序的自動生成器. LEX是1972年貝爾實驗室首先在 UNIX上實現的.2 FLEX(fast lexi

2、cal ananlyzer generator) 是對LEX的擴充,它可在MS-DOS下運行. 我們這里實際使用的是FLEX,但仍稱呼為LEX.LEX簡單的介紹簡單的介紹3 LEX能根據給定的正則表達式自動生成相應的詞法分析程序. LEX的輸入是用LEX 語言寫的源程序, 生成一個用C語言描述的詞法分析程器,所以LEX本身就相當于LEX語言寫的編譯程序. LEX生成的目標程序包含一個狀態轉換矩陣和一個控制執行程序. LEX使用流程使用流程使用LEX的流程如圖:LEX源程序LEXYYLEX.CYYLEX.CC編譯器YYLEX.EXEYYLEX.EXE字符串源程序符號串源程序LEX源程序是使用LE

3、X語言編寫的詞法規則說明,經過LEX翻譯后形成目標文件YYLEX.C;再用C編譯器對YYLEX.C進行翻譯,生成目標程序YYLEX.EXE,它就是詞法分析程序,用YYLEX.EXE就可以將字符串源程序轉換成符號串源程序.用用LEX語言表達正則表達式語言表達正則表達式LEX的輸入是LEX源程序.首先介紹如何表示正則 表達式.LEX表示正則表達式時采用一些元字符* + ( ) | “ “等,表示方法如下. (1)對于單個的字母a,就直接表示成a,如a,+,-等 . (2)abc表示字符a,b,或c中的任一個,如01 表示0或1 (3)a-d表示字符a,b,c或d中的任一個. (4)ab表示除了a或

4、b外的任一個字符.用用LEX語言表達正則表達式語言表達正則表達式(5). 表示除了換行符之外的任一個字符.(6)”text”表示雙引號里的每個字符(包括元字符)都按字符處理,如”ab01”就是表示ab01是字符串,其中的和不是元字符(7) 轉義字符(8)xxx名字xxx表示的正則表達式。(9)r|s表示正則表達式r或正則表達式s。(10)rs表示正則表達式r與正則表達式s的連接。用用LEX語言表達正則表達式語言表達正則表達式(11)(r)表示()內的優先級高于括號外。(12)r*表示正則表達式r可重復零次或多次。(13)r+表示正則表達式r可重復一次或多次。(14)r?表示r是一個可選的正則表

5、達式。(15)rm,n其中m,n是正整數，表達正則表達式r的 mn次重復。(16)rm表示正則表達式r的m次重復。(17)rm,表示正則表達式r的m到多次的重復。(18)行的開始，$行的結尾用用LEX語言表達正則表達式語言表達正則表達式例：1)二進制數 (0|1)*2)以aa或bb開頭的由a和b任意組成的字符串 (aa|bb)(a|b)*或(aa|bb)ab*3) 任何一個從09的數字:0-94)長度不超過8的小寫字符串a-z1,8用用LEX語言表達正則表達式語言表達正則表達式5) 無符號整數0-9+6)可帶小數點的有符號數(“+”|”-”)?0-9+(“.”0-9+)?7) 可帶指數的有符號

6、數(“+”|”-”)?0-9+(“.”0-9+)?(E(“+”|”-”)?0-9+)?8)標識符：字母或_開頭，后跟字母數字、下劃線等字符a-zA-Z_(a-zA-Z_|0-9)*9)空白區 tn+LEX有一個重要的元字符約定是用大括號指出正則表達式的名字。在前面已經提到過可以為正則表達式起名，這些名字也可使用在其他的正則表達式中，而為了將正則表達式名和普通的字符序列區分開來，將正則表達式放在大括號中。 例如，無符號整數定義為：num=0-9+ 其中，num為正則表達式名。在有符號的整數的定義中，可以引用正則表達式名num: signedNum=(+|-)?num 注意：在定義正則表達式名時并

7、不寫大括號，只有在使用正則表達式名時才加上大括號。用用LEX語言表達正則表達式語言表達正則表達式LEX有個特征，在方括號（表示字符類）中，大多數的元字符都喪失了其特殊狀況，且不必用引號括起來。甚至如果可以首先將連字符列出來的話，則也可以將其看作字符。因此，可將前一個數字的正則表達式(“+”|”-”)寫作-+，但不能寫成+-，這是因為元字符“-”用于表示字符的一個范圍。又例如：.”?表示了句號、引號和問號3個字符中的任一個字符，此時，這三個字符在方括號中都喪失了它們元字符的含義。但是有一些字符即使是在方括號中也仍是元字符，如和。如果要得到像反斜杠這種真正的字符就必須在字符前加一個反斜杠。由于引號

8、在方括號內已失去了它們的元字符的含義，所以不能用引號，因此就表示了真正的字符和。LEX源程序結構源程序結構 LEX源程序是用LEX語言編寫的詞法規則說明，即用LEX語言對表示高級程序設計語言的單詞集的正則表達式進行描述。LEX源程序分三個部分： 1.說明部分 2.識別規則 3.輔助過程。各部分之間用%隔開。即： 說明部分 % 識別規則 % 輔助過程 LEX源程序結構：說明部分源程序結構：說明部分1 說明部分： 用于定義識別規則中要用到的正則表達式名，包括： 變量說明、 標識符常量說明、 正則定義， C語言的說明信息（C語言的說明部分必須用分介符%和%括起來）。LEX源程序結構：說明部分源程序結

9、構：說明部分說明部分由如下形式的LEX語句組成： D1 R1 D2 R2 Dn Rn其中，R1，R2，Rn使用LEX語言表示的正則表達式；D1，D2，Dn是給正則表達式起的名字，稱為正則表達式名。限定在Ri中只能出現字母表中的字符，以及前面已經定義過的正則表達式名，這樣就可以定義程序語言的單詞符號。 LEX源程序結構：說明部分源程序結構：說明部分例如，用LEX語句寫的標識符和無符號整數的定義如下：標識符：letter a-zA-Z identifier letter+無符號整數：digit 0-9 num digit+C語言的說明信息主要包括將來生成的詞法分析程序要使用的一些庫文件和全局變量的

10、聲明。%和% 中間的內容會原封不動地復制到LEX生成的詞法分析程序的最前部。LEX源程序結構：說明部分源程序結構：說明部分例如下面的一段代碼：% #include int lineno=1; %line (.*)n/表示一行字符LEX源程序結構：識別規則源程序結構：識別規則2 識別規則用正則表達式給出單詞的定義，以及在識別出該正則表達式以后要執行的程序片段，具有如下形式的語句： P1 動作1 P2 動作2 Pn 動作n其中，Pi（i=1，2，3n）是一個用LEX語言描述的正則表達式，也即是單詞符號；動作i是C語言的程序語句，表示當在識別出形為Pi的單詞符號時，詞法分析應執行的動作。該動作一般是

11、返回單詞的單詞記號及單詞值。例如：LEX源程序結構：識別規則源程序結構：識別規則 %line printf(“%5d %s”,lineno+,yytext);這段代碼表示識別出一行字符后，輸出行號以及這行字符，然后行號遞增。yytext是LEX的內部命字，它的內容就是正則表達式line匹配的字符串。LEX源程序中的識別規則完全決定了詞法分析程序的功能。該詞法分析程序只能識別P1，P2，Pn這些單詞符號。識別出的單詞符號保存在yytext中。LEX源程序結構：輔助過程源程序結構：輔助過程3輔助過程給出用戶所需要的其他操作，它是識別部分某些動作需要調用的過程。如果不是C語言的庫函數，則要在此給出具

12、體的定義。這些程序也可以存入另外的程序文件中，單獨編譯，最后和詞法分析程序連接裝配到一起。例如：下段輔助過程：%main()yylex();return 0;LEX源程序結構：輔助過程源程序結構：輔助過程int yywrap()return 1;這段代碼包含了一個調用函數yylex()的main()過程。yylex()是由LEX構造的過程的名字，該過程進行詞法分析。運行運行FLEX將上述三段代碼連在一起，假設保存在名為exam1.lex的文件中，最好與FLEX在同一目錄下，那么，在DOS下進入FLEX所在的目錄，FLEX運行就可以產生詞法分析程序，運行的命令(根據自己情況更改路徑)運行運行FL

13、EX這樣就會在同一目錄下產生一個文件LEX.YY.C，這就是根據exam1.lex由LEX生成的詞法分析程序。接下來可以對LEX.YY.C進行編譯（可以用Visual C+ 6.0，或者Turbo C等）從而得到可執行文件LEX.YY.EXE，執行該文件，隨意輸入一行字符串，按回車則在屏幕上顯示該字符串。一些常用一些常用LEX內部名字及含義內部名字及含義在上例中的LEX源程序中包含的C程序中，引用了一個LEX內部命令yytext,下面給出一些常用的LEX內部命字及其含義如下：lex.yy.c LEX輸出文件名yylex LEX掃描例程yytext 當前行為匹配的串yyin LEX 輸入文件（默

14、認為stdin,即鍵盤）；yyout LEX輸出文件 （默認為stdout，即顯示器）input LEX緩沖的輸入例程；ECHO LEX默認行為，即將yytext()打印到yyoutyywrap 這一函數在文件（或輸入）的末尾調用。如果函數的返回值是1，就停止解析。 舉例舉例1.例子 exam2.txt這段代碼由LEX產生的程序的功能是：輸入以字符a開頭或結尾的任意字符串，則將該字符串顯示出來，而對去其他的輸入串則不能輸出。因為在LEX代碼中，識別出.*n描寫的單詞后，沒有動作，所以就沒有輸出。對于ends_with_a和begins_with_a描述的單詞，用ECHO輸出到yyout.這個LEX輸入還有一個值得注意的特征：所列的規則具有二義性（ambiguous）,這是因為輸入串可匹配多個規則。實際上，無論它是否以a開頭或結尾，都可與表達式.*n匹配。LEX有一個解決這種二義性的優先權系統。首先，LEX總是匹配可能的最長子串（因此LEX總是生成符合最長