一个简单编译器的实现

基于flex与bison的一个简单编译器的研究与实践[摘要]编译是程序执行过程中一个重要的步骤，分为词法分析、语法分析、语义分析、中间代码生成、中间代码优化、机器代码生成、机器代码优化几个步骤。本文使用flex与bison工具，编写了简洁的代码，实现了对一个简单语言的简单程序的词法分析、语法分析，最后生成了相应的抽象语法树。得出了flex与bison是编写词法分析器和语法分析器的有效工具的结论。[关键词]编译抽象语法树词法语法程序目录摘要第一章绪论1.1为什么要用编译器1.2编译步骤第二章简单编译器的研究与实现2.1简单编译器的结构2.2词法分析2.3语法分析2.4语义分析第三章实验结果全文总结第一章绪论1.1为什么要用编译器在计算机中，程序可以用不同的语言来编写，比如C，C++，汇编语言，机器代码等。计算机能够直接识别的只有机器代码，因此需要编译器来将其他语言编译成机器代码，或者将一种语言编译成另一种语言[1]。编译器是一个计算机程序（或一系列程序），它能将用程序语言写的源代码编译成计算机能够识别的目标代码，后者往往是二进制代码[2]。近年来基本的编译器设计都没多大的改变，而且它们正迅速地成为计算机科学课程中的中心一环。[5]1.2编译步骤1.2.1预处理一个较为复杂的程序可能被分割为多个模块，并存放于对应的源文件中。预处理器是一个程序，它把源程序拼接在一起，并把宏转化为源语言的语句[3]。1.2.2词法分析经过预处理的源程序会作为输入传递给编译器，词法分析是编译的第一个步骤。词法分析器以字符流的形式读入源程序，将它们组织成有意义的单词（token）[3]。flex是一种词法分析工具，它基于lex做了改进，能够更快地生成C语言词法分析程序。1.2.3语法分析语法分析是编译的第二个步骤。在这个步骤中，根据语言的语法识别词法分析后得到的字符流，生成语法树。为了能够为应用程序提供清晰简洁的接口，隐藏复杂的底层信息，抽象语法树仅仅设计了有实际意义的节点。Bison是一种语法分析工具，它基于YACC做了改进，能够自动生成C语言语法分析程序。第二章简单编译器的研究与实践2.1简单编译器的结构2.1.1编译器的功能本文将实现一个能将某些具有代表性的程序片段转换成三地址代码的编译器。例如：程序片段：a=1;b=10;While(ab)a=a+1;b=a+b;三地址代码：100：a=1101:b=10102:ifabgoto104103:goto107104:t1=a+1105:a=t1106:goto102107:t2=a+b;108:b=t2;2.1.2本语言的词法和语法语言的最小单元成为词素，词素包括数字的字面值、运算符和关键字等[3]。本语言的终结符有标识符（以字母开头，可以包含字母或数字）、正整数、运算符、while关键字、符号。本语言的语法规则定义如下：program→stmt|programstmtstmt→while_stmt|assign_stmtwhile_stmt→WHILE(bool_expr)stmtassign_stmt→ID=expr;bool_stmt→exprexpr|exprexpr|expr==exprexpr→primary_expr+expr|primary_expr-exprprimary_expr→ID|NUMBER每一条推导式中→代表“具有以下形式”，左边是要定义的语法成分，右边是相应的词素构成，|表示或者，大写的单词表示终结符。2.1.3简单编译器的结构简单编译器包括词法分析程序、语法分析程序、符号表管理程序和中间代码生成程序。分别实现将字符流转化为单词符号流，用单词符号流构建抽象语法树，管理语法分析过程中向符号表中增改信息的功能。2.1.4程序编写和连接本文借助flex工具生成词法分析器，bison工具生成语法分析器，用C语言编写程序，所有程序在同一目录下，用gcc编译连接。2.2词法分析2.2.1为什么使用flex词法分析通常所做的就是在输入中寻找字符的模式（pattern），而一种简洁明了的模式的描述方式就是正则表达式（regularexpression）。Flex会把所有的正则表达式翻译成一种高效的内部格式（确定性有穷自动机，DFA），使它几乎可以同时处理所有需要匹配的模式，因此它的速度可以成百倍地提高[4]。另外，flex版本的词法分析器比相应的手写的C代码更简短，因此也更容易调试。2.2.2flex代码及含义首先包括进由bison产生的头文件，其中有对关键字、终结符的枚举。然后将字符流组织成有意义的单词（token），再返回给yylex()函数。在yyparse()运行过程中会多次调用yylex()函数来获取单词（token）。%optionnoyywrapnodefaultyylineno%{#includestdio.h#includestdlib.h#includeheadfile.h#includeparser.tab.h%}%%while{returnWHILE;}[a-zA-Z][a-zA-Z0-9]*{yylval.s=yytext;returnID;}[0-9]+{yylval.i=atoi(yytext);returnNUMBER;}=={returnEQUAL;}\n|{};|+|-|*|/|(|)|||={yylval.s=yytext;returnyytext[0];}%%2.2.3词法分析部分总结Flex根据所提供的lexer.l文件，自动生成yy.lexer.c文件，编译成功后得到相应的yy.lexer.exe可执行文件，后续进行语法分析时会调用该文件中的内容，使输入字符串以单词符号流的形式进入语法分析器。2.3语法分析2.3.1为什么使用bisonBison基于所给的语法来生成可以识别这个语法中有效语句的语法分析器[4]，它基于2.1.2中所给的语法来识别语法上的正确输入。通过在识别之后加入一些语句进行抽象语法树的生成，就可以实现语法分析的整个过程并为目标代码的生成提供接口。Bison所生成的代码也将比手写的代码简短、易于调试。2.3.2抽象语法树的相关定义抽象语法树使用同一节点类型以便管理，同时定义了根据不同输入数据建立节点的函数：pastnodenewAstnode(){pastnodea=(pastnode)malloc(sizeof(_astnode));if(a==NULL){printf(runoutofmemory.\n);exit(0);}memset(a,0,sizeof(_astnode));returna;}pastnodenewNum(intnum){pastnodea=newAstnode();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-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;returna;}pastnodenewWhile(pastnodel,pastnoder){pastnodea=newAstnode();a-nodetype=while;a-l=l;a-r=r;returna;}2.3.3打印语法树打印语法树时，先查看该节点的节点类型，根据类型选择不同的打印方式，再进行对左右子数的递归调用。intshowAst(pastnodea,intlayer){inti;for(i=1;i=layer;i++){printf();}if(a-nodetype==number){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:\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==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.3.4Bison代码及含义Bison代码首先定义了联合类型表示终结符或非终结符可以为哪些类型，然后就是语法分析部分，大括号内是相应的建立节点的语句，当整个程序执行完时，一棵抽象语法树就建成了。%{#includeheadfile.h#includestdio.h#includestdlib.h%}%union{structastnode*a;inti;char*s;}%tokeniNUMBER%tokensID%tokenWHILEEQUAL%typeaprogramstmtwhile_stmtassign_stmtbool_exprexprprimary_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('',$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{