一、背景
- 概念
yacc(Yet Another Compiler Compiler)荐开，是Unix/Linux上一個用來生成編譯器的編譯器（編譯器代碼生成器）.
使用巴克斯范式(BNF)定義語法擂送，能處理上下文無關(guān)文法(context-free)楞泼。出現(xiàn)在每個產(chǎn)生式左邊(left-hand side：lhs)的符號是非終端符號甸各，出現(xiàn)在產(chǎn)生式右邊(right-hand side：rhs)的符號有非終端符號和終端符號忽冻，但終端符號只出現(xiàn)在右端痴腌。
yacc是開發(fā)編譯器的一個有用的工具,采用LR（1）（實際上是LALR(1)）語法分析方法雌团。
LR(k)分析方法是1965年Knuth提出的，括號中的k（k >=0）表示向右查看輸入串符號的個數(shù)士聪。LR分析法正視給出一種能根據(jù)當(dāng)前分析棧中的符號串和向右順序查看輸入串的k個符號就可唯一確定分析器的動作是移進(jìn)還是規(guī)約和用哪個產(chǎn)生式規(guī)約锦援。
這種方法具有分析速度快，能準(zhǔn)確剥悟，即使地指出出錯的位置灵寺，它的主要缺點是對于一個使用語言文法的分析器的構(gòu)造工作量相當(dāng)大曼库，k愈大構(gòu)造愈復(fù)雜，實現(xiàn)比較困難略板。
一個LR分析器有3個部分組成：
-
總控程序毁枯，也可以稱為驅(qū)動程序。
對所有的LR分析器總控程序都是相同的叮称。 -
分析表或分析函數(shù)种玛。
不同的文法分析表將不同，同一個文法采用的LR分析器不同時颅拦，分析表也不同蒂誉，分析表又可分為動作(ACTION)表和狀態(tài)轉(zhuǎn)換(GOTO)表兩個部分，它們都可用二維數(shù)組表示距帅。 -
分析棧右锨，包括文法符號棧和相應(yīng)的狀態(tài)棧。
它們均是先進(jìn)后出棧碌秸。 分析器的動作由棧頂狀態(tài)和當(dāng)前輸入符號所決定(LR(0)分析器不需要向前查看輸入符號)绍移。
LR分析器工作過程如下 :
其中SP為棧指針，S[i]為狀態(tài)棧讥电，X[i]為文法符號棧蹂窖。狀態(tài)轉(zhuǎn)換表內(nèi)容按關(guān)系GOTO[Si，X] = Sj確定恩敌，該關(guān)系式是指當(dāng)棧頂狀態(tài)為Si遇到當(dāng)前文法符號為X時應(yīng)轉(zhuǎn)向狀態(tài)Sj瞬测。X為終結(jié)符或非終結(jié)符。 ACTION[Si纠炮，a]規(guī)定了棧頂狀態(tài)為Si是遇到輸入符號a應(yīng)執(zhí)行的動作月趟。
本文討論yacc語法的格式并描述可用的各種特征和選項
二、yacc語法結(jié)構(gòu)
yacc語法包括三部分：定義段恢口、規(guī)則段和用戶子例程段
...定義段...
%%
...規(guī)則段...
%%
...用戶子例程段...
各部分由以兩個百分號開頭的行分開孝宗，盡管某一個部分可以為空，但是前兩部分是必須的耕肩，第三部分和前面的百分號可以省略因妇。
符號
yacc 語法由符號組成，即語法的“詞”猿诸。符號是一串不以數(shù)字開頭的字母婚被、數(shù)字、句點和下劃線两芳。符號error專用于錯誤恢復(fù)摔寨，另外，yacc對任何符號都不會附加“先驗”的意義怖辆。
由詞法分析程序產(chǎn)生的符號叫做終結(jié)符號或者標(biāo)記是复。定義在規(guī)則左側(cè)的叫做非終結(jié)符號或者非終結(jié)。標(biāo)記也可能是字面上引用的字符竖螃，通常遵循約定：標(biāo)記大寫淑廊，非終結(jié)符號小寫。
定義段
定義段包括文字塊特咆，逐字拷貝到生成的C文件開頭部分的C代碼季惩，通常包括聲明和#include行∧甯瘢可能有%union %start %token %type %left %right 和 %nonassoc聲明画拾。
也可以包含普通的C語言風(fēng)格的注釋，所有這些都是可選的菜职，在簡單的語法分析程序中青抛，定義段可能完全是空的。
如在定義部分定義標(biāo)志：
%token INTEGER
當(dāng)運(yùn)行yacc后酬核，會產(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)志對應(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 */
返回加號或減號耸序。注意要把減號放在前面，避免被認(rèn)作是范圍符號菠齿。
對于操作符佑吝，可以定義%left和%right：%left表示左相關(guān)（left-associative），%right表示右相關(guān)（right-associative）绳匀。可以定義多組%left或%right芋忿，在后面定義的組有更高的優(yōu)先級。如：
%left ‘+’ ‘-‘
%left ‘*’ ‘/’
上面定義的乘法和除法比加法和減法有更高的優(yōu)先級疾棵。
改變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的某個域。如：
%token <iValue> INTEGER
%type <nPtr> expr
把expr綁定到nPtr是尔，把INTEGER綁定到iValue殉了。yacc處理時會做轉(zhuǎn)換。如：
expr: INTEGER { $$ = con($1); }
轉(zhuǎn)換結(jié)果為：
yylval.nPtr = con(yyvsp[0].iValue);
其中yyvsp[0]是值棧（value stack）當(dāng)前的頭部拟枚。
定義一元減號符有更高的優(yōu)先級的方法：
%left GE LE EQ NE '>' '<'
%left '+' '-'
%left '*'
%nonassoc UMINUS
%nonassoc的含義是沒有結(jié)合性薪铜。它一般與%prec結(jié)合使用表示該操作有同樣的優(yōu)先級众弓。如：
expr: '-' expr %prec UMINUS { $$ = node(UMINUS, 1, $2); }
表示該操作的優(yōu)先級與UMINUS相同，在上面的定義中隔箍，UMINUS的優(yōu)先級高于其他操作符谓娃，所以該操作的優(yōu)先級也高于其他操作符計算。
規(guī)則段
規(guī)則段由語法規(guī)則和包括C代碼的動作組成蜒滩。
規(guī)則中目標(biāo)或非終端符放在左邊滨达，后跟一個冒號（：），然后是產(chǎn)生式的右邊俯艰，之后是對應(yī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表示右邊的第二個標(biāo)記的值画株，依次類推。$$表示歸約后的值涩搓。
用戶子例程段
yacc 將用戶子例程段的內(nèi)容完全拷貝到C文件中污秆，通常這部分包括從動作調(diào)用的例程。
該部分是函數(shù)部分昧甘。當(dāng)yacc解析出錯時良拼，會調(diào)用函數(shù)yyerror()，用戶可自定義函數(shù)的實現(xiàn)充边。
main函數(shù)是調(diào)用yacc解析入口函數(shù)yyparse()庸推。如：
int main(void)
{
yyparse();
return 0;
}
動作
動作 是yacc與在語法中規(guī)則相符時執(zhí)行的C代碼，動作一定是C復(fù)合語句浇冰。
動作有4種可能：
- 移進(jìn)：
當(dāng)Sj = GOTO[Si贬媒，a]成立，則把Sj移入到狀態(tài)棧肘习，把a(bǔ)移入到文法符號棧际乘。其中i，j表示狀態(tài)號漂佩。 - 規(guī)約：
當(dāng)在棧頂形成句柄為β時脖含，則用β歸約為相應(yīng)的非終結(jié)符A，即當(dāng)文法中有 A-->β的產(chǎn)生式投蝉，而β的長度為r（即|β| = r）,則從狀態(tài)棧和文法符號棧中自棧頂向下去掉r個符號养葵，即棧指針SP減去r。并把A移入文法符號棧內(nèi)瘩缆，再把滿足Sj = GOTO[Si关拒，A]的狀態(tài)移進(jìn)狀態(tài)棧，其中Si為修改指針后的棧頂狀態(tài)。 - 接受acc:
當(dāng)規(guī)約到文法符號棧只剩文法的開始符號S時着绊，并且輸入符號串已結(jié)束即當(dāng)前輸入符是‘#’谐算，則為分析成功。 - 報錯：
當(dāng)遇到狀態(tài)棧頂為某一狀態(tài)下出現(xiàn)不該遇到的文法符號時畔柔，則報錯氯夷，說明輸入串不是該文法能接受的句子臣樱。
通過使用后面跟有數(shù)字的美元符號靶擦，動作可以查閱在規(guī)則中與符號有關(guān)的值,冒號后面跟的第一個符號是數(shù)字1，例如：
date：month '/' day '/' year
{ printf ("date %d-%d-%d found",$1,$3,$5);}
而名字雇毫，$$是指冒號左邊符號的值玄捕，符號值可以有不同的C類型。
三棚放、遞歸處理
遞歸處理有左遞歸和右遞歸枚粘。
左遞歸形式：
list: item
| list ',' item;
右遞歸形式：
list: item
| item ',' list
使用右遞歸時，所有的項都壓入堆棧里飘蚯，才開始規(guī)約馍迄；而使用左遞歸的話，同一時刻不會有超過三個項在堆棧里局骤。
歧義和沖突
由于語法有歧義或者包含沖突攀圈，yacc對于語法規(guī)范的翻譯可能會失敗。一些情況下峦甩，語法確實有歧義赘来，也就是說對于一個單獨的輸入字符串有兩種可能的分析而且yacc處理不了。
另外一些情況凯傲，語法并無歧義犬辰，但yacc使用的語法分析技術(shù)不足以分析這個語法。
-
移進(jìn)/歸約沖突
當(dāng)一個輸入字符串有兩種可能的分析時冰单，而且其中一個分析完成一個規(guī)則（歸約選項）幌缝，而另一個卻沒有（移進(jìn)選項）時，移進(jìn)/歸約沖突便發(fā)生了诫欠。
例如：
%%
e: ‘X’
|e '+' e
;
對于輸入字符串“X+X+X” 涵卵，有兩種可能的分析： “（X+X）+X”或者“X+(X+X)”，采用歸約選項使得語法分析程序使用第一個分析呕诉，而采用移進(jìn)選項則使用另一個缘厢。
-
歸約/歸約沖突
當(dāng)同樣的標(biāo)記可以完成兩個不同的規(guī)則時，就會發(fā)生歸約/歸約沖突甩挫。
例如：
%%
prog: proga | progb
proga: 'X' ;
progb: 'Y' ;
一個“X”可能是proga贴硫，也可能是progb。
大多數(shù)歸約/歸約沖突沒這么明顯，但是幾乎在任何情況下它們在語法中都表現(xiàn)為錯誤英遭。
-
If-Else 的沖突
當(dāng)有兩個IF一個ELSE時间护，該ELSE和哪個IF匹配是一個問題。有兩種匹配方法：與第一個匹配和與第二匹配挖诸。現(xiàn)代程序語言都讓ELSE與最近的IF匹配汁尺，這也是yacc的缺省行為。
雖然yacc行為正確多律，但為避免警告痴突，可以給IF-ELSE語句比IF語句更高的優(yōu)先級：
%nonassoc IFX
%nonassoc ELSE
stmt: IF expr stmt %prec IFX
| IF expr stmt ELSE stmt
四、特殊字符
由于yacc處理符號標(biāo)記而不是文本狼荞，它的輸入字符集比起lex來說就簡單的多辽装，下面列出了yacc所使用的特殊符號的列表：
%
具有兩個%標(biāo)記的行將yacc語法分成了幾部分；
定義段的所有聲明都是以%開始相味，包括%{ %} %union %start %token %type %left %right 和 %nonassoc聲明拾积。\
反斜線符號是廢棄的百分號同義詞，在動作中丰涉，C語言字符串中有其通常作用拓巧。$
在動作中，美元符號引入一個值引用一死，舉例來說肛度，$3表示規(guī)則右端第3個符號的值。'
文字標(biāo)記由一個單引號結(jié)束摘符，例如 'z' 贤斜。<>
在一個動作的值引用中，可以不考慮尖括號包圍起來的默認(rèn)類型逛裤。"
有些yacc版本在文字標(biāo)記中將單引號和雙引號同等對待瘩绒，這樣使用根本不方便。{}
動作中C代碼在大括號中带族。;
除了后面緊接著是以豎線開頭的規(guī)則外锁荔，規(guī)則部分每個都是以分號結(jié)束。|
當(dāng)連續(xù)兩個規(guī)則具有相同的左端蝙砌，第二個規(guī)則可用一個 | 代替符號和冒號阳堕。:
在每一條規(guī)則里，左端的每個符號后面都跟著一個冒號择克。_
符號可以包括和字母恬总、數(shù)字以及句點在一起的下劃線。.
符號可以包括與字母肚邢、數(shù)字壹堰、下劃線一起的句點拭卿。=
早期版本使用，現(xiàn)已不推薦贱纠。
五峻厚、Yacc 源程序的風(fēng)格
建議按照如下風(fēng)格來寫：
- 終端符名全部用大寫字母，非終端符全部用小寫字母谆焊；
- 把語法規(guī)則和語義動作放在不同的行惠桃；
- 把左部相同的規(guī)則寫在一起，左部只寫一次辖试，而后面所有規(guī)則都寫在豎線“|”之后辜王；
- 把分號“；”放在規(guī)則最后剃执，獨占一行誓禁；
- 用制表符來對齊規(guī)則和動作。
