《編譯原理實踐與指導教程》——1.2 實驗指導

本節書摘來自華章計算機《編譯原理實踐與指導教程》一書中的第1章，第1.2節,作者：許暢 陳嘉 朱曉瑞著， 更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。

詞法分析和文法分析這兩塊，可以說是在整個編譯器當中被自動化得最好的部分。也就是說即使沒有任何的理論基礎，在掌握了工具的用法之後，也可以在短時間内做出功能很全很棒的詞法分析程式和文法分析程式。當然這并不意味着，詞法分析和文法分析部分的理論基礎并不重要。恰恰相反，這一部分被認為是計算機理論在工程實踐中最成功的應用之一，對它的介紹也是編譯理論課中的重點。但本節指導内容的重點不在于理論而在于工具的使用。

本節指導内容将分别介紹詞法分析工具gnu flex和文法分析工具gnu bison。如前所述，完成實驗一并不需要太多的理論基礎，隻要看完并掌握了本節的大部分内容即可完成實驗一。

1.2.1　詞法分析概述

詞法分析程式的主要任務是将輸入檔案中的字元流組織成為詞法單元流，在某些字元不符合程式設計語言詞法規範時要有能力報告相應的錯誤。詞法分析程式是編譯器所有子產品中唯一讀入并處理輸入檔案中每一個字元的子產品，它使得後面的文法分析階段能在更高抽象層次上運作，而不必糾結于字元串處理這樣的細節問題。

進階程式設計語言大多采用英文作為輸入方式，而英文有個非常好的性質，就是它比較容易斷詞：相鄰的英文字母一定屬于同一個詞，而字母與字母之間插入任何非字母的字元（如空格、運算符等）就可以将一個詞斷成兩個詞。判斷一個詞是否符合語言本身的詞法規範也相對簡單，一個直接的辦法是我們可以事先列一張搜尋表，将所有符合詞法規範的字元串都存放在表中，每次我們從輸入檔案中斷出一個詞後，通過查找這張表就可以判斷該詞究竟合法還是不合法。

正因為詞法分析任務的難度不高，是以在實用的編譯器中它常常是手工寫成，而非使用工具生成。例如，我們下面要介紹的這個工具gnu flex原先就是為了幫助gcc進行詞法分析而被開發出來的，但在版本4.0之後，gcc的詞法分析器已經一律改為手寫了。不過，實驗一要求使用工具來做，而詞法分析程式生成工具所基于的理論基礎，是計算理論中最入門的内容：正規表達式（regular expression）和有限狀态自動機（finite state automata）。

一個正規表達式由特定字元串構成，或者由其他正規表達式通過以下三種運算得到：

1）并運算（union）：兩個正規表達式r和s的并記作r | s，意為r或s都可以被接受。

2）連接配接運算（concatenation）：兩個正規表達式r和s的連接配接記作rs，意為r之後緊跟s才可以被接受。

3）kleene閉包（kleene closure）：一個正規表達式r的kleene閉包記作r*，它表示：e | r | rr | rrr | …。

有關正規表達式的内容在課本的理論部分已讨論過。正規表達式之是以被人們廣泛應用，一方面是因為它表達能力足夠強（基本上可以表示所有的詞法規則），同時還易于書寫和了解；另一方面是因為判斷一個字元串是否被一個特定的正規表達式接受可以做到非常高效（線上性時間内即可完成）。比如，我們可以将一個正規表達式轉化為一個nfa（即不确定的有限狀态自動機），然後将這個nfa轉化為一個dfa（即确定的有限狀态自動機），再将轉化好的dfa進行化簡，之後我們就可以通過模拟這個dfa的運作對輸入串進行識别了。具體的nfa和dfa的含義以及如何進行正規表達式、nfa及dfa之間的轉化等，請參考課本的理論部分。這裡我們僅需要知道，前面所述的所有轉化和識别工作，都可以由工具自動完成。而我們所需要做的僅僅是為工具提供作為詞法規範的正規表達式。

1.2.2　gnu flex介紹

flex的前身是lex。lex是1975年由mike lesk和當時還在at&t做暑期實習的eric schmidt共同完成的一款基于unix環境的詞法分析程式生成工具。雖然lex很出名并被廣泛使用，但它的低效和諸多問題也使其頗受诟病。後來伯克利實驗室的vern paxson使用c語言重寫了lex，并将這個新的程式命名為flex（意為fast lexical analyzer generator）。無論在效率上還是在穩定性上，flex都遠遠好于它的前身lex。我們在linux下使用的是flex在gnu license下的版本，稱作gnu flex。

gnu flex在linux下的安裝非常簡單。可以去它的官方網站下載下傳安裝包自行安裝，不過在基于debian的linux系統下，更簡單的安裝方法是直接在指令行輸入如下指令：

雖然版本不一樣，但gnu flex的使用方法與課本上介紹的lex基本相同。首先，需要自行完成包括詞法規則等在内的flex代碼。至于如何編寫這部分代碼我們在後面會提到，現在先假設這部分寫好的代碼名為lexical.l。随後，我們使用flex對該代碼進行編譯：

編譯好的結果會儲存在目前目錄下的lex.yy.c檔案中。打開這個檔案你會發現，該檔案本質上就是一份c語言的源代碼。這份源代碼裡目前對我們有用的函數隻有一個，叫做yylex()，該函數的作用就是讀取輸入檔案中的一個詞法單元。我們可以再為它編寫一個main函數：

這個main函數通過指令行讀入若幹個參數，取第一個參數為其輸入檔案名并嘗試打開該輸入檔案。如果檔案打開失敗則退出，如果成功則調用yylex()進行詞法分析。其中，變量yyin是flex内部使用的一個變量，表示輸入檔案的檔案指針，如果不設定它，那麼flex會将它自動設定為stdin（即标準輸入，通常連接配接到鍵盤）。注意，如果将main函數獨立設為一個檔案，則需要聲明yyin為外部變量：

将這個main函數單獨放到一個檔案main.c中（也可以直接放入lexical.l中的使用者自定義代碼部分，這樣就可以不必聲明yyin；甚至可以不寫main函數，因為flex會自動給你配一個，但不推薦這麼做），然後編譯這兩個c源檔案。我們将輸出程式命名為scanner：

注意編譯指令中的“-lfl”參數不可缺少，否則gcc會由于缺少庫函數而報錯。之後我們就可以使用這個scanner程式進行詞法分析了。例如，想要對一個測試檔案test.cmm進行詞法分析，隻需要在指令行輸入：

就可以得到你想要的結果了。

1.2.3　flex：編寫源代碼

以上介紹的是使用flex建立詞法分析程式的基本步驟。在整個建立過程中，最重要的檔案無疑是你所編寫的flex源代碼，它決定了你的詞法分析程式的一切行為。接下來我們介紹如何編寫flex源代碼。

flex源代碼檔案包括三個部分，由“%%”隔開，如下所示：

第一部分為定義部分，實際上就是給後面某些可能經常用到的正規表達式取一個别名，進而簡化詞法規則的書寫。定義部分的格式一般為：

其中name是名字，definition是任意的正規表達式（正規表達式該如何書寫後面會介紹）。例如，下面的這段代碼定義了兩個名字：digit和letter，前者代表0到9中的任意一個數字字元，後者則代表任意一個小寫字母、大寫字母或下劃線：

flex源代碼檔案的第二部分為規則部分，它由正規表達式和相應的響應函數組成，其格式為：

其中pattern為正規表達式，其書寫規則與前面部分的正規表達式的定義相同。而action則為将要進行的具體操作，這些操作可以用一段c代碼表示。flex将按照這部分給出的内容依次嘗試每一個規則，盡可能比對最長的輸入串。如果有些内容不比對任何規則，flex預設隻将其拷貝到标準輸出，想要修改這個預設行為隻需要在所有規則的最後加上一條“.”（即比對任何輸入）規則，然後在其對應的action部分書寫你想要的行為即可。

例如，下面這段flex代碼在遇到輸入檔案中包含一串數字時，會将該數字串轉化為整數值并列印到螢幕上：

其中變量yytext的類型為char*，它是flex為我們提供的一個變量，裡面儲存了目前詞法單元所對應的詞素。函數atoi()的作用是把一個字元串表示的整數轉化為int類型。

flex源代碼檔案的第三部分為使用者自定義代碼部分。這部分代碼會被原封不動地拷貝到lex.yy.c中，以友善使用者自定義所需要執行的函數（之前我們提到過的main函數也可以寫在這裡）。值得一提的是，如果使用者想要對這部分用到的變量、函數或者頭檔案進行聲明，可以在前面的定義部分（即flex源代碼檔案的第一部分）之前使用“%{”和“%}”符号将要聲明的内容添加進去。被“%{”和“%}”所包圍的内容也會被一并拷貝到lex.yy.c的最前面。

下面通過一個簡單的例子來說明flex源代碼該如何書寫。我們知道unix/linux下有一個常用的文字統計工具wc，它可以統計一個或者多個檔案中的（英文）字元數、單詞數和行數。利用flex我們可以快速地寫出一個類似的文字統計程式：

其中yyleng是flex為我們提供的變量，你可以将其了解為strlen(yytext)。我們用變量chars記錄輸入檔案中的字元數、words記錄單詞數、lines記錄行數。上面這段程式很好了解：每遇到一個換行符就把行數加一，每識别出一個單詞就把單詞數加一，每讀入一個字元就把字元數加一。最後在main函數中把chars、words和lines的值全部列印出來。需要注意的是，由于在規則部分裡我們沒有讓yylex()傳回任何值，是以在main函數中調用yylex()時，可以不嵌套外層的while循環。

真正的wc工具可以一次傳入多個參數進而統計多個檔案。為了能夠讓這個flex程式對多個檔案進行統計，我們可以修改main函數如下：

其中yyrestart(f)函數是flex提供的庫函數，它可以讓flex将其輸入檔案的檔案指針yyin設定為f（當然你也可以像前面一樣手動設定令yyin = f）并重新初始化該檔案指針，令其指向輸入檔案的開頭。

1.2.4　flex：書寫正規表達式

flex源代碼中無論是定義部分還是規則部分，正規表達式都在其中扮演了重要的作用。那麼，如何在flex源代碼中書寫正規表達式呢？我們下面介紹一些規則：

1）符号“.”比對除換行符“n”之外的任何一個字元。

3）符号“^”用在方括号之外則會比對一行的開頭，符号“$”用于比對一行的結尾，符号“<>”用于比對檔案的結尾。

4）符号“{”和“}”含義比較特殊。如果花括号之内包含了一個或者兩個數字，則代表花括号之前的那個表達式需要出現的次數。例如，a{5}會比對aaaaa，a{1,3}則會比對a、aa或者aaa。如果花括号之内是一個在flex源代碼的定義部分定義過的名字，則表示那個名字對應的正規表達式。例如，在定義部分如果定義了letter為[a-za-z]，則{letter}{1,3}表示連續的一至三個英文字母。

5）符号“”為kleene閉包操作，比對零個或者多個表達式。例如{letter}表示零個或者多個英文字母。

6）符号“+”為正閉包操作，比對一個或者多個表達式。例如{letter}+表示一個或者多個英文字母。

7）符号“?”比對零個或者一個表達式。例如，表達式-?[0-9]+表示前面帶一個可選的負号的數字串。無論是*、+還是?，它們都隻對其最鄰近的那個字元生效。例如abc+表示ab後面跟一個或多個c，而不表示一個或者多個abc。如果你要比對後者，則需要使用小括号“(”和“)”将這幾個字元括起來：(abc)+。

8）符号“|”為選擇操作，比對其之前或之後的任一表達式。例如，faith | hope | charity表示這三個串中的任何一個。

9）符号“”用于表示各種轉義字元，與c語言字元串裡“”的用法類似。例如，“n”表示換行，“t”表示制表符，“*”表示星号，“\”代表字元“”等。

10）符号“"”（英文引号）将逐字比對被引起來的内容（即無視各種特殊符号及轉義字元）。例如，表達式"…"就表示三個點而不表示三個除換行符以外的任意字元。

11）符号“/”會檢視輸入字元的上下文，例如，x/y識别x僅當在輸入檔案中x之後緊跟着y，0/1可以比對輸入串01中的0但不比對輸入串02中的0。

12）任何不屬于上面介紹過的有特殊含義的字元在正規表達式中都僅比對該字元本身。

下面我們通過幾個例子來練習一下flex源代碼裡正規表達式的書寫：

1）帶一個可選的正号或者負号的數字串，可以這樣寫：[+–]?[0-9]+。

2）帶一個可選的正号或者負号以及一個可選的小數點的數字串，表示起來要困難一些，可以考慮下面幾種寫法：

a）[+–]?[0-9.]+會比對太多額外的模式，比如1.2.3.4；

b）[+–]?[0-9]+.?[0-9]+會漏掉某些模式，比如12.或者.12；

c）[+–]?[0-9]*.?[0-9]+會漏掉12.；

d）[+–]?[0-9]+.?[0-9]*會漏掉.12；

e）[+–]?[0-9].?[0-9]會多比對空串或者隻有一個小數點的串；

f）正确的寫法是：[+–]?([0-9]*.?[0-9]+|[0-9]+.)。

3）假設我們現在做一個彙編器，目标機器的cpu中有32個寄存器，編号為0…31。彙編源代碼可以使用r後面加一個或兩個數字的方式來表示某一個寄存器，例如r15表示第15号寄存器，r0或r00表示第0号寄存器，r7或者r07表示第7号寄存器等。現在我們希望識别彙編源代碼中所有可能的寄存器表示，可以考慮下面幾種寫法：

a）r[0-9]+可以比對r0和r15，但它也會比對r99999，目前世界上還不存在cpu能擁有一百萬個寄存器。

b）r[0-9]{1,2}同樣會比對一些額外的表示，例如r32和r48等。

c）r(0-2?|[4-9]|(3(0|1)?))是正确的寫法，但其可讀性比較差。

d）正确性毋庸置疑并且可讀性最好的寫法應該是：r0 | r00 | r1 | r01 | r2 | r02 | r3 | r03 | r4 | r04 | r5 | r05 | r6 | r06 | r7 | r07 | r8 | r08 | r9 | r09 | r10 | r11 | r12 | r13 | r14 | r15 | r16 | r17 | r18 | r19 | r20 | r21 | r22 | r23 | r24 | r25 | r26 | r27 | r28 | r29 | r30 | r31，但這樣寫的話可擴充性又非常差，如果目标機器上有128甚至256個寄存器呢？

1.2.5　flex：進階特性

前面介紹的flex内容已足夠幫助我們完成實驗一的詞法分析部分。下面介紹一些flex裡面的進階特性，能讓你在使用flex的過程中感到更友善和靈活。這部分内容是可選的，跳過也不會對實驗一的完成産生負面影響。

yylineno選項

在寫編譯器程式的過程中，經常會需要記錄行号，以便在報錯時提示輸入檔案的哪一行出現了問題。為了能記錄這個行号，我們可以自己定義某個變量，例如lines，來記錄詞法分析程式目前讀到了輸入檔案的哪一行。每當識别出“n”，我們就讓lines = lines + 1。

實際上，flex内部已經為我們提供了類似的變量，叫做yylineno。我們不必去維護yylineno的值，它會在每行結束自動加一。不過，預設狀态下它并不開放給使用者使用。如果我們想要讀取yylineno的值，則需要在flex源代碼的定義部分加入語句“%option yylineno”。

需要說明的是，雖然yylineno會自動增加，但當我們在詞法分析過程中調用yyrestart()函數讀取另一個輸入檔案時它卻不會重新被初始化，是以我們需要自行添加初始化語句yylineno = 1。

輸入緩沖區

課本上介紹的詞法分析程式的工作原理都是在模拟一個dfa的運作。這個dfa每次讀入一個字元，然後根據狀态之間的轉換關系決定下一步應該轉換到哪個狀态。事實上，實用的詞法分析程式很少會從輸入檔案中逐個讀入字元，因為這樣需要進行大量的磁盤操作，效率較低。更加高效的辦法是一次讀入一大段輸入字元，并将其儲存在專門的輸入緩沖區中。

在flex中，所有的輸入緩沖區都有一個共同的類型，叫做yy_buffer_state。你可以通過yy_create_buffer()函數為一個特定的輸入檔案開辟一塊輸入緩沖區，例如，

其中yy_buf_size是flex内部的一個常數，通過調用yy_switch_to_buffer()函數可以讓詞法分析程式到指定的輸入緩沖區中讀字元，調用yy_flush_buffer()函數可以清空緩沖區中的内容，而調用yy_delete_buffer()則可以删除一個緩沖區。

如果你的詞法分析程式要支援檔案與檔案之間的互相引用（例如c語言中的#include），你可能需要在詞法分析的過程中頻繁地使用yyrestart()切換目前的輸入檔案。在切換到其他輸入檔案再切換回來之後，為了能繼續之前的詞法分析任務，你需要無損地保留原先輸入緩沖區的内容，這就需要使用一個棧來暫存目前輸入檔案的緩沖區。雖然flex也提供相關的函數來幫助你做這件事情，但這些函數的功能比較弱，建議自己寫更好。

flex庫函數input

flex庫函數input()可以從目前的輸入檔案中讀入一個字元，這有助于你不借助正規表達式來實作某些功能。例如，下面這段代碼在輸入檔案中發現雙斜線“//”後，将從目前字元開始一直到行尾的所有字元全部丢棄掉：

flex庫函數unput(char c)可以将指定的字元放回到輸入緩沖區中，這對于宏定義等功能的實作是很友善的。例如，假設之前定義過一個宏#define buffer_len 1024，當在輸入檔案中遇到字元串buffer_len時，下面這段代碼将該宏所對應的内容放回輸入緩沖區：

flex宏reject可以幫助我們識别那些互相重疊的模式。當我們執行reject之後，flex會進行一系列的操作，這些操作的結果相當于将yytext放回輸入之内，然後試圖去比對目前規則之後的那些規則。例如，考慮下面這段flex源代碼：

這段代碼會統計輸入檔案中所有的pink、ink和pin出現的個數，即使這三個單詞之間互有重疊。

flex還有更多的特性，感興趣的讀者可以參考其使用者手冊。

1.2.6　詞法分析提示

為了完成實驗一，首先需要閱讀c––語言文法（附錄a），包括文法定義和補充說明。除了int、float和id這三個詞法單元需要你自行為其書寫正規表達式之外，剩下的詞法單元都沒有難度。

閱讀完c––語言文法，對c––的詞法有大概的了解之後，就可以開始編寫flex源代碼了。在敲入所有的詞法之後，為了能檢驗你的詞法分析程式是否工作正常，你可以暫時向螢幕列印目前的詞法單元的名稱，例如：

為了能夠報告錯誤類型a，你可以在所有規則的最後增加類似于這樣的一條規則：

完成flex源代碼的編寫之後，使用前面介紹過的方法将其編譯，就可以自己書寫一些小規模的輸入檔案來測試你的詞法分析程式了。一定要確定你的詞法分析程式的正确性。如果詞法分析這裡出了問題而沒有檢查出來，到了後面文法分析時發現了前面出現的問題再回頭調試，那将增加許多不必要的麻煩。為了使你在編寫flex源代碼時少走彎路，下面給出幾條建議：

1）留意空格和回車的使用。如果不注意，有時很容易讓本應是空白符的空格或者回車變成正規表達式的一部分，有時又很容易讓本應是正規表達式一部分的空格或回車變成flex源代碼裡的空白符。

2）正規表達式和其所對應的動作之間，永遠不要插入空行。

3）如果對正規表達式中的運算符優先級有疑問，那就不要吝啬使用括号來確定正規表達式的優先級确實是你想要的。

4）使用花括号括起每一段動作，即使該動作隻包含有一行代碼。

5）在定義部分我們可以為許多正規表達式取别名，這一點要好好利用。别名可以讓後面的正規表達式更加容易閱讀、擴充和調試。

6）在正規表達式中引用之前定義過的某個别名（例如digit）時，時刻謹記該别名一定要用花括号“{”和“}”括起來。

1.2.7　文法分析概述

詞法分析的下一階段是文法分析。文法分析程式的主要任務是讀入詞法單元流、判斷輸入程式是否比對程式設計語言的文法規範，并在比對規範的情況下建構起輸入程式的靜态結構。文法分析使得編譯器的後續階段看到的輸入程式不再是一串字元流或者單詞流，而是一個結構整齊、處理友善的資料對象。

文法分析與詞法分析有很多相似之處：它們的基礎都是形式語言理論，它們都是計算機理論在工程實踐中最成功的應用，它們都能被高效地完成，它們的建構都可以被工具自動化完成。不過，由于文法分析本身要比詞法分析複雜得多，手寫一個文法分析程式的代價太大，是以目前絕大多數實用的編譯器在文法分析這裡都是使用工具幫助完成的。

正規表達式難以進行任意大的計數，是以很多在程式設計語言中常見的結構（例如，比對的括号）無法使用正則文法進行表示。為了能夠有效地對常見的文法結構進行表示，人們使用了比正則文法表達能力更強的上下文無關文法（context free grammar或cfg）。然而，雖然上下文無關文法在表達能力上要強于正則語言，但在判斷某個輸入串是否屬于特定cfg的問題上，時間效率最好的算法也要o(n3)，這樣的效率讓人難以接受。是以，現代程式設計語言的文法大多屬于一般cfg的一個足夠大的子集，比較常見的子集有ll(k)文法以及lr(k)文法。判斷一個輸入是否屬于這兩種文法都隻需要線性時間。

上下文無關文法g在形式上是一個四元組：終結符号（也就是詞法單元）集合t、非終結符号集合nt、初始符号s以及産生式集合p。産生式集合p是一個文法的核心，它通過産生式定義了一系列的推導規則，從初始符号出發，基于這些産生式，經過不斷地将非終結符替換為其他非終結符以及終結符，即可得到一串符合文法規約的詞法單元。這個替換和推導的過程可以使用樹形結構表示，稱作文法樹。事實上，文法分析的過程就是把詞法單元流變成文法樹的過程。盡管在之前曾經出現過各式各樣的算法，但目前最常見的建構文法樹的技術隻有兩種：自頂向下方法和自底向上方法。我們下面将要介紹的工具bison所生成的文法分析程式就采用了自底向上的lalr(1)分析技術（通過一定的設定還可以讓bison使用另一種稱為glr的分析技術，不過對該技術的介紹已經超出了我們讨論的範圍）。而其他的某些文法分析工具，例如基于java語言的jtb生成的文法分析程式，則是采用了自頂向下的ll(1)分析技術。當然，具體的工具采用哪一種技術這種細節，對于工具的使用者來講都是完全屏蔽的。和詞法分析程式的生成工具一樣，工具的使用者所要做的僅僅是将輸入程式的程式設計語言的文法告訴文法分析程式生成工具，雖然工具本身不能幫助直接構造出文法樹，但我們可以通過在文法産生式中插入語義動作這種更加靈活的形式，來實作一些甚至比構造文法樹更加複雜的功能。

1.2.8　gnu bison介紹

bison的前身為基于unix的yacc。令人驚訝的是，yacc的釋出時間甚至比lex還要早。yacc所采用的lr分析技術的理論基礎早在50年代就已經由knuth逐漸建立了起來，而yacc本身則是貝爾實驗室的s.c. johnson基于這些理論在1975～1978年寫成的。到了1985年，當時在uc berkeley的一個研究所學生bob corbett在bsd下重寫了yacc，後來gnu project接管了這個項目，為其增加了許多新的特性，于是就有了我們今天所用的gnu bison。

gnu bison在linux下的安裝非常簡單，你可以去它的官方網站上下載下傳安裝包自行安裝，基于debian的linux系統下更簡單的方法同樣是直接在指令行敲入如下指令：

雖說版本不一樣，但gnu bison的基本使用方法和課本上所介紹的yacc沒有什麼不同。首先，我們需要自行完成包括文法規則等在内的bison源代碼。如何編寫這份代碼後面會提到，現在先假設這份寫好的代碼名為syntax.y。随後，我們使用bison對這份代碼進行編譯：

編譯好的結果會儲存在目前目錄下的syntax.yy.c檔案中。打開這個檔案你就會發現，該檔案本質上就是一份c語言的源代碼。事實上，這份源代碼裡目前對我們有用的函數隻有一個，叫做yyparse()，該函數的作用是對輸入檔案進行文法分析，如果分析成功沒有錯誤則傳回0，否則傳回非0。不過，隻有這個yyparse()函數還不足以讓我們的程式跑起來。前面說過，文法分析程式的輸入是一個個的詞法單元，那麼bison通過什麼方式來獲得這些詞法單元呢？事實上，bison在這裡需要使用者為它提供另外一個專門傳回詞法單元的函數，這個函數的名字正是yylex()。

函數yylex()相當于嵌在bison裡的詞法分析程式。這個函數可以由使用者自行實作，但因為我們之前已經使用flex生成了一個yylex()函數，能不能讓bison使用flex生成的yylex()函數呢？答案是肯定的。

仍以bison源代碼檔案syntax.y為例。首先，為了能夠使用flex中的各種函數，需要在bison源代碼中引用lex.yy.c：

随後在使用bison編譯這份源代碼時，我們需要加上“-d”參數：

這個參數的含義是，将編譯的結果分拆成syntax.tab.c和syntax.tab.h兩個檔案，其中.h檔案裡包含着一些詞法單元的類型定義之類的内容。得到這個.h檔案之後，下一步是修改我們的flex源代碼lexical.l，增加對syntax.tab.h的引用，并且讓flex源代碼中規則部分的每一條action都傳回相應的詞法單元，如下所示：

其中，傳回值plus和sub等都是在bison源代碼中定義過的詞法單元（如何定義它們在後文中會提到）。由于我們剛剛修改了lexical.l，需要重新将它編譯出來：

接下來重寫main函數。由于bison會在需要時自動調用yylex()，我們在main函數中也就不需要調用它了。不過，bison是不會自己調用yyparse()和yyrestart()的，是以這兩個函數仍需要我們在main函數中顯式地調用：

現在我們有了三個c語言源代碼檔案：main.c、lex.yy.c以及syntax.tab.c，其中lex.yy.c已經被syntax.tab.c引用了，是以我們最後要做的就是把main.c和syntax.tab.c放到一起進行編譯：

其中“-lfl”不要省略，否則gcc會因缺少庫函數而報錯，但“-ly”這裡一般情況下可以省略。現在我們可以使用這個parser程式進行文法分析了。例如，想要對一個輸入檔案test.cmm進行文法分析，隻需要在指令行輸入：

就可以得到你想要的結果。

1.2.9　bison：編寫源代碼

我們前面介紹了使用flex和bison聯合建立文法分析程式的基本步驟。在整個建立過程中，最重要的檔案無疑是你所編寫的flex源代碼和bison源代碼檔案，它們完全決定了所生成的文法分析程式的一切行為。flex源代碼如何進行編寫前面已經介紹過了，接下來我們介紹如何編寫bison源代碼。

同flex源代碼類似，bison源代碼也分為三個部分，其作用與flex源代碼大緻相同。第一部分是定義部分，所有詞法單元的定義都可以放到這裡；第二部分是規則部分，其中包括具體的文法和相應的語義動作；第三部分是使用者函數部分，這部分的源代碼會被原封不動地拷貝到syntax.tab.c中，以友善使用者自定義所需要的函數（main函數也可以寫在這裡，不過不推薦這麼做）。值得一提的是，如果使用者想要對這部分所用到的變量、函數或者頭檔案進行聲明，可以在定義部分（也就是bison源代碼的第一部分）之前使用“%{”和“%}”符号将要聲明的内容添加進去。被“%{”和“%}”所包圍的内容也會被一并拷貝到syntax.tab.c的最前面。

下面我們通過一個例子來對bison源代碼的結構進行解釋。一個在控制台運作可以進行整數四則運算的小程式，其文法如下所示（這裡假設詞法單元int代表flex識别出來的一個整數，add代表加号+，sub代表減号–，mul代表乘号*，div代表除号/）：

這個小程式的bison源代碼為：

這段bison源代碼以“%{”和“%}”開頭，被“%{”和“%}”包含的内容主要是對stdio.h的引用。接下來是一些以%token開頭的詞法單元（終結符）定義，如果你需要采用flex生成的yylex()的話，那麼在這裡定義的詞法單元都可以作為flex源代碼裡的傳回值。與終結符相對的，所有未被定義為%token的符号都會被看作非終結符，這些非終結符要求必須在任意産生式的左邊至少出現一次。

第二部分是書寫産生式的地方。第一個産生式左邊的非終結符預設為初始符号（你也可以通過在定義部分添加%start x來将另外的某個非終結符x指定為初始符号）。産生式裡的箭頭在這裡用冒号“:”表示，一組産生式與另一組之間以分号“;”隔開。産生式裡無論是終結符還是非終結符都各自對應一個屬性值，産生式左邊的非終結符對應的屬性值用

$$

表示，右邊的幾個符号的屬性值按從左到右的順序依次對應為$1、$2、$3等。每條産生式的最後可以添加一組以花括号“{”和“}”括起來的語義動作，這組語義動作會在整條産生式歸約完成之後執行，如果不明确指定語義動作，那麼bison将采用預設的語義動作{

= $1 }。語義動作也可以放在産生式的中間，例如a →

b { … } c，這樣的寫法等價于a → bmc，m → e { … }，其中m為額外引入的一個非終結符。需要注意的是，在産生式中間添加語義動作在某些情況下有可能會在原有文法中引入沖突，是以使用時要特别謹慎。

此時，你可能有疑問：每一個非終結符的屬性值都可以通過它所産生的那些終結符或者非終結符的屬性值計算出來，但是終結符本身的屬性值該如何得到呢？答案是：在yylex()函數中得到。因為我們的yylex()函數是由flex源代碼生成的，是以要想讓終結符帶有屬性值，就必須回頭修改flex源代碼。假設在我們的flex源代碼中，int詞法單元對應着一個數字串，那麼我們可以将flex源代碼修改為：

其中yylval是flex的内部變量，表示目前詞法單元所對應的屬性值。我們隻需将該變量的值賦成atoi(yytext)，就可以将詞法單元int的屬性值設定為它所對應的整數值了。

回到之前的bison源代碼中。在使用者自定義函數部分我們寫了兩個函數：一個很簡單的隻調用了yyparse()的main函數以及另一個沒有傳回類型并帶有一個字元串參數的yyerror()的函數。yyerror()函數會在你的文法分析程式中每發現一個文法錯誤時被調用，其預設參數為“syntax error”。預設情況下yyerror()隻會将傳入的字元串參數列印到标準錯誤輸出上，而你也可以自己重新定義這個函數，進而使它列印一些别的内容，例如，在前面我們就在該參數前面多列印了“error: ”的字樣。

現在，編譯并執行這個程式，然後在控制台輸入10 – 2 + 3，然後輸入回車，最後輸入ctrl+d結束，你會看到螢幕上列印出了計算結果11。

1.2.10　bison：屬性值的類型

在上面的例子中，每個終結符或非終結符的屬性值都是int類型。但在我們建構文法樹的過程中，我們希望不同的符号對應的屬性值能有不同的類型，而且最好能對應任意類型而不僅僅是int類型。下面我們介紹如何在bison中解決這個問題。

第一種方法是對宏yystype進行重定義。bison裡會預設所有屬性值的類型以及變量yylval的類型都是yystype，預設情況下yystype被定義為int。如果你在bison源代碼的“%{”和“%}”之間加入#define yystype float，那麼所有的屬性值就都成為了float類型。那麼如何使不同的符号對應不同的類型呢？你可以将yystype定義成一個聯合體類型，這樣你就可以根據符号的不同來通路聯合體中不同的域，進而實作多種類型的效果。

這種方法雖然可行，但在實際操作中還是稍顯麻煩，因為你每次對屬性值的通路都要自行指定哪個符号對應哪個域。實際上，bison中已經内置了其他的機制來友善你對屬性值類型的處理，一般而言我們還是更推薦使用這種方法而不是上面介紹的那種。

我們仍然還是以前面的四則運算小程式為例，來說明bison中的屬性值類型機制是如何工作的。原先這個四則運算程式隻能計算整數值，現在我們加入浮點數運算的功能。修改後的文法如下所示：

在這份文法中，我們希望詞法單元int能有整型屬性值，而float能有浮點型屬性值，其他的非終結符為了簡單起見，我們讓它們都具有雙精度型的屬性值。這份文法以及類型方案對應的bison源代碼如下：

首先，我們在定義部分的開頭使用%union{…}将所有可能的類型都包含進去。接下來，在%token部分我們使用一對尖括号< >把需要确定屬性值類型的每個詞法單元所對應的類型括起來。對于那些需要指定其屬性值類型的非終結符而言，我們使用%type加上尖括号的辦法确定它們的類型。當所有需要确定類型的符号的類型都被定下來之後，規則部分裡的

、$1等就自動地帶有了相應的類型，不再需要我們顯式地為其指定類型了。

**1.2.11　bison：文法單元的位置**

實驗要求中需要你輸出每一個文法單元出現的位置。你當然可以自己在flex中定義每個行号和列号以及在每個動作中維護這個行号和這個列号，并将它們作為屬性值的一部分傳回給文法單元。這種做法需要我們額外編寫一些維護性的代碼，非常不友善。bison有沒有内置的位置資訊供我們使用呢？答案是肯定的。

前面介紹過bison中每個文法單元都對應了一個屬性值，在語義動作中這些屬性值可以使用

、$1、$2等進行引用。實際上除了屬性值之外，每個文法單元還對應了一個位置資訊，在語義動作中這些位置資訊同樣可以使用@$、@1、@2等進行引用。位置資訊的資料類型是一個yyltype，其預設的定義是：

其中的first_line和first_column分别是該文法單元對應的第一個詞素出現的行号和列号，而last_line和last_column分别是該文法單元對應的最後一個詞素出現的行号和列号。有了這些内容，輸出所需的位置資訊就比較友善了。但注意，如果直接引用@1、@2等将每個文法單元的first_line列印出來，你會發現列印出來的行号全都是1。

為什麼會出現這種問題？主要原因在于，bison并不會主動替我們維護這些位置資訊，我們需要在flex源代碼檔案中自行維護。不過隻要稍加利用flex中的某些機制，維護這些資訊并不需要太多的代碼量。我們可以在flex源檔案的開頭部分定義變量yycolumn，并添加如下的宏定義yy_user_action：

其中yylloc是flex的内置變量，表示目前詞法單元所對應的位置資訊；yy_user_action宏表示在執行每一個動作之前需要先被執行的一段代碼，預設為空，而這裡我們将其改成了對位置資訊的維護代碼。除此之外，最後還要在flex源代碼檔案中做更改，就是在發現了換行符之後對變量yycolumn進行複位：

這樣就可以實作在bison中正常列印位置資訊。

1.2.12　bison：二義性與沖突處理

bison有一個非常好用但也很惱人的特性：對于一個有二義性的文法，它有自己的一套隐式的沖突解決方案（一旦出現歸約/歸約沖突，bison總會選擇靠前的産生式；一旦出現移入/歸約沖突，bison總會選擇移入）進而生成相應的文法分析程式，而這些沖突解決方案在某些場合可能并不是我們所期望的。是以，我們建議在使用bison編譯源代碼時要留意它所給的提示資訊，如果提示文法有沖突，那麼請一定對源代碼進行修改，盡量把所有的沖突全部消解掉。

前面那個四則運算的小程式，如果它的文法變成這樣：

雖然看起來好像沒什麼變化（exp → exp add factor | exp sub factor變成了exp→exp add exp | exp sub exp），但實際上前面之是以沒有這樣寫，是因為這樣做會引入二義性。例如，如果輸入為1 – 2 + 3，文法分析程式将無法确定先算1 – 2還是2 + 3。文法分析程式在讀到1 – 2的時候可以歸約（即先算1 – 2）也可以移入（即先算2 + 3），但由于bison預設移入優先于歸約，文法分析程式會繼續讀入+ 3然後計算2 + 3。

為了解決這裡出現的二義性問題，要麼重寫文法（exp → exp add factor | exp sub factor相當于規定加減法為左結合），要麼顯式地指定運算符的優先級與結合性。一般而言，重寫文法是一件比較麻煩的事情，而且會引入不少像exp → term這樣除了增加可讀性之外沒任何什麼實質用途的産生式。是以更好的解決辦法還是考慮優先級與結合性。

在bison源代碼中，我們可以通過“%left”、“%right”和“%nonassoc”對終結符的結合性進行規定，其中“%left”表示左結合，“%right”表示右結合，而“%nonassoc”表示不可結合。例如，下面這段結合性的聲明代碼主要針對四則運算、括号以及指派号：

其中assign表示指派号，lp表示左括号，rp表示右括号。此外，bison也規定任何排在後面的算符其優先級都要高于排在前面的算符。是以，這段代碼實際上還規定括号優先級高于乘除、乘除高于加減、加減高于指派号。在實驗一所使用的c––語言裡，表達式exp的文法便是沖突的，你需要模仿前面介紹的方法，根據c––語言的文法補充說明中的内容為運算符規定優先級和結合性，進而解決掉這些沖突。

另外一個在程式設計語言中很常見的沖突就是嵌套if-else所出現的沖突（也被稱為懸空else問題）。考慮c––語言的這段文法：

假設我們的輸入是：if (x > 0) if (x == 0) y = 0; else y = 1;，那麼語句最後的這個else是屬于前一個if還是後一個if呢？标準c語言規定在這種情況下else總是比對距離它最近的那個if，這與bison的預設處理方式（移入/歸約沖突時總是移入）是一緻的。是以即使我們不在bison源代碼裡對這個問題進行任何處理，最後生成的文法分析程式的行為也是正确的。但如果不處理，bison總是會提示我們該文法中存在一個移入/歸約沖突。有沒有辦法把這個沖突去掉呢？

顯式地解決懸空else問題可以借助于運算符的優先級。bison源代碼中每一條産生式後面都可以緊跟一個%prec标記，指明該産生式的優先級等同于一個終結符。下面這段代碼通過定義一個比else優先級更低的lower_than_else算符，降低了歸約相對于移入else的優先級：

這裡else和lower_than_else的結合性其實并不重要，重要的是當文法分析程式讀到if lp exp rp時，如果它面臨歸約和移入else這兩種選擇，它會根據優先級自動選擇移入else。通過指定優先級的辦法，我們可以避免bison在這裡報告沖突。

前面我們通過優先級和結合性解決了表達式和if-else語句裡可能出現的二義性問題。事實上，有了優先級和結合性的幫助，我們幾乎可以消除文法中所有的二義性，但我們不建議使用它們解決除了表達式和if-else之外的任何其他沖突。原因很簡單：隻要是bison報告的沖突，都有可能成為文法中潛在的一個缺陷，這個缺陷的來源很可能是你所定義的程式設計語言裡的一些連你自己都沒有意識到的文法問題。表達式和二義性的問題，我們之是以敢使用優先級和結合性的方法來解決，是因為我們對沖突的來源非常了解，除此之外，隻要是bison認為有二義性的文法，大部分情況下這個文法也能看出二義性。此時你要做的不是掩蓋這些文法上的問題，而是仔細對文法進行修訂，發現并解決文法本身的問題。

1.2.13　bison：源代碼的調試

以下這部分内容是可選的，跳過不會對實驗一的完成産生負面影響。

在使用bison進行編譯時，如果增加-v參數，那麼bison會在生成.yy.c檔案的同時幫我們多生成一個.output檔案。例如，執行

指令後，你會在目前目錄下發現一個新檔案syntax.output，這個檔案中包含bison所生成的文法分析程式對應的lalr狀态機的一些詳盡描述。如果你在使用bison編譯的過程中發現自己的文法裡存在沖突，但無法确定在何處，就可以閱讀這個.output檔案，裡面對于每一個狀态所對應的産生式、該狀态何時進行移入何時進行歸約、你的文法有多少沖突以及這些沖突在哪裡等都有十分完整地描述。

例如，如果我們不處理前面提到的懸空else問題，.output檔案的第一句就會是：

繼續向下翻，找到狀态112，.output檔案對該狀态的描述為：

這裡我們發現，狀态112在讀到else時既可以移入又可以歸約，而bison選擇了前者，将後者用方括号括了起來。知道是這裡出現了問題，我們就可以以此為線索修改bison源代碼或者重新修訂文法了。

對一個有一定規模的文法規範（如c––語言）而言，bison所産生的lalr文法分析程式可以有一百甚至幾百個狀态。即使将它們都輸出到了.output檔案裡，在這些狀态裡逐個尋找潛在的問題也是挺費勁的。另外，有些問題，例如文法分析程式在運作時刻出現“segmentation fault”等，很難從對狀态機的靜态描述中發現，必須要在動态、互動的環境下才容易看出問題所在。為了達到這種效果，在使用bison進行編譯的時候，可以通過附加-t參數打開其診斷模式（或者在代碼中加上#define yydebug 1）：

在main函數調用yyparse()之前我們加一句：yydebug = 1;，然後重新編譯整個程式。之後運作這個程式你就會發現，文法分析程式現在正像一個自動機，在進行一個一個狀态地轉換，并将目前狀态的資訊列印到标準輸出上，以友善你檢查自己代碼中哪裡出現了問題。以前面的四則運算小程式為例，當打開診斷模式之後運作程式，螢幕上會出現如下字樣：

如果我們輸入4，你會明顯地看到文法分析程式出現了狀态轉換，并将目前棧裡的内容列印出來：

繼續輸入其他内容，我們可以看到更進一步的狀态轉換。

注意，診斷模式會使文法分析程式的性能下降不少，建議在不使用時不要随便打開。

1.2.14　bison：錯誤恢複

當輸入檔案中出現文法錯誤的時候，bison總是會讓它生成的文法分析程式盡早地報告錯誤。每當文法分析程式從yylex()得到了一個詞法單元，如果目前狀态并沒有針對這個詞法單元的動作，那就會認為輸入檔案裡出現了文法錯誤，此時它預設進入下面這個錯誤恢複模式：

1）調用yyerror("syntax error")，隻要你沒有重寫yyerror()，該函數預設會在螢幕上列印出syntax error的字樣。

2）從棧頂彈出所有還沒有處理完的規則，直到文法分析程式回到了一個可以移入特殊符号error的狀态。

3）移入error，然後對輸入的詞法單元進行丢棄，直到找到一個能夠跟在error之後的符号為止（該步驟也被稱為再同步）。

4）如果在error之後能成功移入三個符号，則繼續正常的文法分析；否則，傳回前面的步驟二。

這些步驟看起來似乎很複雜，但實際上需要我們做的事情隻有一件，即在文法裡指定error符号應該放到哪裡。不過，需謹慎考慮放置error符号的位置：一方面，我們希望error後面跟的内容越多越好，這樣再同步就會更容易成功，這提示我們應該把error盡量放在高層的産生式中；另一方面，我們又希望能夠丢棄盡可能少的詞法單元，這提示我們應該把error盡量放在底層的産生式中。在實際應用中，人們一般把error放在行尾、括号結尾等地方，本質上相當于讓行結束符“;”以及括号“{”、“}”、“(”、“)”等作為錯誤恢複的同步符号：

以上幾個産生式僅僅是示例，并不意味着把它們照搬到你的bison源代碼中就可以讓文法分析程式能夠滿足實驗一的要求。你需要進一步思考如何書寫包含error的産生式才能夠檢查出輸入檔案中存在的各種文法錯誤。

1.2.15　文法分析提示

想要做好一個文法分析程式，第一步要仔細閱讀并了解c––文法規範。c––的文法要比它的詞法複雜很多，如果缺乏對文法的了解，在調試和測試文法分析程式時你将感到無所适從。另外，如果沒弄懂c––文法中每條産生式背後的具體含義，則無法在後面的實驗二中去分析這些産生式的語義。

接下來，我們建議你先寫一個包含所有文法産生式但不包含任何語義動作的bison源代碼，然後将它和修改以後的flex源代碼、main函數等一起編譯出來先看看效果。對于一個沒有文法錯誤的輸入檔案而言，這個程式應該什麼也不輸出；對于一個包含文法錯誤的輸入檔案而言，這個程式應該輸出syntax error。如果你的程式能夠成功地判别有無文法錯誤，再去考慮優先級與結合性該如何設定以及如何進行錯誤恢複等問題；如果你的程式輸出的結果不對，或者說你的程式根本無法編譯，那你需要重新閱讀前文并仔細檢查哪裡出了問題。好在此時代碼并不算多，借助于bison的.output檔案以及診斷模式等幫助，要查出錯誤并不是太難的事情。

下一步需要考慮文法樹的表示和構造。文法樹是一棵多叉樹，是以為了能夠建立它，你需要實作多叉樹的資料結構。你需要專門寫函數完成多叉樹的建立和插入操作，然後在bison源代碼檔案中修改屬性值的類型為多叉樹類型，并添加語義動作，将産生式右邊的每一個符号所對應的樹結點作為産生式左邊的非終結符所對應的樹結點的子結點逐個進行插入。具體這棵多叉樹的資料結構怎麼定義、插入操作怎麼完成等完全取決于你的設計，在設計過程中有一點需要注意：在實驗二中我們還會在這棵文法樹上進行一些其他操作，是以現在的資料結構設計會對後面的語義分析産生一定的影響。

構造完這棵樹之後，下一步就是按照實驗二要求中提到的縮進格式将它列印出來，同時要求列印的還有行号以及一些相關資訊。為了能列印這些資訊，你需要寫專門的代碼對生成的文法樹進行周遊。由于還要求列印行号，是以在之前生成文法樹的時候你就需要将每個結點第一次出現時的行号都記錄下來（使用位置資訊@n、使用變量yylineno或者自己維護這個行号均可以）。這段負責列印的代碼僅是為了實驗一而寫，後面的實驗不會再用，是以我們建議你将這些代碼組織在一起或者寫成函數接口的形式，以友善後面的實驗對代碼的調整。