編譯原理實(shí)踐10-詞法分析程序的自動(dòng)生成器LEX

編譯原理實(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)單的介紹1LEX(lexicalananlyzergenerator)

一個(gè)詞法分析程序的自動(dòng)生成器.LEX是1972年貝爾實(shí)驗(yàn)室首先在UNIX上實(shí)現(xiàn)的.2FLEX(fastlexicalananlyzergenerator)

是對(duì)LEX的擴(kuò)充,它可在MS-DOS下運(yùn)行.我們這里實(shí)際使用的是FLEX,但仍稱呼為L(zhǎng)EX.LEX簡(jiǎn)單的介紹LEX能根據(jù)給定的正則表達(dá)式自動(dòng)生成相應(yīng)的詞法分析程序輸入:是用LEX語(yǔ)言寫的源程序生成:用C語(yǔ)言描述的詞法分析程序LEX生成的目標(biāo)程序包含一個(gè)狀態(tài)轉(zhuǎn)換矩陣和一個(gè)控制執(zhí)行程序.

LEX使用流程使用LEX的流程如圖:LEX源程序LEXYYLEX.CYYLEX.CC編譯器YYLEX.EXEYYLEX.EXE字符串源程序符號(hào)串源程序LEX源程序是使用LEX語(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á)式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或b外的任一個(gè)字符.用LEX語(yǔ)言表達(dá)正則表達(dá)式(5).表示除了換行符之外的任一個(gè)字符.(6)”text”表示雙引號(hào)里的每個(gè)字符(包括元字符)都按字符處理,如”ab[01]”就是表示ab[01]是字符串,其中的[和]不是元字符(7)\轉(zhuǎn)義字符(8){xxx}名字xxx表示的正則表達(dá)式。(9)r|s表示正則表達(dá)式r或正則表達(dá)式s。(10)rs表示正則表達(dá)式r與正則表達(dá)式s的連接。用LEX語(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è)可選的正則表達(dá)式。(15)r{m,n}其中m,n是正整數(shù)，表達(dá)正則表達(dá)式r的m~n次重復(fù)。(16)r{m}表示正則表達(dá)式r的m次重復(fù)。(17)r{m,}表示正則表達(dá)式r的m到多次的重復(fù)。(18)^行的開(kāi)始，$行的結(jié)尾用LEX語(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è)從0~9的數(shù)字:[0-9]4)長(zhǎng)度不超過(guò)8的小寫字符串[a-z]{1,8}用LEX語(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)數(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ū)[\t\n]+元字符約定元字符約定：可以為正則表達(dá)式起名，這些名字也可使用在其他的正則表達(dá)式中，需正則表達(dá)式放在大括號(hào)中。例如，無(wú)符號(hào)整數(shù)定義為：num=[0-9]+其中，num為正則表達(dá)式名。 在有符號(hào)的整數(shù)的定義中，可以引用正則表達(dá)式名num:signedNum=(+|-)?{num}注意：在定義正則表達(dá)式名時(shí)并不寫大括號(hào)，只有在使用正則表達(dá)式名時(shí)才加上大括號(hào)。用LEX語(yǔ)言表達(dá)正則表達(dá)式在方括號(hào)（表示字符類）中，大多數(shù)的元字符都喪失了其特殊狀況，且不必用引號(hào)括起來(lái)。甚至如果可以首先將連字符(-)列出來(lái)的話，則也可以將其看作字符。因此，可將正則表達(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)在方括號(hào)內(nèi)已失去了它們的元字符的含義，所以不能用引號(hào)，因此[\^\\]就表示了真正的字符^和\。LEX源程序結(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ō)明部分1說(shuō)明部分：用于定義識(shí)別規(guī)則中要用到的正則表達(dá)式名，包括：變量說(shuō)明、標(biāo)識(shí)符常量說(shuō)明、正則定義，C語(yǔ)言的說(shuō)明信息（C語(yǔ)言的說(shuō)明部分必須用分介符%和%括起來(lái)）。LEX源程序結(jié)構(gòu)：說(shuō)明部分說(shuō)明部分由如下形式的LEX語(yǔ)句組成：D1

R1

D2R2

……DnRn其中，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ō)明部分例如，用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ù)文件和全局變量的聲明。%{和%}中間的內(nèi)容會(huì)原封不動(dòng)地復(fù)制到LEX生成的詞法分析程序的最前部。LEX源程序結(jié)構(gòu)：說(shuō)明部分例如下面的一段代碼：%{#include<stdio.h>intlineno=1;%}line^(.*)\n//表示一行字符LEX源程序結(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，3……n）是一個(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)作一般是返回單詞的單詞記號(hào)及單詞值。LEX源程序結(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ò)程3輔助過(guò)程給出用戶所需要的其他操作，它是識(shí)別部分某些動(dòng)作需要調(diào)用的過(guò)程。如果不是C語(yǔ)言的庫(kù)函數(shù)，則要在此給出具體的定義。這些程序也可以存入另外的程序文件中，單獨(dú)編譯，最后和詞法分析程序連接裝配到一起。例如：下段輔助過(guò)程：%%main(){yylex();return0;}LEX源程序結(jié)構(gòu)：輔助過(guò)程intyywrap(){return1;}這段代碼包含了一個(gè)調(diào)用函數(shù)yylex()的main()過(guò)程。yylex()是由LEX構(gòu)造的過(guò)程的名字，該過(guò)程進(jì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)行FLEX這樣就會(huì)在同一目錄下產(chǎn)生一個(gè)文件LEX.YY.C，這就是根據(jù)exam1.lex由LEX生成的詞法分析程序。接下來(lái)可以對(duì)LEX.YY.C進(jìn)行編譯（可以用VisualC++6.0）從而得到可執(zhí)行文件LEX.YY.EXE，執(zhí)行該文件，隨意輸入一行字符串，按回車則在屏幕上顯示該字符串。一些常用LEX內(nèi)部名字及含義在上例中的LEX源程序中包含的C程序中，引用了一個(gè)LEX內(nèi)部命令yytext,下面給出一些常用的LEX內(nèi)部命字及其含義如下：lex.yy.cLEX輸出文件名yylexLEX掃描例程yytext當(dāng)前被某規(guī)則匹配的字符串yyinLEX輸入文件（默認(rèn)為stdin,即鍵盤）；yyoutLEX輸出文件

（默認(rèn)為stdout，即顯示器）inputLEX緩沖的輸入例程；ECHOLEX默認(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