一个简单编译器的实现.doc

基于flex与bison的一个简单编译器的研究与实践摘要编译是程序执行过程中一个重要的步骤，分为词法分析、语法分析、语义分析、中间代码生成、中间代码优化、机器代码生成、机器代码优化几个步骤。本文使用flex与bison工具，编写了简洁的代码，实现了对一个简单语言的简单程序的词法分析、语法分析，最后生成了相应的抽象语法树。得出了flex与bison是编写词法分析器和语法分析器的有效工具的结论。关键词 编译 抽象语法树 词法 语法 程序目录摘要第1章 绪论1.1 为什么要用编译器1.2 编译步骤第2章 简单编译器的研究与实现2.1 简单编译器的结构2.2 词法分析2.3 语法分析2.4 语义分析第三章 实验结果全文总结 第一章 绪论1.1 为什么要用编译器 在计算机中，程序可以用不同的语言来编写，比如C，C+，汇编语言，机器代码等。计算机能够直接识别的只有机器代码，因此需要编译器来将其他语言编译成机器代码，或者将一种语言编译成另一种语言1。编译器是一个计算机程序（或一系列程序），它能将用程序语言写的源代码编译成计算机能够识别的目标代码，后者往往是二进制代码2。近年来基本的编译器设计都没多大的改变，而且它们正迅速地成为计算机科学课程中的中心一环。51.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=1 101: b=10 102: if a expr | expr expr | 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），而一种简洁明了的模式的描述方式就是正则表达式（regular expression）。Flex会把所有的正则表达式翻译成一种高效的内部格式（确定性有穷自动机，DFA），使它几乎可以同时处理所有需要匹配的模式，因此它的速度可以成百倍地提高4。另外，flex版本的词法分析器比相应的手写的C代码更简短，因此也更容易调试。2.2.2 flex代码及含义 首先包括进由bison产生的头文件，其中有对关键字、终结符的枚举。然后将字符流组织成有意义的单词（token），再返回给yylex()函数。在yyparse()运行过程中会多次调用yylex()函数来获取单词（token）。%option noyywrap nodefault yylineno%#include #include #include headfile.h#include parser.tab.h%while return WHILE;a-zA-Za-zA-Z0-9* yylval.s=yytext;return ID;0-9+ yylval.i=atoi(yytext);return NUMBER;= return EQUAL;n| ;|+|-|*|/|(|)|nodetype=number;a-value=num;return a;pastnode newId(char* string)pastnode a=newAstnode();a-nodetype=id;a-string=string;return a;pastnode newExpr(int oper,pastnode l,pastnode r)pastnode a=newAstnode();a-nodetype=expression;a-value=oper;a-l=l;a-r=r;return a;pastnode newStmt(pastnode l,pastnode r)pastnode a=newAstnode();a-nodetype=statement;a-l=l;a-r=r;return a;pastnode newAssign(char* string,pastnode r)pastnode a=newAstnode();a-nodetype=assign;pastnode l=newId(a-string);a-l=l;a-r=r;return a;pastnode newWhile(pastnode l,pastnode r)pastnode a=newAstnode();a-nodetype=while;a-l=l;a-r=r;return a;2.3.3 打印语法树 打印语法树时，先查看该节点的节点类型，根据类型选择不同的打印方式，再进行对左右子数的递归调用。int showAst(pastnode a,int layer)int i;for (i=1;inodetype=number)printf (number:%d,a-value);printf(n);return 0;if (a-nodetype=id)printf (id:%s,a-string);printf(n); return 0;if(a-nodetype=expression)if (a-value=EQUAL) printf(= expression:n);else printf(%c expression:n,a-string);if (a-l!=NULL) showAst(a-l,layer+1);if (a-r!=NULL) showAst(a-r,layer+1);return 0;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);return 0;if(a-nodetype=assign)printf(assign statement:n);if (a-l!=NULL) showAst(a-l,layer+1);if (a-r!=NULL) showAst(a-r,layer+1);return 0;if(a-nodetype=while)printf(while statement:n);showAst(a-l,layer+1);showAst(a-r,layer+1);return 0;2.3.4 Bison代码及含义 Bison代码首先定义了联合类型表示终结符或非终结符可以为哪些类型，然后就是语法分析部分，大括号内是相应的建立节点的语句，当整个程序执行完时，一棵抽象语法树就建成了。%#include headfile.h#include#include%unionstruct astnode *a;int i;char* s;%token NUMBER%token ID%token WHILE EQUAL%type program stmt while_stmt assign_stmt bool_expr expr primary_expr%start program%program:stmt $=$1; |stmt program $=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); |expr EQUAL expr $=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 语义分析 经过语法分析后，虽然明确了代码的组成结构，但并不知道其中的一些属性是否符合语言的规范，更不知道语法结构能够实现什么功能。要知道语法成分的含义和用途，以及需要进行的相应操作和运算，就需要进行语义分析。在该步骤中，会将申明的变量填到符号表中，利用语法树符号表中的信息来检查源程序是否与语言定义的含义和功能一致。通常，语义分析过程所需进行检车的项目十分繁杂。对一些常见语言来说，需要检查：在说明语句中是否有矛盾的类型说明；在表达式中，对某些运算符而言，是否有类型不匹配的运算对象；在过程调用中，实际参数与形式参数是否在个数、次序、种属等方面按相应语言的规定进行对应等。 第三章 实验结果3.1 编译过程Flex lexer.lBison -d parser.yGcc lex.yy.c parser.tab.c ast.c -o compiler3.2 运行结果 Assign_stmt Id:a Number:1 Assign_stmt Id:b Number:10 While_stmt expression Id:a Id:b Assign_stmt Id:a + expression Id:a Id:a+1 Assign_stmt Id:a + expression Id:a Id:b 全文总结 本文实现了对一种简单语言的编译器的词法分析、语