語法分析程序的自動生成工具

1、5.10 語法分析程序的自動生成工具迄今為止，讀者已經(jīng)學(xué)習(xí)了語法分析和語義翻譯的基本知識。從理論上講，對于常見的程序設(shè)計語言的語法結(jié)構(gòu)，我們已能構(gòu)造相應(yīng)的處理程序，以完成語法分析和語義翻譯工作。本節(jié)，我們將介紹幾種語法分析器的自動生成工具，這些工具可將用戶輸入的文法自動轉(zhuǎn)換成LL或LR語法分析程序，除此之外，它們還允許用戶在產(chǎn)生式中插入語義處理動作 (語義子程序)，并在分析程序中的適當(dāng)位置安排調(diào)用語義子程序的代碼。目前，這些工具已在許多領(lǐng)域的軟件系統(tǒng)研制過程中得到廣泛的使用。5.10.1 LALR(1)分析器的自動生成工具YACC和OCCSYACC (Yet Another CompilerC

2、ompiler)是LALR(1)分析器的自動生成工具，它的第1版于70年代初發(fā)表，是美國貝爾實驗室的軟件產(chǎn)品 (作者為S.C.Johnson)。這個工具目前在UNIX，DOS等系統(tǒng)平臺上廣泛流行。OCCS (Other Compiler Compiler System)是由A.I.Holub開發(fā)的與YACC類似的工具28。與YACC不同的是，OCCS給用戶提供了一個功能較為完善，基于窗口的調(diào)試系統(tǒng)yydebug.c，此調(diào)試系統(tǒng)能使用戶實際觀察分析動作中的處理過程和分析棧的變化情況，以及根據(jù)不同的棧狀態(tài)及指定的輸入符號設(shè)置斷點等等。此外，OCCS比YACC有更完善的錯誤診斷機(jī)制，其輸出的代碼也比

3、YACC有更好的可維護(hù)性。不過，二者的用法基本相同，本節(jié)主要介紹國內(nèi)十分流行的YACC的用法，對于OCCS所特有的功能，則只作簡要的說明。使用YACC構(gòu)造語法分析程序非常簡便，它要求用戶按一定規(guī)則編寫出“文法處理說明文件”，簡稱YSP (Yacc SPecification)文件，文件的擴(kuò)展名為“.y”。當(dāng)輸入YSP文件時，YACC就會自動構(gòu)造出相應(yīng)的C語言形式的語法分析器。該分析器主要包括由YACC提供的標(biāo)準(zhǔn)總控程序和一個LALR(1)語法分析表。其使用過程如圖5 13所示。在DOS系統(tǒng)下，使用YACC的格式為：YACC選擇項filename.y此命令根據(jù)用戶輸入的名為filename.y的

4、YSP文件，使YACC自動生成相應(yīng)的C語言形式的語法分析器源文件ytab.c (有的YACC系統(tǒng)生成的文件名為y.tab.c)。然后。用戶可在C環(huán)境下將其編譯成可執(zhí)行文件。其工作過程如圖5 14所示。    一、 YSP文件的結(jié)構(gòu)一個完整的YSP文件由說明、規(guī)則、程序三個部分組成，各部分之間以雙百分號“%”隔開：說明部分%規(guī)則部分%程序部分其中，用方括號括起來的說明部分和程序部分可以空缺，但規(guī)則部分則是必須的。因此，YSP文件的最簡形式是：%規(guī)則部分首先，我們以一個簡單臺式計算器中的處理程序的自動生成為例，說明怎樣編寫YSP文件。該計算器的功能為：讀入一行算術(shù)表達(dá)

5、式，然后計算并打印它的值。算術(shù)表達(dá)式的文法如下：Expr Expr + Term | TermTerm Term * Factor | FactorFactor ( Expr ) | digit其中，終結(jié)符號digit是09中的任何一個數(shù)字。該文法的YSP文件可編寫如下：%/*說明部分*/#include <stdio.h>#include <ctype.h>%tokendigit300%/*規(guī)則部分*/Line:Expr nprintf("%dn",$1);/*打印表達(dá)式值*/;Expr:Expr + Term $=$1+$3;/*Expr=Exp

6、r+Term*/|Term/*Expr=Term*/;Term:Term * Factor $=$1*$3;/*Term=Term*Factor*/|Factor/*Term=Factor*/;Factor:( Expr )$=$2;/*Factor=Expr*/|digit/*Factor=digit的屬性值*/;%/*程序部分*/int yylex(void)/*詞法分析程序*/int c;c=getchar( );/*讀入一個字符*/if(isdigit(c)/*判別c是否為數(shù)字*/yylval=c-0;return digit;return c;void yyerror( )/*出錯處

7、理程序*/printf("Syntax errorn");void main( )yyparse( );/*調(diào)用語法分析程序*/下面分別論述YSP文件各部分的組成規(guī)則。    二、 YSP說明部分的組成YSP文件中的說明部分用于定義規(guī)則部分所使用的變量及語法符號。它可以包含以下幾類信息。1變量定義變量定義需要用一對特殊括號“%”和“%”括起來，其內(nèi)容包括規(guī)則部分中的語義動作及程序部分所需使用的有關(guān)文件 (如C語言的有關(guān)頭文件)的引用說明、數(shù)據(jù)結(jié)構(gòu)的定義、全局和外部變量的定義以及函數(shù)原型的定義等等，這部分內(nèi)容應(yīng)遵守C語言的規(guī)定。例如：%#incl

8、ude <stdio.h>.int count;extern double value;.int addedfunction(int a,float b);.%2. 開始符號定義文法的開始符號由說明符號%start指明(請注意，YACC中的所有說明符號均由“%”引出)，例如：%startStartSymbol指明StartSymbol為文法開始符號。若未給出開始符號的定義，則系統(tǒng)將自動以第1條語法規(guī)則的左部符號作為開始符號。例如，前面所給出的YSP文件例子中，就沒有給出開始符號的定義，所以，系統(tǒng)將認(rèn)為非終結(jié)符號Line是開始符號。3. 詞匯表定義在這部分，用戶可以給出終結(jié)符號表、聯(lián)

9、合 (union)和類型 (type)說明。YACC要求所用到的所有文字形式的終結(jié)符號都應(yīng)明確加以說明；對于未說明者，則均按非終結(jié)符號處理。終結(jié)符號說明由說明符號%token或%term引出，其書寫格式有兩種。第1種書寫格式為%tokenTname1 Tname2 .各個終結(jié)符號之間用空格分隔。在一行寫不下時，可用%token另起一行繼續(xù)定義。在前例中，僅說明了一個終結(jié)符號digit。第2種書寫格式允許用戶自行定義終結(jié)符號的內(nèi)部編碼值，其格式為：%tokenTname <integer>其中，<integer>應(yīng)為大于256的整數(shù)。前例中的digit就是采用這種格式定義

10、的，其內(nèi)部碼為300。當(dāng)用戶未給出終結(jié)符號的內(nèi)部碼時，系統(tǒng)將按終結(jié)符號的出現(xiàn)順序，從257開始，依次為其定義內(nèi)部碼值：257，258，。 YACC內(nèi)部約定，當(dāng)詞法分析程序從輸入字符串中識別出一個終結(jié)符號時，將返回該終結(jié)符號的內(nèi)部碼值。還需指出，除文字型的終結(jié)符號外，對于程序設(shè)計語言中的單字符運(yùn)算符、分隔符等終結(jié)符號，可在文法中用單引號括起來直接使用，不必用%token定義，其內(nèi)部碼值就是它的ASCII碼 (其值將不會大于256，這也是用戶自定義的終結(jié)符號內(nèi)部碼之值不能小于257的原因)。在詞匯表定義中，還可以通過使用聯(lián)合 (%Union)和類型說明 (%type)，對每個文法符號定義其語義屬性

11、應(yīng)具有的數(shù)據(jù)類型。例如，假定非終結(jié)符號A具有屬性attra，其值為整型；非終結(jié)符號B具有兩個屬性b1和b2，其中b1為整數(shù)，b2為實數(shù)；則可用聯(lián)合說明告訴YACC，文法符號具有兩種類型：%Unionint attra;structint b1;float b2; attrb然后再用%type說明非終結(jié)符號A和B所具有的類型：%type <attra>A%type <attrb>B其中，尖括號<>中的名字是聯(lián)合定義中的成員。一般說來，若使用了聯(lián)合定義，則須用類型說明(%type)對每個文法符號的數(shù)據(jù)類型進(jìn)行定義 (每個符號有且僅有一種類型)，否則，YACC將會

12、報錯。使用上述方式，允許在一行中定義多個文法符號，只需用空格將其隔開即可，若在一行寫不下時，則需另起一行后重新用%type命令繼續(xù)定義。若在說明部分未用聯(lián)合進(jìn)行說明，則YACC自動使用缺省類型。YACC約定，每個文法符號的缺省類型均為整型。4優(yōu)先級與結(jié)合性定義為了能夠解決文法中出現(xiàn)的一些二義性和部分語法分析沖突，YACC提供了定義優(yōu)先級和結(jié)合性等手段。在后面我們將對此進(jìn)行詳述。    三、 YSP文件語法規(guī)則部分的組成語法規(guī)則部分是整個YSP文件的主體，它由文法的一組產(chǎn)生式及每一產(chǎn)生式相應(yīng)的語義動作組成。對于文法中的每個產(chǎn)生式A1 | 2 | n在YSP文件中將相

13、應(yīng)地寫成：A ：1語義動作1；| 2語義動作2；.| n語義動作n；其中，A為產(chǎn)生式左部非終結(jié)符號，冒號“：”是產(chǎn)生式左部與右部的分界符 (相當(dāng)于“” )，對于未在說明部分說明過的文字終結(jié)符號需要用單引號括起來。每個產(chǎn)生式必須用分號“；”作為結(jié)束標(biāo)志 (注意，若分號是產(chǎn)生式右部中的終結(jié)符號時，需用單引號括起來)。對于一個產(chǎn)生式左部非終結(jié)符號的每個候選式，用戶都可以用C語言為其編寫一段相關(guān)的語義處理程序，它們需用花括號 括起來。在生成語法分析程序時，YACC將自動把它們嵌入到LALR分析表相應(yīng)的位置。爾后進(jìn)行語法分析時，當(dāng)按某非終結(jié)符號的候選式歸約句柄時，就自動執(zhí)行相應(yīng)的語義處理程序。為了與語法

14、分析有機(jī)地結(jié)合，在語義處理程序中往往需要使用YACC提供的偽變量來表示產(chǎn)生式中相應(yīng)文法符號的語義動作返回值。YACC約定，產(chǎn)生式左部符號的屬性值用$表示，而右部第k個符號的屬性值用$k表示 (事實上，這種格式我們已在前面的章節(jié)中多次見到了)。例如，對于產(chǎn)生式ExprExpr+Term|Term在YSP文件中將相應(yīng)地寫成：Expr: Expr + Term $=$1+$3;| Term;它表示按第1個候選式歸約時，左部符號Expr的屬性值為該產(chǎn)生式右部第一符號Expr與第三符號Term的屬性值之和；按第2個產(chǎn)生式歸約時，由于語義動作缺省，YACC自動按$=$1；處理 (不論右部有多少符號)。最后

15、需指出，當(dāng)候選式為時，將不寫任何符號，例如，將寫成 A：動作，若動作缺省，系統(tǒng)將仍執(zhí)行動作$=$1，只是此時$1所代表的是按A歸約之前棧頂符號的屬性。    四、 YSP文件程序部分的組成YSP文件的程序部分是可選的。它由例行C語言程序 (函數(shù))組成，主要包括主程序main( )、詞法分析子程序yylex( )、出錯處理子程序yyerror( )、語法規(guī)則部分語義動作中所調(diào)用的用戶自定義函數(shù)以及其它輔助函數(shù)等等。下面對它們的格式、功能和用法作概括地說明。(1) YACC在處理YSP文件之后，將輸出一個名為y.tab.c的C程序文件，此文件含有名為yyparse(

16、)的語法分析程序 (函數(shù))。主程序main( )的主要作用，在于調(diào)用函數(shù)yypase( )對源程序進(jìn)行語法分析。當(dāng)語法分析成功結(jié)束時，yyparse( )返回值為0；而在發(fā)現(xiàn)源程序有語法錯誤時，除返回值為1外，它還調(diào)用yyerror( )函數(shù)輸出出錯信息。函數(shù)main( )和yyerror( )可由YACC庫提供 (只需在編譯命令行中加入選擇項ly即可)，其格式分別為main( )return (yyparse( )；及#include stdio.hyyerror(s)char*s；fprintf(stderr,"%sn",s);如果用戶認(rèn)為上述函數(shù)的功能不滿足要求，例如

17、還需要在主程序中做其它的輔助處理，或需要yyerror輸出更詳細(xì)的出錯信息，也可以自行編寫這兩個函數(shù)。但須注意，在main( )函數(shù)中至少要有一條調(diào)用yyparse( )函數(shù)的語句。(2) YACC系統(tǒng)規(guī)定，在語法分析程序yyparse( )運(yùn)行時，須有一個名為yylex( )的詞法分析程序?qū)ζ渲С?。每?dāng)yyparse( )調(diào)用yylex( )時，yylex( )就從輸入字符流中識別出一個單詞，并將該單詞的內(nèi)部碼及其語義值 (若有的話)分別通過return語句及全局變量yylval回送給yyparse( )。可見，yyparse( )的輸入來源于yylex( )的返回信息。詞法分析程序需由用戶

18、提供。它可由用戶手工編寫或通過LEX工具自動生成。由LEX生成的詞法分析程序包含在文件lex.yy.c中，LEX為其確定的名字正好也是yylex( )。為了使yyparse( )能使用LEX所生成的yylex( )函數(shù)，最簡便的方法是在YSP文件的程序部分寫上一條形如#include "lex.yy.c"的語句即可。在YSP文件中，整個程序部分都可缺省。用戶可將所需的程序 (函數(shù))在某個C文件中進(jìn)行定義，再將它與YACC生成的y.tab.c文件編譯、連接在一起即可。聯(lián)合使用LEX和YACC來自動生成語法分析器的處理流程如圖5 15所示。設(shè)用戶已準(zhǔn)備好的LEX源文件和YSP文

19、件分別為scanner.l和parser.y，并假定main( )和yyerror( )由YACC庫提供，則在UNIX環(huán)境下依次執(zhí)行下列三條命令：lex scanner.l/* 生成含有yylex( )的lex.yy.c文件*/yacc parser.y/*生成含有yyparse( )的y.tab.c文件*/cc y.tab.c lyll/*對文件y.tab.c進(jìn)行編譯*/便可得到可執(zhí)行的語法分析器。如果用戶在YSP文件中提供了自己編寫的main( )函數(shù)和yyerror( )函數(shù)，則選擇項ly不用給出。    五、 二義性文法的處理由于LALR分析要求文法是非二

20、義性的，因此，當(dāng)一文法有二義性時，YACC構(gòu)造的分析表必然會含有分析動作沖突，此時YACC會報告沖突動作的數(shù)目。若需了解沖突項目更詳盡的內(nèi)容，可在調(diào)用YACC對YSP文件進(jìn)行處理的命令中使用選擇項V。這樣，YACC會產(chǎn)生一個附加文件YOUT.PUT。該文件含有關(guān)于沖突的進(jìn)一步描述信息，以及YACC按照“缺省規(guī)則”自行解決的沖突信息。YACC系統(tǒng)內(nèi)約定解決沖突的原則為：(1) 當(dāng)發(fā)生歸約歸約沖突時，按照YSP文件中排列在前面的產(chǎn)生式進(jìn)行歸約；(2) 當(dāng)發(fā)生移進(jìn)歸約沖突時，按照移進(jìn)優(yōu)先于歸約的原則進(jìn)行處理。這條規(guī)則正確地解決了由于懸空else的二義性所產(chǎn)生的移進(jìn)歸約沖突，即保證了使else總是與其

21、左側(cè)尚未被匹配的then配對。然而，上述缺省規(guī)則不能保證總與用戶的要求一致。因此，YACC通過為文法中某些運(yùn)算符定義優(yōu)先級和結(jié)合性等手段，提供了一些可能解決移進(jìn)-歸約沖突的途徑。在YSP文件的說明部分，用戶可使用命令%left (%right)來指明跟在其后的所有運(yùn)算符具有相同的優(yōu)先級和左 (右)結(jié)合性質(zhì)。例如，命令%left+-%left*/使得上述運(yùn)算符均具有左結(jié)合性質(zhì)。用戶還可用%nonassoc命令告訴YACC，其后所跟的運(yùn)算符不具有結(jié)合性。例如%nonassoc<>= .指明<、>等符號不具有結(jié)合性質(zhì) (即該運(yùn)算符的相鄰兩次出現(xiàn)不能結(jié)合)。YACC規(guī)定，出現(xiàn)在

22、同一結(jié)合性說明中的各個符號具有相同的優(yōu)先級；說明排列的次序決定了優(yōu)先級的高低，排列在前者優(yōu)先級較低，而排列在后者則較高。例如，在上面的例子中，+、 - 的優(yōu)先級低于 *、/。有時，處于某些產(chǎn)生式右部的最左終結(jié)符號的優(yōu)先級難以說明 (如一元減運(yùn)算符)，則可通過給該產(chǎn)生式附加說明的方式，強(qiáng)制定義這類運(yùn)算符的優(yōu)先級。其格式為：%prec<終結(jié)符號>這種說明告訴YACC，該產(chǎn)生式右部最左終結(jié)符號與上述說明中的終結(jié)符號具有相同的優(yōu)先級和結(jié)合性。例如，在后面的YACC應(yīng)用實例中，有如下說明：%left*/ %left UMINUS/*一元減運(yùn)算符*/Expr: - Expr%prec UMIN

23、US$=-$2;前者指明終結(jié)符號UMINUS具有左結(jié)合性，且優(yōu)先級最高 (因在“*”，“/”等之后定義)；后者則強(qiáng)制定義表達(dá)式中的一元減運(yùn)算符與UMINUS具有相同的優(yōu)先級和結(jié)合性。當(dāng)然，上述說明方式也可通過在詞法分析程序中，當(dāng)識別出一元減運(yùn)算符時，返回終結(jié)符號UMINUS的內(nèi)部碼的方式來實現(xiàn)。另外，還可通過給產(chǎn)生式定義優(yōu)先級和結(jié)合性的手段來解決移進(jìn)歸約沖突。YACC規(guī)定，對于規(guī)則部分中的每個產(chǎn)生式，若無任何附加的強(qiáng)制性說明，則其優(yōu)先級和結(jié)合性與該產(chǎn)生式右部的最右終結(jié)符號的優(yōu)先級和結(jié)合性相同 (自然，該終結(jié)符號的優(yōu)先級和結(jié)合性應(yīng)在說明部分加以定義)。于是，當(dāng)需在“移進(jìn)輸入符號a”和“按產(chǎn)生式A

24、進(jìn)行歸約”這兩個動作之間進(jìn)行選擇時，YACC將按下述規(guī)則解決沖突：若產(chǎn)生式A的優(yōu)先級高于a，或兩者優(yōu)先級相同但產(chǎn)生式A是左結(jié)合的，則選取歸約動作；否則選取移進(jìn)動作。實踐表明，這種解決移進(jìn)歸約沖突的策略是合理的，在絕大多數(shù)情況下都是與實際情況相吻合的。有了優(yōu)先級和結(jié)合性的定義，可簡化文法的產(chǎn)生式結(jié)構(gòu)。例如，在前面的表達(dá)式文法中可省去非終結(jié)符號Term和Factor，僅使用一個非終結(jié)符Expr即可。在一文法中，文法符號的多少直接影響到語法分析程序的運(yùn)行效率。一般說來，減少文法符號的個數(shù)，可減少分析表的狀態(tài)數(shù)，從而可節(jié)省內(nèi)存空間并提高分析速度。還需要指出，在使用YACC時，應(yīng)盡量使用左遞歸形式定義產(chǎn)

25、生式，這樣做同樣可以從時間和空間上提高語法分析程序的效率。    六、 關(guān)于嵌入動作與語法變換前面說過，YACC允許在規(guī)則部分每個產(chǎn)生式的最右側(cè)，附加上進(jìn)行語義處理的語義動作，以便在以后執(zhí)行語法分析程序的過程中，每當(dāng)使用一個產(chǎn)生式進(jìn)行歸約 (也只有在進(jìn)行歸約)時，將自動執(zhí)行相應(yīng)的語義動作。這是S屬性翻譯文法的特征之一。但有時我們也希望把一個動作放在產(chǎn)生式的其它地方，而不是最右端。例如，在對條件語句Stmtif Expr then /*action1*/Stmt/*action2*/進(jìn)行處理時，為了能夠及時回填Expr的真出口，需在then后“嵌入”語義動作 (參見

26、5.6節(jié))。一般說來，解決此類問題的方法，是對原文法進(jìn)行如5.6節(jié)中那樣的語法變換。除此而外，YACC (及OCCS，下同)還提供了一種更簡單的處理方法，即允許用戶自由地在產(chǎn)生式右部的任何位置嵌入所希望的語義動作。但需指出，YACC將自動為其增加產(chǎn)生式，以保證“動作”在進(jìn)行“歸約”時才被執(zhí)行 (即保持S屬性文法的特征)。例如，產(chǎn)生式A action1 action2將被YACC處理為A 001 action2001 action1其中，001是YACC內(nèi)部自動引入的虛擬非終結(jié)符號 (實際上，001并不存在，這里使用這個名字只是為了說明其原理)。當(dāng)然，上述處理方法也許會帶來副作用，即可能引起新的

27、移進(jìn)歸約沖突，若發(fā)生這樣的問題，則只能由用戶自行設(shè)法解決。還需要指出，在產(chǎn)生式中嵌入語義動作之后，代碼段中出現(xiàn)的、代表文法符號屬性的$，$1，$2等符號的意義有可能會被改變。例如，在下面產(chǎn)生式中，$i與文法符號的對應(yīng)關(guān)系為A:ab$=$1+$2;/*A1*/ c$=$1+$2+$3+$4;$1$2$3 $4因為動作A1對應(yīng)了一個隱含的非終結(jié)符號001，它將在上面的產(chǎn)生式中占一個符號的位置，因此其語義值只能通過$3來引用，同時，文法符號c的語義值則應(yīng)由$4來引用。另外，在動作A1中不能出現(xiàn)對$3和$4的引用，這是因為，在執(zhí)行該動作時，$3和$4對應(yīng)的文法符號尚未在分析棧中形成。在OCCS中，還允

28、許用戶對文法進(jìn)行另一種變換，即允許用戶使用方括號 定義產(chǎn)生式的可選部分。例如，對形如A: a b c ；的產(chǎn)生式，系統(tǒng)內(nèi)部將其變換為A: a 001 c ；001: b|/*/；在這種情況下，用戶在編寫語義子程序時，應(yīng)特別注意對產(chǎn)生式中各文法符號屬性的正確引用。例如，對產(chǎn)生式A：a b c $=$1+$2; d $=$1+$2+$3; ；其中，方括號內(nèi)的文法符號和語義動作實際上對應(yīng)用于產(chǎn)生式001: b c $=$1+$2; ；因此，對上述產(chǎn)生式而言，只能將方括號內(nèi)的部分視為一個文法符號，從而，需用$3而不是用$4來引用文法符號d的語義屬性。如果歸約過程使用了產(chǎn)生式001: $=$1+$2;/

29、*產(chǎn)生式*/；則在動作$=$1+$2+$3;中$2無意義，處理過程可能出現(xiàn)難以預(yù)料的結(jié)果。因此，當(dāng)用戶需傳送語義值時，應(yīng)在此處避免使用 定義產(chǎn)生式。OCCS還提供了一種允許用戶使用自反傳遞閉包的語法變換手段，例如，對于產(chǎn)生式A :a b* c ；OCCS內(nèi)部將其變換為A：a 001 c ；001:001 b |/*產(chǎn)生式*/；其屬性引用的原理與可選情形類似，這里就不再討論了。    七、 YACC應(yīng)用實例為了便于學(xué)習(xí)編寫YSP文件，下面給出一個生成具有較強(qiáng)功能計算器的完整YSP文件實例。此計算器能進(jìn)行加、減、乘、除和賦值等運(yùn)算，并且還有26個寄存器 (變量)，分別用26個小寫英文字母表示。當(dāng)給寄存器 (變量)賦值時，不打印計算結(jié)果，其它情況則打印出表達(dá)式的值。%/*下面是說明部分*/#include <stdio.h>#include <ctype.h>int reg26;int base;%startList%tokendigitletterUMINUS%left|%left&%right!%left+-%left*/%le