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

编译原理课程设计——简单编译器的设计与实现设计时间：2016年12月姓名组长：语法分析部分，语义分析和中间代码生成部分，符号表的管理，目标代码的生成，数据结构的设计和总体框架的设计。组员：中间代码优化部分，负责从DAG图中获得优化后的四元式代码，以及将中间变量填写入符号表内。组员：中间代码优化部分，负责优化DAG图的建立。组员：词法分析部分，词法分析部分的符号表和错误表的记录。摘要 41.概述 52.课程设计任务及要求 62.1设计任务 62.2设计要求 63.算法及数据结构 73.1算法的总体思想(流程) 73.2词法分析模块 8 83.2.2数据结构 8 3.3语法分析(含语义分析和中间代码生成)模块 3.3.2数据结构 3.4中间代码优化模块 3.4.1功能 3.4.2数据结构 3.5.2数据结构 4.程序设计与实现 4.1程序流程图 4.2程序说明 4.3实验结果 5.系统特色 6.结论 7.参考文献 8.收获、体会和建议 过有限自动机的状态跳转来实现，根据自动机结束状态来得到该单词的了优化，该编译器的目标代码是8086汇编语言代码，能够实现将优化后的四元能够支持前置++和后置++这种语法，拥有类似C语言的if条件语句和while循环语句以及cout简单输出功能。在表达式语代码，我们所选定的目标代码是8086汇编语言代码，所以该阶段的任务是将优2.1设计任务达式、算术表达式、逻辑表达式、关系表达式和位运算表达式；能够支持if条1、在深入理解编译原理基本原理的基础上，对于选定的题目，以小组为单2、设计系统的数据结构和程序结构，设计每个模块的处理流程。要求设计并回答指导教师的提问；6、提交课程设计报告。3.算法及数据结构3.1算法的总体思想(流程)我们将编译器的设计按照功能划分为以下四个部分，通过这四个部分来实现编译器的全部功能。如下图。符号表符号表记录数据和标识符填写符号表中数据关系中间代码优优化后四元式目标代码生错误表语法和语义分析以及中间代码生成词法分析器目标语言变量检查源语言四元式TOKEN图3.1算法总体思想图词法分析器用来对输入的字符流进行词法分析，识别每一个单词并生成相应的TOKEN码，并记录它们的数据信息。语法分析和语义分析以及中间代码的生成被划分为一个模块是因为它们的不可分割性，当某个语法分析通过后，就开始产生语义动作生成相应的四元式，因此该部分用来对词法分析产生的TOKEN序列进行语法分析，从而在符号表中记录相关数据信息，并且产生中间代码。中间代码优化模块是为了简化中间代码而设计的，该部分通过四元式构建相应的无向图，通过算法产生优化后的四元式序列。目标代码生成模块用于产生汇编代码，将优化后的四元式进行翻译，生成对应的汇编语言。该编译器包含了前端和后端的基本功能，能够进行词法错误检测、语法错误检测、标识符定义错误检测，并提示错误行数，且编译后生成可以直接运行的汇编程序，可以算是一个较为完整的简单编译器。3.2词法分析模块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值为70-99现有能够识别的运算符有：charKT[34][15]={"auto","short","int","lon"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"charOT[23][3]{"+","-","*","/","%","++","--","=",typedefstructERRORL{//错误记录表charname[100];//错误内容intline;//行数记录，系统编码标记structINT*tpl;//整型指针structREAL*tpR;//实型指针structCHAR*tpc;//字符指针structSYNBL*tplT;//标识符表指针char*tpKT;//关键字指针char*tpPT;//界符指针char*tpOT;//运算符指针}TOKEN;typedefstructIdentifier{//标识符表structIdentifier*next;typedefstructINT{//整数型表}HINT;typedefstructREAL{//实数型表charname[100];//标识符名字structTYPEL*type;//类型表指针charL;//活跃信息structPFINFL*pfinfl;//函数表指针structLENL*lenl;//长度表指针structVALL*vall;//活动记录表指针初始化自动机运行自动机，进行状态转换N标识符?Y生成对应token毕?Y打印输出token结束数、浮点数?Y记录错误信息关键字?界符?图3.2词法分析算法3.3语法分析(含语义分析和中间代码生成)模块该模块接收词法分析模块得到TOKEN序列，通过对TOKEN序列的语法分析，判断该语法是否合法，如果合法则执行相应的语义动作，生成中间代码。在语法分析模块，我们设计了比较接近于C语言的语法结构，虽然不如C语言语法那么灵活，但是依然能够满足用户基本的需求，源程序的编写与C语言类似，对C语言用户来说没有陌生感。文法结构如下(这里的{}代表可以循环生成，符号'{外面有单引号):Type->'int'|'real'|'char'Parameter->e|'void'|Type结构体声明文法：Declaration->{e|'struct'i4'{'Base_declaration'Y';'|Base_declaration}Base_declaration->gStructure->g|E‘;'|If|WFun->i4'(‘')';|i4'('Assignment{‘if条件语句文法：‘if’‘('ExpressionWhile->'while''('Expression'Y''{'Content'}'赋值表达式文法：Assignment->i4!ld'='Logical_or|ld'='Logical_or|Logical_or逻辑表达式文法：Logicalor->Logicaland{'||'Logicaland}Logical_and->Inclusive_or{'&&'Inclusive_or}Inclusive_or->Exclusive_or{'I'Exclusive_or}And->Equality{'&'Equality}关系表达式文法：Equality->Relational{w0Rel算术表达式文法：Shift->Additive{w2Additive}Additive->Multiplicative{w3Multiplicative}Primary->i4|constant|'('Expression'Y'其中符号表示：w0->'=='|'!='w1->'<|'>'|'<='|'>=w3->'+'|'-'w4->'*′|'’|'%’w5->'!'|'~′|'++'|'--'|'sizeofw6->'++'|'--'|'['Expression]|!i4其中在生成四元式的过程中需要用到语义栈来存储当前的token,以便当识别到typedefstructOperand{//操作数structTOKEN*tpToken;charOperatorL[37][5]{"+","-","*","/","%","++","--","=","gt","1b","if","el","ie","wh","do","we","inc","dec","arr","si",".","cstructOperand*operand[3];//3个操作数structQuaternary*next;chartval;//类码，类型代码，决定下列指针选择，现有类码为：i(整structAINFL*ainfl;//数组表指针structRINFL*rinfl;//结构体表指针typedefstructAINFL{//数组表intlow;//数组下界structTYPEL*ctp;//成分类型指针，指向该维数组成分的类型的指针intclen;//成分类型的长度，成分类型数据所占值单元的个数typedefstructRINFL{//结构表intOFF;//(区距)—是idk的值单元首址相对于所在记录值区区头位置ERRORERROR开始开始NYNYNPush(i4)”=※?Next(w)Y程序NERRORYNext(w)程序程序ld子程序”=※?开始NY结束图3.4逻辑或算法开始开始NNYExpression子程序NYConstant?YYN图3.5数据生成部分算法开始YY子程序NERRORNERRORN//else※?YY程序N→ERRORYY程序NERRORNERRORNYERRORNERRORY开始开始YNYNYGEM(we)NYYGEM(wh)程序子程序结束图3.7while循环语句算法3.4中间代码优化模块该部分的功能是对从前端得到的四元式进行优化，目的是为了精简代码数量，使得编译后的程序能够更高效的运行，这里我们采用了DAG算法对中间代码进行优化。首先对前端输出的四元式进行基本块划分，然后对一个基本块执行DAG算法，构造一个无向图，从该图中获取到优化后的四元式序列。之后清空该图，对之后的基本块执行相同的算法，直到将所有基本块的四元式序列都优化为止，最后输出优化后的四元式序列。typedefstructBlock{structQuaternary*qua_block;//分块后的四元式块集合读取四元式N语句?Y新建一个基本块将四元式加入到当前基本块内毕?Y结束开始开始读取四元式(,B_A)赋值N四元式?值?YY将A添加到B的mark标记上否存在?Y新建操作数结点新建该运算结点，并将B,C连接为该结点的孩子若被添加结点的主标记是中间变量，则交换逆序检查删除存在的非用户定义标识符标记N基本块结束?Y结束(w,B,A)双目或单目赋值Y在图中查找该运算是否已经(=,C1,_A)常值运算或者赋计算出常值NNNN图3.9DAG优化创建算法从DAG中获取优化后四元式的算法如下图所示：开始开始Y下一个图结点为空?N读取图结点N点?YN存在从标记?YN从标记为非临时变量?Y将主标记的值赋给从标记N该结点为非叶结点?Y以该结点的运算符为标准生成相应四元式N存在从标记?Y从标记为非临时变量?Y将主标记的值赋给从标记结束N图3.10优化后四元式获取算法3.5目标代码生成模块该模块的功能是通过优化后的四元式序列生成目标代码——汇编语言。该部分首先会对得到的四元式序列进行分析，对四元式序列中的操作数进行判断，如果该操作数是系统生成的中间变量(该中间变量不能在运算化简中被舍弃),那一个目标语句链表来保存目标语句的相关信息，其中包含存储的目标代码语句，当前语句的类型目前有4种，一种是0,表示此语句为一般语句，另外3种分别为i、e、d,分别代表if、else、do的四元式产生的目标语句，这些语句因为涉及到跳转，需要当读取到它们跳转到的语句时才能获得地址信息，所以它们所生成的目标语句的跳转地址需要回填，这个语句类型作为回填时查找该语句charcode[30];//存储的目标代码structObject*fron;目标代码的生成算法如下图所示：开始开始更新符号表生成目标代码头部(生成数据段目标代码)Y基本块为空?N取基本块Y四元式序列为空?N读四元式并生成相应的目标代码结束文件生成目标代码尾部图3.11目标代码生成算法4.程序设计与实现4.1程序流程图开始开始词法分析器存在词法错误?N四元式生成语法有错误?标识符定义有错误?N汇编代码生成输出错误信息程序运行结果输出到屏幕结束图4.1程序运行流程图4.2程序说明程序的编写使用的是C++语言，采用了类的封装，将整个编译器拆分为了四个模块，分别是词法分析器模块、语法分析(含语义分析和中间代码生成)模块、中间代码优化模块和目标代码生成模块，各个模块由上到下依次继承，实现了良好的封装性。下面按照每个模块类的设计对各个模块所含有的成员和方法进行说明。词法分析：classScanner{//词法分析器模块private;charch,ch_before;//当前词，前一voidCreatNewToken(TOKEN*&t);//创建新的Token结点voidreset(int&state,char*code,int&i,int&warn);//重置自动机状态intstate_change(intst,charch,int&warn);//自动机状态转换voidstatetocode(TOKEN*t,intstatline,intwarn);//根据自动机状态生成Token序列public:structERRORL*error_head;//错误表头指针structERRORL*error_now;//错误表当前位置voidScan();//词法分析主函数voidConvertFtoS(floatvoidConvertStoC(stringvoidConvertStoI(stringvoidConvertStoF(stringvoidCoutErrorL();//输出错误表}语法分析、语义分析和中间代码生成：classGrammaticalAnalysis:publicprivate://语法部分structTOKEN*ch;//当前词intStart();//语法，开始Scanner{//语法分析和语义动作及//中间代码生成模块intFType();//语法，函数类型intType();//语法，变量类型intDeclaration();//语法，声明intBasedeclaration();//语法，基本类型声明intId();//语法，基本类型intId_Expression();//语法，数据类型intExpression();//语法，表达式intCout();//语法，输出函数intAssignment();//语法，赋值intLogical_or();//语法，逻辑或intLogical_and();//语法，逻辑与intExclusiveor();//语法，异或intEquality();//语法，相等intAdditive();//语法，加法减法intMultiplicative();//语法，乘法除法intUnary();//语法，前置算符intPrimary();//语法，标识符、常数生成structTOKEN*chsem;//入语义栈的词structTOKEN*operandnow;//当前操作数structQuaternary*quater_now;//当前四元式指针voidCreateSEM();//生成一个语义栈voidDeStack();//出栈intcounter;//系统变量计数器voidCreateQuaternary();//生成一个四元式voidPushQuaternary();//入四元式队列voidBi_oper_qua();//双目算符的操作数生成voidUnary_oper_qua();//单目算符的操作数生成voidAssign_oper_qua();//赋值操作数生成voidGetMark(TOKEN*ch_ope);//获取运算符voidGetMark_front(TOKEN*ch_ope);//获取前置运算符intFindSynbl();//查重voidPushSynbl();//添加进符号表intCoutSynbl();//输出符号表voidCheckSynbl();//检查标识符是否被定义，未定义则记录到错误表中voidGrammar();//语法部分GrammaticalAnalysis(){token=NULL;counror_now=NULL;}//语义部分structOperand*operand[3];//语义操作数structQuaternary*quater;//structIdentifier*id;//用户定义标识符structIdentifier*idnow;//当前标识符指针voidCoutQuaternary();//输出四元式classOptimization:publicGrammaticalAnalysis{//中间代码优化模块private:structQuaternary*optimize_now;//当前优化四元式structBlock*optimize_block_now;//优化后的当前块structBlock*block_now;//当前块指针structOperand*find_now_numl;//当前查找词structOperand*find_now_num2;//当前查找词char*find_now_ope;//structOperand*add当前查找运算符now;//当前需要加入的结点char*op_now;//当前运算符structDAG*find_begin;//查找开始处structDAG*pos;//找到的位置structMark*mark_pos;//找到的标记位置structDAG*temp_dag;//待交换标记所在的dag结点structMark*templ;//待交换标记1structMark*temp2;//待交换标记2voidCreateOptimize();//创建一个优化后四元式头部voidCreateOptimize_Block();//创建一个优化后块头部voidDivideBlock();//块划分函数voidCoutBlock();//按基本块输出四元式voidCreateDAG();//创建一个DAGvoidAddDAG();//加入一个DAG点intFindDAG();//检查重复DAG结点intFindDAGunary();//检查单目运算符重复DAGintMainMark();//检查该标记是不是主标记voidSwopMark();//交换两个标记voidDeleteMark();//删除一个标记voidCoutOptimize();//输出优化后的四元式public;structQuaternary*optimize;//优化四元式structBlock*optimize_block;//优化后的块voidOptimize();classObjectCode:publicOptimization{//目标代码生成模块private:structObject*obj_now;//当前目标代码structBlock*blo;structQuaternary*qua;structOperand*num;//当前操作数intfindnum;//需要查找的系统变量名称intSystemExist();//查找符号表中是否有必须的中间变量voidUpdateSymbol();//更新符号表，将系统生成中间变量放入voidGetObjCode();//生成目标代码voidAddObject();//加入obj结点voidCoutObj();//输出目标代码voidJudge(string&st);//获取操作数类型，存到numTypeintFindobj();//从后向前寻找相应类型的首个目标代码语句intFindobjhead();//从前向后寻找相//目标代码生成函数(代码段具体语句)voidGetHead();//目标代码头部生成(含数据段)voidGetTail();//目标代码尾部生成public:structObject*obj;//目标代码指针voidObjCode();//目标代码主函数]4.3实验结果voidmain(){a=1;b=1;while(b<5){if(a%2==0){}输出结果如下所示，显示为结果为行数、token值、单词。E:\SimpleCompiler\b4444444voidmain()abA[cdaE:SimpleCompiler\440401b二1353540b5)4(4a00%2二=0)B33564004444if(a%2=二0){a1b图4.2词法分析结果语法分析模块：变量的定义会被保存在符号表中，用于之后的标识符检测和最后的目标代码生成阶段，符号表存储结果如下图。图4.3符号表显示 b该模块会执行相应的语义动作并生成中间代码——四元式，产生的四元式结果如下图所示。四元式!四元式!da,t1,,(%,a,2,t2)if,t3图4.4四元式显示结果中间代码优化：中间代码优化采用DAG算法按照基本块进行四元式优化，得到的最后优化四元式结果如下图所示。(=,1,_;b)wh,)do,t1,,块3:(%,a,2,t2(==,t2,0,t3)if,t3,,块4:c0,a,,5中6inc,a,,t5)WE编译成功!图4.5优化后四元式结果目标代码模块会产生相应的汇编代码，并最终生成可编译的.ASM汇编文件，生成的最终文件结果如下图所示。code.ASM-记事本code.ASM-记事本code.ASM-记事本ASSUMECS:CSEG,DS:DSEGSTART:MOVAX,DSEGMOVDS,AXLAB1:MOVBX,1AB3:MOVBX,1LAB5:MOVAX,bAB6:MOVBX,5AB7:MOVCX,1LAB8:CMPAX,BXLAB12:MOVBX,t1LAB13:CMPBX,OLAB15:MOVAX,aLAB16:MOVBX,2LAB17:MOVDX,0LAB18:IDIVBXLAB19:MOVt2,DXLAB20:MOVAX,t2LAB21:MOVBX,0LAB22:MOVCX,1LAB23:CMPAX,BXLAB24:JELAB26LAB25:MOVCX,0LAB26:MOVt3,CXLAB27:MOVBX,t3LAB28:CMPBX,0LAB29:JZLAB42LAB30:MOVAX,aLAB31:AAALAB32:0RAX,3030HLAB33:MOVBX,AXLAB34:MOVDL,BHLAB35:MOVAH,O2HLAB36:INT21HLAB37:MOVDL,BLLAB38:INT21HLAB39:MOVDL,10LAB40:INT21HLAB41:JMPLAB46LAB42:MOVBX,bLAB43:MOVt4,BXLAB29:JZLAB42LAB30:MOVAX,aLAB31:AAALAB32:0RAX,3030HLAB33:MOVBX,AXLAB34:MOVDL,BHLAB35:MOVAH,O2HLAB36:INT21HLAB37:MOVDL,BLLAB38:INT21HLAB39:MOVDL,10LAB40:INT21HLAB41:TMPLAB46LAB42:MOVBX,bLAB44:INCBXLAB45:MOVb,BXLAB46:MOVBX,aLAB47:INCBXLAB48:MOVa,BXLAB49:MOVt5,BXLAB50:JMPLAB5LAB51:MOVAH,4CHMOVAL,0图4.6目标代码生成结果该模块已经配置好了相应环境，会自动调用汇编的编译文件生成可执行文件，并自动执行该可执行文件，从而向屏幕打印输出源程序的结果，实现完整的编译程序。运行结果如下图所示。Microsoft(R)OverlauLinkerVersion3.69Copyright(C)MicrosoftCorp1983-1988.A11LIMK:warningL4021:nostacksegmentE:N>code.exe2M图4.7源程序结果显示●main(4444—abC●main(4444—abCU404041b11一测试样例2:voidmain(){while(a<=5){cout++b;778…9(0……y44…g8…9(0……y44…口写U404041C二;while(a5———aC55图4.8词法分析结果四元式b,t4图4.9四元式生成结果E:\SimpleCompiler\bi块1:t2e块4:决5决5块6:(inc,b,,t4t4,图4.10中间代码优化结果目标代码生成：code.ASM-记事本code.ASM-记事本文件(F)编辑(E)格式(O)查看文件(F)编辑(E)格式(O)查code.ASM-记事本DSEGSEGMENTCSEGSEGMENTASSUMECS:CSEG,DS:DSEGSTART:MOVAX,DSEGMOVDS,AXLAB2:MOVa,BXLAB3:MOVBX,1LAB6:MOVc,BXLAB10:CMPAX,BXLAB11:JLELAB13LAB15:CMPBX,0LAB17:MOVLAB18:MOVLAB19:INCLAB20:MOVLAB21:MOVLAB22:AAAL