编译毕业论文

中国农业大学学士学位论文第一章绪论摘要编译原理课程是全国高等院校计算机系各专业必修的专业技术基础课程。这门课程具有原理性强、概念多、理论与实践结合紧密等特点。为了提高教学质量和工作效率，将计算机辅助教学引入该课程的教学环节中是非常有必要的。整个软件分为两个部分，分别用于PL/0演示和教学练习解题。教学练习系统包括了一下6个部分：语法基础部分、词法分析、语法部分、中间代码生成、基本块划分、基本块内的优化。我所要做的工作内容主要有：PL/0演示部分的功能完善和错误纠正；教学练习部分中基本块内的优化，实现由四元式向DAG图的转化。编译原理辅助教学软件的设计充分利用VisualC++.Net开发环境的底层控制能力和C++高级语言，C++语言中的封装、继承等概念使得编程实现简单，逻辑清楚。该软件可辅助教师教学，也有利于学生理解编译原理课程中的基本原理，同时也可以作为课程的配套练习工具。关键字：基本块内的优化，面向对象技术，编译原理中国农业大学学士学位论文第一章绪论AbstractAsweallknown,therearethousandsofcomputerlanguageexistingintheworld.Somanylanguagescouldbeappliedinthecomputerbyreasonofcompilerprogram.‘CompilerPrinciple’isanimportantspecialcourseforthecomputermajor,particularlyforsoftwaremajorofcomputerdepartment.Inordertoprovidestudentswithastraightandexplicitunderstandingofcomplierprocessofseniorlanguage,wedevelopedthecomputer-assistedsoftwareofcomplierprogramtohelpintheclass.Thissoftwareisconsistedoftwoparts:oneisCAI(Computer-AidedInstruction)ofPL/0,theotherisanexercisesystemforteachersandstudents.Theexercisesystemisconsistedoffiveparts:BaseSyntaxAnalysis,LexicalAnalysis,SyntaxAnalysis,IntermediateCodeGeneration,BasicBlockPartitioningandBasicblockintheoptimization.Mostofmyworkinvolve:PL/0perfectdemonstrationofthefunctionanderrorcorrection;partofteachingpracticeinthebasicblockoptimization,andfromfourformulatotheDAGgraphic.ComputerAssistedInstructionofCompilation,takingfulladvantageofthebasalpowerfulcontrolabilityofVisualC++.NetandC++,isagoodassistantsoftwarehelpfulforstudentstostudyandunderstandthecourseofCompilerPrincipleclearly.Itcouldbeusednotonlyforteacher’sillustrationinclass,butalsoforstudents’exerciseafterclass.Keyboard:Basicblockintheoptimization,Object-OrientedProgramming,CompilerPrinciple中国农业大学学士学位论文致谢第一章绪论1.1编译原理辅助教学软件的设计背景本系统以编译原理为基础、以C/C++为实现语言、VisualStudio.Net2003为开发平台，主要实现编译器的基本设计方法和一些自动构造功能。本系统是一个教学辅助软件，实现辅助教学和辅助课后习题求解的功能。本系统包含了编译器所有的组成部分，如词法分析、语法分析、语义分析、代码生成和代码优化等各个部分。编译器本身就是一个十分庞大而复杂的系统软件，涉及到许多复杂的数据结构、程序设计语言和算法，要开发实现其功能，在理论上要求掌握编译技术和有关编译的抽象概念，在技术上要求具有软件开发的能力。我们此次的设计是在前人已经开发了部分功能模块的基础上，继续完成其它部分功能，并对以前存在的问题进行处理。1.2编译原理课程建设的研究现状编译原理是一门理论性极强，抽象程度也很高的课程，关于这一课程的教学应该更多的与实践相结合，突破传统的教学模式才能去得良好的效果。目前国内对这一课程的教学主要采取多媒体方式，配合图形、动画效果，而达到使学生更容易接受和感兴趣。清华大学计算机系曾基于DOS环境开发了编译原理辅助教学软件THPL0CAI和TH_CCAIS，能动态地显示程序编译的过程，并能够解答相关习题，显示程序的中间状态。这套系统被应用教学，并取得了很大的成效。但是DOS环境下，对程序的操作性受到了很大的限制。另一方面，目前的多媒体教学大都采用Windows平台，这种只能在DOS平台下实现的功能在实际的教学中已经很难应用。因此，开发一个可以应用于Windows平台下的软件系统成为一种趋势，已经有不少学校在着手这一方面的开发。1.3系统环境的选择作为一个用于辅助教学的软件，我们所完成的系统应该具有很好的人机交互界面，实现完备的功能的同时具有方便简单的操作性。另一方面，考虑到系统将来的应用环境是在Windows操作系统下，因此我们所开发出来的软件应该能够较好地与Windows平台接合。VisualC++正式这样一个开发环境，它操作简单，而且界面结构和风格明晰，使用灵活，同时它兼容标准C和标准C++语言。而C++语言功能强大、能够有效地实现封装和继承。VisualC++采用的框架是MFC。MFC不仅仅是人们通常理解的一个类库。如果选择了MFC，也就选择了一种程序结构，一种编程风格。MFC早在Windows3.x的时代就出现了，那时的VisualC++还是16位的。经过这些年的不断补充和完善，MFC已经十分成熟。中国农业大学学士学位论文致谢由于该软件以前所完成的各模块是在VC++.Net2003下实现的整合，因此最终本系统选择了由C++/C语言实现的VC++.Net2003作为编译系统的开发工具。1.4编译原理辅助教学软件功能设计说明编译原理辅助教学软件，其功能（图1-1）包括如下方面：1、语法基础部分：对文法符号串进行：最左或最右推导构造语法树判定输入串是否为指定文法的句子或句型（规范句型）2、词法分析：对正规式、有穷自动机和正规文法三者关系有：输入正规式可给出对应的不确定的、确定的和最小的有穷自动机输入有穷自动机可进行确定化和最小化输入正规文法可给出相应正规式3、语法分析：语法分析部分可对已输入的文法：构造LL（1）、LR分析表，其中LR分析表可有四种：LR（0）、SLR（1）、LALR（1）、LR（1）若所构造的分析表满足相应文法的要求，则用相应分析表可对输入的终结符串进行分析，给出分析过程，并说明输入串是否为正确句子。4、中间代码生成：该过程应可对以PASCAL语句格式给出的简单语句序列：生成四元式代码对含有条件语句和循环语句的语句序列可给出相应四元式代码及其回填次序。对表达式和赋值语句可生成逆波兰式。5、划分基本块对四元式形式的中间代码进行基本块的划分。6、基本块内的优化对C语言形式的复制语句表示的四元式序列构造DAG图输出优化结果中国农业大学学士学位论文致谢图1-1系统整体框架图语法基础部分最左推导生成语法树最右推导中间代码生成编译原理辅助教学软件LL(1)分析法自顶向下自底向上语法部分LR(1)分析法SLR(1)分析法LR(0)分析法LALR(1)分析法划分基本块词法分析NFA到DFADFA最小化正规式到NFA正规文法到正规式基本块内的优化中国农业大学学士学位论文致谢第二章系统开发环境及其相应的技术简介2.1编译原理概述编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。从概念上讲，一个编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序的一种表示形式转化成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的，下图给出了一个编译过程划分成了词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段，我们将就这几个方面进行系统模块设计，实现其功能。如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理[5]。将高级语言翻译成较低级的、面向机器的汇编语言或者某种中间表示，是非常复杂和困难的事情。通过几代计算机科学家的探索经验可以得出一套行之有效的思想，这就是，把高级语言的翻译这个问题划分成若干个相对容易解决的小问题，然后采用分而治之的策略逐个攻破。下图为编译流程图中国农业大学学士学位论文致谢图2-1编译过程2.2面向对象技术面向对象程序设计技术（OOP）是目前流行的系统设计开发技术，它包括面向对象分析和面向对象程序设计。OOP之所以引起如此大的关注，和C++编程语言的流行是分不开的。面向对象的编程方法具有四个基本特征：抽象：抽象就是忽略一个主题中与目前目标无关的那些方面，以便更充分地注意与当前目标有关的方面[6]。继承：是一种联结类的层次模型，并且允许类的重用，它提供了一种明确表述共性地方法。对象的一个新类可以从现有的类中派生，这个过程成为继承类。派生类可以从它地基类那里继承方法和实例变量，并且类可以修改或增加新的方法使之更适合特殊的需要[6]。封装：是面向对象特征之一，是对象和类概念的主要特征。封装是把过程和数据包围起来，对数据的访问只能通过已定义的类。这些对象通过一个受保护地接口访问其他对象[6]。源程序词法分析、语法分析输出代码生成语义分析代码编译抽象语法树中国农业大学学士学位论文致谢多态性：是指允许不同类地对象对同一消息做出其相应的响应。比如同样的加法，将数字相加和字符串相加，是不一样的。多态性语言具有灵活、抽象行为共享、代码共享的优势，很好地解决了应用程序函数同名问题[6]。2.3MFCMFC微软基础类库(MicrosoftFoundationClasses)，是一个把API函数利用面向对象的原理逻辑地组织起来的类库。基于MFC的应用程序设计，开发人员在程序设计的过程中可以不必去了解多如牛毛的API函数，只用专注在MFC的结构上即可。MFC中有3个非常重要的基本基类：CObject类、CCmdTarget类和CWnd类。其中CCmdTarget类从CObject类派生，而CWnd类又从CCmdTarget类派生。从派系的角度出发，MFC类库可分为四大类：CObject类派生的支持动态创建对象和串行化的类、从CCmdTarget类派生的支持消息映射和命令传递的类、从CWnd类派生的支持标准Windows消息并在屏幕上显示一个窗口的类、非CObject派生的类。[6]基于MFC的应用程序框架是定义了程序结构的MFC类库中类的集合。运用MFC应用程序框架能或得标准化的程序结构和用户接口，开发人员就不必过多地考虑用户界面，而把主要的精力放在程序设计上，以提高程序设计的效率。有了应用程序框架之后，开发人员只要依据个人需要在派生类中改写虚函数，定义新的数据成员，用资源编辑器增加或修改用户界面，进行消息映射、定义新类就行了。另外，MFC不