<input id="ohw05"></input>
  • <table id="ohw05"><menu id="ohw05"></menu></table>
  • <var id="ohw05"></var>
  • <code id="ohw05"><cite id="ohw05"></cite></code>
    <label id="ohw05"></label>
    <var id="ohw05"></var>
  • 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 分析:

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

    posted @ 2022-06-25 21:13  GoCodingInMyWay  閱讀(108)  評論(0編輯  收藏  舉報
    国产美女a做受大片观看