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