编译技术课程设计报告书

课程设计报告(2010–2011年度第1学期)名称：编译技术课程设计A题目：L语言编译器的设计与实现院系：计算机系班级：软件0802学号：200809020205学生姓名：龚泽滢指导教师：鲁斌李莉设计周数：2周成绩：日期：2011年1月14日1《编译技术》课程设计任务书一、课程设计的目的与要求1．任务：实现一个简单的编译程序，能够对指定程序设计语言进行编译。2．目的：加深对课堂讲授知识的理解，熟练掌握编译程序设计原理及常用的技术，建立编译程序的整体概念，使得学生初步具有研究、设计、编制和调试编译程序的能力。3．要求：熟悉有关定义、概念和实现算法，设计出程序流程框图和数据结构，编写出完整的源程序，进行静态检查，设计出输入数据、显示输出数据；基本功能完善，方便易用，操作无误；通过课程设计学会编译程序设计与实现的常用技术，具备初步分析、设计和开发编译程序的能力，具备分析与检查软件错误、解决和处理实验结果的能力。4．学生要求人数：2人，1人负责扫描器和目标代码生成器的设计和实现，另1人负责语法分析器和语法制导翻译程序的设计和实现。二、主要内容下面是课程设计主要内容的简介，详细内容请见《编译技术课程设计指导书》。1．扫描器设计该扫描器是一个子程序，其输入是源程序字符串，每调用一次输出一个单词符号。为了避免超前搜索，提高运行效率，简化扫描器的设计，假设程序设计语言中，基本字不能用作一般标识符，如果基本字、标识符和常数之间没有确定的运算符或界符作间隔，则用空白作间隔。2．语法分析器设计以算法优先分析方法为例，设计一个算符优先语法分析程序。算符优先分析属于自下而上的分析方法，该语法分析程序的输入是终结符号串（即单词符号串，以一个“#”结尾），如果输入串是句子则输出“YES”，否则输出“NO”和错误信息。当然，也可采用预测分析等方法设计语法分析器，具体方法自定。3．语法制导翻译程序设计采用语法制导翻译方法，实现算术表达式、赋值语句和基本控制语句等的翻译。本语法制导翻译程序的输入是终结符号串（即单词符号串，以一个“#”结尾），如果输入符号串是句子,则按照其语义进行翻译,输出等价的四元式序列。4．目标代码生成器设计将程序设计语言的中间代码翻译为目标代码，输入是四元式序列，输出是汇编代码文件。2三、进度计划序号设计内容完成时间备注1任务布置，资料查询，方案制定第一周周一2算法设计，程序实现第一周周二至第二周周四3撰写报告，软件验收第二周周五4四、设计成果要求1．完成规定的课程设计任务，所设计软件功能符合要求；2．完成课程设计报告，要求格式规范，内容具体而翔实，应体现自身所做的工作，注重对设计思路的归纳和对问题解决过程的总结。五、考核方式1．平时成绩＋验收答辩＋实验报告；2．五级分制。学生姓名：指导教师：鲁斌李莉2011年1月4日本组组员：龚泽滢（200809020205）邵婧婕（200809020224）其中我负责语法/语义分析部分。3语法/语义分析目的通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。任务在词法分析程序产生的token文件、符号表文件基础上，完成语法和语义分析，产生相应的中间代码——四元式序列。在此，可把语法/语义分析作为独立的一遍进行处理。采用如下四元式：操作码助记符四元式意义:=(51,a,0,r)r←a+(43,a,b,r)r←a+b-(45,a,b,r)r←a-b*(41,a,b,r)r←a*b/(48,a,b,r)r←b/aj(53,a,b,n)若ab转至第n个四元式j=(54,a,b,n)若a=b转至第n个四元式j(57,a,b,n)若ab转至第n个四元式j=(58,a,b,n)若a=b转至第n个四元式j=(56,a,b,n)若a=b转至第n个四元式j(52,0,0,n)转至第n个四元式j(55,a,b,n)若ab转至第n个四元式实验正文数据结构1输入token文件、符号表文件，其数据结构与词法分析产生的文件相同。2输出四元式序列文件，其纪录结构如下：typedefstructequ{intop;//四元式操作码语法/语义分析程序符号表文件四元式序列文件符号表文件token文件4intop1;//操作数在符号表中的入口地址intop2;//操作数在符号表中的入口地址intresult;//结果变量在符号表中的入口地址}equ;程序中可用数组Equ存放四元式序列，定义为：equEqu[EQU_LEN]可用变量intLineOfEqu做指针，指向下一个即将产生的四元式符号表文件的结构与输入相同，语法分析中对于符号表不做操作，只是在文件头部增加一个记录变量多少的数据。程序结构说明为方便编程，将语言文法整理如下：L→S|S;LS→id:=ES→ifBthenSS→ifBthenSelseSS→whileBdoSS→beginLend变量说明语句的文法：S→varD|εD→L:K;|L:K;DL→i,L|iK→integer|bool|real其中，B表示布尔表达式，E表示算术表达式可采用递归下降分析法或其它方法进行语法分析。语法/语义分析程序可划分为三个模块，结构如下：parser为主程序模块，Declear为说明语句分析模块，L_begin为复合语句分析模块。其中L_begin结构图如下：L_BeginparserDeclear5经常使用的过程和函数：gen(intop,inta,intb,intr)：生成一个四元式NewTemp()：产生一个临时变量，返回其在符号表中的入口地址BackPatch(intaddr,intaddr2)：回填函数，完成四元式转移目标的回填voidgetbuf()：获取文件中的一组数据voidprogram()：程序由程序首部、程序体和;组成voidproghead()：程序首部：program+标识符+；voidblock()：程序体部分，常量说明、变量说明、语句部分实验算法思想（包含主程序的示意图）（1）主程序的示意图如下图所示：（2）递归下降分析程序示意图如下图所示：L_IfL_BeginL_LetL_WhileL_AnalizeB_AnalizeE_Analize程序首部调用getbuf()获取文本文档中的下一组字符调用block()End6（3）语法串分析过程示意图如下图所示：7（4）statement语句分析函数示意图如下图所示：（5）expression表达式分析函数如下图所示：8（6）term分析函数示意图如下图所示：（7）factor分析过程示意图如下图所示：（8）语义分析器：设置语义过程1、emit(char*result,char*ag1,char*op,char*ag2)该函数的功能是生成一个三地址语句送到四元式表中。9四元式表的结构如下：struct{charresult[8];charag1[8];charop[8];charag2[8];}quad[20];(2)char*newtemp()该函数回送一个新的临时变量名，临时变量名产生的顺序为T1，T2，…char*newtemp(void){char*p;charm[8];p=(char*)malloc(8);k++;itoa(k,m,10);strcpy(p+1,m);p[0]=’t’;return(p);}2、设计思想函数lrparser在语法分析的基础上插入相应的语义动作：将输入串翻译成四元式序列。分析程序可知，需要进行四元式翻译的只有赋值语句、表达式和if语句、while语句等控制语句。在实现时，我采用这样的方法：先建立一个关于四元式的结构体，并建立一个存放这样的结构体的向量。当遇到赋值号:=时，声明一个结构体，并把这个结构体插入向量中。由于在赋值号前必然是一个变量ID，可以在遇到一个变量ID时，就把这个ID的值存入临时变量tmp。由于在后面可能要用到也可能用不到，所以不用担心tmp值覆盖的问题。在向量中插入结构体变量后，需要将ID填入对应的项中，然后可以继续遍历。遇到下一个ID则写入。若:=后面是一个表达式，则可以在再新建一个结构体变量，在其中处理表达式的四元式生成。然后把所得的地址存入上一层的对应位置。实验总结这次的实验比较难。刚刚拿到手的时候感觉无从下手，找不到一个突破点。其主要10难点在于如何实现回填技术。在实现语法分析器时，整体采用模块化编程的思想。将一个程序拆分成各个部分，分别实现。在实现各个子模块时需要注意的地方就是在实现语法分析时要考虑到各种情况，比如同时定义多个变量等。对此我采用了后缀的处理方式。后缀可有可无。这样就能解决在顺序分析程序时出现多条相同类型的语句以及在一条语句中出现多个变量定义等情况。还有就是在处理语义分析时如何处理表达式和控制语句回填位置这样的问题。本次实验虽然比较大，但不得不说，它在很大程度上锻炼了我们分析、处理问题的能力。由于我采用的是模块化编程的方式。这样编程的好处在于程序的结构清晰，紧密相连。但是带来的负面结果是程序的函数多。无论在写函数还是在调试程序的时候需要极大的耐心。实验中也遇到了不少小问题。比如读文件时如何才能使指针回退等。这些都通过自己的努力和同学的帮助，不仅仅是克服了这些问题，更重要的意义在于我又学会了一些以前不懂的知识。同时我也感受到了理论与实现之间的差距。那些平时上课时觉得很容易懂的知识，要通过自己在计算机上进行实现并不像想象中的那么容易。我们能理解的知识用计算机语言表述成计算机能理解的语言，这不仅需要很扎实的编程基础，更要彻彻底底的搞懂所学的理论知识，并达到将所学知识融会贯通的程度。这样才能自由的应付实现时出现的细节问题。总之，这次的课程设计让我收获颇多。参考资料【1】陈火旺、刘春林、谭庆平、赵克佳、刘越，编译原理（第三版）.北京：国防工业出版社【2】黄贤英、王柯柯，编译原理及实践教程。北京：清华大学出版社【3】马知行、曹启君，编译方法。机械工业出版社附录一：程序代码#includeiostream#includewindows.h#includestdio.h11usingnamespacestd;#defineAND1#defineBEGIN2#defineBOOL3#defineDO4#defineELSE5#defineEND6#defineFALSE7#defineIF8#defineINTEGER9#defineNOT10#defineOR11#definePROGRAM12#defineREAL13#defineTHEN14#defineTRUE15#defineVAR16#defineWHILE17#defineID18#define整数19#define实数20#defineLBR21#defineRBR22#defineADD23#defineSUB24#defineMUL25#defineDIV26#defineDOT27#defineCOM28#defineCOL29#defineSEM30#defineASS31#defineEQU32#defineLEQ33#defineLAB34#defineNEQ35#defineRAB36#defineGEQ37#defineODD38#pragmaoncetypedefstructtoken{intlabel;//单词序号12charname[30];//单词本身intcode;//单词的机内码intaddr;//地址，单词为保留字时为-1，为标识符或常数时为大于的数值，即在符号表中的入口地址。token(){label=0;code=0;addr=0;}}token;voidgetbuf();voidprogram();voidproghead();//程序首部由program标识符组成voidblock();//程序体部分voiderror(intn);voidconsdefi();voidconsexpl();v