编译原理学士学位毕业论文.doc
《编译原理学士学位毕业论文.doc》由会员分享，可在线阅读，更多相关《编译原理学士学位毕业论文.doc（16页珍藏版）》请在冰点文库上搜索。
中国农业大学学士学位论文第一章绪论
摘要
编译原理课程是全国高等院校计算机系各专业必修的专业技术基础课程。
这门课程具有原理性强、概念多、理论与实践结合紧密等特点。
为了提高教学质量和工作效率，将计算机辅助教学引入该课程的教学环节中是非常有必要的。
整个软件分为两个部分，分别用于PL/0演示和教学练习解题。
教学练习系统包括了一下6个部分：
语法基础部分、词法分析、语法部分、中间代码生成、基本块划分、基本块内的优化。
我所要做的工作内容主要有：
PL/0演示部分的功能完善和错误纠正；教学练习部分中基本块内的优化，实现由四元式向DAG图的转化。
编译原理辅助教学软件的设计充分利用VisualC++.Net开发环境的底层控制能力和C++高级语言，C++语言中的封装、继承等概念使得编程实现简单，逻辑清楚。
该软件可辅助教师教学，也有利于学生理解编译原理课程中的基本原理，同时也可以作为课程的配套练习工具。
关键字：
基本块内的优化，面向对象技术，编译原理
Abstract
Asweallknown,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平台接合。
Visual C++正式这样一个开发环境，它操作简单，而且界面结构和风格明晰，使用灵活，同时它兼容标准C和标准C++语言。
而C++语言功能强大、能够有效地实现封装和继承。
Visual C++采用的框架是MFC。
MFC不仅仅是人们通常理解的一个类库。
如果选择了MFC，也就选择了一种程序结构，一种编程风格。
MFC早在Windows 3.x的时代就出现了，那时的Visual C++还是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图
输出优化结果
语法基础部分
最左推导
生成语法树
最右推导
中间代码生成
编译原理辅助教学软件
LL
（1）分析法
自顶
向下
自底
向上
语法部分
LR
（1）分析法
SLR
（1）分析法
LR（0）分析法
LALR
（1）分析法
划分基本块
词法分析
NFA到DFA
DFA最小化
正规式到NFA
正规文法到正规式
基本块内的优化
图1-1系统整体框架图
第二章系统开发环境及其相应的技术简介
2.1编译原理概述
编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。
从概念上讲，一个编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序的一种表示形式转化成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的，下图给出了一个编译过程划分成了词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段，我们将就这几个方面进行系统模块设计，实现其功能。
如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理[5]。
将高级语言翻译成较低级的、面向机器的汇编语言或者某种中间表示，是非常复杂和困难的事情。
通过几代计算机科学家的探索经验可以得出一套行之有效的思想，这就是，把高级语言的翻译这个问题划分成若干个相对容易解决的小问题，然后采用分而治之的策略逐个攻破。
下图为编译流程图
源程序
词法分析、语法分析
输出
代码生成
语义分析
代码编译
抽象语法树
图2-1编译过程
2.2面向对象技术
面向对象程序设计技术（OOP）是目前流行的系统设计开发技术，它包括面向对象分析和面向对象程序设计。
OOP之所以引起如此大的关注，和C++编程语言的流行是分不开的。
面向对象的编程方法具有四个基本特征：
抽象：
抽象就是忽略一个主题中与目前目标无关的那些方面，以便更充分地注意与当前目标有关的方面[6]。
继承：
是一种联结类的层次模型，并且允许类的重用，它提供了一种明确表述共性地方法。
对象的一个新类可以从现有的类中派生，这个过程成为继承类。
派生类可以从它地基类那里继承方法和实例变量，并且类可以修改或增加新的方法使之更适合特殊的需要[6]。
封装：
是面向对象特征之一，是对象和类概念的主要特征。
封装是把过程和数据包围起来，对数据的访问只能通过已定义的类。
这些对象通过一个受保护地接口访问其他对象[6]。
多态性：
是指允许不同类地对象对同一消息做出其相应的响应。
比如同样的加法，将数字相加和字符串相加，是不一样的。
多态性语言具有灵活、抽象行为共享、代码共享的优势，很好地解决了应用程序函数同名问题[6]。
2.3MFC
MFC微软基础类库（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不只是一个功能单纯的界面开发系统,它提供的类绝大部分用来进行界面开发,关联一个窗口的动作,但它提供的类中有好多类不与一个窗口关联,即类的作用不是一个界面类,不实现对一个窗口对象的控制（如创建,销毁）,而是一些在WinOS（用MFC编写的程序绝大部分都在WinOS中运行）中实现内部处理的类,如数据库的管理类等。
[3]
VisualC++系列的工具中使用了MFC应用程序架构。
因此，在利用这些工具进行开发时，熟悉MFC将有助于软件开发过程的顺利进行。
2.4VisualC++.NET概述
在众多的开发软件工具中，Microsoft公司的VisualC++.NET独树一帜，将面向对象的程序设计方法和可视化的软件开发环境完美地结合起来。
VisualC++程序的执行速度以及对操作系统访问的权限之高，是其他许多语言无法比拟的，加上Windows操作系统的支持，就使得VisualC++的高级程序员对整个计算机的硬件系统和软件系统在各方面的访问和控制更加游刃有余。
因此，有人说：
“用VisualC++的眼光看，整个计算机都是透明的，或者说是完全裸露的”[6]。
第三章代码优化的实现思想
3.1优化技术简介
所谓优化，实质上是对代码进行等价变换，使得变换后的代码运行结果和变换前代码运行结果相同，而运行速度加快或是占用存储空间减少，或两者都有[5]。
优化可在编译的不同阶段进行，对同一阶段，涉及的程序范围也有所不同，在同一范围内，可进行多种优化。
一般，优化工作阶段可在中间代码生成之后和目标代码生成之后进行。
中间代码的优化是对中间代码进行等价变换。
目标代码的优化是在目标代码生成之后进行的，对应于具体的计算机，很大程度上依赖于具体的机器[5]。
3.2常用代码优化技术
3.2.1强度削弱
强度削弱是指用执行效率较高的操作等价地替换原操作。
例如，乘（或除）以2的n次方的运算可用左（或右）移n位实现（X*8等价于X<<3）;类似地，以2的n次方为模的求模运算可用按位与操作实现（例如，X%8==X&7）。
另外，用加法代替乘法也可提高效率.如x*=3可替换为：
{t=x;x+=t;x+=t；}。
联合使用移位和加法，可以削弱乘法的强度。
例如x*=9可替换为{t=x;t<<=3;x+=t;}即x*9=x*8+x=（x<<3）+x。
注意，上述优化与具体运算对象的值有关，有时会得不偿失，故应权衡各利弊，酌情采用。
对于非算术运算也可削弱强度，如尽量多使用寄存器，少访问内存（或外存）等。
3.2.2常数合并与常数传播
常数合并是指在编译时就将源程序中常数表达式之值先行算出，不必生成计算该表达式的代码。
例如，a+2*3可翻译成a+6.表达式a+1+3在翻译阶段生成的代码为：
{T1=a；T1+=1；T1+=3；}，由于对T1的两次定值未被引用，可将其修改为：
{T1=a;T1+=4；}。
常数传播是指在运行时，若一些变量之值在某段代码中保持不变，则在此范围内对该变量的引用可替换为对其值的直接引用，传播将一直延续到对其重新定值为止。
例如，a=3;…/*未对a重新定值*/;b=a;可改为:
a=3;…;b=3;等等。
3.2.3删除无用变量与无用代码
变量的最后一次引用到下次引用之前的最近一次赋值期间，可视为无用变量。
在变量的无用期内。
对其的任何赋值均可删除。
对于那些被赋值后从未被引用的变量，对其进行赋值操作也是无用赋值，可删除之。
例如，程序{t0=a;t0+=5;x=t0;…;t0+=1;…t0=b;}中的赋值t0+=1可予以删除。
无用代码是指控制永远不能到达的代码，如：
语句if（0）{…}中花括号内为无用代码。
对于无用代码，可将其删除。
无用代码可能还会受常数传播的影响，例如，函数
fool（）{inti,j,array[10];i=5;++i;j=array[i];…}
中，i并不是无用变量，但利用常数传播优化后，函数变为
fool（）{inti,j,array[10];i=5;++i;j=array[6];…}
此时，i变为无用变量，删除后程序为
fool（）{intj;array[10];j=array[6];…}
3.3基本块内的优化思想及算法
3.3.1基本块介绍
所谓基本块是指程序中一个顺序执行的语句序列，其中只有一个入口语句和一个出口语句。
执行时只能从其入口语句进入，从其出口语句退出。
对于一个给定的程序，我们可以把它划分为一系列的基本块。
在各基本块的范围内分别进行优化。
基本块内可进行优化的项目有：
删除公共子表达式；删除无用代码；重新命名临时变量；交换语句次序。
在程序中划分基本块的算法如下：
⑴确定各基本块的入口：
①程序的第一四元式；
②转向语句的目标四元式；
③紧跟在条件转移四元式后的四元式。
⑵从每个入口四元式开始，确定各基本块应包含的四元式：
每个入口及此入口到下一入口之间的四元式（不含下一入口），或直至停机四元式为止的所有四元式都属于相应的基本块。
⑶执行上述⑴,⑵后，凡未包含在任何基本块中的四元式，都是控制不可能达到的四元式，应删除。
3.3.2DAG图介绍
基本块的DAG图表示优化基本块的一种有效工具是无回路有向图（DirectedAcyclicGraph,简记为DAG），一个基本块可以用一个DAG来表示。
DAG对其各结点按如下方式进行标记：
·DAG中每个叶结点，用一变量或常数标记，表示该点代表此变量（常数）之值。
若代表变量A的地址值，则用addr（A）标记。
在表示变量的初值时，变量加下标0用于区分变量的当前值；
·DAG的内部结点都用一运算符标记，代表用其直接后继所代表之值进行该运算后的结果。
·DAG的各结点上，可附加若干符号名，以表示这些符号都持有相应结点所代表的值。
以下是DAG图结点类型的对应表：
注：
图中ni为结点编号，结点下面的符号（运算符、标识符或常数）是各结点的标记，各结点右边的标识符是结点的附加标识符。
3.3.3DAG图的构造算法
假设DAG各结点信息将用某种适当的数据来存放。
并设有一个标识符（包括常数）与结点的对应表。
NODE（A）是描述这种对应关系的一个函数，它的值或者是一个结点编号n，或者无定义。
前一种情况代表DAG中存在一个结点n，A是其上的标记或附加标识符。
首先，DAG为空；
对基本块的每一四元式，依次执行：
1.如果NODE（B）无定义，则构造一标记为B的叶结点并定义NODE（B）为这个结点；
如果当前四元式是0型，则记NODE（B）的值为n，转4.
如果当前四元式是1型，则转2
（1）。
如果当前四元式为2型，则：
（1）如果NODE（C）无定义，则构造一标记为C的叶结点并定义NODE（C）为这个结点；
（2）转2
（2）。
2.
（1）如果NODE（B）是标记为常数的叶结点，则转2（3），否则转3
（1）。
（2）如果NODE（B）和NODE（C）都是标记为常数的叶结点，则转2（4），否则转3
（2）。
（3）执行opB（即合并已知量），令得到的新常数为P。
如果NODE（B）是处理当前四元式时新构造出来的结点，则删除它。
如果NODE（P）无定义，则构造一用P做标记的叶结点n。
置NODE（P）=n，转4。
（4）执行BopC（即合并已知量），令得到的新常数为P。
如果NODE（B）或NODE（C）是处理当前四元式时新构造出来的结点，则删除它。
如果NODE（P）无定义，则构造一用P做标记的叶结点n。
置NODE（P）=n，转4。
3.
（1）检查DAG中是否已有一结点，其唯一后继为NODE（B），且标记为op（即找公共子表达式）。
如果没有，则构造该结点n，否则就把已有的结点作为它的结点并设该结点为n，转4。
（2）检查DAG中是否已有一结点，其左后继为NODE（B），其右后继为NODE（C），且标记为op（即找公共子表达式）。
如果没有，则构造该结点n，否则就把已有的结点作为它的结点并且设该节点为n，转4。
4.如果NODE（A）无定义，则把A附加在结点n上并令NODE（A）=n；否则先把A从NODE（A）结点上附加标识符集中删除（注意，如果NODE（A）是叶节点，则其标记A不删除），把A附加到新结点n上并令NODE（A）=n。
转处理下一四元式。
而后，我们可由DAG重新生成原基本块的一个优化的代码序列。
第四章具体模块的设计与实现
4.2基本块的优化的设计与实现
4.2.1系统模式的选择
基本块内的优化这部分因为涉及到作图，所以，在选择设计模式的时候必须要慎重，这样以后的工作才能顺利进行下去。
虽然绘图过程在视图/文档模式下实现起来比较方便，但这部分的设计，最终选择了对话框模式来做，主要出于以下几方面的原因：
首先，整个软件已经实现的功能模块都是在对话框中完成的，为了实现整体风格的统一，使用对话框模式比较协调；其次，对话框模式设计时可以方便的添加控件，虽然增加了绘图的难度，但是在这一部分又省去了不少麻烦；再次，对话框界面的直观效果好，在功能并不是很繁多的时候，可以非常方便的通过点击按钮来实现各种操作，对于一个用于教学演示的系统这一点很重要。
4.1.2
致谢
本课题是在王莲芝老师的悉心指导和严格要求下完成的。
王老师慈祥和蔼、平易近人，在生活、学习和毕设上给予了我们无微不至的关怀和帮助。
毕业设计期间，老师在课题的选题、方案确定和实施等各方面都给予了我大量精心的指导，付出了巨大的心血，使我对做软件开发的思路和认识上有了极大的飞跃。
在此，对王老师表示诚挚的敬意和忠心的感谢，祝愿老师永远身体健康、生活愉快。
感谢协助老师指导我们的宋强师兄。
在毕设的过程中，师兄经常来到实验室询问我们的毕设情况，跟我们一起讨论，及时的给我们纠正问题，给予了很多宝贵
升级会员 