使用FLEX&BISON實作ANSIC文法剖析器

《使用FLEX&BISON實作ANSIC文法剖析器》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、編譯器期末專題使用FLEX&BISON實作ANSIC文法剖析器王清松(922805)、簡祥任(022851)內容—、簡介FLEX&BISON-1-二、FLEX&BISON的運作原理-2-三、使用FLEX&BISON設計剖析器-2-四、測試案例與測試-4-五、心得與討論-10-參考資料-10-一、簡介FLEX&ISONFLEX是一種用來產生詞彙解析器的程式，這種程式可以用來辨識文句中的詞彙單元。FLEX需要讀取規則定義檔，規則的定義是由常規表示式(regularexpression)與C的原始碼構成。FLEX會產生一個名爲lex.y

2、y.cC的原始碼，其中包含重要的yy丄ex()函式。這個檔案之後會被編譯並連結成剖析器的一部分，當yy"x()執行時，剖析器會開始讀取輸入串流(來自於標準輸入或檔案)，並在成功辨識出某個辭彙的版型(pmem)時做出對應的動作。BISON是革奴(GNU)的自由軟體之一，它支援各種常見的作業系統，主要的用途是產生文句的剖析器。BISON高度相容於其前身Yacc，且強化了許多功能，特別是錯誤恢復與模組化的技術。因爲BISON需要依賴詞彙剖析器來處理輸入文字，一般會與LEX/FLEX合用，但也可以用人工手寫的方式或者其他自動工具來產生詞彙

3、剖析的功能。實際上BISON會將前後文無關文(context-free)的LALR文法轉換成C或者C++的程式碼，用以實作文法的剖析。它也可以爲模稜兩可的文法產生GLR(一般化的從左至右、右優先衍生)剖析器，在這種情形中，剖析器會在遇到衝突時，模擬多個LALR的自動機平行的執行，並解決剖析過程中遇到的衝突。二・FLEX&ISON的運作原理FLEX與BISON在內部透過函數呼叫彼此互動。剖析程序從呼叫yyparse()函數開始，剖析到輸入結尾時(end・of・input)就會回傳YYACCEPT，若剖析過程中發生無法恢復的文法錯誤時

4、，會回傳YYABORTo在yyparse()函數中，會使用到FLEX產生的yylex()函數，當yy"x()辨識到詞彙時，會將之放入yytext變數中，這時yyparse()再使用yytext查找狀態轉移或化簡規則。在BISON的規則中，我們可以加入特殊的保留字符error作錯誤恢復(errorrecovery)，當剖析過程中遇到錯誤時，剖析器會先尋找錯誤恢復規則，若找到定義的恢復規則，則會嘗試恢復錯誤並繼續剖析，否則呼叫yypatse()函數回報錯誤，並且中止剖析。三・使用FLEX&ISON設計剖析器欲建立語言之文法剖析器，我們

5、需要該語言的辭彙與文法定義。現今較常使用的ansiC語言定義，是由JeffLee在1985年依據ANSI標準公佈的版本，其內容包含詞彙規範與文法規則。我們沿用其標準並增減了部分內容，在詞彙部分共有九十二類定義，而文法規則共六十三條'語言定義的細節請參考lex.1與grammar.y檔案。在我們的實作中'原始碼包含main.h、main.c以及語言定義lex.1'grammar.y共四個檔案，經FLEX與BISON的處理後會再產生lex・yy.c、grammar.tab.h、grammar.tab.c等三彳固C的原始五馬，這些原始碼

6、即可用來建構我們的剖析器。下圖即爲檔案之間的關係(虛線部分是自動產生的檔案，實線部份爲撰寫的原始碼)：其中main.cti含主程序，而語言定義透過FLEX與BISON所產生的C語言原始碼經編譯成日的碼後會與主程序連結。在主程序中我們爲FLEX產生的詞彙解析函數yy1*()重新設計了輸入處理，也就是以GetInput()覆蓋FLEX內的input()函數，這麼做的目的是要在剖析過程中計算程式碼的欄數與行數。另外我們也改寫了BISON預設的錯誤報告方式，設計了FancyErrorReport()函數置入BISON產生的yyerz匸()

7、函數中取代原內容，如此便能在剖析錯誤時追蹤更精確的位置。在編譯程式時，爲了簡化「產生lex.yy.c、產生grammar,tab.*再編譯原始碼、連結日的碼」的過程，我們也寫了一個簡易的Makefile設定檔，其內容如下：01SHELL=/bin/bash02LEX=/usr/bin/flex0304YACC=/usr/bin/bison05all:1ex.1grammar.y06$(LEX)lex・丄07$(YACC)-dgrammar・y-v0809$(CC)lex.yy.cgrammar.main.c-oCParser10c

8、lean:11rm*.yy.cab.*-f如此即可透過make有效率的完成一系列的工作。最後產生的執行檔是CParser，即爲我們的剖析器'詳細過程如撷圖：■[rv@home_gwsrc]$make

9、/usr/bin/flexlex.1/usr/b