一个简单编译器的实现

1、基于flex与bison的一个简单编译器的研究与实践摘要编译是程序执行过程中一个重要的步骤，分为词法分析、语法分析、语义分析、中间代码生成、中间代码优化、机器代码生成、机器代码优化几个步骤。本文使用flex与bison工具，编写了简洁的代码，实现了对一个简单语言的简单程序的词法分析、语法分析，最后生成了相应的抽象语法树。得出了flex与bison是编写词法分析器和语法分析器的有效工具的结论。关键词编译抽象语法树词法语法程序目录摘要第一章绪论1.1 为什么要用编译器1.2 编译步骤第二章简单编译器的研究与实现2.1 简单编译器的结构2.2 词法分析2.3 语法分析2.4 语义分析第三章实验结果全

2、文总结第一章绪论1.1.1 么要用编译器在计算机中，程序可以用不同的语言来编写，比如计算机能够直接识别的只有机器代码，将一种语言编译成另一种语言1。编译器是一个计算机程序（或一系列程序）机能够识别的目标代码，后者往往是二进制代码近年来基本的编译器设计都没多大的改变，中心一环。51.2编译步骤1.2.1 预处理一个较为复杂的程序可能被分割为多个模块，C,C+,汇编语言，机器代码等。因此需要编译器来将其他语言编译成机器代码，或者,它能将用程序语言写的源代码编译成计算2。而且它们正迅速地成为计算机科学课程中的并存放于对应的源文件中。预处理器是个程序，它把源程序拼接在一起，并把宏转化为源语言的语句3。

3、1.1.2 词法分析经过预处理的源程序会作为输入传递给编译器，词法分析是编译的第一个步骤。词法分析器以字符流的形式读入源程序，将它们组织成有意义的单词（token）3。flex是一种词法分析工具，它基于lex做了改进，能够更快地生成C语言词法分析程序。1.1.3 语法分析语法分析是编译的第二个步骤。在这个步骤中，根据语言的语法识别词法分析后得到的字符流，生成语法树。为了能够为应用程序提供清晰简洁的接口，隐藏复杂的底层信息，抽象语法树仅仅设计了有实际意义的节点。Bison是一种语法分析工具，它基于YACC做了改进,能够自动生成C语言语法分析程序。第二章简单编译器的研究与实践2.1 简单编译器的结

4、构2.1.1 编译器的功能本文将实现一个能将某些具有代表性的程序片段转换成三地址代码的编译器。例如：程序片段：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 本语言的词法和语法语言的最小单元成为词素，词素包括数字的字面值、运算符和关键字等3。本语言的终结符有标识符(以字母开头，可以包含字母或数字)、正整数、运算符、while关键字、符号。本语言的语法规则

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每一条推导式中f代表“具有以下形式"，左边是要定义的语法成分，右边是相应的词素构成，|表示或者，大写的单词表示终结符。1.1.3 简单编译器的结构简单编译器包括词

6、法分析程序、语法分析程序、符号表管理程序和中间代码生成程序。分别实现将字符流转化为单词符号流，用单词符号流构建抽象语法树，管理语法分析过程中向符号表中增改信息的功能。1.1.4 程序编写和连接本文借助flex工具生成词法分析器，bison工具生成语法分析器，用C语言编写程序，所有程序在同一目录下，用gcc编译连接。2.2 词法分析2.2.1 为什么使用flex词法分析通常所做的就是在输入中寻找字符的模式(pattern),而一种简洁明了的模式的描述方式就是正则表达式(regularexpression)oFlex会把所有的正则表达式翻译成一种高效的内部格式(确定性有穷自动机，DFA),使它几乎

7、可以同时处理所有需要匹配的模式，因此它的速度可以成百倍地提高4。另外，flex版本的词法分析器比相应的手写的C代码更简短，因此也更容易调试。2.2.2 flex代码及含义首先包括进由bison产生的头文件，其中有对关键字、终结符的枚举。然后将字符流组织成有意义的单词(token),再返回给yylex()函数。在yyparse()运行过程中会多次调用yylex()函数来获取单词(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 词法分析部分总结Flex根据所提供的lexer.l文件，自动生成yy.lexer.c文件，编译成功后得到相应的yy.lexer.exe可执行文件，后续进行语法分析时会调用该文件中的内容，使输入字符串以单词符号流的形式进入语法分析器。2.3 语法分析2.3.1 为什么使用bisonBison基于所给的语法来生成可以识别这个语法中有效语句的语法分析器4,它基于2.1.2 中所给的语法来识别语法上的正确输入。通过在识别之后加入一些语句进行抽象语法树的生成

10、，就可以实现语法分析的整个过程并为目标代码的生成提供接口。Bison所生成的代码也将比手写的代码简短、易于调试。2.1.3 抽象语法树的相关定义抽象语法树使用同一节点类型以便管理，同时定义了根据不同输入数据建立节点的函数：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 打印语法树打印语法树时，先查看该节点的节点类型，根据类型选择不同的打印方式，再进行对左右子数的递归调用。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、码首先定义了联合类型表示终结符或非终结符可以为哪些类型，然后就是语法分析部分，大括号内是相应的建立节点的语句，当整个程序执行完时，一棵抽象语法树就建成了。%(#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语法分析部分总结Bison可以根据所给的.y文件自动生成语法分析器，调用词法分析器来生成抽象语法树，为后面生成中间代码做准备。2.4语义分析经过语法分析后，虽然明确了代码的组成结构，但并不知道其中的一些属性是否符合语言的规范，更不知道语法结构能够实现什么功能。要知道语法成分的含义和用途，以及需要进行的相应操作和运算，就需要进行语义分析。在该步骤中，会将申明的变量填到符号表中，利用语法树符号表中的信息来检查源