一、背景

• 概念
  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)作。

本文討論yacc語法的格式并描述可用的各種特征和選項(xiàng)

二、yacc語法結(jié)構(gòu)

yacc語法包括三部分：定義段、規(guī)則段和用戶子例程段

...定義段...

%%

...規(guī)則段...

%%

...用戶子例程段...

各部分由以兩個(gè)百分號(hào)開頭的行分開，盡管某一個(gè)部分可以為空，但是前兩部分是必須的，第三部分和前面的百分號(hào)可以省略。

符號(hào)

yacc 語法由符號(hào)組成，即語法的“詞”。符號(hào)是一串不以數(shù)字開頭的字母、數(shù)字、句點(diǎn)和下劃線。符號(hào)error專用于錯(cuò)誤恢復(fù)，另外，yacc對(duì)任何符號(hào)都不會(huì)附加“先驗(yàn)”的意義。

由詞法分析程序產(chǎn)生的符號(hào)叫做終結(jié)符號(hào)或者標(biāo)記。定義在規(guī)則左側(cè)的叫做非終結(jié)符號(hào)或者非終結(jié)。標(biāo)記也可能是字面上引用的字符，通常遵循約定：標(biāo)記大寫，非終結(jié)符號(hào)小寫。

定義段

定義段包括文字塊，逐字拷貝到生成的C文件開頭部分的C代碼，通常包括聲明和#include行?？赡苡?union %start %token %type %left %right 和 %nonassoc聲明。

也可以包含普通的C語言風(fēng)格的注釋，所有這些都是可選的，在簡(jiǎn)單的語法分析程序中，定義段可能完全是空的。

如在定義部分定義標(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ī)則段由語法規(guī)則和包括C代碼的動(dòng)作組成。

規(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; 
}

其中，2表示右邊的第二個(gè)標(biāo)記的值，依次類推。$$表示歸約后的值。

用戶子例程段

yacc 將用戶子例程段的內(nèi)容完全拷貝到C文件中，通常這部分包括從動(dòng)作調(diào)用的例程。
該部分是函數(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; 
}

動(dòng)作

動(dòng)作 是yacc與在語法中規(guī)則相符時(shí)執(zhí)行的C代碼，動(dòng)作一定是C復(fù)合語句。

動(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)生式，而β的長(zhǎng)度為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ò)，說明輸入串不是該文法能接受的句子。

通過使用后面跟有數(shù)字的美元符號(hào)，動(dòng)作可以查閱在規(guī)則中與符號(hào)有關(guān)的值,冒號(hào)后面跟的第一個(gè)符號(hào)是數(shù)字1，例如：

date：month  '/'  day   '/'  year  
           { printf ("date %d-%d-%d  found",$1,$3,$5);}  

而名字，$$是指冒號(hào)左邊符號(hào)的值，符號(hào)值可以有不同的C類型。

三、遞歸處理

遞歸處理有左遞歸和右遞歸。
左遞歸形式：

list: item 
    | list ',' item;

右遞歸形式：

list: item 
     | item ',' list

使用右遞歸時(shí)，所有的項(xiàng)都?jí)喝攵褩＠?，才開始規(guī)約；而使用左遞歸的話，同一時(shí)刻不會(huì)有超過三個(gè)項(xiàng)在堆棧里。

歧義和沖突

由于語法有歧義或者包含沖突，yacc對(duì)于語法規(guī)范的翻譯可能會(huì)失敗。一些情況下，語法確實(shí)有歧義，也就是說對(duì)于一個(gè)單獨(dú)的輸入字符串有兩種可能的分析而且yacc處理不了。

另外一些情況，語法并無歧義，但yacc使用的語法分析技術(shù)不足以分析這個(gè)語法。

• 移進(jìn)/歸約沖突
  當(dāng)一個(gè)輸入字符串有兩種可能的分析時(shí)，而且其中一個(gè)分析完成一個(gè)規(guī)則（歸約選項(xiàng)），而另一個(gè)卻沒有（移進(jìn)選項(xiàng)）時(shí)，移進(jìn)/歸約沖突便發(fā)生了。
  例如：

%%  
e: ‘X’  
     |e  '+'   e  
         ;  

對(duì)于輸入字符串“X+X+X” ，有兩種可能的分析： “（X+X）+X”或者“X+(X+X)”，采用歸約選項(xiàng)使得語法分析程序使用第一個(gè)分析，而采用移進(jìn)選項(xiàng)則使用另一個(gè)。

• 歸約/歸約沖突
  當(dāng)同樣的標(biāo)記可以完成兩個(gè)不同的規(guī)則時(shí)，就會(huì)發(fā)生歸約/歸約沖突。
  例如：

%%  
prog:    proga | progb  
proga:       'X' ;  
progb:       'Y' ;  

一個(gè)“X”可能是proga，也可能是progb。

大多數(shù)歸約/歸約沖突沒這么明顯，但是幾乎在任何情況下它們?cè)谡Z法中都表現(xiàn)為錯(cuò)誤。

• 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 ELSE
stmt: IF expr stmt %prec IFX 
       | IF expr stmt ELSE stmt

四、特殊字符

由于yacc處理符號(hào)標(biāo)記而不是文本，它的輸入字符集比起lex來說就簡(jiǎn)單的多，下面列出了yacc所使用的特殊符號(hào)的列表：

%
具有兩個(gè)%標(biāo)記的行將yacc語法分成了幾部分；
定義段的所有聲明都是以%開始，包括%{ %} %union %start %token %type %left %right 和 %nonassoc聲明。

\
反斜線符號(hào)是廢棄的百分號(hào)同義詞，在動(dòng)作中，C語言字符串中有其通常作用。

$
在動(dòng)作中，美元符號(hào)引入一個(gè)值引用，舉例來說，$3表示規(guī)則右端第3個(gè)符號(hào)的值。

'
文字標(biāo)記由一個(gè)單引號(hào)結(jié)束，例如 'z' 。

<>
在一個(gè)動(dòng)作的值引用中，可以不考慮尖括號(hào)包圍起來的默認(rèn)類型。

"
有些yacc版本在文字標(biāo)記中將單引號(hào)和雙引號(hào)同等對(duì)待，這樣使用根本不方便。

{}
動(dòng)作中C代碼在大括號(hào)中。

;
除了后面緊接著是以豎線開頭的規(guī)則外，規(guī)則部分每個(gè)都是以分號(hào)結(jié)束。

|
當(dāng)連續(xù)兩個(gè)規(guī)則具有相同的左端，第二個(gè)規(guī)則可用一個(gè) | 代替符號(hào)和冒號(hào)。

:
在每一條規(guī)則里，左端的每個(gè)符號(hào)后面都跟著一個(gè)冒號(hào)。

_
符號(hào)可以包括和字母、數(shù)字以及句點(diǎn)在一起的下劃線。

.
符號(hào)可以包括與字母、數(shù)字、下劃線一起的句點(diǎn)。

=
早期版本使用，現(xiàn)已不推薦。

五、Yacc 源程序的風(fēng)格

建議按照如下風(fēng)格來寫：

1. 終端符名全部用大寫字母，非終端符全部用小寫字母；
2. 把語法規(guī)則和語義動(dòng)作放在不同的行；
3. 把左部相同的規(guī)則寫在一起，左部只寫一次，而后面所有規(guī)則都寫在豎線“|”之后；
4. 把分號(hào)“；”放在規(guī)則最后，獨(dú)占一行；
5. 用制表符來對(duì)齊規(guī)則和動(dòng)作。