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

基于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=1 101: b=10 102: if ab goto 104 103: goto 107 104: t1=a+1 105: a=t1 106: goto 102 107: t2=a+b; 108:b=t2; 2.1.2 本语言的词法和语法 语言的最小单元成为词素，词素包括数字的字面值、运算符和关键字等[3]。本语言的终结符有标识符（以字母开头，可以包含字母或数字）、正整数、运算符、while关键字、符号。 本语言的语法规则定义如下： program → stmt | program stmt stmt → while_stmt | assign_stmt while_stmt → WHILE ( bool_expr ) stmt assign_stmt → ID = expr; bool_stmt → expr expr | expr expr | expr == expr expr → primary_expr + expr | primary_expr - expr primary_expr → ID | NUMBER 每一条推导式中→代表“具有以下形式”，左边是要定义的语法成分，右边是相应的词素构成，|表示或者，大写的单词表示终结符。 2.1.3 简单编译器的结构 简单编译器包括词法分析程序、语法分析程序、符号表管理程序和中间代码生成程序。分别实现将字符流转化为单词符号流，用单词符号流构建抽象语法树，管理语法分析过程中向符号表中增改信息的功能。 2.1.4 程序编写和连接 本文借助flex工具生成词法分析器，bison工具生成语法分析器，用C语言编写程序，所有程序在同一目录下，用gcc编译连接。 2.2 词法分析 2.2.1 为什么使用flex 词法分析通常所做的就是在输入中寻找字符的模式（pattern），而一种简洁明了的模式的描述方式就是正则表达式（reg