1、编译原理课程设计第一章 概述1.1 项目背景：编译原理是国内外各高等院校计算机科学技术类专业，特别是计算机软件专业的一门重要专业课程。该课程系统地介绍编译程序的结构、工作流程及编译程序各组成部分的设计原理和实现技术。由于该课程理论性和实践性都比较强，内容较为抽象复杂，涉及到大量的软件设计算法，因此，一直是一门比较难学的课程。为了更好地理解和掌握编译技术的基本概念、基本原理和实现方法，实践环节非常重要，只有通过上机进行程序设计，才能对比较抽象的教学内容产生具体的感性认识，增强综合分析问题、解决问题的能力，并对提高软件设计水平大有益处。1.2 设计目的： 课程设计是学生学完本课程基础知识后的最后一
2、个实践性教学环节。作为一项专业综合能力训练，是本课程学习情况的总结与提高，是培养独立思考和科学工作方法，实现由学习向应用过渡的重要环节。 本次课程设计的主要目的如下：1、通过本次课程设计，全面系统的了解编译原理程序构造的一般原理和基本方法，尤其是对简单优先分析方法的认识和理解；2、提高对编译程序工作基本过程及各个阶段基本任务的分析技能；3、加强对编译程序的生成过程、构造工具及编译程序总流程框图的理解，巩固所学的课本知识。4、掌握简单优先文法分析是如何根据语法规则逐一分析词法分析所得到的单词，检查语法错误，即掌握语法分析过程；5、掌握简单优先文法分析器的设计与调试；6、掌握运用程序方法实现简单优
3、先文法分析的方法；7、锻炼并增强程序设计的能力，提高自己的编程水平。1.3 实验环境与开发工具： 本门课程设计“简单优先文法判定及分析器的构造”的实验是以计算机为基础的，其开发环境主要在两个方面，即硬件环境和软件环境。硬件环境是指你是用什么类型的服务器，内存硬盘的限制等等。软件环境就是软件运行的环境，例如你的操作系统是什么，你要运行的程序需要什么其他的软件支持什么的。我在试验过程中，所用计算机的软件设备和硬件指标分别如下：一、硬件环境：处理器 AMD 5200+ 2.70GHz内存（RAM） 2G 硬盘 320G 显示器AOC L1.831W 256M显卡二、软件环境：Windows 2000
4、/XP OS Microsoft Visual C+6.0 1.4 C+语言C+类中包含私有、公有和保护成员 C+类中可定义三种不同访问控制权限的成员。一种是私有(Private)成员，只有在类中说明的函数才能访问该类的私有成员，而在该类外的函数不可以访问私有成员；另一种是公有(Public)成员，类外面也可访问公有成员，成为该类的接口；还有一种是保护(Protected)成员，这种成员只有该类的派生类可以访问，其余的在这个类外不能访问。 1.5 Microsoft Visual C+ClassWizard（类向导）是Visual C+提供的强大的类处理工具。其中的Message Map(消息
5、映射)选项卡可以让我们添加或删除要处理的Windows消息处理器；Member Variable(成员变量)选项卡为应用程序中的类创建成员变量，并和控件联系在一起；Class Info（类信息）选项卡显示了应用程序中所包含类的一般信息，包括定义的头文件和源文件类名，以及与之相关联的基类。并且Add Class 按钮提供了在工程中创建新类的方法。1、第二章 需求分析2.1 问题陈述2.1.1 简单优先文法简单优先分析法是按照文法符号（终结符和非终结符）的优先关系确定句柄的，即它按一定的文法的基本思想，对一个文法按一定的原则求出该文法所有符号（包括终结符和非终结符）之间的优先关系按照这种关系确定规
6、约过程中的句柄，它的规约过程实际上是规范规约。简单优先分析法准确、规范，但分析效率很低，实际使用价值不大。在文法的符号之间建立一种(实际是三种)优先关系RVV,在分析的过程中,利用优先关系的比较,来确定前句型的句柄;在找到句柄后按相应的产生式归约之,并将归约出的VN符号压入栈,再进行新的比较,直到出错或分析成功.设G是已化简的文法,s,tV,若G中存在规范句型 =st, 则s,t与的句柄之间的关系必有下述情况之一 (1) A (2) (3) ST. .ST. ST . 在图1中S在句柄中而T不在。图2中ST都不在句柄中。图3中T在句柄中而S不在。对于上述情况我们规定图1:ST。图2：S=T；图
7、3:ST;2.1.2 简单优先文法的定义若一文法G的任何两个符号之间至多存在一种优先关系,且任意两个不同的产生式无相同的右部,则称G为简单优先文法。文法优先关系是指文法符号之间的关系，包括、 。1) S1=S2当且仅当中有规则 US1S2； 2)S1S2当且仅当中有规则 US1并使得 S2成立；根据关系乘积得到： S2当且仅当中有规则 U并使得R2.1.3 简单优先文法的算法利用优先矩阵进行分析的方法是,逐次查看当前句型X1X2Xm相邻两个符号的优先关系,一旦出现Xi+kXi+k+1, Xi+k即为句柄的尾符号,然后从Xi+k开始向左查看已扫描过的符号,直到发现Xi-1Y 表示X的优先性比Y的
8、优先性大。3） XY 表示X的优先性比Y的优先性小。由以上三种关系的定义，由文法产生式可求得问答符号之间的优先关系。为了表示简洁明了，我们把文法之间的关系用关系矩阵表示，称作优先关系矩阵。在优先关系矩阵中，矩阵中的元素要么为空要么只有一种关系，元素为空时表示该文法的任何句型中不会出现该符号对的相邻关系，在分析过程中若遇到这种相邻关系出现，则为出错，也就可以肯定输入符号串不是该文法的句子。2.3 分析器的构造 分析栈 输入流第三章 逻辑设计3.1系统的组织与基本工作流程本系统采用C+程序设计语言编写，主要用来分析用户输入文法的简单优先关系并构造优先关系表。系统的组织主要有以下基本分组成。 1）优
9、先文法判定模块 此模块根据简单优先文法的定义设计，判定输入的文法是否为简单优先文法。如果是，则继续执行下面的程序，如果不是，则退出。2）等于关系的判断模块 此模块判定文法中等于关系，判定出后保存入dengyuij中。3）小于关系模块此模块判定文法中小于关系，判定出后保存入相应的栈表中。4）大于关系模块同上面一样，判定大于关系，保存入相应的栈表中。5） 关系矩阵的构造经过分析，系统调用栈表中等于、小于、大于的数据，排列构成矩阵。3.2 总体结构逻辑结构图 第思章 软件功能设计4.1 软件功能分析4.1.1 判定文法是否为简单优先文法根据简单优先文法的定义可知：for( i=0;iright.si
10、ze ();i+) if(rightj=righti&i!=j) cout该文法不是简单优先文法，请重新输入。endl; return false; return true;4.1.2 查找分析文法优先关系相等for(i=0;in;i+) for(j=4;j10;j+) if(aij+1!=0) for(k=1;k=m;k+) for(r=1;r=m;r+) if(aar0=aij&aa0k=aij+1) b_dengyur-1k-1=1; printf(B等于的矩阵是：n); for(i=0;im;i+) printf( ); for(j=0;jm;j+) printf( %d ,b_den
11、gyuij); printf(nn); 4.1.3 查找分析文法中小于的关系for(i=0;im;i+) for(j=0;jm;j+) for(k=0;k1) b_xiaoyuij=1; printf(B的矩阵是：n); for(i=0;im;i+) printf( ); for(j=0;jm;j+) printf( %d ,b_xiaoyuij); printf(nn); 4.1.4 查找分析文法中大于的关系for(i=0;im;i+) for(j=0;jm;j+) for(k=0;km;k+) bbij+=b_transpose_tailjiaik*b_dengyukj; for(i=0;
12、im;i+) for(j=0;jm;j+) for(k=0;k1) b_dayuij=1; printf(B的矩阵是：n); for(i=0;im;i+) printf( ); for(j=0;jm;j+) printf( %d ,b_dayuij); printf(nn); 4.1.5 构造文法的简单优先关系矩阵for(i=0;im;i+) for(j=0;jm;j+) if(b_xiaoyuij=1) aai+1j+1=; else if(b_dengyuij=1) aai+1j+1=; for(i=1;i=m;i+) for(j=1;j=A&aa0j) aaij= ; printf(这些
13、文法得到的优先矩阵是：n); for(i=0;i=m;i+) for(j=0;j=m;j+) printf( %c ,aaij); printf(nn); 第五章 界面设计测试用例：S：=bAbA：=(B|aB：=Aa)5.1用户输入文法界面此界面为系统运行时首先出现的界面，根据提示输入文法的规则数，然后输入文法。5.2优先矩阵的初始状态5.3 文法中等于关系相应代码为for(i=0;in;i+) for(j=4;j10;j+) if(aij+1!=0) for(k=1;k=m;k+) for(r=1;r=m;r+) if(aar0=aij&aa0k=aij+1) b_dengyur-1k-1
14、=1; printf(B等于的矩阵是：n); for(i=0;im;i+) printf( ); for(j=0;jm;j+) printf( %d ,b_dengyuij); printf(nn); 5.4 小于关系相应代码为for(i=0;im;i+) for(j=0;jm;j+) for(k=0;k1) b_xiaoyuij=1; printf(B的矩阵是：n); for(i=0;im;i+) printf( ); for(j=0;jm;j+) printf( %d ,b_xiaoyuij); printf(nn);5.5 大于关系大于关系相应代码为：for(i=0;im;i+) for
15、(j=0;jm;j+) for(k=0;km;k+) bbij+=b_transpose_tailjiaik*b_dengyukj; for(i=0;im;i+) for(j=0;jm;j+) for(k=0;k1) b_dayuij=1; printf(B的矩阵是：n); for(i=0;im;i+) printf( ); for(j=0;jm;j+) printf( %d ,b_dayuij); printf(nn); 5.6 优先关系矩阵相应代码为： for(i=0;im;i+) for(j=0;jm;j+) if(b_xiaoyuij=1) aai+1j+1=; else if(b_d
16、engyuij=1) aai+1j+1=; for(i=1;i=m;i+) for(j=1;j=A&aa0j) aaij= ; printf(这些文法得到的优先矩阵是：n); for(i=0;i=m;i+) for(j=0;j=m;j+) printf( %c ,aaij); printf(nn); 小结随着编译技术的发展和社会对编译程序需求的不断增长，一些编译程序的自动生成工具。它的功能是以任一语言的词法规则、语法规则和语义解释出发，自动产生该语言的编译程序。目前很多自动生成工具已广泛使用，如词法分析程序的生成系统LEX，语法分析程序的生成系统YACC等。同时，不断有人使用自展技术来构造编译
17、程序，并且其影响越来越大。将串行程序转换成并行程序的自动并行编译技术也正在深入研究之中。通过本次课程设计很好复习了数据结构中所学的知识，认识到很多知识的运用问题，对栈的运用有了更深的理解，本次设计最深的感触是简单优先文法是一个非常准确，规范但分析效率很低的一种文法。通过本次课程设计，让我对简单优先算法尤其是小于关系有了较全面深入的了解，并且通过上机操作等更好的理解了相关理论知识，增强了自己的动手能力。本次课程设计中我的主要任务是对简单优先文法中的小于关系做相应的算法思想、编程设计和调试。在课程设计过程中，我对数据结构相关知识的掌握不够牢固，尤其对指针方面的内容，从而在编写程序过程中出现地址符丢
18、失等错误，这在后来的调试中通过查阅了相关材料后和同学的帮助下得以解决；另外，我对类的有关知识不够了解，从而导致未定义类，造成程序错误。此外，在画流程图时，画的比较烦琐，后来经过精简得出了比较简练流程图。总之，这次课程设计让我受益匪浅。不仅加深了我对编译原理和数据结构等课程的了解，而且也通过查阅资料和实践弥补了所有的不足之处。在今后的学习中，我会加强自己的动手能力，让理论和实践相结合，并且加强在专业课方面的学习。参考文献1、编译原理（第2版）清华大学出版社 张素琴 吕映之 等著2、Visual C+6.0开发使用手册 机械工业出版社 Brian Siler等著3、编译程序设计 北京大学出版社 王
19、永宁著（实现佳）4、程序设计语言编译原理 国防工业大学出版社 陈火旺著（原理强）5、编译原理（第二版） 西北工业大学出版社 蒋立源等著（方法全）6、软件工程导论（第三版） 清华大学出版社 张海潘著感谢：首先，感谢范老师能在此次课程设计中给我这样一个锻炼的机会，论文的完成离不开范老师的悉心指导和关怀。 在本次课程设计中，我从范老师身上学到了很多东西。范老师认真负责的工作态度，严谨的治学精神和深厚的理论水平都使我收益匪浅。她无论在理论上还是在实践中，都给与我很大的帮助，使我得到不少的提高这对于我以后的工作和学习都有一种巨大的帮助。 另外，在系统开发过程中，同组的同学也给与我不少帮助，在此一起感谢。
20、附录：#include#include#includeint n;char aa1010;char a1010;int bb2020=0;int b_dengyu2020=0;int b_head2020;int b_headjia2020;int b_head_I2020;int b_tail2020;int b_tailjia2020;int b_transpose_tailjia2020;int b_dayu2020;int b_xiaoyu2020;main() int i,j,k,r,L1=0,L2=0,m,len; char b10=0,c10=0; printf(请输入该文法的规
21、则数n：); scanf(%d,&n); printf(请输入这些文法：); for(i=0;i=n-1;i+) scanf(%s,ai);/输出终结符和非终结符 for(i=0;i=A&aij=L1) bk=aij; L1+; else if(aij!=:&aij!=) for(r=0;cr!=0;r+) if(aij=cr) break; if(r=L2) cr=aij; L2+; m=L1+L2; for(i=1;i=L1;i+) aa0i=bi-1; aai0=bi-1; for(j=0,i=L1+1;jL2,i=m;j+,i+) aa0i=cj; aai0=cj; printf(这个
22、优先矩阵的初始状态是：n); for(i=0;i=m;i+) for(j=0;j=m;j+) printf( %c ,aaij); printf(nn); /求b=的过程 len=strlen(a); for(i=0;in;i+) for(j=4;j10;j+) if(aij+1!=0) for(k=1;k=m;k+) for(r=1;r=m;r+) if(aar0=aij&aa0k=aij+1) b_dengyur-1k-1=1; printf(B等于的矩阵是：n); for(i=0;im;i+) printf( ); for(j=0;jm;j+) printf( %d ,b_dengyui
23、j); printf(nn); /求B_head的过程 for(i=0;in;i+) if(ai4!=0) for(k=1;k=m;k+) for(r=1;r=m;r+) if(aar0=ai0&aa0k=ai4) b_headr-1k-1=1; printf(B_head的矩阵是：n); for(i=0;im;i+) printf( ); for(j=0;jm;j+) printf( %d ,b_headij); printf(nn); /求B_head+的过程 for(i=0;im;i+) for(j=0;jm;j+) b_headjiaij=b_headij; for(i=0;im;i+) for(j=0;jm;j+) if(b_headjiaji=1) for(k=0;km;k+) b_headjiajk=b_headjiajk+b_headjiaik; if(b_he
