語(yǔ)法分析程序的自動(dòng)生成工具

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

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

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

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

5、式，然后計(jì)算并打印它的值。算術(shù)表達(dá)式的文法如下：Expr Expr + Term | TermTerm Term * Factor | FactorFactor ( Expr ) | digit其中，終結(jié)符號(hào)digit是09中的任何一個(gè)數(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( );/*讀入一個(gè)字符*/if(isdigit(c)/*判別c是否為數(shù)字*/yylval=c-0;return digit;return c;void yyerror( )/*出錯(cuò)處

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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