這篇文章主要講解了“l(fā)inux bison的作用是什么”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“l(fā)inux bison的作用是什么”吧！

創(chuàng)新互聯(lián)專注于沾化網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。 熱誠為您提供沾化營銷型網(wǎng)站建設(shè)，沾化網(wǎng)站制作、沾化網(wǎng)頁設(shè)計(jì)、沾化網(wǎng)站官網(wǎng)定制、重慶小程序開發(fā)服務(wù)，打造沾化網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供沾化網(wǎng)站排名全網(wǎng)營銷落地服務(wù)。

在linux中，bison是用來生成語法分析器程序的工具，它可以將用戶提供的語法規(guī)則轉(zhuǎn)化成一個(gè)語法分析器；bison需要和flex（詞法分析器）配合使用來處理復(fù)雜的文件解析工作。通過給定語法的產(chǎn)生式開始，bison會(huì)通過算法，最終構(gòu)造得到動(dòng)作表，然后利用這個(gè)動(dòng)作表去解析句子。

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會(huì)通過算法，最終構(gòu)造得到動(dòng)作表，然后利用這個(gè)動(dòng)作表去解析句子。具體來說，bison 讀取用戶提供的語法的產(chǎn)生式，生成一個(gè) C 語言格式的 LALR(1) 動(dòng)作表，并將其包含進(jìn)一個(gè)名為yyparse的 C 函數(shù)，這個(gè)函數(shù)的作用就是利用這個(gè)動(dòng)作表來解析 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=%6d\n", 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)容會(huì)被直接復(fù)制到生成.c文件的開頭部分。

包含%option選項(xiàng)

%option noyywrap /* 定義段中包含了option選項(xiàng)*/

%{
#include "cal.tab.h"
extern int yylval;
%}

規(guī)則段%%...%%之間部分，為一系列匹配模式(正則表達(dá)式)和動(dòng)作(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代碼，會(huì)被原樣復(fù)制到c文件中，一般這里定義一些輔助函數(shù)等。

int terror(chr *s)
{
    printf("%s\n", s);
    return 0;
}

2 bison(yacc, parser)文件內(nèi)容結(jié)構(gòu)（*.y ,分3部分，%%分隔）

/*P1: declarations 定義段*/
%{

%}
 
%%
/*P2: grammar rules 規(guī)則段(rule-action)*/
    
     A: a1  {  語義動(dòng)作1 }
	  | a2  {  語義動(dòng)作2 }
	  | …
	  | an  {  語義動(dòng)作n }
	  | b  //沒有{…},則使用缺省的語義動(dòng)作       
	; //產(chǎn)生式結(jié)束標(biāo)記
    //語義動(dòng)作一般是在產(chǎn)生式右部分析完，歸約動(dòng)作進(jìn)行前執(zhí)行。
    A→ a1 | a2 |  … | an | b 
%%

/* P3: supporting C routines 用戶輔助程序段(C函數(shù)) */

定義段可以分為兩部分：

1. %{ 和%}之間的部分，C語言編寫的，包括頭文件include、宏定義、全局變量定義、函數(shù)聲明等;

2. 對(duì)文法的終結(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)先級(jí)低，最后定義的優(yōu)先級(jí)最高，同時(shí)定義的優(yōu)先級(jí)想通過。  
%left表示左結(jié)合，%right表示右結(jié)合；  
%nonassoc 表示不可結(jié)合（即它定義的終結(jié)符不能連續(xù)出現(xiàn)。例如<，如果文法中不允許出現(xiàn)形如a
%left AA BB  
%nonassoc CC  
%right DD  
表示優(yōu)先級(jí)關(guān)系為：AA=BB注意：也可以于%prec來結(jié)合使用來改變token的優(yōu)先級(jí)和結(jié)合性 例如： :'-' expr %prec NEG { $$ = -$2; };  

%union 聲明語法符號(hào)的語義值類型的集合，  
bison中每個(gè)符號(hào)包括記號(hào)和非終結(jié)符都有一個(gè)不同數(shù)據(jù)類型的語義值，并使用yylval變量在移進(jìn)和歸約中傳遞這些值，YYSTYPE（宏定義）為yylval的類型，默認(rèn)為int；  
我們使用%union來重新定義符號(hào)的類型  
%union  
{  
int iValue; /* integer value */  
char sIndex; /* symbol table index */  
nodeType *nPtr; /* node pointer */  
};  

%type 定義非終結(jié)符其屬性值的類型。  
%type sym1 sym2  
%type sym3  

%start 指定文法的開始的文法符號(hào)（非終結(jié)符），是最終需要規(guī)約而成的符號(hào)。  
定義形式為：%start startsym ， 其中startsym為文法的開始符號(hào)。  
如果不使用%start定義文法開始符號(hào)，則默認(rèn)在第二部分規(guī)則段中定義的第一條生產(chǎn)式規(guī)則的左部非終結(jié)符為開始符號(hào)。

規(guī)則段由rule(語法規(guī)則)和action(包括C代碼)組成。

bison規(guī)則基本是BNF，做了一點(diǎn)簡化以易于輸入。

規(guī)則中目標(biāo)或非終端符放在左邊，后跟一個(gè)冒號(hào)：然后是產(chǎn)生式的右邊，之后是對(duì)應(yīng)的動(dòng)作（用{}包含）。

%%
  program: program expr '\n' { printf("%d\n", $2); }
  ;

  expr: INTEGER {$$ = $1; }
           | expr '+' expr { $$ = $1 + $3; }
           | expr '-' expr { $$ = $1 - $3}
  ;
%%

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

用戶輔助程序段為C代碼，會(huì)被原樣復(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    
    void yyerror(char*);
    int yylex(void);
	
    int sym[26];
%}

%%
program:
    program statement '\n'
    |
    ;
statement:
     expr    {printf("%d\n", $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, "%s\n", 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

感謝各位的閱讀，以上就是“l(fā)inux bison的作用是什么”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對(duì)linux bison的作用是什么這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！