編譯原理實(shí)踐

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

2、cal ananlyzer generator) 是對(duì)LEX的擴(kuò)充,它可在MS-DOS下運(yùn)行. 我們這里實(shí)際使用的是FLEX,但仍稱呼為L(zhǎng)EX.LEX簡(jiǎn)單的介紹簡(jiǎn)單的介紹3 LEX能根據(jù)給定的正則表達(dá)式自動(dòng)生成相應(yīng)的詞法分析程序. LEX的輸入是用LEX 語(yǔ)言寫的源程序, 生成一個(gè)用C語(yǔ)言描述的詞法分析程器,所以LEX本身就相當(dāng)于LEX語(yǔ)言寫的編譯程序. LEX生成的目標(biāo)程序包含一個(gè)狀態(tài)轉(zhuǎn)換矩陣和一個(gè)控制執(zhí)行程序. LEX使用流程使用流程使用LEX的流程如圖:LEX源程序LEXYYLEX.CYYLEX.CC編譯器YYLEX.EXEYYLEX.EXE字符串源程序符號(hào)串源程序LEX源程序是使用LE

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

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

5、達(dá)式。(15)rm,n其中m,n是正整數(shù)，表達(dá)正則表達(dá)式r的 mn次重復(fù)。(16)rm表示正則表達(dá)式r的m次重復(fù)。(17)rm,表示正則表達(dá)式r的m到多次的重復(fù)。(18)行的開(kāi)始，$行的結(jié)尾用用LEX語(yǔ)言表達(dá)正則表達(dá)式語(yǔ)言表達(dá)正則表達(dá)式例：1)二進(jìn)制數(shù) (0|1)*2)以aa或bb開(kāi)頭的由a和b任意組成的字符串 (aa|bb)(a|b)*或(aa|bb)ab*3) 任何一個(gè)從09的數(shù)字:0-94)長(zhǎng)度不超過(guò)8的小寫字符串a(chǎn)-z1,8用用LEX語(yǔ)言表達(dá)正則表達(dá)式語(yǔ)言表達(dá)正則表達(dá)式5) 無(wú)符號(hào)整數(shù)0-9+6)可帶小數(shù)點(diǎn)的有符號(hào)數(shù)(“+”|”-”)?0-9+(“.”0-9+)?7) 可帶指數(shù)的有符號(hào)

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

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

8、在方括號(hào)內(nèi)已失去了它們的元字符的含義，所以不能用引號(hào)，因此就表示了真正的字符和。LEX源程序結(jié)構(gòu)源程序結(jié)構(gòu) LEX源程序是用LEX語(yǔ)言編寫的詞法規(guī)則說(shuō)明，即用LEX語(yǔ)言對(duì)表示高級(jí)程序設(shè)計(jì)語(yǔ)言的單詞集的正則表達(dá)式進(jìn)行描述。LEX源程序分三個(gè)部分： 1.說(shuō)明部分 2.識(shí)別規(guī)則 3.輔助過(guò)程。各部分之間用%隔開(kāi)。即： 說(shuō)明部分 % 識(shí)別規(guī)則 % 輔助過(guò)程 LEX源程序結(jié)構(gòu)：說(shuō)明部分源程序結(jié)構(gòu)：說(shuō)明部分1 說(shuō)明部分： 用于定義識(shí)別規(guī)則中要用到的正則表達(dá)式名，包括： 變量說(shuō)明、 標(biāo)識(shí)符常量說(shuō)明、 正則定義， C語(yǔ)言的說(shuō)明信息（C語(yǔ)言的說(shuō)明部分必須用分介符%和%括起來(lái)）。LEX源程序結(jié)構(gòu)：說(shuō)明部分源程序結(jié)

9、構(gòu)：說(shuō)明部分說(shuō)明部分由如下形式的LEX語(yǔ)句組成： D1 R1 D2 R2 Dn Rn其中，R1，R2，Rn使用LEX語(yǔ)言表示的正則表達(dá)式；D1，D2，Dn是給正則表達(dá)式起的名字，稱為正則表達(dá)式名。限定在Ri中只能出現(xiàn)字母表中的字符，以及前面已經(jīng)定義過(guò)的正則表達(dá)式名，這樣就可以定義程序語(yǔ)言的單詞符號(hào)。 LEX源程序結(jié)構(gòu)：說(shuō)明部分源程序結(jié)構(gòu)：說(shuō)明部分例如，用LEX語(yǔ)句寫的標(biāo)識(shí)符和無(wú)符號(hào)整數(shù)的定義如下：標(biāo)識(shí)符：letter a-zA-Z identifier letter+無(wú)符號(hào)整數(shù)：digit 0-9 num digit+C語(yǔ)言的說(shuō)明信息主要包括將來(lái)生成的詞法分析程序要使用的一些庫(kù)文件和全局變量的

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

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

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

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

14、認(rèn)為stdin,即鍵盤）；yyout LEX輸出文件 （默認(rèn)為stdout，即顯示器）input LEX緩沖的輸入例程；ECHO LEX默認(rèn)行為，即將yytext()打印到y(tǒng)youtyywrap 這一函數(shù)在文件（或輸入）的末尾調(diào)用。如果函數(shù)的返回值是1，就停止解析。 舉例舉例1.例子 exam2.txt這段代碼由LEX產(chǎn)生的程序的功能是：輸入以字符a開(kāi)頭或結(jié)尾的任意字符串，則將該字符串顯示出來(lái)，而對(duì)去其他的輸入串則不能輸出。因?yàn)樵贚EX代碼中，識(shí)別出.*n描寫的單詞后，沒(méi)有動(dòng)作，所以就沒(méi)有輸出。對(duì)于ends_with_a和begins_with_a描述的單詞，用ECHO輸出到y(tǒng)yout.這個(gè)LEX輸入還有一個(gè)值得注意的特征：所列的規(guī)則具有二義性（ambiguous）,這是因?yàn)檩斎氪善ヅ涠鄠€(gè)規(guī)則。實(shí)際上，無(wú)論它是否以a開(kāi)頭或結(jié)尾，都可與表達(dá)式.*n匹配。LEX有一個(gè)解決這種二義性的優(yōu)先權(quán)系統(tǒng)。首先，LEX總是匹配可能的最長(zhǎng)子串（因此LEX總是生成符合最長(zhǎng)