概念
?什么是YACC？yacc(Yet Another Compiler Compiler)，是Unix/linux上一個(gè)用來生成編譯器的編譯器（編譯器代碼生成器）.使用巴克斯范式(BNF)定義語法，能處理上下文無關(guān)文法(context-free)。出現(xiàn)在每個(gè)產(chǎn)生式左邊(left-hand side：lhs)的符號(hào)是非終端符號(hào)，出現(xiàn)在產(chǎn)生式右邊(right-hand side：rhs)的符號(hào)有非終端符號(hào)和終端符號(hào)，但終端符號(hào)只出現(xiàn)在右端。yacc是開發(fā)編譯器的一個(gè)有用的工具,采用LR（1）（實(shí)際上是LALR(1)）語法分析方法。LR(k)分析方法是1965年Knuth提出的，括號(hào)中的k（k >=0）表示向右查看輸入串符號(hào)的個(gè)數(shù)。LR分析法正視給出一種能根據(jù)當(dāng)前分析棧中的符號(hào)串和向右順序查看輸入串的k個(gè)符號(hào)就可唯一確定分析器的動(dòng)作是移進(jìn)還是規(guī)約和用哪個(gè)產(chǎn)生式規(guī)約。這種方法具有分析速度快，能準(zhǔn)確，即使地指出出錯(cuò)的位置，它的主要缺點(diǎn)是對(duì)于一個(gè)使用語言文法的分析器的構(gòu)造工作量相當(dāng)大，k愈大構(gòu)造愈復(fù)雜，實(shí)現(xiàn)比較困難。 一個(gè)LR分析器有3個(gè)部分組成：?總控程序，也可以稱為驅(qū)動(dòng)程序。對(duì)所有的LR分析器總控程序都是相同的。?分析表或分析函數(shù)。不同的文法分析表將不同，同一個(gè)文法采用的LR分析器不同時(shí)，分析表也不同，分析表又可分為動(dòng)作(ACTION)表和狀態(tài)轉(zhuǎn)換(GOTO)表兩個(gè)部分，它們都可用二維數(shù)組表示。?分析棧，包括文法符號(hào)棧和相應(yīng)的狀態(tài)棧。它們均是先進(jìn)后出棧。 分析器的動(dòng)作由棧頂狀態(tài)和當(dāng)前輸入符號(hào)所決定(LR(0)分析器不需要向前查看輸入符號(hào))。LR分析器工作過程如下 :其中SP為棧指針，S[i]為狀態(tài)棧，X[i]為文法符號(hào)棧。狀態(tài)轉(zhuǎn)換表內(nèi)容按關(guān)系GOTO[Si，X] = Sj確定，該關(guān)系式是指當(dāng)棧頂狀態(tài)為Si遇到當(dāng)前文法符號(hào)為X時(shí)應(yīng)轉(zhuǎn)向狀態(tài)Sj。X為終結(jié)符或非終結(jié)符。 ACTION[Si，a]規(guī)定了棧頂狀態(tài)為Si是遇到輸入符號(hào)a應(yīng)執(zhí)行的動(dòng)作。 動(dòng)作動(dòng)作有4種可能：移進(jìn)：當(dāng)Sj = GOTO[Si，a]成立，則把Sj移入到狀態(tài)棧，把a(bǔ)移入到文法符號(hào)棧。其中i，j表示狀態(tài)號(hào)。規(guī)約：當(dāng)在棧頂形成句柄為β時(shí)，則用β歸約為相應(yīng)的非終結(jié)符A，即當(dāng)文法中有 A-->β的產(chǎn)生式，而β的長度為r（即|β| = r）,則從狀態(tài)棧和文法符號(hào)棧中自棧頂向下去掉r個(gè)符號(hào)，即棧指針SP減去r。并把A移入文法符號(hào)棧內(nèi)，再把滿足Sj = GOTO[Si，A]的狀態(tài)移進(jìn)狀態(tài)棧，其中Si為修改指針后的棧頂狀態(tài)。接受acc:當(dāng)規(guī)約到文法符號(hào)棧只剩文法的開始符號(hào)S時(shí)，并且輸入符號(hào)串已結(jié)束即當(dāng)前輸入符是‘#’，則為分析成功。報(bào)錯(cuò)：當(dāng)遇到狀態(tài)棧頂為某一狀態(tài)下出現(xiàn)不該遇到的文法符號(hào)時(shí)，則報(bào)錯(cuò)，說明輸入串不是該文法能接受的句子。 YACC文件格式yacc文件分為三部分：... definitions ...（%{}%）%%... rules ...%%... subroutines ... 定義部分第一部分包括標(biāo)志（token）定義和C代碼（用“%{”和“%}”括起來）。如在定義部分定義標(biāo)志：%token INTEGER當(dāng)運(yùn)行yacc后，會(huì)產(chǎn)生頭文件，里面包含該標(biāo)志的預(yù)定義，如：#ifndef YYSTYPE #define YYSTYPE int #endif #define INTEGER 258 extern YYSTYPE yylval;lex使用該頭文件中的標(biāo)志定義。Yacc調(diào)用lex的yylex()來獲得標(biāo)志（token），與標(biāo)志對(duì)應(yīng)的值由lex放在變量yylval中。yylval的類型由YYSTYPE決定，YYSTYPE缺省類型是int。如：[0-9]+ { yylval = atoi(yytext); return INTEGER; }標(biāo)志0-255被保留作為字符值，一般產(chǎn)生的token標(biāo)志從258開始。如：[-+] return *yytext; /* return Operator */返回加號(hào)或減號(hào)。注意要把減號(hào)放在前面，避免被認(rèn)作是范圍符號(hào)。對(duì)于操作符，可以定義%left和%right：%left表示左相關(guān)（left-associative），%right表示右相關(guān)（right-associative）。可以定義多組%left或%right，在后面定義的組有更高的優(yōu)先級(jí)。如：%left ‘+’ ‘-‘%left ‘*’ ‘/’上面定義的乘法和除法比加法和減法有更高的優(yōu)先級(jí)。改變YYSTYPE的類型。如這樣定義TTSTYPE：%union{ int iValue; /* integer value */ char sIndex; /* symbol table index */ nodeType *nPtr; /* node pointer */ };則生成的頭文件中的內(nèi)容是：typedef union{ int iValue; /* integer value */ char sIndex; /* symbol table index */ nodeType *nPtr; /* node pointer */ } YYSTYPE; extern YYSTYPE yylval;可以把標(biāo)志（token）綁定到Y(jié)YSTYPE的某個(gè)域。如：%token <iValue> INTEGER %type <nPtr> exPR把expr綁定到nPtr，把INTEGER綁定到iValue。yacc處理時(shí)會(huì)做轉(zhuǎn)換。如：expr: INTEGER { $$ = con($1); }轉(zhuǎn)換結(jié)果為：yylval.nPtr = con(yyvsp[0].iValue);其中yyvsp[0]是值棧（value stack）當(dāng)前的頭部。 定義一元減號(hào)符有更高的優(yōu)先級(jí)的方法：%left GE LE EQ NE '>' '<' %left '+' '-' %left '*' %nonassoc UMINUS%nonassoc的含義是沒有結(jié)合性。它一般與%prec結(jié)合使用表示該操作有同樣的優(yōu)先級(jí)。如：expr: '-' expr %prec UMINUS { $$ = node(UMINUS, 1, $2); }表示該操作的優(yōu)先級(jí)與UMINUS相同，在上面的定義中，UMINUS的優(yōu)先級(jí)高于其他操作符，所以該操作的優(yōu)先級(jí)也高于其他操作符計(jì)算。 規(guī)則部分規(guī)則部分很象BNF語法。規(guī)則中目標(biāo)或非終端符放在左邊，后跟一個(gè)冒號(hào)（：），然后是產(chǎn)生式的右邊，之后是對(duì)應(yīng)的動(dòng)作（用{}包含）。如：%token INTEGER%%program: program expr '/n' { printf("%d/n", $2); } ;expr: INTEGER { = $1; } | expr '+' expr { = $1 + $3; } | expr '-' expr { $$ = $1 - $3; } ;%%int yyerror(char *s) { fprintf(stderr, "%s/n", s); return 0; }其中，$1表示右邊的第一個(gè)標(biāo)記的值，$2表示右邊的第二個(gè)標(biāo)記的值，依次類推。$$表示規(guī)約后的值。第三部分該部分是函數(shù)部分。當(dāng)yacc解析出錯(cuò)時(shí)，會(huì)調(diào)用函數(shù)yyerror()，用戶可自定義函數(shù)的實(shí)現(xiàn)。main函數(shù)是調(diào)用yacc解析入口函數(shù)yyparse()。如：int main(void) { yyparse(); return 0; }遞歸的處理遞歸處理有左遞歸和右遞歸。左遞歸形式：list: item | list ',' item;右遞歸形式：list: item | item ',' list使用右遞歸時(shí)，所有的項(xiàng)都?jí)喝攵褩＠铮砰_始規(guī)約；而使用左遞歸的話，同一時(shí)刻不會(huì)有超過三個(gè)項(xiàng)在堆棧里。 If-Else的沖突當(dāng)有兩個(gè)IF一個(gè)ELSE時(shí)，該ELSE和哪個(gè)IF匹配是一個(gè)問題。有兩種匹配方法：與第一個(gè)匹配和與第二匹配。現(xiàn)代程序語言都讓ELSE與最近的IF匹配，這也是yacc的缺省行為。雖然yacc行為正確，但為避免警告，可以給IF-ELSE語句比IF語句更高的優(yōu)先級(jí)：%nonassoc IFX %nonassoc ELSEstmt: IF expr stmt %prec IFX | IF expr stmt ELSE stmt 出錯(cuò)處理當(dāng)yacc解析出錯(cuò)時(shí)，缺省的行為是調(diào)用函數(shù)yyerror()，然后從yylex返回一個(gè)值。一個(gè)更友好的方法是忽略一段錯(cuò)誤輸入流，繼續(xù)開始掃描。這里要涉及到Y(jié)ACC中錯(cuò)誤保留字error的應(yīng)用。
Yacc源程序的風(fēng)格建議按照如下風(fēng)格來寫：（1）終端符名全部用大寫字母，非終端符全部用小寫字母；（2）把語法規(guī)則和語義動(dòng)作放在不同的行；（3）把左部相同的規(guī)則寫在一起，左部只寫一次，而后面所有規(guī)則都寫在豎線“|”之后；（4）把分號(hào)“；”放在規(guī)則最后，獨(dú)占一行；（5）用制表符來對(duì)齊規(guī)則和動(dòng)作。
語法分析中的錯(cuò)誤處理當(dāng)進(jìn)行語法分析時(shí)發(fā)現(xiàn)輸入串有語法錯(cuò)誤，最好能在報(bào)告出錯(cuò)信息以后繼續(xù)進(jìn)行語法分析，以便發(fā)現(xiàn)更多的錯(cuò)誤。Yacc處理錯(cuò)誤的方法是：當(dāng)發(fā)現(xiàn)語法錯(cuò)誤時(shí)，yacc丟掉那些導(dǎo)致錯(cuò)誤的符號(hào)適當(dāng)調(diào)整狀態(tài)棧。然后從出錯(cuò)處的后一個(gè)符號(hào)處或跳過若干符號(hào)直到遇到用戶指定的某個(gè)符號(hào)時(shí)開始繼續(xù)分析。Yacc內(nèi)部有一個(gè)保留的終結(jié)符error，把它寫在某個(gè)產(chǎn)生式的右部，則Yacc就認(rèn)為這個(gè)地方可能發(fā)生錯(cuò)誤，當(dāng)語法分析的確在這里發(fā)生錯(cuò)誤時(shí)，Yacc就用上面介紹的方法處理，如果沒有用到 error的產(chǎn)生式，則 Yacc打印出“Syntax error”，就終止語法分析。下面看兩個(gè)使用error的簡(jiǎn)單例子：1．下面的產(chǎn)生式stat: error;使yacc在分析stat推導(dǎo)出的句型時(shí)，遇到語法錯(cuò)誤時(shí)跳過出錯(cuò)的部分，繼續(xù)分析（也會(huì)打印語法錯(cuò)誤信息）2．下面的產(chǎn)生式stat: error ';';使yacc碰到語法錯(cuò)時(shí)，跳過輸入串直到碰到下一個(gè)分號(hào)才繼續(xù)開始語法分析。 嵌入式動(dòng)作對(duì)于語法分析程序中的每一個(gè)語法規(guī)則，都有相應(yīng)的C/C++語句來做一些額外的處理，這個(gè)額外的處理就是語法動(dòng)作。不過語法動(dòng)作和詞法動(dòng)作的不同之處在于，語法動(dòng)作允許嵌入式的語法動(dòng)作，而詞法動(dòng)作不行。盡管yacc的語法分析技術(shù)只允許動(dòng)作在規(guī)則的末端，但yacc可以自動(dòng)模擬嵌入在規(guī)則內(nèi)部的動(dòng)作。如果在規(guī)則內(nèi)部寫入一個(gè)動(dòng)作，yacc就會(huì)創(chuàng)造一個(gè)右側(cè)為空并且左邊是自動(dòng)生成的名字規(guī)則，使得嵌入的動(dòng)作進(jìn)高規(guī)則的動(dòng)作里去，用自動(dòng)成成的名字代替最初的規(guī)則內(nèi)的動(dòng)作。例如： 下面的句子是等價(jià)的thing : A {printf("I am A") ;} Bthing : A fakename B;fakename : {printf("I am A");}這種方式將A植作為$1, 規(guī)則末端的動(dòng)作可將嵌入式動(dòng)作的值作為$2,B的值為$3. Example:[cpp] view plain copy//L文件： %{ #include "FIRST_TA.H" #include <stdio.h> #include <stdlib.h> %} %% a {return A_STATE;} b {return B_STATE;} c {return C_STATE;} not {return NOT;} %% //Y文件： %{ #include <stdio.h> #include <stdlib.h> %} %token A_STATE B_STATE C_STATE NOT %% program : A_STATE B_STATE { int c, d; c = 20; d = 25; } c_state_not { int e,f; e = 30; f = 35; } | A_STATE B_STATE { int a, b; a = 10; b = 15; } c_state_not : C_STATE NOT{} %% 輸入文件的字符：a, b, c, f, c, not
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
