linux bison的作用是什么

206次閱讀

共計 6283 個字符，預計需要花費 16 分鐘才能閱讀完成。

這篇文章主要講解了“linux bison 的作用是什么”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著丸趣 TV 小編的思路慢慢深入，一起來研究和學習“linux bison 的作用是什么”吧！

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

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++; }

 yylex();
 printf(lines=%6d words=%6d chars=%6d\n , 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
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(%s\n , 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 表示不可結合（即它定義的終結符不能連續出現。例如，如果文法中不允許出現形如 a b c 的句子，則就是不可結合的）

%left AA BB
%nonassoc CC
%right DD
表示優先級關系為：AA=BB CC DD，表示結核性為：AA\BB 左結合，DD 右結合，CC 不可結合。
注意：也可以于 %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
%type sindex sym3

%start 指定文法的開始的文法符號（非終結符），是最終需要規約而成的符號。
定義形式為：%start startsym，其中 startsym 為文法的開始符號。
如果不使用 %start 定義文法開始符號，則默認在第二部分規則段中定義的第一條生產式規則的左部非終結符為開始符號。

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

bison 規則基本是 BNF，做了一點簡化以易于輸入。

規則中目標或非終端符放在左邊，后跟一個冒號：然后是產生式的右邊，之后是對應的動作（用 {} 包含）。

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

 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.
3

感謝各位的閱讀，以上就是“linux bison 的作用是什么”的內容了，經過本文的學習后，相信大家對 linux bison 的作用是什么這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是丸趣 TV，丸趣 TV 小編將為大家推送更多相關知識點的文章，歡迎關注！

正文完