一個詞法分析器的生成器全文

Lex–一個詞法分析器的(全文Lex–M.E.Lesk和E.S貝爾MurrayHill,NewJersey翻譯：Lex用于編寫一些程序，這些程序能夠通過正則表達式識別輸入流中的控制流。它能很好的適Lex源文件是一個由正則表達式和相應程序片斷構(gòu)成的表格。表格被轉(zhuǎn)換成程序，該程序被識別后，相應的程序片斷被執(zhí)行。表達式的識別由Lex生成的有限狀態(tài)自動機執(zhí)行。輸入流Lex寫就的詞法分析器接受二義性的說明書，在每一個輸入點上選擇最長的可能匹配。如果必Lex可以生成C或者Ratfor的分析器，Ratfor是一種可以被自動轉(zhuǎn)換為Fortran的語言。在PDP-11UNIX、HoneywellGCOS和IBMOS系統(tǒng)上都可以使用Lex。然而，這個使用手冊只討論了UNIX系統(tǒng)上用C語言生成解析器的方法，它只適用于UNIXVersion7下的Lex形式。對于那些希望聯(lián)合使用編譯器的程序，Lex的設計使其很容易與Yacc一起使用。Lex–M.E.Lesk和E.S貝爾MurrayHill,NewJersey介紹 Lex動作 使用Lex和 實例 字符集 感謝 Lex是一個程序，它被設計用來對輸入字符流進行詞法處理。它接受一種高級的、面向過用戶輸入的代碼說明書給入。Lex識別這些表達式，并且將輸入流分成一些匹配這些表達式的字符串。在這些字符串的分界處，用戶提供的程序片段被執(zhí)行。Lex代碼文件將正則表達式和程序片斷關聯(lián)。對每一條輸入到由Lex生成程序的表達式，相應的代碼片段被執(zhí)行。是不合適的。Lex不是完整的語言，但是是一個新語言的，它可以插入到各種不同的被代碼，Lex可以生成不同的宿主語言。宿主語言用于Lex生成輸出代碼，也用于用戶插入程序片斷。這使得Lex適用于不同的環(huán)境和不同的使用者。每一個應用程序可以是硬件、適用于該任務的宿主語言、用戶背景和局部接口屬性的直接結(jié)合?，F(xiàn)在，Lex唯一支持的宿主語言是CFortran（Ratfor[2]）在過去也被支持。Lex自身存在于UNIX、GCOS和OS/370上；但是Lex生成的代碼可以在任何適當?shù)木幾g器上使用。Lex將用戶輸入的表達式和動作actions（在這篇文章中被稱作源代碼）轉(zhuǎn)換為宿主語言；生成1。圖[式，用來匹配一個或多個、僅出現(xiàn)在行尾字符串中的空格或者制表符（C語言傳統(tǒng)，顯式QED中一樣表示“行尾”。沒有提供具體的動作，所以Lex生成的程序（yylex）會忽略這些字 [[\t]+printf("Lex可以被獨自用于簡單的轉(zhuǎn)換，或者在詞法層面上用于分析和統(tǒng)計。Lex也可以在語法分析器的中用于詞法分析階段；將Lex和Yacc[3]結(jié)合使用是極其方便的。Lex僅識別正則表達式；Yacc編寫的語法分析器可以接受一大類上下文無關文法，但是需要一個底層的分析器識別輸入記號。因此結(jié)合使用Lex和Yacc是合適的。當用于語法分析器的預處理程序時，Lex用于分割輸入流，而語法分析器將結(jié)果賦予結(jié)構(gòu)。這種情況下的流程圖如2所示（比如一個編譯器的前半部分）。程序的其他部分，由其他生成或者手寫，可以被方便的插入由Lex產(chǎn)生的程序中。圖Yaccyylex是Yacc用于接收語法分析器結(jié)果的名字，所以使用Lex中的名字可Lex由源文件中的正則表達式產(chǎn)生確定的有窮狀態(tài)自動機[4]。為了節(jié)省空間，這個自動機是被解釋，而不是被編譯得到的。結(jié)果仍是高速分析器。特別的，Lex程序識別和分割輸入流的時間與輸入的長度成正比。Lex中規(guī)則的數(shù)量和復雜度對于執(zhí)行速度來說是無關的，除非規(guī)則中因此也就是Lex生成程序的大小。在由Lex生成的程序中，用戶的片斷（每一條正則表達式匹配后的動作）像switch中的case一般的Lex{user而definitions和usersubroutines經(jīng)常被忽略。第二個%%是可選擇的，但是第一個必須存在rules的開始。因此最簡單的Lex程序是（沒有definitions和rules），這個程序輸入將不加修改地到輸出integerprintf("foundkeywordinteger，找到后輸出“foundkeywordINT”。在這個例子中，主程序為C語言并且用Cprintf打印字符串。用第一個出現(xiàn)的空白符或者制表符作為表達式的結(jié)束標記。如果action僅僅是一條簡單的C表達式，那么它可以直接寫在這一行的 這些規(guī)則是不夠強大的，比如pertroleum應該變?yōu)間aseum；一種處理它的方法將在下文中予正則表達式的定義與QED[5]很相似。一個正則表達式用于識別一組匹配的字符串。它包括文本"\[]???.*+|()$/{}%<用者可以避免上面的操作符，并且這樣做對于以后擴展Lex長度是安全的。。一些標準的帶有\(zhòng)的C轉(zhuǎn)義字符也會被識別：\n是換行符，\t是制表符，\b是回退符。想引入\，使用\\。因為換行符在表達式中是不合法的，所以\n必須被使用；而制表符和回退符告。（例如，[0-z]ASCII中表示的字符要多于在EBCDIC中）。如果想在字符類中使用-作為.a0個a；而表示1個或者的a實例。例如(ab|ab|(ab|上下文有關。Lex可以識別少量的soigo^$。如^（^相矛$等價。左線性文法在Lex中由開始狀態(tài)10節(jié)中闡述。如果一條規(guī)則只在Lex自動解釋器處于開始狀態(tài)x時被執(zhí)行，則該規(guī)則應該有使用尖括號的前綴最后，初始的%是特別的，它用于分隔Lex當一條上述表達式匹配以后，Lex將執(zhí)行相應的動作。本節(jié)介紹Lex中編寫動作的一些特點。注意，Lex中存在一個從輸入到輸出直接拷貝的默認動作。在遇到所有不匹配的字符串時，這個默認動作自動執(zhí)行。另外，如果Lex用戶希望截獲所有輸入而沒有輸出，那么必須提供能夠匹配所有字符的規(guī)則。當在Yacc中使用Lex時，這是一種常見情形。我們可以認為action是忽略輸入是最簡單的事情之一，這僅僅需要使用一條C空語句;["yytext的字符數(shù)組中。因此，打印匹配的名字，可以使用規(guī)則印字符串”（%表示數(shù)據(jù)轉(zhuǎn)換，s表示字符串類型）yytext中的字符。所以這條語句ECHO書寫：有時，獲得匹配字符串的結(jié)束位置是方便的；因此Lexyyleng來計算已經(jīng)[a?zA?Z]+{words++;chars+=獲得。有時，一個Lex動作可能需要處理當規(guī)則沒有能夠正確識別時的字符寬度。兩個例程用nyytext中保留的剩余字符數(shù)。先前已經(jīng)匹配if(yytext[yyleng?1]==￠\\￠)...normaluser}得右面的字符串”def被追加到后面。注意，標志字符串結(jié)束的引號應該在代碼“normal=-printf("Operator(=-)...actionfor=-}它會打印一條信息，返回操作符后的字符到輸入流中。另外，它也可以將其處理為a”。如=-printf("Operator(=-)...actionfor=-}=-=-/[?另外，Lex允許直接使用I/O一；input0以表示文件結(jié)束；unputinput之間的關系必須保留，否則Lex不能完成向前搜索的操作。Lex在不需要的時候不會向前搜索，但是每一個以+*?$結(jié)尾的、或者含參閱下文中有關Lex使用的字符集的討論。默認的Lex100個字符作為備用限制。另一個用戶可以重定義的Lexyywrap()Lex遇到文件結(jié)束符時被調(diào)用。如果yywrap0。這樣Lex才可以繼續(xù)運行。yywrap1。這個例程對于在程序末尾打印表格、yywrapinput()，一個只包含空的文件是不能夠被處理Lex可以處理二義性的說明書。當超過一個表達式可以同時匹配當前輸入時，Lex做出如下選integerkeywordaction[a?z]+identifieractionintegersidentifier因為[a-z]+8個字符而integer7integer7個字符，那么將使用關鍵字規(guī)identifier進行解釋?！痜irst’quotedstringhere,‘second’’first’quotedstringhere,‘second’’is*請注意，Lex通常用于將輸入流分隔開，而不是查找所有滿足表達式的匹配。這意味著每一個Lex規(guī)則可能是he\n 有時候，用戶希望這種選擇。動作REJECT表示“進行下一次選擇?！彼沟卯敭斍耙?guī)則被shehe個數(shù)：she{s++;REJECT;}he{h++;\n he中的REJECT動作；另外，知道哪些輸入字符同時在兩個類中是不必要a[bc]+{...;a[cd]+{...;43accd2通常，當Lex的目的不是分隔輸入流而是查找輸入中的所有項目的實例時，REJECT是有用thethhe。假設一個叫做diagram的二維數(shù)組不斷遞增，適當?shù)脑次?記住Lex{userrulesLex定義變量。變量可以在定義部分或者規(guī)則部分實現(xiàn)。請記住Lex是將規(guī)則轉(zhuǎn)換為一個程序。任何不能被Lex解釋的代任何如下的一行被直接拷貝到Lex生成的程序中：不符合Lex展為生成代碼中的任意函數(shù)；如果緊跟在第一個%%Lex寫成的、包含動作的函數(shù)中的適當位置。此時它更像程序代碼片斷，并且應該在第一條Lex序。這種方法可以被用作在Lex代碼或者生成代碼中添加注釋。注釋必須符合宿主語言的規(guī)1的預處理程序，或者拷貝不像程序的任何在第三個%%Lex輸出，無論它具有什么樣的格Lex中的定義在第一個%%限制符以前。這一部分的任何一行，如果它不在%{和%}之間，并1，那么會被認為是Lex中替換字符的定義。這樣的行的形式如下name它使得作為解釋的字符串被關聯(lián)到name。nametranslation必須至少用一個空白符或者制表符分開。name必須以字母開頭。translation由規(guī)則（rule）中的語法{name}調(diào)用。例如， Fortran35.EQ.I，應該加入一條上下文相關文法型代碼程序調(diào)節(jié)Lex12節(jié)的“代碼格式總結(jié)”中討論。編譯一個Lex源文件程序需要兩步。首先，Lex源程序必須轉(zhuǎn)換為宿主目標語言的程序。然后，這個程序被編譯和加載，通常這一部結(jié)合Lexlex.yy.c中。I/O庫的定義在C標準庫中[6]。Lex生成程序與OS/370標準稍有不同，因為OS編譯器比起UNIXGCOS的編譯器稍遜一GCOS和UNIX上生成的C程序是一樣的。lexsourcecclex.yy.ca.out文件，用于以后的運行。在Yacc中使用Lex的方法見下。盡管Lex默認的I/O例程使用C標準庫，但是Lexinput，outputunput被給定，庫會被省略。如果您想在Yacc中使用Lex，請注意Lexyylex()Yacc分析中需要被使用到。通常，Lex庫中默認的主程序會調(diào)用這個例程，但是如果是使用Yacc加載，并且是它的主程序使用，那么Yaccyylex()Lex規(guī)則應returntoken被返回。一種簡單的獲得Yacctoken名字的方法是將Lex的輸出文件作為Yacc輸出文件的一部分，這通過在Yacc輸入的最后一個部分加入行#include來實現(xiàn)。假設某文法叫做good，而詞則是better，那么Unix中的指令序列如下yaccgoodlexccy.tab.c?ly為了獲得調(diào)用Yacc解析器的主程序，Yacc庫(-ly)Lex庫使用前被加載。Lex和Yacc的73。這里給出一個適當?shù)腖ex源程序int{k=atoi(yytext);if(k%7==0)[0?9]+printf("%d",k+3);}3。為了避免這個，只需要增加一些規(guī)則，比如：int{

k=printf("%d",k%7==0?k+3:} 含有“.”和由字母前導的數(shù)字字符串被后面兩條規(guī)則截獲，并且不會改變。if-else被一條C語言a?b:c的表達式表示“如果a那么bc”。int[a?z]+ {intprintf("LengthNo.words\n");for(i=0;i<100;i++)if(lengs[i]>0)}行最后處理。如果yywrap返回0（錯誤），它表示還有輸入，程序會繼續(xù)、處理。提供yywrap會造成無限循環(huán)。NL.Schryer撰寫，用于將雙精度的Fortran轉(zhuǎn)換為abczW[^""[^正則表達式中，引號括住了空白符。其被解釋為“50 /*convertconstants*/for(p=yytext;*p!=0;p++){if(*p==￠d￠||*p==*p=+￠e￠?}} 41ysecr{a}{t}{a}{n}… jmgiqc4{l}{o}{g}103ety4lv{m}{i}{n}1{1amyrmq{m}{a}{x}1yytext[0]=+‘a(chǎn)’–}dykvya71{m}{a}{c}{h}{yytext[0]=+‘r’– 下面的部分將介紹3種處理不同環(huán)境的方法：在環(huán)境改變時數(shù)規(guī)則改變，此時簡單的使Lex并不參與其中。而令Lex記住該標志以作為規(guī)則的起始狀態(tài)，可能是更方便的。任何一條規(guī)則都可以與一個開始狀態(tài)聯(lián)系。只有當Lex處于開始狀態(tài)時，該條規(guī)則才可以被識別。當前amagicfirstbint {flag=‘a(chǎn)’; {flag=‘b’; {flag=‘c’; {flag=0;{switch{case‘a(chǎn)’:printf("first");magiccase‘b’:printf("second");break;case‘c’:printf("third");break;default:ECHO;break;}}%Startname1name2這是一條只有當Lexname1時才執(zhí)行的規(guī)則。為了進入起始狀態(tài)，執(zhí)行動作語BEGINBEGIN重新初始化Lex%STARTAABB {ECHO;BEGIN {ECHO;BEGIN {ECHO;BEGIN 這里的邏輯與前一種處理問題的方法一樣，但是LexLexinput，outputunput來處理I/O中的字符。因此這些例程中支持的字符能夠被Lexyytext返回。在內(nèi)部，一個字符由一個短整數(shù)表示，如果樣。如果通過提供I/O例程翻譯字符使得翻譯模式改變，那么Lex必須被由給定的轉(zhuǎn)換表通告。這必須在定義部分中，并且必須被只包含“%T”的行包括。表格包含形如{integer}{character28293031390，并且不能用大于硬件字符集的整數(shù)定義字符。一般的Lex{user1．定義，形式為“namespacetranslation”2．被包含的代碼，形式為“spacecode”%Sname1name2...numberspacecharacter-%xnnn是一個十進制整數(shù)，表示數(shù)組的長度。而x是下列參數(shù)之一： 位置positions 狀態(tài)states 樹節(jié)點treenodes 轉(zhuǎn)移transitions 打包的字符類packedcharacterclasses 輸出數(shù)組的長度outputarraysize 字符 符號"x"，即使x 符號"x"，即使x 字符x或者[x?z]字符x、y或者 除了x 在一行開始處的<