Flex & Bison 開始

語言: CN / TW / HK

Flex 與 Bison 是為編譯器和直譯器的程式設計人員特別設計的工具:

  • Flex 用於詞法分析(lexical analysis,或稱 scanning),把輸入分割成一個個有意義的詞塊,稱為記號(token)。
  • Bison 用於語法分析(syntax analysis,或稱 parsing),確定這些記號是如何彼此關聯的。

例如,如下程式碼片段:

alpha = beta + gamma;

詞法分析把這段程式碼分解為這樣一些記號: alpha , = , beta , + , gamma , ; 。接著語法分析確定了 beta + gamma 是一個表示式,而這個表示式被賦給了 alpha

不過後來它們在其他應用領域被證明也非常有效。任何應用程式,尤其文字處理,只要在其輸入中尋找特定的模式,或者它使用命令語言作為輸入,都適合使用 Flex 與 Bison。

例如,SQL 分析:

在編譯器結構中,詞法分析器、語法分析器是編譯器前端的主要組成部分。大多數編譯器組織成三個主要的階段:前端、優化器和後端。前端專注於理解源語言程式,將其轉換為某種中間表示(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 個人實踐的經驗分享,可關注公眾號!