編譯器的自動生成工具LEX和YACC的使用方法

1、編譯器的自動生成工具LEX和YACC的使用方法一、 詞法分析程序產(chǎn)生器LEX的用法11 Lex概述Lex是一個詞法分析器（掃描器）的自動產(chǎn)生系統(tǒng)，它的示意圖如圖1.1。Lex源程序是用一種面向問題的語言寫成的。這個語言的核心是正規(guī)表達(dá)式，用它描述輸入串的詞法結(jié)構(gòu)。在這個語言中用戶還可以描述當(dāng)某一個詞形被識別出來時要完成的動作，例如在高級語言的詞法分析器中，當(dāng)識別出一個關(guān)鍵字時，它應(yīng)該向語法分析器返回該關(guān)鍵字的內(nèi)部編碼。Lex并不是一個完整的語言，它只是某種高級語言（稱為lex的宿主語言）的擴(kuò)充，因此lex沒有為描述動作設(shè)計新的語言，而是借助其宿主語言來描述動作。我們只介紹C作為lex的宿主語言

2、時的使用方法，在Unix系統(tǒng)中， FORTRAN語言的一種改進(jìn)形式Ratfor也可以做lex的宿主語言。圖1.1 Lex示意圖   Lex自動地表示把輸入串詞法結(jié)構(gòu)的正規(guī)式及相應(yīng)的動作轉(zhuǎn)換成一個宿主語言的程序，即詞法分析程序，它有一個固定的名字yylex，在這里yylex是一個C語言的程序。yylex將識別出輸入串中的詞形，并且在識別出某詞形時完成指定的動作。 看一個簡單的例子：寫一個lex源程序，將輸入串中的小寫字母轉(zhuǎn)換成相應(yīng)的大寫字母。程序如下：%a-z printf(“%c”,yytext0+'A'-'a')；上述程

3、序中的第一行%是一個分界符，表示識別規(guī)則的開始。第二行就是識別規(guī)則。左邊是識別小寫字母的正規(guī)式。右邊就是識別出小寫字母時采取的動作:將小寫字母轉(zhuǎn)換成相應(yīng)的大寫字母。 Lex的工作原理是將源程序中的正規(guī)式轉(zhuǎn)換成相應(yīng)的確定有限自動機(jī)，而相應(yīng)的動作則插入到y(tǒng)ylex中適當(dāng)?shù)牡胤?，控制流由該確定有限自動機(jī)的解釋器掌握，對于不同的源程序，這個解釋器是相同的。12 lex源程序的格式lex源程序的一般格式是：輔助定義的部分     %     識別規(guī)則部分%      用戶子程

4、序部分其中用花括號起來的各部分都不是必須有的。當(dāng)沒有“用戶子程序部分”時，第二個%也可以省去。第一個%是必須的，因為它標(biāo)志著識別規(guī)則部分的開始，最短的合法的lex源程序是： %  它的作用是將輸入串照原樣抄到輸出文件中。  識別規(guī)則部分是Lex源程序的核心。它是一張表，左邊一列是正規(guī)式，右邊一列是相應(yīng)的動作。下面是一條典型的識別規(guī)則：integer printf（"found keywcrd INT"）;這條規(guī)則的意思是在輸入串中尋找詞形“integer”，每當(dāng)與之匹配成功時，就打印出 “found keyword INT”

5、這句話。注意在識別規(guī)則中，正規(guī)式與動作之間必須用空格分隔開。動作部分如果只是一個簡單的C表達(dá)式，則可以寫在正規(guī)式右邊同一行中，如果動作需要占兩行以上，則須用花括號括起來，否則會出錯。上例也可以寫成：integer printf（"found keyword INT"）; 下面先介紹識別規(guī)則部分的寫法，再介紹其余部分。1.3 Lex用的正規(guī)式一個正規(guī)式表示一個字符串的集合。正規(guī)式由正文字符與正規(guī)式運(yùn)算符組成。正文字符組成基本的正規(guī)式，表示某一個符號串；正規(guī)式運(yùn)算符則將基本的正規(guī)式組合成為復(fù)雜的正規(guī)式，表示字符串的集合。例如：ab僅表示字符串a(chǎn)b，而(a b)+表示字

6、符串的集合：ab，abab，ababab，。Lex中的正規(guī)式運(yùn)算符有下列十六種：     “ - ？ * + | （） / $ % < > 上述運(yùn)算符需要作為正文字符出現(xiàn)在正規(guī)式中時，必須借助于雙引號”或反斜線，具體用法是；xyz“+”或xyz+表示字符串xyz+為避免死記上述十多個運(yùn)算符，建議在使用非數(shù)字或字母字符時都用雙引號或反斜線。要表示雙引號本身可用”，要表示反外線用”或前面說過，在識別規(guī)則中空格表示正規(guī)式的結(jié)束，因此要在正規(guī)式中引進(jìn)空格必須借助雙引號或反斜線，但出現(xiàn)在方括號之內(nèi)的空格是例外。幾個特殊符號：n是回車換行（newline

7、）t是tab b是退格（back space）下面按照運(yùn)算符的功能分別介紹上述正規(guī)式運(yùn)算符。1 字符的集合用方括號對可以表示字符的集合。正規(guī)式 a b c與單個字符a或b或c匹配在方括號中大多數(shù)的運(yùn)算符都不起作用，只有、- 和 例外。運(yùn)算符 - 表示字符的范圍，例如a-z 0-9 _ 表示由所有小寫字母，所有數(shù)字、尖括號及下劃線組成的字符集合。如果某字符集合中包括-在內(nèi)，則必須把它寫在第一個或最后一個位置上，如-+0-9與所有數(shù)字和正負(fù)號匹配。在字符集合中，運(yùn)算符必須寫在第一個位置即緊接在左方括號之后，它的作用是求方括號中除之外的字符組成的字符集合相對于計算機(jī)的字符集的補(bǔ)集

8、，例如abc與除去a、b和c以外的任何符號匹配。運(yùn)算符在方括號中同樣發(fā)揮解除運(yùn)算符作用的功能。2 與任意字符匹配的正規(guī)式 運(yùn)算符形成的正規(guī)式與除回車換行符以外的任意字符匹配。在lex的正規(guī)式中，也可以用八進(jìn)制數(shù)字與一起表示字符，如40-176與ASCII字符集中所有在八進(jìn)制 40（空格）到八進(jìn)制176（）之間的可打印字符匹配。3 可有可無的表達(dá)式運(yùn)算得？指出正規(guī)式中可有可無的子式，例如ab?c與ac或abc匹配，即b是可有可無的。4 閉包運(yùn)算運(yùn)算符*和十是 Lex正規(guī)式中的閉包運(yùn)算符，它們表示正規(guī)式中某子式的重復(fù)，例如a*表示由0個或多個a組成的字符串的集合，而a+表示由1個或多個a

9、組成的字符串的集合，下面兩個正規(guī)式是常用的：a-z+A-Za-zA-Za-z 0-9*第一個是所有由小寫字母組成的字符串的集合，第二個是由字母開頭的字母數(shù)字串組成的集合。5、選擇和字符組運(yùn)算符|表示選擇：（ab|cd）與ab或cd匹配運(yùn)算符（）表示一組字符，注意（）與 的區(qū)別。（ab）表示字符串a(chǎn)b，而ab則表示單個字符a或b。圓括號（）用于表示復(fù)雜的正規(guī)式，例如：（ab|cd+）？（ef）*與abefef, efef, cdef, cddd匹配，但不與abc, abcd或abcdef匹配。6、上下文相關(guān)性lex可以識別一定范圍的上下文，因此可在一定程度上表示上下文相關(guān)性。 

10、0;若某正規(guī)式的第一個字符是，則僅當(dāng)該正規(guī)式出現(xiàn)在一行的開始處時才被匹配，一行的開始處是指整個輸入串的開始或者緊接在一個回車換行之后，注意還有另一個作用即求補(bǔ)，的這兩種用法不可能發(fā)生矛盾。 若某正規(guī)式的最后一個字符是$，則僅當(dāng)該表達(dá)式出現(xiàn)在一行的結(jié)尾處時才被匹配，一行的結(jié)尾處是指該表達(dá)式之后緊接一個回車換行。運(yùn)算符/指出某正規(guī)式是否被匹配取決于它的后文，例如ab/cd僅在ab之后緊接cd的情況下才與ab匹配。$其實是/的一個特殊情形，例如下面兩個正規(guī)式等價：ab$,ab/ n 某正規(guī)式是否被匹配，或者匹配后執(zhí)行什么樣的動作也可能取決于該表達(dá)式的前文，前文相關(guān)性的處理方法在后

11、面專門討論，將用到運(yùn)算符<> 7、重復(fù)和輔助定義當(dāng)被 括起來的是數(shù)字對時， 表示重復(fù)；當(dāng)它括起來的是一個名字時，則表示輔助定義的展開。例如:a1，5表示集合a.aa.aaa.aaaa.aaaaa。digit則與預(yù)先定義的名叫dight的串匹配，并將有定義插入到它在正規(guī)式中出現(xiàn)的位置上，輔助定義在后面專門討論。最后，符號%的作用是作為lex源程序的段間分隔符。14 Lex源程序中的動作 前面說過當(dāng)Lex識別出一個詞形時，要完成相應(yīng)的動作。這一節(jié)敘述Lex為描述動作提供的幫助。首先應(yīng)指出，輸入串中那些不與任何識別規(guī)則中的正規(guī)式匹配的字符串將被原樣照抄到輸出文件中去。因此如果用

12、戶不僅僅是希望照抄輸出，就必須為每一個可能的詞形提供識別規(guī)則，并在其中提供相應(yīng)的動作。用lex為工具寫程序語言的詞法分析器時尤其要注意。最簡單的一種動作是濾掉輸入中的某些字符串，這種動作用C的空語句“；”來實現(xiàn)。例：濾掉輸入串中所有空格、tab和回車換行符，相應(yīng)的識別規(guī)則如下：tn；如果相鄰的幾條規(guī)則的動作都相同，則可以用|表示動作部分，它指出該規(guī)則的動作與下一條規(guī)則的動作相同。例如上倒也可以寫成：“ ”| “t”|“n”；注意t和n中的雙引號可以去掉。外部字符數(shù)組yytext的內(nèi)容是當(dāng)前被某規(guī)則匹配的字符串，例如正規(guī)式a-z+與所有由小寫字母組成的字符串匹配，要想知道與它匹配的具體字符串是什

13、么，可用下述規(guī)則：az printf（“ s”， yytext）;動作printf（“s”，yytext）就是將字符數(shù)組yytext的內(nèi)容打印出來，這個動作用得很頻繁，Lex提供了一個宏ECHO來表示它，因此上述識別規(guī)則可以寫成：az+  ECHO；請注意，上面說過缺省的動作就是將輸入串原樣抄到輸出文件中，那么上述規(guī)則起什么作用呢？這一點(diǎn)將在“規(guī)則的二義性”一節(jié)中解釋。有時有必要知道被匹配的字符串中的字符個數(shù)，外部變量yyleng就表示當(dāng)前yytext中字符的個數(shù)。例如要對輸入串中單詞的個數(shù)和字符的個數(shù)進(jìn)行計數(shù)（單詞假定是由大寫或小寫字母組成的字符串），可用下述規(guī)則：a-z

14、AZ+   words+；Chars+=yyleng；注意被匹配的字符串的第一個字符和最后一個字符分別是yytext0和yytextyyleng-1下面介紹三個Lex提供的在寫動作時可能用到的C函數(shù)lyymore（）當(dāng)需下一次被匹配的字符串被添加在當(dāng)前識別出的字符串后面，即不使下一次的輸入替換yytext中已有的內(nèi)容而是接在它的內(nèi)容之后，必須在當(dāng)前的動作中調(diào)用yymore( )。例：假設(shè)一個語言規(guī)定它的字符串括在兩個雙引號之間，如果某字符串中含有雙引號，則在它前面加上反斜線。用一個正規(guī)式來表達(dá)該字符串的定義很不容易，不如用下面較簡明的正規(guī)式與yymore（）配合來識別：&q

15、uot; "*   if（yytextyyleng1= =yymore( );elsenormal user processing;當(dāng)輸入串為”abc"def”時，上述規(guī)則首先與前五個字符”abc匹配，然后調(diào)用yymore（ ）使余下部分”def被添加在前一部分之后，注意作為字符串結(jié)尾標(biāo)志的那個雙引號由”normal user proessing”部分負(fù)責(zé)處理。2yyless（n）如果當(dāng)前匹配的字符串的末尾部分需要重新處理，那么可以調(diào)用 yyless（n）將這部分子串“退回”給輸入串，下次再匹配處理。yyless(n)中的n是不退回的字符個數(shù)，即退回的字

16、符個數(shù)是yyleng-n。例；在C語言中串“=-a”具有二義性，假定要把它解釋為“=-a”同時給出信息，可用下面的識別規(guī)則：=-a-zA-Z  printf（“Operator（=-）ambiguousn”）；yyless（yyleng-1）;action for-上面的規(guī)則先打印出一條說明出現(xiàn)二義性的信息，將運(yùn)算符后面的字母返回給輸入串，最后將運(yùn)算符按“=”處理另外，如果希望把“=- a”解釋為”- a”，這只需要把負(fù)號與字母一起退回給輸入串等候下次處理，用下面的規(guī)則即可：=-a-zA-Z       

17、          printf（“Operator（=-）               ambiguousn”）；               yyless (yyleng-1);    

18、          action for =                3. yywrap ( )當(dāng)Lex處理到輸入串的文件尾時，自動地調(diào)用yywrap（），如果 yywrap（）返回值是1，那么Lex就認(rèn)為對輸入的處理完全結(jié)束，如果yywrap（）返回的值是0,Lex就認(rèn)為有新的輸入串等待處理。Lex自動提供一個yywrap（），它總是返回1，如果用戶

19、希望有一個返回0的yywrap（ ），那么就可以在”用戶子程序部分”自己寫一個 yywrap（），它將取代Lex自動提供的那個yywrap（），在用戶自己寫的yywrap（）中，用戶還可以作其他的一些希望在輸入文件結(jié)束處要作的動作，如打印表格、輸出統(tǒng)計結(jié)果等，使用yywrap（）的例子在后面舉出。1. 5識別規(guī)則的二義性有時Lex的程序中可能有多于一條規(guī)則與同一個字符串匹配，這就是規(guī)則的二義性，在這種情況下，Lex有兩個處理原則：1） 能匹配最多字符的規(guī)則優(yōu)先;2） 在能匹配相同數(shù)目的字符的規(guī)則中，先給出的規(guī)則優(yōu)先。例：設(shè)有兩規(guī)則按下面次序給出：integer   kegw

20、ord actiona-z+   identifier action如果輸入是integers，則它將被當(dāng)成標(biāo)識符處理，因為規(guī)則integer只能匹配7個字符，而a-z+能匹配8個字符；如果輸入串是integer，那么它將被當(dāng)作關(guān)鍵字處理，因為兩條規(guī)則都能與之匹配，但規(guī)則integer先給出。 1.6 lex源程序中的輔助定義部分Lex源程序的第一部分是輔助定義，到目前為止我們只涉及到怎樣寫第二部分，即識別規(guī)則部分的寫法，現(xiàn)在來看第一部分的寫法。在Lex源程序中，用戶為方便起見，需要一些輔助定義，如用一個名字代表一個復(fù)雜的正規(guī)式。輔助定義必須在第一個之前給出，并且必須從第一

21、列開始寫，輔助定義的語法是：name   translation例如用名字IDENT來代表標(biāo)識符的正規(guī)式的輔助定義為IDENT   a-zA-Za-zA-Z0-9*輔助定義在識別規(guī)則中的使用方式是用運(yùn)算符 將 name括起來，Lex自動地用 translation去替換它，例如上述標(biāo)識符的輔助定義的使用為：IDENT  action for identifer下面我們用輔助定義的手段來寫一段識別FORTRAN語言中整數(shù)和實數(shù)的Lex源程序：D    0一9E    DEde-

22、+？ D+D+   printf（“integer”）；D+"."D*(E)?   |D*"."D+(E)?   |D+E   printf( "real" );請注意在輔助定義部分中可以使用前面的輔助定義。例如：定義E時使用了D，但所用的輔助定義必須是事先已定義過的，不能出現(xiàn)循環(huán)定義。上面的規(guī)則只是說明輔助定義的用法，并不是識別FORTRAN中數(shù)的全部規(guī)則，因為它不能處理類似35.EQI這樣的問題，即會把35.EQI中的35.E當(dāng)作實數(shù)，怎么解決這種問題

23、請讀者思考。除了上面介紹的輔助定義之外，用戶還需要在Lex源程序中使用變量，還需要有一些自己寫的子程序。前面已經(jīng)見過兩個常用的變量即yytext和yylong，也介紹過幾個Lex提供的子程序yymore,yyless和yywrap,現(xiàn)在介紹用戶如何自己定義變量和寫子程序。Lex是把用戶寫的Lex源程序轉(zhuǎn)換成一個C語言的程序yylex，在轉(zhuǎn)換過程中，Lex是把用戶自己的變量定義和子程序照抄到y(tǒng)ylex中去,lex規(guī)定屬于下面三種情況之一的內(nèi)容就照抄過去；1） 以一個空格或tab起頭的行，若不是 Lex的識別規(guī)則的一部分，則被照抄到 Lex產(chǎn)生的程序中去。如果這樣的行出現(xiàn)在第一個之前，它所含的定義

24、就是全局的，即Lex產(chǎn)生的程序中的所有函數(shù)都可使用它。如果這樣的行緊接在第一個之后但在所有識別規(guī)則之前，它們就是局部的，將被抄到涉及它的動作相應(yīng)的代碼中去。注意這些行必須符合C語言的語法，并且必須出現(xiàn)在所有識別規(guī)則之前。這一規(guī)定的一個附帶的作用是使用戶可以為Lex源程序或Lex產(chǎn)生的詞法分析器提供住解，當(dāng)然注解必須符合C語言文法。2） 所有被界于兩行和之間的行，無論出現(xiàn)在哪里也無論是什么內(nèi)容都被照抄過去，要注意 和必須分別單獨(dú)占據(jù)一行例如:#define ENDOFFILE 0#include <head.h>int flag提供上面的措施主要因為在C語言中有一些行如上例中的宏定義

25、或文件蘊(yùn)含行必須從第一列開始寫。3） 出現(xiàn)在第二個之后的任何內(nèi)容，不論其格式如何，均被照抄過去。1.7 怎樣在Unix系統(tǒng)中使用Lex假定已經(jīng)寫好了一個Lex源程序。怎樣在Unix系統(tǒng)中從它得到一個詞法分析器呢？Lex自動地把Lex源程序轉(zhuǎn)換成一個C語言的可運(yùn)行的程序，這個可運(yùn)行的程序放在叫Lex.yy.c的文件中，這個C語言程序再經(jīng)過C編譯，即可運(yùn)行。例，有一名叫source的Lex源程序，第一步用下面的命令將它轉(zhuǎn)換成lex.yy.c：$lex source（$是 Unix的提示符）。Lex.yy.c再用下面的命令編譯即得到可運(yùn)行的目標(biāo)代碼 a.out：$cc lex.yy.c -ll上面的

26、命令行中的-11是調(diào)用Lex的庫，是必須使用的。Lex可以很方便地與Yacc配合使用，這將在下一章中介紹。1.8例子這一節(jié)舉兩個例子看看Lex源程序的寫法。1將輸入串中所有能被7整除的整數(shù)加3，其余部分照原樣輸出，先看下面的Lex源程序：    int k；0-9+  scanf（-1， yytext，“d”，k）;if（k 7 = =0）     printf（“d”，k+3）；else   printf（“ d”, k）;上面的程序還有不足的地方，如對

27、負(fù)整數(shù)，只是將其絕對值加上3，而且象X7,49.63這樣的項也做了修改，下面對上面的源程序稍作修改就避免了這些問題。int k; -?0-9+       scanf（1，yytext，“d”，&k）；     printf（“d”，k7= =0？k+3;k）;-?0-9+   ECHO;A-Za-zA-Za-z0-9+   ECHO;2下一個例子統(tǒng)計輸人串中各種不同長度的單詞的個數(shù)，統(tǒng)計結(jié)果在數(shù)組lengs中,單詞定

28、義為由字母組成的串，源程序如下；int lengs 100;a-z+ lengsyyleng+;|n ;yywrap ( )  int i ；  printf（“Length No.words n”） ;for（i0；i100；i+)  if（lengsi0）     ptintf（“5d 10dn”，i， lengsi）;return (1);在上面的流程序中，當(dāng)Lex讀入輸入串時，它只統(tǒng)計而不輸出，到輸入串讀入完畢后，才在調(diào)用 yywrap（）時輸出統(tǒng)計結(jié)果，為此用戶自己提供了yywrap（

29、），注意yywrap（）的最后一個語句是返回值1。1.9 再談上下文相關(guān)性的處理在3中介紹Lex用的正規(guī)式時提到了上下文相關(guān)性的表示，這里再詳細(xì)介紹Lex提供的處理上下文相關(guān)的措施。要處理的問題是某些規(guī)則在不同的上下文中要采取不同的動作，或者說同樣的字符串在不同的上下文中有不同的解釋。例如在程序設(shè)計語言中，同一個等號“=”，在說明部 分表示為變量賦初值，這時的動作應(yīng)是修改符號表內(nèi)容；而在語句部分等號就是賦值語句的賦值號，這時又應(yīng)該產(chǎn)生相應(yīng)于賦值語句的代碼。因此要依據(jù)等號所處的上下文來判斷它的含義。Lex提供了兩種主要的方法:1）使用標(biāo)志來區(qū)分不同的上下文標(biāo)志是用戶定義的變量，用戶在不同的上下文

30、中為它置不同的值，以區(qū)分它在哪個上下文中，這樣識別規(guī)則就可以根據(jù)標(biāo)志當(dāng)前值決定在哪個上下文中并采取相應(yīng)的動作。例：將輸入串照原樣輸出，但對magic這個詞，當(dāng)它出現(xiàn)在以字母a開頭的行中，將其改為first，出現(xiàn)在以b開頭的行中將其改為second，出現(xiàn)在以c開頭的行中則改為third。使用標(biāo)志flag的Lex源程序如下；int flag ;a   flag='a'ECHO;b   flag='b' ECHO;c   flag='c' ECHO;n   flag=o;

31、ECHO;magic      switch (flag)                    case 'a' : printf (“first”); break;           case 'b': printf (“

32、second”); break;           case 'c' : printf (“third”); break;           default; ECHO; break;               2）使用開始條件來區(qū)分不同

33、上下文在Lex源程序中用戶可以用名字定義不同的開始條件。當(dāng)把某個開始條件立置于某條識別規(guī)則之前時，只有在Lex處于這個開始條件下這條規(guī)則才起使用，否則等于沒有這條規(guī)則。Lex當(dāng)前所處的開始條件可以隨時由用戶程序（即Lex動作）改變。開始條件由用戶在Lex源程序的“輔助定義部分”定義，語法是Start name1 name2 name3其中Start可以縮寫成S或s。開始條件名字的順序可以任意給出，有很多開始條件時也可以由多個Start行來定義它們。開始條件在識別規(guī)則中的使用方法是把它用尖括號括起來放在識別規(guī)則的正規(guī)式左邊:name1expression要進(jìn)入開始條件如Name1，在動作中用語句

34、BEGIN name1它將Lex所處的當(dāng)前開始條件改成 name1。要恢復(fù)正常狀態(tài)，用語句BEGIN 0它將 Lex恢復(fù)到 Lex解釋器的初始條件。一條規(guī)則也可以在幾個開始條件下都起作用，如<name1 ，name2，name3> rule使rule在三個不同的開始條件下都起作用。要使一條規(guī)則在所有開始條件下都起作用，就不在它前面附加任何開始條件。例：解決1）中的問題，這次用開始條件，Lex源程序如下：start     AA BB CCa     ECHO； BEGIN AA；b  

35、;   ECHO； BEGIN BB；c     ECHO； BEGIN CC；n     ECHO； BEGIN 0；AAmagic   printf （“first”） ;BBmagic   Printf（“second”）；CCmagic   Printf（“third”）；1.10 Lex源程序格式總結(jié)為使用方便起見，將Lex源程序的格式，Lex的正規(guī)式的格式等總錄于此。Lex源程序的一般格式為：definitionsrules

36、user subroutines輔助定義部分包括以下項目；1）輔助定義，格式為：    name translation2）直接按照抄的代碼，格式為：    空格   代碼3）直接照抄的代碼，格式為：        代碼    4）開始條件，格式為：   S namel name2還有幾個其他項目，不常使用故略去。識別規(guī)則部分的格式是 &

37、#160;  expression action其中expression必須與action用空格分開，動作如果多于一行，要用花括號括起來。Lex用的正規(guī)式用的運(yùn)算符有以下一些：x     字符x“x”    字符x，若為運(yùn)算符，則不起運(yùn)算符作用x     同上xy     字符x或yx-z     字符x，或y，或zx     除x以外的

38、所有字符.     除回車換行外的所有字符x     出現(xiàn)在一行開始處的xyx     當(dāng) Lex處于開始條件 y時， xX     出現(xiàn)在一行末尾處的xx？     可有可無的 Xx*     0個或多個xx+     1個或多個xx|y     X或y（x） 

39、60;  字符xx/y     字符x但僅當(dāng)其后緊隨y    xx     輔助定義XX的展開x（m,n）    m到n個x二、語法分析程序自動產(chǎn)生器yacc的使用方法2.l yacc概述形式語言都有嚴(yán)格定義的語法結(jié)構(gòu)，我們對它們進(jìn)行處理時首先要分析其語法結(jié)構(gòu)。yacc是一個語法分析程序的自動產(chǎn)生器，嚴(yán)格地說Lex也是一個形式語言的語法分析程序的自動產(chǎn)生器。不過Lex所能處理的語言僅限于正規(guī)語言，而高級語言的詞法結(jié)構(gòu)

40、恰好可用正規(guī)式表示，因此Lex只是一個詞法分析程序的產(chǎn)生器。yacc可以處理能用LALR（1）文法表示的上下文無關(guān)語言。而且我們將會看到y(tǒng)acc具有一定的解決語法的二義性的功能。yacc的用途很廣，但主要用于程序設(shè)計語言的編譯程序的自動構(gòu)造上。例如可移植的C語言的編譯程序就是用yacc來寫的。還有許多數(shù)據(jù)庫查詢語言是用yacc實現(xiàn)的。因此，yacc又叫做“編譯程序的編譯程序（"A Compiler ComPiler"）。yacc的工作示意圖如下； 圖2.1 yacc示意圖在圖2.1中，“yacc源程序”是用戶用yacc提供的一種類似BNF的語言寫的要處理的語言的語法描述。y

41、acc會自動地將這個源程序轉(zhuǎn)換成用LR方法進(jìn)行語法分析的語法分析程序yyparse，同Lex一樣，yacc的宿主語言也是C，因此yyparse是一個C語言的程序，用戶在主程序中通過調(diào)用yyparse進(jìn)行語法分析。語法分析必須建立在詞法分析的基礎(chǔ)之上，所以生成的語法分析程序還需要有一個詞法分析程序與它配合工作。yyparse要求這個詞法分析程序的名字為yylex。用戶寫yylex時可以借助于Lex。因為Lex產(chǎn)生的詞法分析程序的名字正好是yylex，所以 Lex與yacc配合使用是很方便的，這將在2.5的2.5.3中詳細(xì)介紹，請注意詞法分析程序也是可以包含在yacc源程序中的。在yacc源程序中

42、除了語法規(guī)則外，還要包括當(dāng)這些語法規(guī)則被識別出來時，即用它們進(jìn)行歸約時要完成的語義動作，語義動作是用C語言寫的程序段。語法分析的輸出可能是一棵語法樹，或生成的目標(biāo)代碼，或者就是關(guān)于輸入串是否符合語法的信息。需要什么樣的輸出都是由語義動作和程序部分的程序段來實現(xiàn)的。下面分節(jié)介紹yacc源程序的寫法以及在Unix系統(tǒng)中使用yacc的有關(guān)命令。2.2 yacc源程序的一般格式一個yacc源程序一般包括三部分：說明部分；語法規(guī)則部分；程序段部分，這三部分內(nèi)容依次按下面的格式組織在一起：說明部分語法規(guī)則部分程序段部分上述三部分中說明部分和程序段部分不必要時可省去，當(dāng)沒有程序段部分時，第二個也可以省去。但

43、是第一個是必須有的。下面詳細(xì)介紹各部分的組成及寫法。2.3 yacc源程序說明部分的寫法yacc源程序的說明部分定義語法規(guī)則中要用的終結(jié)符號，語義動作中使用的數(shù)據(jù)類型、變量、語義值的聯(lián)合類型以及語法規(guī)則中運(yùn)算符的優(yōu)先級等。這些內(nèi)容的組織方式如下：頭文件表宏定義數(shù)據(jù)類型定義全局變量定義語法開始符定義語義值類型定義終結(jié)符定義運(yùn)算符優(yōu)先級及結(jié)合性定義2.3.1 頭文件表yacc直接把這部分定義抄到所生成的C語言程序y.tab.c中去的，所以要按C語言的語法規(guī)定來寫。頭文件表是一系列C語言的include語句，要從每行的第一列開始寫，例如：includestdio.hinclude math.hinc

44、ludectype.h#include “header.h”.2.3.2 宏定義這部分用C語言的 define語句定義程序中要用的宏。例如. define EOF Odefine max（x,y）（xy）？x:y）. 2.3.3 數(shù)據(jù)類型定義這部分定義語義動作中或程序段部分中要用到的數(shù)據(jù)類型，例如：. typedef struct interval             double lo， hi；    INTERVAL；.2.3.

45、4 全局變量定義外部變量（external variable）和yacc源程序中要用到的全局變量都在這部分定義，例如：.extern int nfg;douhle dreg 26；INTERVAL Vreg26；.另外非整型函數(shù)的類型聲明也包含在這部分中，請參看2.6例2。重申一遍，上述四部分括在 和之間的內(nèi)容是由yacc原樣照抄到y(tǒng).tab.c中去，所以必須完全符合C語言文法，另外，界符和最好各自獨(dú)占一行，即最好不寫成% int x; %2.3.5 語法開始符定義上下文無關(guān)文法的開始符號是一個特殊的非終結(jié)符，所有的推導(dǎo)都從這個非終結(jié)符開始，在yacc中，語法開始符定義語句是：% start

46、  非終結(jié)符如果沒有上面的說明，yacc自動將語法規(guī)則部分中第一條語法規(guī)則左部的非終結(jié)符作為語法開始符。2.3.6語義值類型定義yycc生成的語法分析程序yyparse用的是LR分析方法，它在作語法分析時除了有一個狀態(tài)棧外，還有一個語義值棧，存放它所分析到的非經(jīng)結(jié)符和終結(jié)符的語義值，這些語義值有的是從詞法分析程序傳回的，有的是在語義動作中賦與的，這些在介紹語義動作時再詳細(xì)說明。如果沒有對語義值的類型做定義，那么yacc認(rèn)為它是整型（int）的，即所有語法符號如果賦與了語義值，則必須是整型的，否則會出類型錯，但是用戶經(jīng)常會希望語義值的類型比較復(fù)雜，如雙精度浮點(diǎn)數(shù)，字符串或樹結(jié)

47、點(diǎn)的指針。這時就可以用語義值類型定義進(jìn)行說明。因為不同的語法符號的語義值類型可能不同，所以語義值類型說明就是將語義值的類型定義為一個聯(lián)合（Union），這個聯(lián)合包括所有可能用到的類型（各自對應(yīng)一個成員名），為了使用戶不必在存取語義值時每次都指出成員名，在語義值類型定義部分還要求用戶說明每一個語法符號（終結(jié)符和非終結(jié)符）的語義值是哪一個聯(lián)合成員類型。下面舉例說明并請參看2.6例2。 union        int ival        

48、;double dval        INTERVAL VVal;        token ival DREG VREGtoken dval CONSTtype  dyaldexptype  vvalvexP在上述定義中，以union開始的行定義了語義值的聯(lián)合類型，共有三個成員類型分別取名為ival, dval, vval。以token開始的行定義的是終結(jié)符（見2.3.7）所以DREG,VREG和CONST都是終

49、結(jié)符，尖括號中的名字就是這些終結(jié)符的語義值的具體類型。如DREG和VREG這兩個終結(jié)符的語義值將是整型（int）的，成員名是ival。以tyPe開始的行是說明非終結(jié)符語義值的類型。如非終結(jié)符dexP的語義值將是雙精度浮點(diǎn)類型，請注意，在yacc中非終結(jié)符不必特別聲明，但是當(dāng)說明部分有對語義值類型的定義，而且某非終結(jié)符的語義值將被存取，就必須用上面的方法定義它的類型。2.3.7 終結(jié)符定義在yacc源程序語法規(guī)則部分出現(xiàn)的所有終結(jié)符（文字字符literal除外）必須在這部分定義，定義方法如下例： token DIGIT LETTER每個終結(jié)符定義行以token開頭，注意與token之間沒有空格，

50、一行中可以定義多個終結(jié)符，它們之間用空格分開，終結(jié)符名可以由字母，數(shù)字，下劃線組成，但必須用字母開頭。非終結(jié)符名的組成規(guī)則與此相同。終結(jié)符定義行可多于一個。yacc規(guī)定每個終結(jié)符都有一個唯一的編號（token number）。當(dāng)我們用上面的方式定義終結(jié)符時，終結(jié)符的編號由yacc內(nèi)部決定，其編號規(guī)則是從257開始依次遞增，每次加1.但這個規(guī)則不適用于文字字符（literal）的終結(jié)符。例如在下面的語法規(guī)則中，；'就是文字字符終結(jié)符:stats： stats'；' stat；expr: expr'+' expr;文字字符終結(jié)符在規(guī)則中出現(xiàn)時用單引號括起來。

51、它們不需要用token語句定義，yacc對它們的編號就采用該字符在其字符集（如ASCII）中的值。注意上面兩條語法規(guī)則末尾的分號是yacc元語言的標(biāo)點(diǎn)符號，不是文字字符終結(jié)符。yacc也允許用戶自己定義終結(jié)符的編號。如果這樣，那么終結(jié)符定義的格式就是：token終結(jié)符名   整數(shù)其中“終結(jié)符名”就是要定義的終結(jié)符，“整數(shù)”就是該終結(jié)符的編號，每一個這樣的行定義一個終結(jié)符。特別注意不同終結(jié)符的編號不能相同。例如%token BEGIN     100token END     101%token

52、IF     105token THEN     200.在3.6中我們說過如果用戶定義了語義值的類型，那么那些具有有意義的語義值的終結(jié)符其語義值的類型要用Union中的成員名來說明，除了在3.6段中介紹的定義方法外，還可以把對終結(jié)符的定義和其語義值的類型說明分開，例如%token DREG VREG CONSTtype ival DREG VREGtype dval CONST2.3.8運(yùn)算符優(yōu)先級及結(jié)合性定義請看下面的關(guān)于表達(dá)式的文法：%token NAMEexpr: expr'+' expr&

53、#160;   |expr '' expr    |expr'*'expr    |NAME     這個文法有二義性，例如句子abc可以解釋成（a b）一 c也可以解譯成 a（b c），雖然這兩種解釋都合理但造成了二義性，如果將句子ab*C解釋為（ab）*c就在語義上錯了。yacc允許用戶規(guī)定運(yùn)算符的優(yōu)先級和結(jié)合性，這樣就可以消除上述文法的二義性。例如規(guī)定”'具有相同的優(yōu)先級，而且都是左結(jié)合的，

54、這樣。abc就唯一地解釋為( a b)一 c。再規(guī)定'*'的優(yōu)先級大于”，則 a b* c就正確地解釋為 a（b*c） 了，因此上述文法的正確形式應(yīng)是token NAMEleft '+''-left '*' expr：expr'+ expr    |expr'- exPr    |expr'* expr    |NAME     在說明部分中以le

55、ft開頭的行就是定義算符的結(jié)合性的行。left表示其后的算符是遵循左結(jié)合的；right表示右結(jié)合性，而nonassoc則表示其后的算符沒有結(jié)合性。優(yōu)先級是隱含的，在說明部分中，排在前面行的算符較后面行的算符的優(yōu)先級低；排在同一行的算符優(yōu)先級相同，因此在上述文法中，和一優(yōu)先級相同，而它們的優(yōu)先級都小于'*，三個其符都是左結(jié)合的。在表達(dá)式中有時要用到一元運(yùn)算符，而且它可能與某個二元運(yùn)算符是同一個符號，例如一元運(yùn)算符負(fù)號“-”就與減號-相同，顯然一元運(yùn)算符的優(yōu)先級應(yīng)該比相應(yīng)的二元運(yùn)算符的優(yōu)先級高。至少應(yīng)該與*'的優(yōu)先級相同，這可以用yacc的prec子句來定義，請看下面的文法：tok

56、en NAMEleft '-''+left '*'''expr:expr'+' expr    |expr'+' expr    |expr'-expr    |expr'*' expr    |expr' expr    |'-'expr prec'*&

57、#39;    |NAME     在上述文法中，為使一元的優(yōu)先級與*相同，我們使用了子句prec*它說明它所在的語法規(guī)則中最右邊的運(yùn)算符或終結(jié)符的優(yōu)先級與prec后面的符號的優(yōu)先級相同，注意prec子句必須出現(xiàn)在某語法規(guī)則結(jié)尾處分號之前，prec子句并不改變作為二元運(yùn)算符時的優(yōu)先級。上面介紹的八項定義，沒有必要的部分都可以省去。2.4. yacc源程序中語法規(guī)則部分的寫法語法規(guī)則部分是yacc源程序的核心部分，這一部分定義了要處理的語言的語法及要采用的語義動作。下面介紹語法規(guī)則的書寫格式、語義動作的寫法

58、以及yacc解決二義性和沖突的具體措施。最后介紹錯誤處理。2.4.1語法規(guī)則的書寫格式每條語法規(guī)則包括一個左部和一個右部，左右部之間用冒號:來分隔，規(guī)則結(jié)尾處要用分號”;”標(biāo)記，所以一條語法規(guī)則的格式如下：nonterminal : BODY；或nonterminal：BODY其中nonterminal是一個非終結(jié)符，右部的BODY是一個由終結(jié)符和非終結(jié)符組成的串、可以為空，請看幾個例子：stat: WHILE bexp DO Stat    stat: IF bexp THEN stat    stat：/* e

59、mpty*    上面的第三條語法規(guī)則的右部為空，用*和*括起來的部分是注解?？梢园炎蟛糠墙K結(jié)符相同的語法規(guī)則集中在一起，規(guī)則間用短線|分隔，最后一條規(guī)則之后才用分號，例如：stat： WHILE bexp DO stat    | IF bexp THEN stat    |* empty*    對語法規(guī)則部分的書寫有幾條建議：1. 用小寫字母串表示非終結(jié)符，用大寫字母串表示終結(jié)符。2將左部相同的產(chǎn)生式集中在一起，象上例一樣。3各條

60、規(guī)則的右部盡量對齊，例如都從第一個tab處開始。按這樣的風(fēng)格寫yacc源程序清晰可讀性強(qiáng)而且易修改和檢查錯誤。4如果產(chǎn)生式（語法規(guī)則）需要遞歸，盡可能使用左遞歸方式例如：seq: item        | seq', item    因為用左遞歸方式可以使語法分析器盡可能早地進(jìn)行歸約，不致使?fàn)顟B(tài)棧溢出。2.4.2 語義動作當(dāng)語法分析程序識別出某個句型時，它即用相應(yīng)的語法規(guī)則進(jìn)行歸約，yscc在進(jìn)行歸約之前，先完成用戶提供的語義動作，這些語義動作可以是返回語法符號的語

61、義值，也可以是求某些語法符號的語義值，或者是其他適當(dāng)?shù)膭幼魅缃⒄Z法樹，產(chǎn)生目標(biāo)代瑪，打印有關(guān)信息等。終結(jié)符的語義值是通過詞法分析程序返回的，這個值由全局變量（yacc自動定義的）yylval帶回，如果用戶在詞法分析程序識別出某終結(jié)符時，給yylval賦與相應(yīng)的值，這個值就自動地作為該終結(jié)符的語義值。當(dāng)語義值的類型不是int時，要注意yylval的值的類型須與相應(yīng)的終結(jié)符的語義值類型一致。語義動作是用C語言的語句寫成的，跟在相應(yīng)的語法規(guī)則后面，用花括號括起來。例如：A：'('B')'    hello（l，“abc”）；X

62、XX：YYY ZZZ     printf（“a messagen”）；      flag25；      要存取語法符號的語義值，用戶要在語義動作中使用以開頭的偽變量，這些偽變量是yacc內(nèi)部提供的，用戶不用定義。偽變量代表產(chǎn)生式左部非終結(jié)符的語義值，產(chǎn)生式右部各語法符號的語義值按從左到右的次序為1， 2，。例如在下面的產(chǎn)生式中：A :B C D;A的語義值為，B、C、D的語義值依次為 1，2，3。為說明偽變量的作用，請看下例，有產(chǎn)

63、生式expr:'('expr')'    左的邊的exPr的值應(yīng)該等于右連的expr的值，表示這個要求的語義動作為，expr: '('expr')'        $=$2;     如果在產(chǎn)生式后面的語義動作中沒有為偽變量賦值， yaCC自動把它置為產(chǎn)生式右部第一個語法符號的值（即1）。在較復(fù)雜的應(yīng)用中，往往需要在產(chǎn)生式右部的語法符號之間插入語義動作這意味著使語法分析器在

64、識別出句型的一部分時就完成這些動作。請看下例：A：B        1；   C   X=$2; y=$3; 例中x 的值最后為1而y的值置為符號C的語義值，注意B后面的語義動作1并非將符號A的語義值置為1，這是因為上面的例子是按下面的方式實現(xiàn)的。ACT：*empty。   1；    A：BACTC  X2；y=$3；   &

65、#160; ；即 yacc自動設(shè)置一個非終結(jié)符 ACT及一個空產(chǎn)生式用以完成上述語義動作。關(guān)于語義動作的實例請讀者詳細(xì)閱讀6中的兩個例子。2.4.3 yacc解決二義性和沖突的方法在2.3.8中已涉及到二義性和沖突的問題，這里再集中介紹一下，這在寫Yacc源程序時會經(jīng)常碰到。二義性會帶來沖突。在2.3.8中我們介紹了yacc可以用為算符確定優(yōu)先級和結(jié)合規(guī)則解決由二義性造成的沖突，但是有一些由二義性造成的沖突不易通過優(yōu)先級方法解決，如有名的例子：stat：IF bexp THEN stat    |IF bexp THEN stat &

66、#160;  ELSE stat;對于這樣的二義性造成的沖突和一些不是由二義性造成的沖突，Yacc提供了下面兩條消除二義性的規(guī)則：A1出現(xiàn)移進(jìn)歸約沖突時，進(jìn)行移進(jìn)；A2. 出現(xiàn)歸約歸約沖突時，按照產(chǎn)生式在yacc源程序中出現(xiàn)的次序，用先出現(xiàn)的產(chǎn)生式歸約。我們可以看出用這兩條規(guī)則解決上面的IF語句二義性問題是合乎我們需要的。所以用戶不必將上述文法改造成無二義性的。當(dāng)Yacc用上述兩條規(guī)則消除了二義性，它將給出相應(yīng)信息。下面再稍微嚴(yán)格地介紹一下Yacc如何利用優(yōu)先級和結(jié)合性來解決沖突的。Yacc源程序中的產(chǎn)生式也有一個優(yōu)先級和結(jié)合性這個優(yōu)先級和結(jié)合性就是該產(chǎn)生式右部最后一個終結(jié)

67、符或文字字符的優(yōu)先級和結(jié)合性，當(dāng)使用了Prec子句時，該產(chǎn)生式的優(yōu)先級和結(jié)合性由Prec子句決定。當(dāng)然如果產(chǎn)生式右部最后一個終結(jié)符或文字字符沒有優(yōu)先級或結(jié)合性，則該產(chǎn)生式也沒有優(yōu)先級或結(jié)合性。根據(jù)終結(jié)符（或文字字符）和產(chǎn)生式的優(yōu)先級和結(jié)合性，Yacc又有兩個解決沖突的規(guī)則：P1. 當(dāng)出現(xiàn)移進(jìn)/歸約沖突或歸約歸約沖突，而當(dāng)時輸入符號和語法規(guī)則（產(chǎn)生式）均沒有優(yōu)先級和結(jié)合性，就用 AI和A2來解決這些沖突。P2當(dāng)出現(xiàn)移進(jìn)歸約沖突時，如果輸入符號和語法規(guī)則都有優(yōu)先級和結(jié)合性，那么如果輸入符號的優(yōu)先級大于產(chǎn)生式的優(yōu)先級就移進(jìn)如果輸入符號的優(yōu)先級小于產(chǎn)生式的優(yōu)先級就歸約。如果二者優(yōu)先級相等，則由結(jié)合性決定動作，左結(jié)合則歸約，右結(jié)合則移進(jìn)，無結(jié)合性則出錯。用優(yōu)先級和結(jié)合性能解決的沖突，yacc不報告給用戶。2.4.4 語法分析中的錯誤處理當(dāng)進(jìn)行語法分析時發(fā)現(xiàn)輸入串有語法錯誤，最好能在報告出錯信息以后繼續(xù)進(jìn)行語法分析，以便發(fā)現(xiàn)更多的錯誤。yacc處理錯誤的方法是：當(dāng)發(fā)現(xiàn)語法錯誤時，yacc丟掉那些導(dǎo)致