.jpg)
在linux中，bison是用來生成語法分析器程序的工具，它可以將用戶提供的語法規(guī)則轉(zhuǎn)化成一個(gè)語法分析器；bison需要和flex（詞法分析器）配合使用來處理復(fù)雜的文件解析工作。通過給定語法的產(chǎn)生式開始，bison會通過算法，最終構(gòu)造得到動作表，然后利用這個(gè)動作表去解析句子。
本教程操作環(huán)境：linux7.3系統(tǒng)、Dell G3電腦。
unix Lex/YACC 發(fā)展為 Linux FLex/Bison
Lex是1975年由Mike Lesk和當(dāng)時(shí)尚在AT&T實(shí)習(xí)的Eric Schmidt共同完成的（Schmidt做的更多），是一個(gè)詞法分析器的生成程序，可以單獨(dú)使用也可以與Johnson的yacc協(xié)同工作。lex很有名氣，但是無奈效率太低加上有bug。大概在1987年，Lawrence Berkeley實(shí)驗(yàn)室的Vern Paxson用C重新寫了Lex，并命名為FLex（the Fast Lexical Analyzer Generator），基于伯克利許可證。flex現(xiàn)在是SourceForge的一個(gè)項(xiàng)目，依然基于伯克利許可，
[Flex](https://github.com/westes/flex?“Flex”) 是起初unix版lex的free (but non-gnu) implementation，用于c/c ++ 的詞法掃描生成器。
（注意：Schmidt曾是google的CEO）
bison的前身是yacc。yacc是由貝爾實(shí)驗(yàn)室的S.C.Johnson基于Knuth大神的LR語法分析理論，于1975～1978年寫成。大約1985年，UC Berkeley 的研究生Bob Corbett使用改進(jìn)的內(nèi)部算法實(shí)現(xiàn)了伯克利yacc，來自FSF的Richard Stallman改寫了伯克利yacc并將其用于GNU項(xiàng)目，添加了很多特性，形成了今天的GNU Bison。bison現(xiàn)在作為FSF的項(xiàng)目被維護(hù)，基于GNU公共許可證發(fā)布，[Bison](http://www.gnu.org/software/bison/manual/)是兼容yacc的free的語法生成器。
早期Unix的Lex/YACC，發(fā)展為FLex/Bison，新版本的程序是向上兼容的(即兼容老版本)，現(xiàn)chang用Flex和Bison。
flex/bison工作原理
使用的角度，F(xiàn)lex和Bison是Linux下用來生成詞法分析器和語法分析器兩個(gè)程序的工具，可以處理結(jié)構(gòu)化輸入，一般結(jié)合使用來處理復(fù)雜的文件解析工作。
bison可以將用戶提供的語法規(guī)則轉(zhuǎn)化成一個(gè)語法分析器。簡單來說，通過給定語法的產(chǎn)生式開始，bison會通過算法，最終構(gòu)造得到動作表，然后利用這個(gè)動作表去解析句子。具體來說，bison 讀取用戶提供的語法的產(chǎn)生式，生成一個(gè) C 語言格式的 LALR(1) 動作表，并將其包含進(jìn)一個(gè)名為yyparse的 C 函數(shù)，這個(gè)函數(shù)的作用就是利用這個(gè)動作表來解析 Token 流 ，而這個(gè) token 流 是由 flex 生成的詞法分析器掃描源程序得到的。
flex文件是定義pattern（哪是黃豆，哪是綠豆…），通過flex處理（詞法分析）將輸出切分成一段一段的token（將輸入的豆子一個(gè)個(gè)摘出來），從而執(zhí)行不同的action（黃豆就磨豆?jié){（action），綠豆去做綠豆糕(action)）…
flex 生成的tokens可以喂給Bison處理（更簡便易調(diào)試），當(dāng)然也可以不喂給bison而直接自己處理就得了（如喜下例）。但是使用bison可以更方便的處理復(fù)雜的邏輯，編寫簡單，調(diào)試方便。
編碼實(shí)戰(zhàn)：字符統(tǒng)計(jì)器
//本例中僅僅使用flex以及少量手寫代碼（main中），來完成字符串統(tǒng)計(jì)功能。 Yolandas-MacBook-Pro:flex-bison liuyuanyuan$ cat fb1-1.l /* 統(tǒng)計(jì)輸入字符串*/ %{ int chars = 0; int words = 0; int lines =0; %} %% [a-zA-Z]+ { words++; chars += strlen(yytext); } n { chars++; lines++;} . { chars++; } %% int main(int args, char **argv) { yylex(); printf("lines=%6d words=%6d chars=%6dn", lines, words, chars); return 0; } //Linux 系統(tǒng)上用 -lfl 選項(xiàng)編譯, Mac 的編譯選項(xiàng)是 -ll Yolandas-MacBook-Pro:flex-bison liuyuanyuan$ gcc -ll lex.yy.c -o fb1-1 Yolandas-MacBook-Pro:flex-bison liuyuanyuan$ ./fb1-1 hello this is yolanda bye. lines= 3 words= 5 chars= 28
1?flex(fast lex, scanner)文件內(nèi)容結(jié)構(gòu)（*.l,?分3部分）
/* P1: declarations(定義段) */ %{ %} %% /* P2: translation rules(規(guī)則段) */ %% /* P3: auxiliary functions(用戶輔助程序段，c函數(shù))*/
定義段?包括文字塊、定義、內(nèi)部聲明等。
c語言的頭文件、函數(shù)和變量的聲明等一般就放在%{…%}之間，這一部分的內(nèi)容會被直接復(fù)制到生成.c文件的開頭部分。
包含%option選項(xiàng)
%option noyywrap /* 定義段中包含了option選項(xiàng)*/ %{ #include "cal.tab.h" extern int yylval; %}
規(guī)則段?%%…%%之間部分，為一系列匹配模式(正則表達(dá)式)和動作(C代碼)。
當(dāng)flex掃描程序運(yùn)行時(shí)，它把輸入與規(guī)則段的模式進(jìn)行匹配，每次發(fā)現(xiàn)一個(gè)匹配（被匹配的輸入稱為標(biāo)記（token））時(shí)就執(zhí)行與那種模式相關(guān)的C代碼。
pattern（正則表達(dá)式） { action(c代碼) } example: [0-9]+ {yylval = atoi(yytest); return NUMBER;}
用戶輔助程序段?為C代碼，會被原樣復(fù)制到c文件中，一般這里定義一些輔助函數(shù)等。
int terror(chr *s) { printf("%sn", s); return 0; }
2 bison(yacc, parser)文件內(nèi)容結(jié)構(gòu)（*.y ,?分3部分，%%分隔）
/*P1: declarations 定義段*/ %{ %} %% /*P2: grammar rules 規(guī)則段(rule-action)*/ A: a1 { 語義動作1 } | a2 { 語義動作2 } | … | an { 語義動作n } | b //沒有{…},則使用缺省的語義動作 ; //產(chǎn)生式結(jié)束標(biāo)記 //語義動作一般是在產(chǎn)生式右部分析完，歸約動作進(jìn)行前執(zhí)行。 A→ a1 | a2 | … | an | b %% /* P3: supporting C routines 用戶輔助程序段(C函數(shù)) */
定義段?可以分為兩部分：
1. %{ 和%}之間的部分，C語言編寫的，包括頭文件include、宏定義、全局變量定義、函數(shù)聲明等;
2. 對文法的終結(jié)符和非終結(jié)符做一些相關(guān)聲明。
常用的Bison標(biāo)記聲明有：%token %union %start %type %left %right %nonassoc等。
%token 定義文法中使用了哪些終結(jié)符。定義形式： %token TOKEN1 TOKEN2 ?
終結(jié)符一般全大寫；（如 TOKEN1 TOKEN2） ?
一行可定義多個(gè)終結(jié)符，空格分隔； ?%left、%right、%nonassoc 也是定義文法中使用了哪些終結(jié)符。定義形式與%token類似。 ?
先定義的優(yōu)先級低，最后定義的優(yōu)先級最高，同時(shí)定義的優(yōu)先級想通過。 ?
%left表示左結(jié)合，%right表示右結(jié)合； ?
%nonassoc 表示不可結(jié)合（即它定義的終結(jié)符不能連續(xù)出現(xiàn)。例如
%left AA BB ?
%nonassoc CC ?
%right DD ?
表示優(yōu)先級關(guān)系為：AA=BB注意：也可以于%prec來結(jié)合使用來改變token的優(yōu)先級和結(jié)合性 例如： :’-‘ expr %prec NEG { $$ = -$2; }; ? %union 聲明語法符號的語義值類型的集合， ?
bison中每個(gè)符號包括記號和非終結(jié)符都有一個(gè)不同數(shù)據(jù)類型的語義值，并使用yylval變量在移進(jìn)和歸約中傳遞這些值，YYSTYPE（宏定義）為yylval的類型，默認(rèn)為int； ?
我們使用%union來重新定義符號的類型 ?
%union ?
{ ?
int iValue; /* Integer value */ ?
char sIndex; /* symbol table index */ ?
nodeType *nPtr; /* node pointer */ ?
}; ?%type 定義非終結(jié)符其屬性值的類型。 ?
%type sym1 sym2 ?
%typesym3 ? %start 指定文法的開始的文法符號（非終結(jié)符），是最終需要規(guī)約而成的符號。 ?
定義形式為：%start startsym ， 其中startsym為文法的開始符號。 ?
如果不使用%start定義文法開始符號，則默認(rèn)在第二部分規(guī)則段中定義的第一條生產(chǎn)式規(guī)則的左部非終結(jié)符為開始符號。
規(guī)則段?由rule(語法規(guī)則)和action(包括C代碼)組成。
bison規(guī)則基本是BNF，做了一點(diǎn)簡化以易于輸入。
規(guī)則中目標(biāo)或非終端符放在左邊，后跟一個(gè)冒號：然后是產(chǎn)生式的右邊，之后是對應(yīng)的動作（用{}包含）。
%% program: program expr 'n' { printf("%dn", $2); } ; expr: INTEGER {$$ = $1; } | expr '+' expr { $$ = $1 + $3; } | expr '-' expr { $$ = $1 - $3} ; %%
注意：$1表示右邊的第一個(gè)標(biāo)記的值，$2表示右邊的第二個(gè)標(biāo)記的值，依次類推。$$表示歸約后的值。
用戶輔助程序段?為C代碼，會被原樣復(fù)制到c文件中，這里一般自定義一些函數(shù)。
3 flex-bison 代碼協(xié)作方式
flex/bison編碼實(shí)踐：編寫簡單計(jì)算器
1?macos下flex/bison安裝
brew install flex brew install bison # macos下flex/bison安裝簡單方便，另需安裝gcc用于編譯c語言程序。 brew install gcc
2 flex詞法文件：calc.l
%option noyywrap %{ /* * 一個(gè)簡單計(jì)算器的Lex詞法文件 */ void yyerror(char*); #include "calc.tab.h" %} %% /* a-z為變量 */ [a-z] { yylval = *yytext - 'a'; return VARIABLE; } /* 整數(shù) */ [0-9]+ { yylval = atoi(yytext); return INTEGER; } /* 運(yùn)算符 */ [-+()=/*n] {return *yytext;} /* 空白被忽略 */ [ t] ; /* 其他字符都是非法的 */ . yyerror("invalid input"); %%
3 bison語法文件：calc.y
%token INTEGER VARIABLE %left '+' '-' %left '*' '/' %{ #include <stdio.h> void yyerror(char*); int yylex(void); int sym[26]; %} %% program: program statement 'n' | ; statement: expr {printf("%dn", $1);} |VARIABLE '=' expr {sym[$1] = $3;} ; expr: INTEGER |VARIABLE{$$ = sym[$1];} |expr '+' expr {$$ = $1 + $3;} |expr '-' expr {$$ = $1 - $3;} |expr '*' expr {$$ = $1 * $3;} |expr '/' expr {$$ = $1 / $3;} |'('expr')' {$$ = $2;} ; %% void yyerror(char* s) { fprintf(stderr, "%sn", s); } int main(void) { printf("A simple calculator.n"); yyparse(); return 0; }
4 Makefile 文件：
all: clean calc calc: calc.l calc.y bison -d calc.y flex calc.l cc -o $@ calc.tab.c lex.yy.c -lm clean: rm -f calc lex.yy.c calc.tab.c calc.tab.h
5 執(zhí)行
(可以直接執(zhí)行make也就是執(zhí)行Makefile中定義的內(nèi)容，也可以單步執(zhí)行)
Yolandas-MBP:calcSimple liuyuanyuan$ ls -l total 32 -rw-r--r--@ 1 liuyuanyuan staff 157 8 13 09:53 Makefile -rw-r--r--@ 1 liuyuanyuan staff 507 8 13 10:01 calc.l -rw-r--r--@ 1 liuyuanyuan staff 731 8 13 23:04 calc.y Yolandas-MBP:calcSimple liuyuanyuan$ make rm -f calc lex.yy.c calc.tab.c calc.tab.h bison -d calc.y flex calc.l cc -o calc calc.tab.c lex.yy.c -lm Yolandas-MBP:calcSimple liuyuanyuan$ ls -l total 272 -rw-r--r--@ 1 liuyuanyuan staff 157 8 13 09:53 Makefile -rwxr-xr-x 1 liuyuanyuan staff 24600 8 14 12:00 calc -rw-r--r--@ 1 liuyuanyuan staff 507 8 13 10:01 calc.l -rw-r--r-- 1 liuyuanyuan staff 42011 8 14 12:00 calc.tab.c -rw-r--r-- 1 liuyuanyuan staff 2143 8 14 12:00 calc.tab.h -rw-r--r--@ 1 liuyuanyuan staff 731 8 13 23:04 calc.y -rw-r--r-- 1 liuyuanyuan staff 44590 8 14 12:00 lex.yy.c Yolandas-MBP:calcSimple liuyuanyuan$ ./calc A simple calculator. 1+2 3
.png)
