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