編譯原理實踐10-詞法分析程序的自動生成器LEX

編譯原理實踐

--詞法分析程序的自動生成器LEX

由于各種高級程序設計語言的單詞形式基本上可以用一組正規(guī)式來描述，人們就希望能否構造一個自動生成系統(tǒng)，只要給出程序設計語言的各類單詞描述以及識別出各類單詞后應輸出的結果，這種自動系統(tǒng)便能自動產生此程序設計語言的詞法分析程序Lex就是這樣一個工具，他將正規(guī)式轉換為一個NFA，進而轉換為相應的DFA，這個DFA可以識別該正規(guī)式所表示的語言的句子

LEX簡單的介紹1LEX(lexicalananlyzergenerator)

一個詞法分析程序的自動生成器.LEX是1972年貝爾實驗室首先在UNIX上實現的.2FLEX(fastlexicalananlyzergenerator)

是對LEX的擴充,它可在MS-DOS下運行.我們這里實際使用的是FLEX,但仍稱呼為LEX.LEX簡單的介紹LEX能根據給定的正則表達式自動生成相應的詞法分析程序輸入:是用LEX語言寫的源程序生成:用C語言描述的詞法分析程序LEX生成的目標程序包含一個狀態(tài)轉換矩陣和一個控制執(zhí)行程序.

LEX使用流程使用LEX的流程如圖:LEX源程序LEXYYLEX.CYYLEX.CC編譯器YYLEX.EXEYYLEX.EXE字符串源程序符號串源程序LEX源程序是使用LEX語言編寫的詞法規(guī)則說明,經過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或b外的任一個字符.用LEX語言表達正則表達式(5).表示除了換行符之外的任一個字符.(6)”text”表示雙引號里的每個字符(包括元字符)都按字符處理,如”ab[01]”就是表示ab[01]是字符串,其中的[和]不是元字符(7)\轉義字符(8){xxx}名字xxx表示的正則表達式。(9)r|s表示正則表達式r或正則表達式s。(10)rs表示正則表達式r與正則表達式s的連接。用LEX語言表達正則表達式(11)(r)表示()內的優(yōu)先級高于括號外。(12)r*表示正則表達式r可重復零次或多次。(13)r+表示正則表達式r可重復一次或多次。(14)r?表示r是一個可選的正則表達式。(15)r{m,n}其中m,n是正整數，表達正則表達式r的m~n次重復。(16)r{m}表示正則表達式r的m次重復。(17)r{m,}表示正則表達式r的m到多次的重復。(18)^行的開始，$行的結尾用LEX語言表達正則表達式例：1)二進制數(0|1)*2)以aa或bb開頭的由a和b任意組成的字符串(aa|bb)(a|b)*或(aa|bb)[ab]*3)任何一個從0~9的數字:[0-9]4)長度不超過8的小寫字符串[a-z]{1,8}用LEX語言表達正則表達式5)無符號整數[0-9]+6)可帶小數點的有符號數(“+”|”-”)?[0-9]+(“.”[0-9]+)?7)可帶指數的有符號數(“+”|”-”)?[0-9]+(“.”[0-9]+)?(E(“+”|”-”)?[0-9]+)?8)標識符：字母或_開頭，后跟字母數字、下劃線等字符[a-zA-Z_]([a-zA-Z_]|[0-9])*9)空白區(qū)[\t\n]+元字符約定元字符約定：可以為正則表達式起名，這些名字也可使用在其他的正則表達式中，需正則表達式放在大括號中。例如，無符號整數定義為：num=[0-9]+其中，num為正則表達式名。 在有符號的整數的定義中，可以引用正則表達式名num:signedNum=(+|-)?{num}注意：在定義正則表達式名時并不寫大括號，只有在使用正則表達式名時才加上大括號。用LEX語言表達正則表達式在方括號（表示字符類）中，大多數的元字符都喪失了其特殊狀況，且不必用引號括起來。甚至如果可以首先將連字符(-)列出來的話，則也可以將其看作字符。因此，可將正則表達式(“+”|”-”)寫作[-+]，但不能寫成[+-]，這是因為元字符“-”用于表示字符的一個范圍。又例如：[.”?]表示了句號、引號和問號3個字符中的任一個字符，此時，這三個字符在方括號中都喪失了它們元字符的含義。但是有一些字符即使是在方括號中也仍是元字符，如\和^。如果要得到像反斜杠\這種真正的字符就必須在字符前加一個反斜杠。由于引號在方括號內已失去了它們的元字符的含義，所以不能用引號，因此[\^\\]就表示了真正的字符^和\。LEX源程序結構LEX源程序是用LEX語言編寫的詞法規(guī)則說明，即用LEX語言對表示高級程序設計語言的單詞集的正則表達式進行描述。LEX源程序分三個部分：

1.說明部分

2.識別規(guī)則

3.輔助過程。各部分之間用%%隔開。即：

說明部分

%%識別規(guī)則

%%

輔助過程

LEX源程序結構：說明部分1說明部分：用于定義識別規(guī)則中要用到的正則表達式名，包括：變量說明、標識符常量說明、正則定義，C語言的說明信息（C語言的說明部分必須用分介符%和%括起來）。LEX源程序結構：說明部分說明部分由如下形式的LEX語句組成：D1

R1

D2R2

……DnRn其中，R1，R2，…Rn使用LEX語言表示的正則表達式；D1，D2，…Dn是給正則表達式起的名字，稱為正則表達式名。限定在Ri中只能出現字母表∑中的字符，以及前面已經定義過的正則表達式名，這樣就可以定義程序語言的單詞符號。

LEX源程序結構：說明部分例如，用LEX語句寫的標識符和無符號整數的定義如下：標識符：letter[a-zA-Z]identifier{letter}+無符號整數：digit[0-9]num{digit}+C語言的說明信息主要包括將來生成的詞法分析程序要使用的一些庫文件和全局變量的聲明。%{和%}中間的內容會原封不動地復制到LEX生成的詞法分析程序的最前部。LEX源程序結構：說明部分例如下面的一段代碼：%{#include<stdio.h>intlineno=1;%}line^(.*)\n//表示一行字符LEX源程序結構：識別規(guī)則2識別規(guī)則用正則表達式給出單詞的定義，以及在識別出該正則表達式以后要執(zhí)行的程序片段，具有如下形式的語句：P1{動作1}P2{動作2}

……Pn{動作n}其中，Pi（i=1，2，3……n）是一個用LEX語言描述的正則表達式，也即是單詞符號；動作i是C語言的程序語句，表示當在識別出形為Pi的單詞符號時，詞法分析應執(zhí)行的動作。該動作一般是返回單詞的單詞記號及單詞值。LEX源程序結構：識別規(guī)則例如：

%%{line}{printf(“%5d%s”,lineno++,yytext);}這段代碼表示識別出一行字符后，輸出行號以及這行字符，然后行號遞增。yytext是LEX的內部命字，它的內容就是正則表達式line匹配的字符串。LEX源程序中的識別規(guī)則完全決定了詞法分析程序的功能。該詞法分析程序只能識別P1，P2，…Pn這些單詞符號。識別出的單詞符號保存在yytext中。LEX源程序結構：輔助過程3輔助過程給出用戶所需要的其他操作，它是識別部分某些動作需要調用的過程。如果不是C語言的庫函數，則要在此給出具體的定義。這些程序也可以存入另外的程序文件中，單獨編譯，最后和詞法分析程序連接裝配到一起。例如：下段輔助過程：%%main(){yylex();return0;}LEX源程序結構：輔助過程intyywrap(){return1;}這段代碼包含了一個調用函數yylex()的main()過程。yylex()是由LEX構造的過程的名字，該過程進行詞法分析。運行FLEX將上述三段代碼連在一起，假設保存在名為exam1.lex的文件中，最好與FLEX在同一目錄下，那么，在DOS下進入FLEX所在的目錄，FLEX運行就可以產生詞法分析程序，運行的命令(根據自己情況更改路徑)運行FLEX這樣就會在同一目錄下產生一個文件LEX.YY.C，這就是根據exam1.lex由LEX生成的詞法分析程序。接下來可以對LEX.YY.C進行編譯（可以用VisualC++6.0）從而得到可執(zhí)行文件LEX.YY.EXE，執(zhí)行該文件，隨意輸入一行字符串，按回車則在屏幕上顯示該字符串。一些常用LEX內部名字及含義在上例中的LEX源程序中包含的C程序中，引用了一個LEX內部命令yytext,下面給出一些常用的LEX內部命字及其含義如下：lex.yy.cLEX輸出文件名yylexLEX掃描例程yytext當前被某規(guī)則匹配的字符串yyinLEX輸入文件（默認為stdin,即鍵盤）；yyoutLEX輸出文件

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