《编译原理辅助教学软件的设计.doc》由会员分享，可在线阅读，更多相关《编译原理辅助教学软件的设计.doc（15页珍藏版）》请在三一办公上搜索。
1、 摘要编译原理课程是全国高等院校计算机系各专业必修的专业技术基础课程。这门课程具有原理性强、概念多、理论与实践结合紧密等特点。为了提高教学质量和工作效率，将计算机辅助教学引入该课程的教学环节中是非常有必要的。整个软件分为两个部分，分别用于PL/0演示和教学练习解题。教学练习系统包括了一下6个部分：语法基础部分、词法分析、语法部分、中间代码生成、基本块划分、基本块内的优化。我所要做的工作内容主要有：PL/0演示部分的功能完善和错误纠正；教学练习部分中基本块内的优化，实现由四元式向DAG图的转化。编译原理辅助教学软件的设计充分利用Visual C+.Net开发环境的底层控制能力和C+高级语言，C+
2、语言中的封装、继承等概念使得编程实现简单，逻辑清楚。该软件可辅助教师教学，也有利于学生理解编译原理课程中的基本原理，同时也可以作为课程的配套练习工具。关键字：基本块内的优化，面向对象技术，编译原理 Abstract As we all known, there are thousands of computer language existing in the world. So many languages could be applied in the computer by reason of compiler program. Compiler Principle is an impo
3、rtant special course for the computer major, particularly for software major of computer department .In order to provide students with a straight and explicit understanding of complier process of senior language , we developed the computer-assisted software of complier program to help in the class.T
4、his software is consisted of two parts: one is CAI (Computer-Aided Instruction) of PL/0, the other is an exercise system for teachers and students. The exercise system is consisted of five parts: Base Syntax Analysis, Lexical Analysis, Syntax Analysis, Intermediate Code Generation, Basic Block Parti
5、tioning and Basic block in the optimization . Most of my work involve: PL / 0 perfect demonstration of the function and error correction; part of teaching practice in the basic block optimization, and from four formula to the DAG graphic.Computer Assisted Instruction of Compilation, taking full adva
6、ntage of the basal powerful control ability of Visual C+.Net and C+, is a good assistant software helpful for students to study and understand the course of Compiler Principle clearly. It could be used not only for teachers illustration in class, but also for students exercise after class.Key board:
7、 Basic block in the optimization, Object-Oriented Programming, Compiler Principle 第一章 绪论1.1 编译原理辅助教学软件的设计背景 本系统以编译原理为基础、以C/C+为实现语言、Visual Studio.Net 2003为开发平台，主要实现编译器的基本设计方法和一些自动构造功能。本系统是一个教学辅助软件，实现辅助教学和辅助课后习题求解的功能。本系统包含了编译器所有的组成部分，如词法分析、语法分析、语义分析、代码生成和代码优化等各个部分。编译器本身就是一个十分庞大而复杂的系统软件，涉及到许多复杂的数据结构、程序
8、设计语言和算法，要开发实现其功能，在理论上要求掌握编译技术和有关编译的抽象概念，在技术上要求具有软件开发的能力。 我们此次的设计是在前人已经开发了部分功能模块的基础上，继续完成其它部分功能，并对以前存在的问题进行处理。1.2 编译原理课程建设的研究现状 编译原理是一门理论性极强，抽象程度也很高的课程，关于这一课程的教学应该更多的与实践相结合，突破传统的教学模式才能去得良好的效果。目前国内对这一课程的教学主要采取多媒体方式，配合图形、动画效果，而达到使学生更容易接受和感兴趣。清华大学计算机系曾基于DOS环境开发了编译原理辅助教学软件THPL0CAI和TH_CCAIS，能动态地显示程序编译的过程，
9、并能够解答相关习题，显示程序的中间状态。这套系统被应用教学，并取得了很大的成效。但是DOS环境下，对程序的操作性受到了很大的限制。另一方面，目前的多媒体教学大都采用Windows平台，这种只能在DOS平台下实现的功能在实际的教学中已经很难应用。因此，开发一个可以应用于Windows平台下的软件系统成为一种趋势，已经有不少学校在着手这一方面的开发。1.3 系统环境的选择作为一个用于辅助教学的软件，我们所完成的系统应该具有很好的人机交互界面，实现完备的功能的同时具有方便简单的操作性。另一方面，考虑到系统将来的应用环境是在Windows操作系统下，因此我们所开发出来的软件应该能够较好地与Window
10、s平台接合。VisualC+正式这样一个开发环境，它操作简单，而且界面结构和风格明晰，使用灵活，同时它兼容标准C和标准C+语言。而 C+语言功能强大、能够有效地实现封装和继承。VisualC+采用的框架是MFC。MFC不仅仅是人们通常理解的一个类库。如果选择了MFC，也就选择了一种程序结构，一种编程风格。MFC早在Windows3.x的时代就出现了，那时的VisualC+还是16位的。经过这些年的不断补充和完善，MFC已经十分成熟。由于该软件以前所完成的各模块是在VC+.Net 2003下实现的整合，因此最终本系统选择了由C+/C语言实现的VC+.Net 2003作为编译系统的开发工具。1.4
11、编译原理辅助教学软件功能设计说明编译原理辅助教学软件，其功能（图1-1）包括如下方面：1、语法基础部分：对文法符号串进行：最左或最右推导构造语法树判定输入串是否为指定文法的句子或句型（规范句型）2、词法分析：对正规式、有穷自动机和正规文法三者关系有：输入正规式可给出对应的不确定的、确定的和最小的有穷自动机输入有穷自动机可进行确定化和最小化输入正规文法可给出相应正规式3、语法分析：语法分析部分可对已输入的文法：构造LL（1）、LR分析表，其中LR分析表可有四种：LR（0）、SLR（1）、LALR（1）、LR（1）若所构造的分析表满足相应文法的要求，则用相应分析表可对输入的终结符串进行分析，给出分
12、析过程，并说明输入串是否为正确句子。4、中间代码生成：该过程应可对以PASCAL语句格式给出的简单语句序列：生成四元式代码对含有条件语句和循环语句的语句序列可给出相应四元式代码及其回填次序。对表达式和赋值语句可生成逆波兰式。5、划分基本块对四元式形式的中间代码进行基本块的划分。6、基本块内的优化 对C语言形式的复制语句表示的四元式序列构造DAG图 输出优化结果语法基础部分最左推导生成语法树最右推导中间代码生成编译原理辅助教学软件LL(1)分析法自顶向下自底向上语法部分LR(1)分析法SLR(1)分析法LR(0)分析法LALR(1)分析法划分基本块词法分析NFA到DFADFA最小化正规式到NFA
13、正规文法到正规式基本块内的优化 图1-1系统整体框架图第二章 系统开发环境及其相应的技术简介2.1 编译原理概述编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。从概念上讲，一个编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序的一种表示形式转化成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的，下图给出了一个编译过程划分成了词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段，我们将就这几个方面进行系统模块设计，实现其功能。如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的
14、范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理5。 将高级语言翻译成较低级的、面向机器的汇编语言或者某种中间表示，是非常复杂和困难的事情。通过几代计算机科学家的探索经验可以得出一套行之有效的思想，这就是，把高级语言的翻译这个问题划分成若干个相对容易解决的小问题，然后采用分而治之的策略逐个攻破。下图为编译流程图源程序词法分析、语法分析输出代码生成语义分析代码编译抽象语法树图2-1 编译过程2.2 面向对象技术面向对象程序设计技术（OOP）是目前流行的系统设计开发技术，它包括面向对象分析和面向对象程序设计。OOP之所以引起如此大的关注，和C+编程
15、语言的流行是分不开的。面向对象的编程方法具有四个基本特征：抽象：抽象就是忽略一个主题中与目前目标无关的那些方面，以便更充分地注意与当前目标有关的方面6。继承：是一种联结类的层次模型，并且允许类的重用，它提供了一种明确表述共性地方法。对象的一个新类可以从现有的类中派生，这个过程成为继承类。派生类可以从它地基类那里继承方法和实例变量，并且类可以修改或增加新的方法使之更适合特殊的需要6。封装：是面向对象特征之一，是对象和类概念的主要特征。封装是把过程和数据包围起来，对数据的访问只能通过已定义的类。这些对象通过一个受保护地接口访问其他对象6。多态性：是指允许不同类地对象对同一消息做出其相应的响应。比如
16、同样的加法，将数字相加和字符串相加，是不一样的。多态性语言具有灵活、抽象行为共享、代码共享的优势，很好地解决了应用程序函数同名问题6。2.3 MFCMFC微软基础类库(Microsoft Foundation Classes)，是一个把API函数利用面向对象的原理逻辑地组织起来的类库。基于MFC的应用程序设计，开发人员在程序设计的过程中可以不必去了解多如牛毛的API函数，只用专注在MFC的结构上即可。MFC中有3个非常重要的基本基类：CObject类、CCmdTarget类和CWnd类。其中CCmdTarget类从CObject类派生，而CWnd类又从CCmdTarget类派生。从派系的角度出
17、发，MFC类库可分为四大类：CObject类派生的支持动态创建对象和串行化的类、从CCmdTarget类派生的支持消息映射和命令传递的类、从CWnd类派生的支持标准Windows消息并在屏幕上显示一个窗口的类、非CObject派生的类。6基于MFC的应用程序框架是定义了程序结构的MFC类库中类的集合。运用MFC应用程序框架能或得标准化的程序结构和用户接口，开发人员就不必过多地考虑用户界面，而把主要的精力放在程序设计上，以提高程序设计的效率。有了应用程序框架之后，开发人员只要依据个人需要在派生类中改写虚函数，定义新的数据成员，用资源编辑器增加或修改用户界面，进行消息映射、定义新类就行了。另外，M
18、FC不只是一个功能单纯的界面开发系统,它提供的类绝大部分用来进行界面开发,关联一个窗口的动作,但它提供的类中有好多类不与一个窗口关联,即类的作用不是一个界面类,不实现对一个窗口对象的控制(如创建,销毁),而是一些在WinOS(用MFC编写的程序绝大部分都在WinOS中运行)中实现内部处理的类,如数据库的管理类等。3Visual C+系列的工具中使用了MFC应用程序架构。因此，在利用这些工具进行开发时，熟悉MFC将有助于软件开发过程的顺利进行。2.4 Visual C+.NET概述在众多的开发软件工具中，Microsoft 公司的Visual C+.NET 独树一帜，将面向对象的程序设计方法和可
19、视化的软件开发环境完美地结合起来。Visual C+程序的执行速度以及对操作系统访问的权限之高，是其他许多语言无法比拟的，加上Windows操作系统的支持，就使得Visual C+的高级程序员对整个计算机的硬件系统和软件系统在各方面的访问和控制更加游刃有余。因此，有人说：“用Visual C+的眼光看，整个计算机都是透明的，或者说是完全裸露的”6。第三章 代码优化的实现思想3.1 优化技术简介 所谓优化，实质上是对代码进行等价变换，使得变换后的代码运行结果和变换前代码运行结果相同，而运行速度加快或是占用存储空间减少，或两者都有5。 优化可在编译的不同阶段进行，对同一阶段，涉及的程序范围也有所不
20、同，在同一范围内，可进行多种优化。一般，优化工作阶段可在中间代码生成之后和目标代码生成之后进行。中间代码的优化是对中间代码进行等价变换。目标代码的优化是在目标代码生成之后进行的，对应于具体的计算机，很大程度上依赖于具体的机器5。3.2 常用代码优化技术3.2.1强度削弱强度削弱是指用执行效率较高的操作等价地替换原操作。例如，乘(或除)以2的n次方的运算可用左(或右)移n位实现(X*8等价于X3);类似地，以2的n次方为模的求模运算可用按位与操作实现(例如，X%8=X&7)。另外，用加法代替乘法也可提高效率.如x*=3可替换为：t=x; x+=t; x+=t；。联合使用移位和加法，可以削弱乘法的
21、强度。例如x*=9可替换为t=x; t=3; x+=t; 即x*9 = x*8+x = (x3)+x。注意，上述优化与具体运算对象的值有关，有时会得不偿失，故应权衡各利弊，酌情采用。对于非算术运算也可削弱强度，如尽量多使用寄存器，少访问内存(或外存)等。3.2.2常数合并与常数传播常数合并是指在编译时就将源程序中常数表达式之值先行算出，不必生成计算该表达式的代码。例如，a+2*3可翻译成a+6. 表达式a+1+3在翻译阶段生成的代码为：T1=a；T1+=1；T1+=3；，由于对T1的两次定值未被引用，可将其修改为：T1=a; T1+=4；。常数传播是指在运行时，若一些变量之值在某段代码中保持不
22、变，则在此范围内对该变量的引用可替换为对其值的直接引用，传播将一直延续到对其重新定值为止。例如，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) 中花括号内为无用代码。对于无用代码，可将其删除。无用代码可能还
23、会受常数传播的影响，例如，函数fool()int i,j,array10; i=5;+i; j=arrayi; 中，i并不是无用变量，但利用常数传播优化后，函数变为fool()int i,j,array10;i=5;+i; j=array6;此时，i变为无用变量，删除后程序为fool()int j;array10; j=array6;3.3 基本块内的优化思想及算法 3.3.1 基本块介绍 所谓基本块是指程序中一个顺序执行的语句序列，其中只有一个入口语句和一个出口语句。执行时只能从其入口语句进入，从其出口语句退出。对于一个给定的程序，我们可以把它划分为一系列的基本块。在各基本块的范围内分别进行
24、优化。基本块内可进行优化的项目有：删除公共子表达式；删除无用代码；重新命名临时变量；交换语句次序。 在程序中划分基本块的算法如下：确定各基本块的入口：程序的第一四元式；转向语句的目标四元式；紧跟在条件转移四元式后的四元式。从每个入口四元式开始，确定各基本块应包含的四元式：每个入口及此入口到下一入口之间的四元式(不含下一入口)，或直至停机四元式为止的所有四元式都属于相应的基本块。执行上述,后，凡未包含在任何基本块中的四元式，都是控制不可能达到的四元式，应删除。 3.3.2 DAG图介绍 基本块的DAG图表示优化基本块的一种有效工具是无回路有向图(Directed Acyclic Graph,简记
25、为DAG)，一个基本块可以用一个DAG来表示。DAG对其各结点按如下方式进行标记： DAG中每个叶结点，用一变量或常数标记，表示该点代表此变量(常数)之值。若代表变量A的地址值，则用addr(A)标记。在表示变量的初值时，变量加下标0用于区分变量的当前值； DAG的内部结点都用一运算符标记，代表用其直接后继所代表之值进行该运算后的结果。 DAG的各结点上，可附加若干符号名，以表示这些符号都持有相应结点所代表的值。 以下是DAG图结点类型的对应表： 注：图中ni为结点编号，结点下面的符号（运算符、标识符或常数）是各结点的标记，各结点右边的标识符是结点的附加标识符。3.3.3 DAG图的构造算法假
26、设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
27、（2）。 2.（1）如果NODE(B)是标记为常数的叶结点，则转2(3)，否则转3(1)。 （2）如果NODE(B)和NODE(C)都是标记为常数的叶结点，则转2(4)，否则转3(2)。 （3）执行op B（即合并已知量），令得到的新常数为P。如果NODE(B)是处理当前四元式时新构造出来的结点，则删除它。如果NODE(P)无定义，则构造一用P做标记的叶结点n。置NODE(P)= n，转4。 （4）执行B op C（即合并已知量），令得到的新常数为P。如果NODE（B）或NODE（C）是处理当前四元式时新构造出来的结点，则删除它。如果NODE（P）无定义，则构造一用P做标记的叶结点n。置NOD
28、E（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附加到新结
29、点n上并令NODE（A）= n。转处理下一四元式。而后，我们可由DAG重新生成原基本块的一个优化的代码序列。 第四章 具体模块的设计与实现4.2 基本块的优化的设计与实现4.2.1 系统模式的选择 基本块内的优化这部分因为涉及到作图，所以，在选择设计模式的时候必须要慎重，这样以后的工作才能顺利进行下去。虽然绘图过程在视图/文档模式下实现起来比较方便，但这部分的设计，最终选择了对话框模式来做，主要出于以下几方面的原因：首先，整个软件已经实现的功能模块都是在对话框中完成的，为了实现整体风格的统一，使用对话框模式比较协调；其次，对话框模式设计时可以方便的添加控件，虽然增加了绘图的难度，但是在这一部分
30、又省去了不少麻烦；再次，对话框界面的直观效果好，在功能并不是很繁多的时候，可以非常方便的通过点击按钮来实现各种操作，对于一个用于教学演示的系统这一点很重要。 致谢本课题是在王莲芝老师的悉心指导和严格要求下完成的。王老师慈祥和蔼、平易近人，在生活、学习和毕设上给予了我们无微不至的关怀和帮助。毕业设计期间，老师在课题的选题、方案确定和实施等各方面都给予了我大量精心的指导，付出了巨大的心血，使我对做软件开发的思路和认识上有了极大的飞跃。在此，对王老师表示诚挚的敬意和忠心的感谢，祝愿老师永远身体健康、生活愉快。感谢协助老师指导我们的宋强师兄。在毕设的过程中，师兄经常来到实验室询问我们的毕设情况，跟我们
31、一起讨论，及时的给我们纠正问题，给予了很多宝贵的意见。同时，我也要感谢和我一起毕设的郭毓伟同学和何健妮同学，陪我一起走过这段难忘的日子。这些日子我们一起很努力的学习，遇到问题的时候一起想办法解决，他们给了我很多的帮助。在算法设计和调试程序的时候郭毓伟同学帮我解决了很多问题，提出了很多很有建设性的提议，才使我的开发工作得以进行下去。有他们的鼓励和陪伴，在毕设一筹莫展、时间紧迫的情况下，我才能沉着的应付，努力的坚持下去。另外，为帮助我们解决困难，王老师联系了几位有丰富编程经验的师兄。他们认真地帮我们调试程序，解决了一些非常棘手的问题。谢谢他们！在毕业设计的这段时间里，我不仅仅学到了知识，同时深刻感
32、受到了团队合作的重要性。对于编程、调试，有时候由于自己的思维定势，所以即使是很简单的错误都有可能花很长时间都找不出来，但如果有人能够在旁指点一二，那工作的效率就会大大地提高。最后，我还想借此机会对大学里每一位教过我、关心过我的老师说一声：谢谢！是您们孜孜不倦的教诲为我敲开了计算机世界的大门，希望我能够在计算机这个领域里越走越好，不辜负各位老师的厚望，希望有一天我能够为我的母校农大争光。向所有关心、支持和帮助过我的老师、同学再道一声感谢！参考文献1 任哲.MFC Windows应用程序设计.北京：清华大学出版社,20062 张炜.Visual C+.NET程序设计与应用.北京：电子工业出版社,2
33、0023 程秉辉,John Hawke.Windows编程实战.北京：科学出版社,20054 位元文化.精通Visual C+.NET 2003窗口程序设计.北京：清华大学出版社,20065 吕映芝,张素琴,戴桂兰,蒋维杜.编译原理 .北京：清华大学出版社,20056 陈元琰.Visual C+.NET MFC类库应用详解.北京：科学出版社,20037 潘爱民,王国印 译.VC技术内幕 第四版.北京：清华大学出版,20048 李久进.MFC深入浅出. 湖北：华中理工出版社,20049 Kenneth C.Louden . 编译原理及实践.北京：机械工业出版社,200010郑 莉,董 渊.C+语
34、言程序设计.北京：清华大学出版社,200411陈维兴,林小茶.C+面向对象程序设计教程.北京：清华大学出版社,200512(美)Kenneth C.Louden compiled. Compiler Construction Principles and Practice. Thomson Learning,200213 陈火旺,钱家骅,孙永强.程序设计语言编译原理.北京：国防工业出版社,200414 赵克佳, 黄春,沈志宇 译.现代编译原理C语言描述.北京：人民邮电出版社,2006 15 温敬和.编译原理实用教程. 北京：清华大学出版社,200516 李动玉.Visual C+.NET实用编程100例.北京：中国铁道出版社,2006
