编译原理课程设计.docx
- 文档编号:2771586
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:31
- 大小:171.41KB
编译原理课程设计.docx
《编译原理课程设计.docx》由会员分享,可在线阅读,更多相关《编译原理课程设计.docx(31页珍藏版)》请在冰点文库上搜索。
编译原理课程设计
第一章概述
1.1项目背景:
《编译原理》是国内外各高等院校计算机科学技术类专业,特别是计算机软件专业的一门重要专业课程。
该课程系统地介绍编译程序的结构、工作流程及编译程序各组成部分的设计原理和实现技术。
由于该课程理论性和实践性都比较强,内容较为抽象复杂,涉及到大量的软件设计算法,因此,一直是一门比较难学的课程。
为了更好地理解和掌握编译技术的基本概念、基本原理和实现方法,实践环节非常重要,只有通过上机进行程序设计,才能对比较抽象的教学内容产生具体的感性认识,增强综合分析问题、解决问题的能力,并对提高软件设计水平大有益处。
1.2设计目的:
课程设计是学生学完本课程基础知识后的最后一个实践性教学环节。
作为一项专业综合能力训练,是本课程学习情况的总结与提高,是培养独立思考和科学工作方法,实现由学习向应用过渡的重要环节。
本次课程设计的主要目的如下:
1、通过本次课程设计,全面系统的了解编译原理程序构造的一般原理和基本方法,尤其是对简单优先分析方法的认识和理解;
2、提高对编译程序工作基本过程及各个阶段基本任务的分析技能;
3、加强对编译程序的生成过程、构造工具及编译程序总流程框图的理解,巩固所学的课本知识。
4、掌握简单优先文法分析是如何根据语法规则逐一分析词法分析所得到的单词,检查语法错误,即掌握语法分析过程;
5、掌握简单优先文法分析器的设计与调试;
6、掌握运用程序方法实现简单优先文法分析的方法;
7、锻炼并增强程序设计的能力,提高自己的编程水平。
1.3实验环境与开发工具:
本门课程设计“简单优先文法判定及分析器的构造”的实验是以计算机为基础的,其开发环境主要在两个方面,即硬件环境和软件环境。
硬件环境是指你是用什么类型的服务器,内存硬盘的限制等等。
软件环境就是软件运行的环境,例如你的操作系统是什么,你要运行的程序需要什么其他的软件支持什么的。
我在试验过程中,所用计算机的软件设备和硬件指标分别如下:
一、硬件环境:
处理器AMD5200+2.70GHz
内存(RAM)2G
硬盘320G
显示器AOCL1.831W
256M显卡
二、软件环境:
Windows2000/XPOS
MicrosoftVisualC++6.0
1.4C++语言
C++类中包含私有、公有和保护成员
C++类中可定义三种不同访问控制权限的成员。
一种是私有(Private)成员,只有在类中说明的函数才能访问该类的私有成员,而在该类外的函数不可以访问私有成员;另一种是公有(Public)成员,类外面也可访问公有成员,成为该类的接口;还有一种是保护(Protected)成员,这种成员只有该类的派生类可以访问,其余的在这个类外不能访问。
1.5MicrosoftVisualC++
ClassWizard(类向导)是VisualC++提供的强大的类处理工具。
其中的MessageMap(消息映射)选项卡可以让我们添加或删除要处理的Windows消息处理器;MemberVariable(成员变量)选项卡为应用程序中的类创建成员变量,并和控件联系在一起;ClassInfo(类信息)选项卡显示了应用程序中所包含类的一般信息,包括定义的头文件和源文件类名,以及与之相关联的基类。
并且AddClass按钮提供了在工程中创建新类的方法。
1、
第二章需求分析
2.1问题陈述
2.1.1简单优先文法
简单优先分析法是按照文法符号(终结符和非终结符)的优先关系确定句柄的,即它按一定的文法的基本思想,对一个文法按一定的原则求出该文法所有符号(包括终结符和非终结符)之间的优先关系按照这种关系确定规约过程中的句柄,它的规约过程实际上是规范规约。
简单优先分析法准确、规范,但分析效率很低,实际使用价值不大。
在文法的符号之间建立一种(实际是三种)优先关系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:
S﹥T。
图2:
S=T;图3:
S 2.1.2简单优先文法的定义 若一文法G的任何两个符号之间至多存在一种优先关系,且任意两个不同的产生式无相同的右部,则称G为简单优先文法。 文法优先关系是指文法符号之间的关系,包括﹦、<·、·>。 1)S1=S2当且仅当G中有规则U∷=…S1S2…; 2)S1<·S2当且仅当G中有规则U∷=…S1A…并使得 AL+S2成立;根据关系乘积得到: <·=(=)·(L+) 3)S1·>S2当且仅当G中有规则U∷=…AB…并使得AR+S1 2.1.3简单优先文法的算法 利用优先矩阵进行分析的方法是,逐次查看当前句型X1X2…Xm相邻两个符号的优先关系,一旦出现Xi+k>Xi+k+1,Xi+k即为句柄的尾符号,然后从Xi+k开始向左查看已扫描过的符号,直到发现Xi-1 可以证明,Xi到Xi+k之间的符号恰好构成了当前句型的句柄. 2.1.4简单优先分析法的操作步骤 1)将输入符号串a1a2……an#依次逐个存入符号栈S中,直到遇到栈顶符号ai的优先性大于下一个待输入符号aj为止。 2)栈顶当前符号ai为句柄尾,由此向左在栈中找句柄的头符号ak,即找到ak-1小于ak,为止。 3)由句柄ak….ai在文法的产生式中查找右部为ak…ai的产生式,若找到则用相应左部代替句柄,若找不到则为出错,这时可断定输入串不是该文法的句子。 2.2需要完成的功能 2.2.1判定输入的文法是否是简单优先文法 根据简单优先文法的定义可知一个文法是否是简单优先文法可以从以下两点判定: 1)在文法符号集V中,任意两个符号之间最多只有一种优先关系成立。 2)在文法中任意两个产生式没有相同的右部。 2.2.2构造文法的简单优先关系矩阵 简单文法中的优先关系有以下三种: 1)X·=Y表示X和Y的优先关系相等。 2)X·>Y表示X的优先性比Y的优先性大。 3)X<·Y表示X的优先性比Y的优先性小。 由以上三种关系的定义,由文法产生式可求得问答符号之间的优先关系。 为了表示简洁明了,我们把文法之间的关系用关系矩阵表示,称作优先关系矩阵。 在优先关系矩阵中,矩阵中的元素要么为空要么只有一种关系,元素为空时表示该文法的任何句型中不会出现该符号对的相邻关系,在分析过程中若遇到这种相邻关系出现,则为出错,也就可以肯定输入符号串不是该文法的句子。 2.3分析器的构造 分析栈输入流 第三章逻辑设计 3.1系统的组织与基本工作流程 本系统采用C++程序设计语言编写,主要用来分析用户输入文法的简单优先关系并构造优先关系表。 系统的组织主要有以下基本分组成。 1)优先文法判定模块 此模块根据简单优先文法的定义设计,判定输入的文法是否为简单优先文法。 如果是,则继续执行下面的程序,如果不是,则退出。 2)等于关系的判断模块 此模块判定文法中等于关系,判定出后保存入dengyu[i][j]中。 3)小于关系模块 此模块判定文法中小于关系,判定出后保存入相应的栈表中。 4)大于关系模块 同上面一样,判定大于关系,保存入相应的栈表中。 5)关系矩阵的构造 经过分析,系统调用栈表中等于、小于、大于的数据,排列构成矩阵。 3.2总体结构逻辑结构图 第思章软件功能设计 4.1软件功能分析 4.1.1判定文法是否为简单优先文法 根据简单优先文法的定义可知: for(i=0;i if(right[j]==right[i]&&i! =j){ cout<<"该文法不是简单优先文法,请重新输入。 "< returnfalse; } returntrue; 4.1.2查找分析文法优先关系相等 for(i=0;i {for(j=4;j<10;j++) if(a[i][j+1]! ='\0') { for(k=1;k<=m;k++) for(r=1;r<=m;r++) if(aa[r][0]==a[i][j]&&aa[0][k]==a[i][j+1]) b_dengyu[r-1][k-1]=1; } } printf("B等于的矩阵是: \n"); for(i=0;i {printf(""); for(j=0;j printf("%d",b_dengyu[i][j]); printf("\n\n"); } 4.1.3查找分析文法中小于的关系 for(i=0;i for(j=0;j { for(k=0;k b_xiaoyu[i][j]+=b_dengyu[i][k]*b_headjia[k][j]; if(b_xiaoyu[i][j]>1) b_xiaoyu[i][j]=1; } printf("B<的矩阵是: \n"); for(i=0;i {printf(""); for(j=0;j printf("%d",b_xiaoyu[i][j]); printf("\n\n"); } 4.1.4查找分析文法中大于的关系 for(i=0;i for(j=0;j { for(k=0;k bb[i][j]+=b_transpose_tailjia[i][k]*b_dengyu[k][j]; } for(i=0;i for(j=0;j { for(k=0;k b_dayu[i][j]+=bb[i][k]*b_head_I[k][j]; if(b_dayu[i][j]>1) b_dayu[i][j]=1; } printf("B>的矩阵是: \n"); for(i=0;i {printf(""); for(j=0;j printf("%d",b_dayu[i][j]); printf("\n\n"); } 4.1.5构造文法的简单优先关系矩阵 for(i=0;i for(j=0;j {if(b_xiaoyu[i][j]==1) aa[i+1][j+1]='<'; elseif(b_dayu[i][j]==1) aa[i+1][j+1]='>'; elseif(b_dengyu[i][j]==1) aa[i+1][j+1]='='; } for(i=1;i<=m;i++) for(j=1;j<=L1;j++) if(aa[0][j]>='A'&&aa[0][j]<='Z'&&aa[i][j]=='>') aa[i][j]=''; printf("这些文法得到的优先矩阵是: \n"); for(i=0;i<=m;i++) { for(j=0;j<=m;j++) printf("%c",aa[i][j]); printf("\n\n"); } } 第五章界面设计 测试用例: S: : =bAb A: : =(B|a B: : =Aa) 5.1用户输入文法界面 此界面为系统运行时首先出现的界面,根据提示输入文法的规则数,然后输入文法。 5.2优先矩阵的初始状态 5.3文法中等于关系 相应代码为 for(i=0;i {for(j=4;j<10;j++) if(a[i][j+1]! ='\0') { for(k=1;k<=m;k++) for(r=1;r<=m;r++) if(aa[r][0]==a[i][j]&&aa[0][k]==a[i][j+1]) b_dengyu[r-1][k-1]=1; } } printf("B等于的矩阵是: \n"); for(i=0;i {printf(""); for(j=0;j printf("%d",b_dengyu[i][j]); printf("\n\n"); } 5.4小于关系 相应代码为 for(i=0;i for(j=0;j { for(k=0;k b_xiaoyu[i][j]+=b_dengyu[i][k]*b_headjia[k][j]; if(b_xiaoyu[i][j]>1) b_xiaoyu[i][j]=1; } printf("B<的矩阵是: \n"); for(i=0;i {printf(""); for(j=0;j printf("%d",b_xiaoyu[i][j]); printf("\n\n"); 5.5大于关系 大于关系相应代码为: for(i=0;i for(j=0;j { for(k=0;k bb[i][j]+=b_transpose_tailjia[i][k]*b_dengyu[k][j]; } for(i=0;i for(j=0;j { for(k=0;k b_dayu[i][j]+=bb[i][k]*b_head_I[k][j]; if(b_dayu[i][j]>1) b_dayu[i][j]=1; } printf("B>的矩阵是: \n"); for(i=0;i {printf(""); for(j=0;j printf("%d",b_dayu[i][j]); printf("\n\n"); } 5.6优先关系矩阵 相应代码为: for(i=0;i for(j=0;j {if(b_xiaoyu[i][j]==1) aa[i+1][j+1]='<'; elseif(b_dayu[i][j]==1) aa[i+1][j+1]='>'; elseif(b_dengyu[i][j]==1) aa[i+1][j+1]='='; } for(i=1;i<=m;i++) for(j=1;j<=L1;j++) if(aa[0][j]>='A'&&aa[0][j]<='Z'&&aa[i][j]=='>') aa[i][j]=''; printf("这些文法得到的优先矩阵是: \n"); for(i=0;i<=m;i++) { for(j=0;j<=m;j++) printf("%c",aa[i][j]); printf("\n\n"); } 小结 随着编译技术的发展和社会对编译程序需求的不断增长,一些编译程序的自动生成工具。 它的功能是以任一语言的词法规则、语法规则和语义解释出发,自动产生该语言的编译程序。 目前很多自动生成工具已广泛使用,如词法分析程序的生成系统LEX,语法分析程序的生成系统YACC等。 同时,不断有人使用自展技术来构造编译程序,并且其影响越来越大。 将串行程序转换成并行程序的自动并行编译技术也正在深入研究之中。 通过本次课程设计很好复习了数据结构中所学的知识,认识到很多知识的运用问题,对栈的运用有了更深的理解,本次设计最深的感触是简单优先文法是一个非常准确,规范但分析效率很低的一种文法。 通过本次课程设计,让我对简单优先算法尤其是小于关系有了较全面深入的了解,并且通过上机操作等更好的理解了相关理论知识,增强了自己的动手能力。 本次课程设计中我的主要任务是对简单优先文法中的小于关系做相应的算法思想、编程设计和调试。 在课程设计过程中,我对数据结构相关知识的掌握不够牢固,尤其对指针方面的内容,从而在编写程序过程中出现地址符丢失等错误,这在后来的调试中通过查阅了相关材料后和同学的帮助下得以解决;另外,我对类的有关知识不够了解,从而导致未定义类,造成程序错误。 此外,在画流程图时,画的比较烦琐,后来经过精简得出了比较简练流程图。 总之,这次课程设计让我受益匪浅。 不仅加深了我对编译原理和数据结构等课程的了解,而且也通过查阅资料和实践弥补了所有的不足之处。 在今后的学习中,我会加强自己的动手能力,让理论和实践相结合,并且加强在专业课方面的学习。 参考文献 1、编译原理(第2版)清华大学出版社张素琴吕映之等著 2、VisualC++6.0开发使用手册机械工业出版社BrianSiler等著 3、编译程序设计北京大学出版社王永宁著(实现佳) 4、程序设计语言编译原理国防工业大学出版社陈火旺著(原理强) 5、编译原理(第二版)西北工业大学出版社蒋立源等著(方法全) 6、软件工程导论(第三版)清华大学出版社张海潘著 感谢: 首先,感谢范老师能在此次课程设计中给我这样一个锻炼的机会,论文的完成离不开范老师的悉心指导和关怀。 在本次课程设计中,我从范老师身上学到了很多东西。 范老师认真负责的工作态度,严谨的治学精神和深厚的理论水平都使我收益匪浅。 她无论在理论上还是在实践中,都给与我很大的帮助,使我得到不少的提高这对于我以后的工作和学习都有一种巨大的帮助。 另外,在系统开发过程中,同组的同学也给与我不少帮助,在此一起感谢。 附录: #include #include #include intn; charaa[10][10]; chara[10][10]; intbb[20][20]={0}; intb_dengyu[20][20]={0}; intb_head[20][20]; intb_headjia[20][20]; intb_head_I[20][20]; intb_tail[20][20]; intb_tailjia[20][20]; intb_transpose_tailjia[20][20]; intb_dayu[20][20]; intb_xiaoyu[20][20]; main() { inti,j,k,r,L1=0,L2=0,m,len; charb[10]={0},c[10]={0}; printf("请输入该文法的规则数n: "); scanf("%d",&n); printf("请输入这些文法: "); for(i=0;i<=n-1;i++) scanf("%s",a[i]); //输出终结符和非终结符 for(i=0;i<=n-1;i++) for(j=0;a[i][j]! ='\0';j++) { if(a[i][j]>='A'&&a[i][j]<='Z') { for(k=0;b[k]! ='\0';k++) if(a[i][j]==b[k]) break; if(k>=L1) { b[k]=a[i][j]; L1++; } } else if(a[i][j]! =': '&&a[i][j]! ='=') { for(r=0;c[r]! ='\0';r++) if(a[i][j]==c[r]) break; if(r>=L2) { c[r]=a[i][j]; L2++; } } } m=L1+L2; for(i=1;i<=L1;i++) { aa[0][i]=b[i-1]; aa[i][0]=b[i-1]; } for(j=0,i=L1+1;j { aa[0][i]=c[j]; aa[i][0]=c[j]; } printf("这个优先矩阵的初始状态是: \n"); for(i=0;i<=m;i++) { for(j=0;j<=m;j++) printf("%c",aa[i][j]); printf("\n\n"); } //求b==的过程 len=strlen(a); for(i=0;i {for(j=4;j<10;j++) if(a[i][j+1]! ='\0') { for(k=1;k<=m;k++) for(r=1;r<=m;r++) if(aa[r][0]==a[i][j]&&aa[0][k]==a[i][j+1]) b_dengyu[r-1][k-1]=1; } } printf("B等于的矩阵是: \n"); for(i=0;i {printf(""); for(j=0;j printf("%d",b_dengyu[i][j]); printf("\n\n"); } //求B_head的过程 for(i=0;i if(a[i][4]! ='\0') { for(k=1;k<=m;k++) for(r=1;r<=m;r++) if(aa[r][0]==a[i][0]&&aa[0][k]==a[i][4]) b_head[r-1][k-1]=1; } printf("B_head的矩阵是: \n"); for(i=0;i {printf(""); for(j=0;j printf("%d",b_head[i][j]); printf("\n\n"); } //求B_head+的过程 for(i=0;i for(j=0;j b_headjia[i][j]=b_head[i][j]; for(i=0;i for(j=0;j if(b_headjia[j][i]==1) for(k=0;k { b_headjia[j][k]=b_headjia[j][k]+b_headjia[i][k]; if(b_he
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 课程设计