一個簡單編譯器的實現(xiàn).doc

《一個簡單編譯器的實現(xiàn).doc》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、基于flex與bison的一個簡單編譯器的研究與實踐[摘要]編譯是程序執(zhí)行過程中一個重要的步驟，分為詞法分析、語法分析、語義分析、中間代碼生成、中間代碼優(yōu)化、機器代碼生成、機器代碼優(yōu)化幾個步驟。本文使用flex與bison工具，編寫了簡潔的代碼，實現(xiàn)了對一個簡單語言的簡單程序的詞法分析、語法分析，最后生成了相應的抽象語法樹。得出了flex與bison是編寫詞法分析器和語法分析器的有效工具的結(jié)論。[關鍵詞]編譯抽象語法樹詞法語法程序目錄摘要第一章緒論1.1為什么要用編譯器1.2編譯步驟第二章簡單編譯器的研究與實現(xiàn)2.1簡單編譯器的結(jié)構(gòu)2.2詞法分析2.3語法分析2

2、.4語義分析第三章實驗結(jié)果全文總結(jié)第一章緒論1.1為什么要用編譯器在計算機中，程序可以用不同的語言來編寫，比如C，C++，匯編語言，機器代碼等。計算機能夠直接識別的只有機器代碼，因此需要編譯器來將其他語言編譯成機器代碼，或者將一種語言編譯成另一種語言[1]。編譯器是一個計算機程序（或一系列程序），它能將用程序語言寫的源代碼編譯成計算機能夠識別的目標代碼，后者往往是二進制代碼[2]。近年來基本的編譯器設計都沒多大的改變，而且它們正迅速地成為計算機科學課程中的中心一環(huán)。[5]1.2編譯步驟1.2.1預處理一個較為復雜的程序可能被分割為多個模塊，并存放于對應的源文件中

3、。預處理器是一個程序，它把源程序拼接在一起，并把宏轉(zhuǎn)化為源語言的語句[3]。1.2.2詞法分析經(jīng)過預處理的源程序會作為輸入傳遞給編譯器，詞法分析是編譯的第一個步驟。詞法分析器以字符流的形式讀入源程序，將它們組織成有意義的單詞（token）[3]。flex是一種詞法分析工具，它基于lex做了改進，能夠更快地生成C語言詞法分析程序。1.2.3語法分析語法分析是編譯的第二個步驟。在這個步驟中，根據(jù)語言的語法識別詞法分析后得到的字符流，生成語法樹。為了能夠為應用程序提供清晰簡潔的接口，隱藏復雜的底層信息，抽象語法樹僅僅設計了有實際意義的節(jié)點。Bison是一種語法分析工具

4、，它基于YACC做了改進，能夠自動生成C語言語法分析程序。第二章簡單編譯器的研究與實踐2.1簡單編譯器的結(jié)構(gòu)2.1.1編譯器的功能本文將實現(xiàn)一個能將某些具有代表性的程序片段轉(zhuǎn)換成三地址代碼的編譯器。例如：程序片段：a=1;b=10;While(a

5、本語言的終結(jié)符有標識符（以字母開頭，可以包含字母或數(shù)字）、正整數(shù)、運算符、while關鍵字、符號。本語言的語法規(guī)則定義如下：program→stmt

6、programstmtstmt→while_stmt

7、assign_stmtwhile_stmt→WHILE(bool_expr)stmtassign_stmt→ID=expr;bool_stmt→expr>expr

8、expr

9、expr==exprexpr→primary_expr+expr

10、primary_expr-exprprimary_expr→ID

11、NUMBER每一條推導式中→代表“具有以下形式”

12、，左邊是要定義的語法成分，右邊是相應的詞素構(gòu)成，

13、表示或者，大寫的單詞表示終結(jié)符。2.1.3簡單編譯器的結(jié)構(gòu)簡單編譯器包括詞法分析程序、語法分析程序、符號表管理程序和中間代碼生成程序。分別實現(xiàn)將字符流轉(zhuǎn)化為單詞符號流，用單詞符號流構(gòu)建抽象語法樹，管理語法分析過程中向符號表中增改信息的功能。2.1.4程序編寫和連接本文借助flex工具生成詞法分析器，bison工具生成語法分析器，用C語言編寫程序，所有程序在同一目錄下，用gcc編譯連接。2.2詞法分析2.2.1為什么使用flex詞法分析通常所做的就是在輸入中尋找字符的模式（pattern），而一種簡潔明了的模式的描

14、述方式就是正則表達式（regularexpression）。Flex會把所有的正則表達式翻譯成一種高效的內(nèi)部格式（確定性有窮自動機，DFA），使它幾乎可以同時處理所有需要匹配的模式，因此它的速度可以成百倍地提高[4]。另外，flex版本的詞法分析器比相應的手寫的C代碼更簡短，因此也更容易調(diào)試。2.2.2flex代碼及含義首先包括進由bison產(chǎn)生的頭文件，其中有對關鍵字、終結(jié)符的枚舉。然后將字符流組織成有意義的單詞（token），再返回給yylex()函數(shù)。在yyparse()運行過程中會多次調(diào)用yylex()函數(shù)來獲取單詞（token）。%optionnoyy

15、wrapnodefaul