Flex & Bison 開始
Flex 與 Bison 是為編譯器和解釋器的編程人員特別設計的工具：
- Flex 用于詞法分析（lexical analysis，或稱 scanning），把輸入分割成一個個有意義的詞塊，稱為記號（token）。
- Bison 用于語法分析（syntax analysis，或稱 parsing），確定這些記號是如何彼此關聯的。
例如，如下代碼片段：
alpha = beta + gamma;
詞法分析把這段代碼分解為這樣一些記號：alpha, =, beta, +, gamma, ;。接著語法分析確定了 beta + gamma 是一個表達式，而這個表達式被賦給了 alpha。
不過后來它們在其他應用領域被證明也非常有效。任何應用程序，尤其文本處理，只要在其輸入中尋找特定的模式，或者它使用命令語言作為輸入，都適合使用 Flex 與 Bison。
例如，SQL 分析：
- MySQL: C++ 詞法分析, Bison 語法分析
- PostgreSQL: Flex 詞法分析, Bison 語法分析
在編譯器結構中，詞法分析器、語法分析器是編譯器前端的主要組成部分。大多數編譯器組織成三個主要的階段：前端、優化器和后端。前端專注于理解源語言程序，將其轉換為某種中間表示（IR）。而 Flex 與 Bison 就是給編譯器前端設計出的工具。
起源
bison 來源于 yacc，一個由 Stephen C. Johnson 于 1975 年到 1978 年期間在貝爾實驗室完成的語法分析器生成程序。正如它的名字（yacc 是 yet another compiler compiler 的縮寫）所暗示的那樣，那時很多人都在編寫語法分析器生成程序。Johnson 的工具基于 D. E. Knuth 所研究的語法分析理論（因此 yacc 十分可靠）和方便的輸入語法。這使得 yacc 在 Unix 用戶中非常流行，盡管當時 Unix 所遵循的受限版權使它只能夠被使用在學術界和貝爾系統里。大約在 1985 年，Bob Corbett，一個加州伯克利大學的研究生，使用改進的內部算法再次實現了 yacc 并演變成為伯克利 yacc。由于這個版本比貝爾實驗室的 yacc 更快并且使用了靈活的伯克利許可證，它很快成為最流行的 yacc。來自自由軟件基金會（Free Software Foundation）的 Richard Stallman 改寫了 Corbett 的版本并把它用于 GNU 項目中，在那里，它被添加了大量的新特性并演化成為當前的 bison。bison 現在作為 FSF 的一個項目而被維護，且它基于 GNU 公共許可證進行發布。
在 1975 年，Mike Lesk 和暑期實習生 Eric Schmidt 編寫了 lex，一個詞法分析器生成程序，大部分編程工作由 Schmidt 完成。他們發現 lex 既可以作為一個獨立的工具，也可以作為 Johnson 的 yacc 的協同程序。lex 因此變得十分流行，盡管它運行起來有一點慢并且有很多錯誤。（不過 Schmidt 后來在計算機行業里擁有一份非常成功的事業，他現在，2009年，是 Google 的 CEO。2010 年 CEO 移交了，繼續擔任 Google 董事長。）
大概在 1987 年，Lawrence Berkeley 實驗室的 Vern Paxson 把一種用 ratfor（當時流行的一種擴展的 Fortran 語言）寫成的 lex 版本改寫為 C 語言的，被稱為 flex，意思是“快速詞法分析器生成程序”（Fast Lexical Analyzer Generator）。由于它比 AT&T 的 lex 更快速和可靠，并且就像伯克利的 yacc 那樣基于伯克利許可證，它最終也超越了原來的 lex。flex 現在是 SourceForge 的一個項目，依然基于伯克利許可證。
安裝
大多數 Linux 和 BSD 系統自帶 flex 和 bison 作為系統的基礎部分。如果你的系統沒有包含它們，安裝它們也很容易。
例如在 Ubuntu/Debian 系統，可以直接 apt 安裝：
# Ubuntu 20
$ sudo apt install flex bison -y
$ flex -V
flex 2.6.4
$ bison -V
bison (GNU Bison) 3.5.1
范例
范例請見 https://github.com/ikuokuo/start-ai-compiler/tree/main/books/flex_bison ，都來自結語給出的 Flex & Bison 一書。
范例指導了我們如何使用 Flex & Bison 開發一個計算器，并能支持變量、過程、循環和條件表達式，有內置函數，也支持用戶自定義函數。
如下編譯所有范例：
cd books/flex_bison/
# 編譯 release
make
# 編譯 debug
make debug
# 清理
make clean
范例程序會輸出進 _build 目錄，如下執行：
$ ./_build/linux-x86_64/release/1-5_calc/bin/1-5_calc
> (1+2)*3 + 4/2
= 11
$ ./_build/linux-x86_64/release/3-5_calc/bin/3-5_calc
> let sq(n)=e=1; while |((t=n/e)-e)>.001 do e=avg(e,t);;
Defined sq
> let avg(a,b)=(a+b)/2;
Defined avg
> sq(10)
= 3.162
> sqrt(10)
= 3.162
> sq(10)-sqrt(10)
= 0.000178
如果只編譯某一范例：
cd ch01/1-1_wc/
# 編譯 release
make -j8
# 編譯 debug
make -j8 args="debug"
# 清理
make clean
程序
Flex 與 Bison 程序都是由三部分構成：定義部分、規則部分和用戶子例程。
... definition section ...
%%
... rules section ...
%%
... user subroutines section ...
Flex 規則部分基于正則表達式，Bison 則基于 BNF (Backus-Naur Form) 文法。詳細用法，請依照結語給出的 Flex & Bison 一書，及范例。
這里不做過多闡述，本文旨在讓大家了解有 Flex 與 Bison 這樣工具，以及它們能幫助我們完成什么樣的工作。
結語
Flex 與 Bison 是詞法分析器（Scanner）與語法分析器（Parser）的自動生成工具，應用了形式語言理論的結果。這些工具同樣可用于文本搜索、網站過濾、文字處理和命令行語言解釋器。
本文內容主要來源于以下書籍：
GoCoding 個人實踐的經驗分享，可關注公眾號！