编译原理课程设计报告-简单编译器的设计与实现.docx

编译原理课程设计简单编译器的设计与实现班 级：组长：组员： 指导教师：设计时间：2016年12月姓名分工组长：语法分析部分，语义分析和中间代码生成部分，符号表的管理，目标代码的生成，数据结构的设计和总体框架的设计。组员：中间代码优化部分，负责从DAG图中获得优化后的四元式代码，以及将中间变量填写入符号表内。组员：中间代码优化部分，负责优化DAG图的建立。组员：词法分析部分，词法分析部分的符号表和错误表的记录。摘要41.概述52.课程设计任务及要求62.1 设计任务62.2 设计要求63.算法及数据结构73.1算法的总体思想（流程）73.2词法分析模块83.2.1功能83.2.2数据结构83.2.3算法103.3语法分析（含语义分析和中间代码生成）模块113.3.1功能113.3.2数据结构133.3.3算法163.4中间代码优化模块193.4.1功能193.4.2数据结构203.4.3算法203.5目标代码生成模块233.5.1功能233.5.2数据结构243.5.3算法244.程序设计与实现264.1程序流程图264.2 程序说明264.3实验结果325.系统特色406.结论417.参考文献418.收获、体会和建议41摘要一个编译器所进行的工作一般可以划分为五个阶段：词法分析、语法分析、语义分析和中间代码产生、中间代码的优化、目标代码生成。我们设计了并且实现了一个简单的类C语言编译器，该编译器拥有完整的前端和后端，能够进行基本的编译功能并产生可执行文件向屏幕输出源程序的运行结果。该编译器的词法分析器可以识别绝大部分标准C语言支持的词法符号，该词法分析器可以过滤空格、Tab和回车，并且支持注释功能。该词法分析器主要通过有限自动机的状态跳转来实现，根据自动机结束状态来得到该单词的TOKEN值。该模块具有词法错误位置提示功能。该编译器的语法部分采用了递归下降子程序的文法分析方法，所设计的文法支持了函数、函数类型声明、变量类型声明、变量定义、表达式语句、if条件语句和while循环语句以及简单输出功能。在表达式语句方面，我们设计了支持所有算术运算、关系运算、逻辑运算和位运算功能的语法结构，并且语法上支持一维数组和结构体。该编译器语义分析和生成四元式阶段能够对变量定义和语法错误进行检测，能够识别出未定义的标识符和重复定义标识符，该阶段最终实现生成中间代码四元式。该编译器拥有中间代码优化模块，采用DAG优化算法按基本块对四元式进行了优化，该编译器的目标代码是8086汇编语言代码，能够实现将优化后的四元式序列转化生成可执行的汇编语言文件，并且运行执行该文件，向屏幕输出运算结果。该编译程序的主要特色是能够将最终结果输出显示到屏幕，并且该编译程序能够支持前置+和后置+这种语法，拥有类似C语言的这种简便性。关键词：编译原理，词法分析，语法分析，四元式，DAG算法1.概述 编译原理课程兼有很强的理论性和实践性，是计算机专业的一门非常重要的专业基础课程，在系统软件中占有十分重要的地位。编译原理课程设计是本课程重要的综合实践教学环节，是对平时实验的一个补充。通过编译器相关子系统的设计，使学生能够更好地掌握编译原理的基本理论和编译程序构造的基本方法和技巧，融会贯通本课程所学专业理论知识；培养学生独立分析问题、解决问题的能力，以及系统软件设计的能力；培养学生的创新能力及团队协作精神。一个编译器所进行的工作一般可以划分为五个阶段：词法分析、语法分析、语义分析和中间代码产生、中间代码的优化、目标代码生成。首先是词法分析，针对词法分析，我们设计了一个可以识别绝大部分标准C语言支持的词法符号，该词法分析器可以过滤空格、Tab和回车，并且支持注释功能，即过滤掉注释符号$后面的代码。该词法通过有限自动机的状态跳转来实现，根据自动机结束状态来得到该单词的TOKEN值，词法分析器在识别到一个单词后，将该单词记录下来，如果是数据，则会在符号表的相应位置记录它的值，如果是标识符，则会先在符号表上进行查询，若没有则将其记录到符号表上，并将相应TOKEN的指针指向表中该位置。接下来进行语法分析，在语法分析部分，会对所编写的代码的语法进行检验，看是否合乎我们所设定的语法规则，这里我们采用了递归下降子程序的文法分析方法，所设计的文法支持了函数、函数类型声明、变量类型声明、变量定义、表达式语句、if条件语句和while循环语句以及cout简单输出功能。在表达式语句方面，我们设计了支持所有算术运算、关系运算、逻辑运算和位运算功能的语法结构，并且语法上支持一维数组和结构体。在语义分析和中间代码产生的阶段。我们在语法分析程序的相应部分加上了语义动作，实现将输入的语句转换成可识别的中间代码四元式形式。在语义分析部分，主要做的工作是在识别到数据和标识符时将它们压入语义栈，当语法分析到需要生成相应四元式时，执行构建四元式的动作，并将语义栈中的数据作为四元式的数据组成部分。还有就是符号表的构建，当语法分析到变量的定义语句时，需要将被定义的变量记录到符号表内，在记录之前需要检查符号表内该符号是否已经被定义，从而检查重复定义的错误。语义分析和中间代码产生是与语法分析同时进行的，当语法分析结束后，若输入内容的语法正确，则可以获得相应的四元式序列。然后是优化阶段。在优化阶段，我们主要运用了DAG优化算法。首先将编译器前端生成的四元式划分基本块，然后对每一个基本块执行DAG优化算法，通过该算法可以删除多余的赋值操作和无用的中间变量，从而减少四元式的数量，得到更简洁的四元式序列。最后一个阶段是目标代码生成。该阶段将四元式进一步翻译生成相应的目标代码，我们所选定的目标代码是8086汇编语言代码，所以该阶段的任务是将优化后的四元式序列转化生成可执行的汇编语言文件，从而进一步运行执行该文件，向屏幕输出运算结果。2.课程设计任务及要求2.1 设计任务设计一个简单的文法编译器，该编译器包括完整的前端和后端。该编译器可以划分为词法分析、语法分析和语义动作、中间代码优化和目标代码生成四个模块。词法分析：能够识别标准C语言所支持的大部分词法，能够进行简单的词法错误判断，输出错误提示，并且具有注释功能，能够过滤掉无用符号，如空格、Tab和回车等。语法分析和语义动作：能够支持基本类似于C语言的基本语法。语法上能够支持声明语句、基本类型的变量定义，如整型、实型和字符型数据；能够支持表达式语句，包括赋值表达式、算术表达式、逻辑表达式、关系表达式和位运算表达式；能够支持if条件语句和while循环语句。中间代码优化：采用DAG优化算法，能够对四元式进行优化，从而减少中间代码的数量，提高编译后生成的程序的效率。目标代码生成：将中间代码生成汇编语言代码，并且实现目标代码的运行，从而验证编译器编译结果的正确性。2.2 设计要求1、在深入理解编译原理基本原理的基础上，对于选定的题目，以小组为单位，先确定设计方案；2、设计系统的数据结构和程序结构，设计每个模块的处理流程。要求设计合理；3、编程序实现系统，要求运行界面应清楚地反映出系统的运行结果；4、确定测试方案，选择测试用例，对系统进行测试；5、运行系统并要通过验收，讲解运行结果，说明系统的特色和创新之处，并回答指导教师的提问；6、提交课程设计报告。3.算法及数据结构3.1算法的总体思想（流程）我们将编译器的设计按照功能划分为以下四个部分，通过这四个部分来实现编译器的全部功能。如下图。图3.1 算法总体思想图词法分析器用来对输入的字符流进行词法分析，识别每一个单词并生成相应的TOKEN码，并记录它们的数据信息。语法分析和语义分析以及中间代码的生成被划分为一个模块是因为它们的不可分割性，当某个语法分析通过后，就开始产生语义动作生成相应的四元式，因此该部分用来对词法分析产生的TOKEN序列进行语法分析，从而在符号表中记录相关数据信息，并且产生中间代码。中间代码优化模块是为了简化中间代码而设计的，该部分通过四元式构建相应的无向图，通过算法产生优化后的四元式序列。目标代码生成模块用于产生汇编代码，将优化后的四元式进行翻译，生成对应的汇编语言。该编译器包含了前端和后端的基本功能，能够进行词法错误检测、语法错误检测、标识符定义错误检测，并提示错误行数，且编译后生成可以直接运行的汇编程序，可以算是一个较为完整的简单编译器。3.2词法分析模块3.2.1功能通过将源程序输入该模块，词法分析器能够进行分析，检测词法是否正确，从而生成相应的TOKEN码，并向符号表中记录，如果遇到错误词法，则记录在错误表中。该词法分析器所能识别的词法包括以下几个部分。整数：TOKEN值为0实数：TOKEN值为1字符：TOKEN值为2字符串：TOKEN值为3标识符：TOKEN值为4关键字：TOKEN值为10-49现有能够识别的关键字有：auto,short,int,long,real,double,char,struct,union,enum,typedef,const,unsigned,signed,extern,register,static,volatile,void,if,else,switch,case,for,do,while,goto,continue,break,default,sizeof,return,bool,cout.界符：TOKEN值为50-69现有能够识别的界符有：，(，)，”，;，,，.，-，?，#运算符：TOKEN值为70-99现有能够识别的运算符有：+，-，*，/，%，+，-，=，=，,?,#;/界符表char OT233+,-,*,/,%,+,-,=,=, FunctionFunctionFunction - FType i4 ( Parameter ) Declaration Content 类型文法：FType - void|TypeType - int|real|charParameter - |void|Type Id , Type Id Id - i4|i4 i1 结构体声明文法：Declaration - |struct i4 Base_declaration ;|Base_declaration 基本类型定义文法：Base_declaration - | Type Id , Id ; 语句块文法：Content - Structure Structure Structure - |E ;|If|While|Fun|Cout函数调用文法：Fun - i4 ( ) ;|i4 ( Assignment , Assignment ) ;if条件语句文法：If - if ( Expression ) Content | if ( Expression ) Content else Content while循环语句文法：While - while ( Expression ) Content 逗号表达式文法：Expression - Assignment , Assignment 赋值表达式文法：Assignment - i4 . Id = Logical_or | Id = Logical_or | Logical_or逻辑表达式文法：Logical_or - Logical_and | Logical_and Logical_and - Inclusive_or & Inclusive_or Inclusive_or -Exclusive_or | Exclusive_or Exclusive_or -And And And - Equality & Equality 关系表达式文法：Equality - Relational w0 Relational Relational - Shift w1 Shift 算术表达式文法：Shift - Additive w2 Additive Additive - Multiplicative w3 Multiplicative Multiplicative - Unary w4 Unary 前置算符文法：Unary - w5 Postfix | Postfix后置算符文法：Postfix -Primary w6 Primary -i4|constant| ( Expression )其中符号表示：w0 - = | !=w1 - | =w2 - w3 - + | -w4 - * | / | %w5 - ! | | + | - | sizeofw6 - + | - | Expression | . i4其中constant为整数、实数或者字符类型数据，i4为用户自定义标识符，可以由字母、数字和下划线组成，不能以数字开头，并且不能与关键字相同。该模块还要执行相应的语义功能以及中间代码的生成。语义功能主要包括变量的定义、表达式四元式的生成、if条件语句和while循环语句的四元式生成等。变量的定义需要实现与符号表进行信息交换的功能，该变量定义的文法通过检验后，会向符号表中查找该标识符名称，如果没有查到则将该变量的类型和相关信息写入符号表；如果在符号表中查询到该标识符，则说明该变量名已经被定义，于是向错误表中写入标识符重复定义的错误信息，并标注错误行数。表达式和if、while语句在相应文法检验的过程中，会对操作数进行压栈处理，当文法检验成功后，会弹出操作数生成相应的四元式序列。当所有的语句都通过了文法检验并且生成了相应的四元式后，该模块会对四元式中的操作数进行检测，如果该操作数是用户自定义的标识符，就去符号表中查询，如果出现符号表中查询不到的标识符，则说明该标识符未被定义，此时向错误表中写入标识符未定义的错误信息，并标注错误行数。3.3.2数据结构语法分析过程是对词法分析生成的token序列进行分析，判断是否符合语法标准，因此不需要新的数据结构，只需要获取到token序列即可。语义分析的过程则需要额外的数据结构来对语义动作和相应操作进行存储。其中在生成四元式的过程中需要用到语义栈来存储当前的token，以便当识别到算符语法结束位置时从语义栈中弹出token生成相应的四元式序列。另外，在语法分析的过程中，还有变量、数组的定义和结构体的声明，这些语法检验通过后也要通过执行相应的语义动作将相关信息填写入符号表内。因此这里新增了一个语义栈结构体，用来存储生成四元式所需的操作数，还开辟了一个四元式链表，用来存储生成的四元式，四元式中的运算符是通过二维数组的数据结构来保存的。同时符号表中还需要类型表、数组表和结构体表，其中类型表用来存储标识符的类型，如果该标识符是数组或者结构体，则需要额外的数组表或结构体表来存储数据之间的关系。typedef struct SEM/语义栈 struct TOKEN* tpToken; struct SEM* fron; struct SEM* next;SEM;typedef struct Operand/操作数 struct TOKEN* tpToken;Operand;char OperatorL375+,-,*,/,%,+,-,=,=,gt,lb,if,el,ie,wh,do,we,inc,dec,arr,si,.,co;typedef struct Quaternary/四元式 char* Operator;/操作符表 struct Operand* operand3;/3个操作数 struct Quaternary* next;Quaternary;typedef struct TYPEL/类型表 char tval;/类码，类型代码，决定下列指针选择，现有类码为：i(整型),r(实型),c(字符型),a(数组),d(结构体) struct AINFL* ainfl;/数组表指针 struct RINFL* rinfl;/结构体表指针TYPEL;typedef struct AINFL/数组表 int low;/数组下界 int up;/数组上界 struct TYPEL* ctp;/成分类型指针，指向该维数组成分的类型的指针 int clen;/成分类型的长度，成分类型数据所占值单元的个数AINFL;typedef struct RINFL/结构表 char ID10;/结构域名 int OFF;/(区距)是idk的值单元首址相对于所在记录值区区头位置 struct TYPEL* TP;/指针，指向idk域成分类型(在类型表中的信息)RINFL;3.3.3算法图3.3 赋值语法的算法图3.4 逻辑或算法图3.5 数据生成部分算法图3.6 if条件语句算法图3.7 while循环语句算法3.4中间代码优化模块3.4.1功能该部分的功能是对从前端得到的四元式进行优化，目的是为了精简代码数量，使得编译后的程序能够更高效的运行，这里我们采用了DAG算法对中间代码进行优化。首先对前端输出的四元式进行基本块划分，然后对一个基本块执行DAG算法，构造一个无向图，从该图中获取到优化后的四元式序列。之后清空该图，对之后的基本块执行相同的算法，直到将所有基本块的四元式序列都优化为止，最后输出优化后的四元式序列。3.4.2数据结构中间代码优化部分需要建立一个无向图，通过相应算法来实现对基本块的优化，因此这里需要一个图的数据结构，该图结点有左右孩子、编号、运算符、标记和前后指针。其中单独创建了一个标记链表的数据结构，首个标记作为主标记，主标记后面所连接的标记作为从标记。运算符是用来记录四元式的运算符的，左右孩子是为了记录单目运算符和双目运算符所指向的操作数，标记是为了记录操作数，而前后指针是为了在DAG算法中更方便地查找删除重复的非用户定义标识符。此外创建了一个块链表，用来存储分块后的四元式，从而方便将四元式按照基本块进行划分保存，以便进行DAG算法优化。typedef struct Block struct Quaternary* qua_block;/分块后的四元式块集合 struct Block* next;/下一个块Block;typedef struct DAG/无向图 int num; char* oper; struct Mark* mark; struct DAG* lchild; struct DAG* rchild; struct DAG* next; struct DAG* fron;DAG;typedef struct Mark/标记 struct TOKEN* name; struct Mark* fron; struct Mark* next;Mark;3.4.3算法划分基本块的算法如下：图3.8 构建基本块算法构建DAG优化图的算法如下所示：图3.9 DAG优化创建算法从DAG中获取优化后四元式的算法如下图所示：图3.10 优化后四元式获取算法3.5目标代码生成模块3.5.1功能该模块的功能是通过优化后的四元式序列生成目标代码汇编语言。该部分首先会对得到的四元式序列进行分析，对四元式序列中的操作数进行判断，如果该操作数是系统生成的中间变量（该中间变量不能在运算化简中被舍弃），那么就会在符号表中查找，看符号表中是否存在该变量，如果不存在该变量，则向符号表中写入该变量，并标注变量类型，从而方便接下来的目标代码生成。按基本块顺序读取优化后的四元式序列，根据四元式的运算符进行判断，生成相应的汇编代码，当所有基本块都被读完后，汇编代码生成完毕，最后将汇编代码输出到ASM文件中，运行DOS将其编译连接并运行，得到源程序的运行结果。3.5.2数据结构该部分需要一个数据结构来存储目标语句，这里采用链表的数据结构，使用一个目标语句链表来保存目标语句的相关信息，其中包含存储的目标代码语句，该语句所处的位置标号以及当前语句的类型。当前语句的类型目前有4种，一种是0，表示此语句为一般语句，另外3种分别为i、e、d，分别代表if、else、do的四元式产生的目标语句，这些语句因为涉及到跳转，需要当读取到它们跳转到的语句时才能获得地址信息，所以它们所生成的目标语句的跳转地址需要回填，这个语句类型作为回填时查找该语句的标志来使用。typedef struct Object/目标语句 char code30;/存储的目标代码 int lab;/标号 char type;/需要回填的类型,0为不需要回填，i为if的回填，e为else的回填，d为do的回填 struct Object* fron; struct Object* next;Object;3.5.3算法目标代码的生成算法如下图所示：图3.11 目标代码生成算法4.程序设计与实现4.1程序流程图图4.1 程序运行流程图4.2 程序说明程序的编写使用的是C+语言，采用了类的封装，将整个编译器拆分为了四个模块，分别是词法分析器模块、语法分析（含语义分析和中间代码生成）模块、中间代码优化模块和目标代码生成模块，各个模块由上到下依次继承，实现了良好的封装性。下面按照每个模块类的设计对各个模块所含有的成员和方法进行说明。词法分析：class Scanner/词法分析器模块private: char ch,ch_before;/当前词，前一个词 int state,state_before;/状态，前状态 int line,warn;/行数，警告 void CreatNewToken(TOKEN*& t);/创建新的Token结点 void reset(int& state,char* code,int& i,int& warn);/重置自动机状态 int state_change(int st,char ch,int& warn);/自动机状态转换 void state_to_code(TOKEN* t, int state_before, char code100, int line, int warn);/根据自动机状态生成Token序列public: struct TOKEN* token;/token头指针 struct ERRORL* error_head;/错误表头指针 struct ERRORL* error_now;/错误表当前位置 Scanner()token=NULL;error_head=NULL;error_now=NULL;/构造函数 void Scan();/词法分析主函数 int Findexist(char* code, TOKEN*& p);/查询符号表函数 void ConvertItoS(int i, string& s);/类型转换，int to string void ConvertFtoS(float f,string& st);/类型转换，float to string void ConvertStoC(string st,char* c);/类型转换，string to char void ConvertStoI(string st,int& i);/类型转换，string to int void ConvertStoF(string st,float& f);/类型转换，string to float void CoutErrorL();/输出错误表;语法分析、语义分析和中间代码生成：class GrammaticalAnalysis:public Scanner/语法分析和语义动作及/中间代码生成模块private: /语法部分 struct TOKEN* ch;/当前词 int Start();/语法，开始 int Function();/语法，函数 int Parameter();/语法，参数 int FType();/语法，函数类型 int Type();/语法，变量类型 int Declaration();/语法，声明 int Base_declaration();/语法，基本类型声明 int Id();/语法，基本类型 int Id_Expression();/语法，数据类型 int Content();/语法，内容 int Structure();/语法，结构 int Expression();/语法，表达式 int Cout();/语法，输出函数 int Assignment();/语法，赋值 int Logical_or();/语法，逻辑或 int Logical_and();/语法，逻辑与 int Inclusive_or();/语法，或 int Exclusive_or();/语法，异或 int And();/语法，位与 int Equality();/语法，相等 int Relational();/语法，不等 int Shift();/语法，移位 int Additive();/语法，加法减法 int Multiplicative();/语法，乘法除法 int Unary();/语法，前置算符 int Postfix();/语法，后置算符 int Primary();/语法，标识符、常数生成 int IF();/语法，if条件语句 int While();/语法，while循环语句 int Fun();/语法，函数语句 /语义部分 int d;/结构体标记 struct TOKEN* type;/类型标记 struct TOKEN* ch_sem;/入语义栈的词 struct TOKEN* operand_now;/当前操作数 struct SEM* top;/栈顶 struct SEM* base;/栈底 struct Quaternary* quater_now;/当前四元式指针 void CreateSEM();/生成一个语义栈 void PushStack();/入栈 void DeStack();/出栈 int mark;/标明运算符位置 int counter;/系统变量计数器 void CreateQuaternary();/生成一个四元式 void PushQuaternary();/入四元式队列 void Bi_oper_qua();/双目算符的操作数生成 void Unary_oper_qua();/单目算符的操作数生成 void Assign_oper_qua();/赋值操作数生成 void If_While_qua();/IF条件,WHILE循环操作数生成 void GetMark(TOKEN* ch_ope);/获取运算符 void GetMark_front(TOKEN* ch_ope);/获