一個(gè)簡(jiǎn)單編譯器的實(shí)現(xiàn)

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

2、文總結(jié)第一章緒論1.1.1 么要用編譯器在計(jì)算機(jī)中，程序可以用不同的語(yǔ)言來(lái)編寫(xiě)，比如計(jì)算機(jī)能夠直接識(shí)別的只有機(jī)器代碼，將一種語(yǔ)言編譯成另一種語(yǔ)言1。編譯器是一個(gè)計(jì)算機(jī)程序（或一系列程序）機(jī)能夠識(shí)別的目標(biāo)代碼，后者往往是二進(jìn)制代碼近年來(lái)基本的編譯器設(shè)計(jì)都沒(méi)多大的改變，中心一環(huán)。51.2編譯步驟1.2.1 預(yù)處理一個(gè)較為復(fù)雜的程序可能被分割為多個(gè)模塊，C,C+,匯編語(yǔ)言，機(jī)器代碼等。因此需要編譯器來(lái)將其他語(yǔ)言編譯成機(jī)器代碼，或者,它能將用程序語(yǔ)言寫(xiě)的源代碼編譯成計(jì)算2。而且它們正迅速地成為計(jì)算機(jī)科學(xué)課程中的并存放于對(duì)應(yīng)的源文件中。預(yù)處理器是個(gè)程序，它把源程序拼接在一起，并把宏轉(zhuǎn)化為源語(yǔ)言的語(yǔ)句3。

3、1.1.2 詞法分析經(jīng)過(guò)預(yù)處理的源程序會(huì)作為輸入傳遞給編譯器，詞法分析是編譯的第一個(gè)步驟。詞法分析器以字符流的形式讀入源程序，將它們組織成有意義的單詞（token）3。flex是一種詞法分析工具，它基于lex做了改進(jìn)，能夠更快地生成C語(yǔ)言詞法分析程序。1.1.3 語(yǔ)法分析語(yǔ)法分析是編譯的第二個(gè)步驟。在這個(gè)步驟中，根據(jù)語(yǔ)言的語(yǔ)法識(shí)別詞法分析后得到的字符流，生成語(yǔ)法樹(shù)。為了能夠?yàn)閼?yīng)用程序提供清晰簡(jiǎn)潔的接口，隱藏復(fù)雜的底層信息，抽象語(yǔ)法樹(shù)僅僅設(shè)計(jì)了有實(shí)際意義的節(jié)點(diǎn)。Bison是一種語(yǔ)法分析工具，它基于YACC做了改進(jìn),能夠自動(dòng)生成C語(yǔ)言語(yǔ)法分析程序。第二章簡(jiǎn)單編譯器的研究與實(shí)踐2.1 簡(jiǎn)單編譯器的結(jié)

4、構(gòu)2.1.1 編譯器的功能本文將實(shí)現(xiàn)一個(gè)能將某些具有代表性的程序片段轉(zhuǎn)換成三地址代碼的編譯器。例如：程序片段：a=1;b=10;While(a<b)a=a+1;b=a+b;三地址代碼：100：a=1101:b=10102: ifa<bgoto104103: goto107104: t1=a+1105: a=t1106: goto102107: t2=a+b;108:b=t2;1.1.2 本語(yǔ)言的詞法和語(yǔ)法語(yǔ)言的最小單元成為詞素，詞素包括數(shù)字的字面值、運(yùn)算符和關(guān)鍵字等3。本語(yǔ)言的終結(jié)符有標(biāo)識(shí)符(以字母開(kāi)頭，可以包含字母或數(shù)字)、正整數(shù)、運(yùn)算符、while關(guān)鍵字、符號(hào)。本語(yǔ)言的語(yǔ)法規(guī)則

5、定義如下：program-stmt|programstmtstmtfwhile_stmt|assign_stmtwhile_stmtfWHILE(bool_expr)stmtassign_stmtfID=expr;bool_stmtfexpr>expr|expr<expr|expr=exprexprfprimary_expr+expr|primary_expr-exprprimary_exprfID|NUMBER每一條推導(dǎo)式中f代表“具有以下形式"，左邊是要定義的語(yǔ)法成分，右邊是相應(yīng)的詞素構(gòu)成，|表示或者，大寫(xiě)的單詞表示終結(jié)符。1.1.3 簡(jiǎn)單編譯器的結(jié)構(gòu)簡(jiǎn)單編譯器包括詞

6、法分析程序、語(yǔ)法分析程序、符號(hào)表管理程序和中間代碼生成程序。分別實(shí)現(xiàn)將字符流轉(zhuǎn)化為單詞符號(hào)流，用單詞符號(hào)流構(gòu)建抽象語(yǔ)法樹(shù)，管理語(yǔ)法分析過(guò)程中向符號(hào)表中增改信息的功能。1.1.4 程序編寫(xiě)和連接本文借助flex工具生成詞法分析器，bison工具生成語(yǔ)法分析器，用C語(yǔ)言編寫(xiě)程序，所有程序在同一目錄下，用gcc編譯連接。2.2 詞法分析2.2.1 為什么使用flex詞法分析通常所做的就是在輸入中尋找字符的模式(pattern),而一種簡(jiǎn)潔明了的模式的描述方式就是正則表達(dá)式(regularexpression)oFlex會(huì)把所有的正則表達(dá)式翻譯成一種高效的內(nèi)部格式(確定性有窮自動(dòng)機(jī)，DFA),使它幾乎

7、可以同時(shí)處理所有需要匹配的模式，因此它的速度可以成百倍地提高4。另外，flex版本的詞法分析器比相應(yīng)的手寫(xiě)的C代碼更簡(jiǎn)短，因此也更容易調(diào)試。2.2.2 flex代碼及含義首先包括進(jìn)由bison產(chǎn)生的頭文件，其中有對(duì)關(guān)鍵字、終結(jié)符的枚舉。然后將字符流組織成有意義的單詞(token),再返回給yylex()函數(shù)。在yyparse()運(yùn)行過(guò)程中會(huì)多次調(diào)用yylex()函數(shù)來(lái)獲取單詞(token)。%optionnoyywrapnodefaultyylineno%#include<stdio.h>#include<stdlib.h>#include"headfile.

8、h"#include"parser.tab.h"%"while"returnWHILE;a-zA-Za-zA-Z0-9*yylval.s=yytext;returnID;0-9+yylval.i=atoi(yytext);returnNUMBER;"="returnEQUAL;"n"|""""|"+"|"-"|"*"|"/"|"("|")"|&qu

9、ot;>"|"<"="yylval.s=yytext;returnyytext0;%2.2.3 詞法分析部分總結(jié)Flex根據(jù)所提供的lexer.l文件，自動(dòng)生成yy.lexer.c文件，編譯成功后得到相應(yīng)的yy.lexer.exe可執(zhí)行文件，后續(xù)進(jìn)行語(yǔ)法分析時(shí)會(huì)調(diào)用該文件中的內(nèi)容，使輸入字符串以單詞符號(hào)流的形式進(jìn)入語(yǔ)法分析器。2.3 語(yǔ)法分析2.3.1 為什么使用bisonBison基于所給的語(yǔ)法來(lái)生成可以識(shí)別這個(gè)語(yǔ)法中有效語(yǔ)句的語(yǔ)法分析器4,它基于2.1.2 中所給的語(yǔ)法來(lái)識(shí)別語(yǔ)法上的正確輸入。通過(guò)在識(shí)別之后加入一些語(yǔ)句進(jìn)行抽象語(yǔ)法樹(shù)的生成

10、，就可以實(shí)現(xiàn)語(yǔ)法分析的整個(gè)過(guò)程并為目標(biāo)代碼的生成提供接口。Bison所生成的代碼也將比手寫(xiě)的代碼簡(jiǎn)短、易于調(diào)試。2.1.3 抽象語(yǔ)法樹(shù)的相關(guān)定義抽象語(yǔ)法樹(shù)使用同一節(jié)點(diǎn)類(lèi)型以便管理，同時(shí)定義了根據(jù)不同輸入數(shù)據(jù)建立節(jié)點(diǎn)的函數(shù)：pastnodenewAstnode()pastnodea=(pastnode)malloc(sizeof(_astnode);if(a=NULL)printf("runoutofmemory.n");exit(0);memset(a,0,sizeof(_astnode);returna;)pastnodenewNum(intnum)pastnodea=n

11、ewAstnode();a->nodetype="number"a->value=num;returna;)pastnodenewId(char*string)pastnodea=newAstnode();a->nodetype="id"a->string=string;returna;)pastnodenewExpr(intoper,pastnodel,pastnoder)pastnodea=newAstnode();a->nodetype="expression"a->value=oper;a-

12、>l=l;a->r=r;returna;)pastnodenewStmt(pastnodel,pastnoder)pastnodea=newAstnode();a->nodetype="statement"a->l=l;a->r=r;returna;)pastnodenewAssign(char*string,pastnoder)pastnodea=newAstnode();a->nodetype="assign"pastnodel=newId(a->string);a->l=l;a->r=r;ret

13、urna;)pastnodenewWhile(pastnodel,pastnoder)pastnodea=newAstnode();a->nodetype="while"a->l=l;a->r=r;returna;)2.1.4 打印語(yǔ)法樹(shù)打印語(yǔ)法樹(shù)時(shí)，先查看該節(jié)點(diǎn)的節(jié)點(diǎn)類(lèi)型，根據(jù)類(lèi)型選擇不同的打印方式，再進(jìn)行對(duì)左右子數(shù)的遞歸調(diào)用。intshowAst(pastnodea,intlayer)inti;for(i=1;i<=layer;i+)printf("");if(a->nodetype="number"

14、)printf("number:%d",a->value);printf("n");return0;if(a->nodetype="id")printf("id:%s",a->string);printf("n");return0;if(a->nodetype="expression")if(a->value=EQUAL)printf("=expression:n");elseprintf("%cexpression

15、:n",a->string);if(a->l!=NULL)showAst(a->l,layer+1);if(a->r!=NULL)showAst(a->r,layer+1);return0;if(a->nodetype="statement")printf("statement:n");if(a->l!=NULL)showAst(a->l,layer+1);if(a->r!=NULL)showAst(a->r,layer+1);return0;if(a->nodetype=&qu

16、ot;assign")printf("assignstatement:n");if(a->l!=NULL)showAst(a->l,layer+1);if(a->r!=NULL)showAst(a->r,layer+1);return0;if(a->nodetype="while")printf("whilestatement:n");showAst(a->l,layer+1);showAst(a->r,layer+1);return0;)2.1.5 Bison代碼及含義Bison代

17、碼首先定義了聯(lián)合類(lèi)型表示終結(jié)符或非終結(jié)符可以為哪些類(lèi)型，然后就是語(yǔ)法分析部分，大括號(hào)內(nèi)是相應(yīng)的建立節(jié)點(diǎn)的語(yǔ)句，當(dāng)整個(gè)程序執(zhí)行完時(shí)，一棵抽象語(yǔ)法樹(shù)就建成了。%(#include"headfile.h"#include<stdio.h>#include<stdlib.h>%)%unionstructastnode*a;inti;char*s;)%token<i>NUMBER%token<s>ID%tokenWHILEEQUAL%type<a>programstmtwhile_stmtassign_stmtbool_ex

18、prexprprimary_expr%startprogram%program:stmt$=$1;)|stmtprogram$=newStmt($1,$2);showAst($,0);)stmt:while_stmt$=$1;|assign_stmt$=$1;while_stmt:WHILE'('bool_expr')'stmt$=newWhile($3,$5);assign_stmt:ID'='expr''$=newAssign($1,$3);bool_expr:expr'>'expr$=newExpr(&

19、#39;>',$1,$3);|expr'<'expr$=newExpr('<',$1,$3);|exprEQUALexpr$=newExpr(EQUAL,$1,$3);expr:primary_expr'+'expr$=newExpr('+',$1,$3);|primary_expr'-'expr$=newExpr('-',$1,$3);|primary_expr$=$1;primary_expr:ID$=newId($1);NUMBER$=newNum($1);%2.3.5語(yǔ)法分析部分總結(jié)Bison可以根據(jù)所給的.y文件自動(dòng)生成語(yǔ)法分析器，調(diào)用詞法分析器來(lái)生成抽象語(yǔ)法樹(shù)，為后面生成中間代碼做準(zhǔn)備。2.4語(yǔ)義分析經(jīng)過(guò)語(yǔ)法分析后，雖然明確了代碼的組成結(jié)構(gòu)，但并不知道其中的一些屬性是否符合語(yǔ)言的規(guī)范，更不知道語(yǔ)法結(jié)構(gòu)能夠?qū)崿F(xiàn)什么功能。要知道語(yǔ)法成分的含義和用途，以及需要進(jìn)行的相應(yīng)操作和運(yùn)算，就需要進(jìn)行語(yǔ)義分析。在該步驟中，會(huì)將申明的變量填到符號(hào)表中，利用語(yǔ)法樹(shù)符號(hào)表中的信息來(lái)檢查源