数据结构课设finalWord文件下载.docx
- 文档编号:8654656
- 上传时间:2023-05-12
- 格式:DOCX
- 页数:33
- 大小:183.46KB
数据结构课设finalWord文件下载.docx
《数据结构课设finalWord文件下载.docx》由会员分享,可在线阅读,更多相关《数据结构课设finalWord文件下载.docx(33页珍藏版)》请在冰点文库上搜索。
目录
目录-2-
内容摘要-3-
第一章绪论-4-
1.1课程设计目的-4-
1.2课程设计的背景与意义-4-
编译器实现技术是一大宝库,一方面以编译器的实现为背景可以实践几乎全部在数据结构与算法分析课程中学到的主要数据结构与算法;
另一方面,编译器设计中使用的问题求解方法、处理问题的思路被广泛地用于自动数据处理(转换)及其它一些新的研究领域。
没有编译器的出现就没有现代数字计算机的发展。
-4-
1.3课程设计总体要求-4-
1.4【实现提示】-5-
1.5课程设计环境-7-
第二章课程设计分析及解决方案-7-
2.1课程设计分析-7-
2.2课程设计解决方案-7-
第三章程序设计及实现-8-
3.1程序设计-8-
1.主要流程-8-
第四章测试与结果-9-
4.1程序测试数据和结果-9-
总结-10-
参考文献-11-
附录A-12-
内容摘要
本次课设即以“语法规则的存储与显示”、“句子的生成”、“语法(分析)树的建立”等等这些编译器中的一些基本功能的实现为题,引导同学对高级程序设计语言在计算机中的表达和相关的处理有一个初步认识,提前领略“数据的自动转换与处理”这一计算机问题求解的核心技术。
尽管这些功能的实现并不涉及较深入的编译技术,但也需要带着问题预先学习、掌握有关形式语言、编译原理与技术的若干基本概念,这正好是锻炼同学自学能力和创新意识的契机,自然也是本课题的魅力所在。
采用文件的形式有效组织存储高级语言的语法规则和测试用例(如:
是否是换乘站点等信息),可以实现“语法规则的存储与显示”、“句子的生成”、“语法(分析)树的建立”并以图形界面的形式显示。
第一章绪论
1.1课程设计目的
课程设计是【数据结构】课程教学的一个重要环节,是将理论与实际联系的必要过程。
通过课程设计,使学生们加深对课程内容的理解,掌握各种数据结构的应用方式,提高进行软件设计与制作的能力,为培养具有良好的程序设计素质的计算机人才打下坚实的基础。
1.2课程设计的背景与意义
1.3课程设计总体要求
给定若干描述某种高级程序设计语言组成部分的语法规则及测试用例:
1、设计恰当的数据结构实现语法规则的计算机存储并加以显示;
2、对于给定语法规则的句子,能动态显示“句子的生成”;
3、对于给定语法规则的句子(或句型),完成该句子(句型)的“语法(分析)树的建立”,并用图形界面显示;
1.4【实现提示】
1、基本概念
(1)文法(即形式语言的语法):
文法G为一个四元组:
G=(VT,VN,P,S)
VT:
终结符(Terminal)集
VN:
非终结符(Variable)集,VT∩VN=Φ
S:
开始符号(StartSymbol),S∈VN
P:
产生式(Product)集合
α→β,被称为产生式(定义式),读作:
α定义为β。
其中α∈(VT∪VN)+,且α中至少有VN中元素的一个出现。
β∈(VT∪VN)*。
α称为产生式α→β的左部(LeftPart),β称为产生式α→β的右部(RightPart)。
(2)推导:
根据产生式对符号串进行变换的过程
A→γ是文法G的一个产生式,且α、β∈(VT∪VN)*,
称αAβ的直接推导/派生(Derive)出αγβ,也称αγβ直接归约(Reduce)为αAβ。
注意到是根据A→γ而将αγβ中的γ变成了A,所以,一般称将γ归约为A
记为αAβαγβ(αγβαAβ)
(3)最左推导:
每次推导都施加在句型的最左边的语法变量上——与最右归约对应;
(4)语法(分析)树:
(ParseTree,又称语法分析树或分析树)
⏹用树的形式表示句型的结构
⏹树根:
开始符号
⏹中间结点:
非终结符
⏹叶结点:
终结符或者非终结符
⏹每个推导对应一个中间结点及其儿子——一个二级子树-直接短语
显然,如果一个中间结点v标记为A,v的儿子从左到右依次为v1,v2,……,vn,并且它们分别标记为X1,X2,……,Xn,则AX1X2……Xn∈P
设有文法G的一棵语法树T,T的所有叶子顶点从左到右依次标记为X1,X2,…,Xn,则称符号串X1X2…Xn是T的结果(Yield)
(5)二义性(歧义性):
形象地看,就是一个句子(如:
id+id*id)对应两棵不同的语法树。
即有如下两个不同的最左推导:
如果一个文法的句子存在两棵分析树,那么,该句子是二义性的;
如果一个文法包含二义性的句子,则称这个文法是二义性的;
否则,该文法是无二义性的。
(a)一般来说,高级程序设计语言存在无二义性文法,但有时用二义性文法。
如:
表达式文法、条件语句文法
E→E+E|E-E|E*E|E/E|(E)|id
SifexprthenS
ifexprthenSelseS
other
二义性的句子:
ife1thenife2thens1elses2
(b)对于任意一个CFG,不存在算法判定它是无二义性的;
但能给出一组充分条件,满足这组充分条件的文法是无二义性的。
1.5课程设计环境
实验环境:
WindowsXp操作系统
实验软件:
C++builder
第二章课程设计分析及解决方案
2.1课程设计分析
编译器主要利用所给的文法,以及所给的式子,显示出通过文法变换最终产生出式子的生成过程。
2.2课程设计解决方案
(1)从文件中读取语法,将语法存入所设置好的变量中,以便之后对于输入句子的判断。
(2)输入句子,将输入的句子存入result数组中,在输入句子完成后,输入一个‘;
’,以使得跳出循环。
(3)进入分析函数,将result数组中的句子压入s栈中,开始分析,先将s栈的元素逐个压入temp栈中,若temp栈的栈顶元素为符号类,将temp栈的栈顶两个元素也弹出,与之前s栈弹出的一个元素组成compare数组,以判断是否有符合的文法。
变换结束后继续压入temp栈中。
当s栈为空时,将temp栈中的元素弹回s栈中,在弹的过程中,元素开始向上级变换。
然后重复此过程,知道结果变为e为止。
(4)在次返回原栈的过程中,将变换式存入二维数组outp中,然后对outp进行调整,使输出的式子更加整齐。
(5)最后加入图形界面,对数据进行转换并输出。
第三章程序设计及实现
3.1程序设计
1.主要流程
2.分析函数流程
第四章测试与结果
4.1程序测试数据和结果
(1)运行程序出现如下画面
(2)运行完成后
总结
编译原理是计算机专业的一门重要专业课,旨在介绍编译程序构造的一般原理和基本方法。
内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。
编译原理是计算机专业设置的一门重要的专业课程。
虽然只有少数人从事编译方面的工作,但是这门课在理论、技术、方法上都对学生提供了系统而有效的训练,有利于提高软件人员的素质和能力。
通过了对于这次数据结构课设的设计,我对于下学期将要开设的编译原理课程有了初步的认识,而且对于C++的使用,尤其是图形界面的设计有了更加深入的了解。
我认为这个课设对我的帮助很大,身为计算机专业的学生,只有深入的了解计算机程序的运行,编译,结构等,才能在以后的工作中更加得心应手。
参考文献
1、蒋宗礼,姜守旭,《编译原理》,高等教育出版社,国家“十一五”规划教材,2010年2月
2、陈火旺等,程序设计语言编译原理(第3版),国防工业出版社,2003.8.印刷
附录A
程序代码:
/***************************************************************
*Name:
jiemianMain.cpp
*Purpose:
CodeforApplicationFrame
*Author:
fish()
*Created:
2011-11-04
*Copyright:
*License:
**************************************************************/
#include"
wx_pch.h"
jiemianMain.h"
#include<
wx/msgdlg.h>
//(*InternalHeaders(jiemianFrame)
wx/settings.h>
wx/intl.h>
wx/string.h>
//*)
#include<
iostream>
stdio.h>
stdlib.h>
stack>
string>
fstream>
windows.h>
usingnamespacestd;
/************************************************************************/
/*全局变量*/
charr1[20];
charr2[20];
charr3[20];
charre[20];
//答案字符
charoutp[100][100]={'
#'
};
charoutpf[50][50]={'
%'
introw=0;
intseries=0;
intx=0;
//统计输入句子的个数
charfirstgrammerpoint;
charsecondgrammerpoint;
charthirdgrammerpoint;
charcode;
intprinti=0;
intsamepoint=0;
intm=0;
wxStringText;
chartran0[15];
chartran1[15];
chartran2[15];
chartran3[15];
chartran4[15];
chartran5[15];
chartran6[15];
chartran7[15];
chartran8[15];
chartran9[15];
chartran10[15];
chartran11[15];
chartran12[15];
chartran13[15];
chartran14[15];
chartran15[15];
/*结果输入函数*/
voidrule(charresult[20])
{
intk=0;
for(k=0;
k<
100;
k++)
{
strcpy(result,Text.mb_str());
if(result[k]=='
;
'
)
break;
}
x=k;
}
/*节点判断函数*/
intdegree(charc)
if(c==firstgrammerpoint)
return1;
elseif(c==secondgrammerpoint)
return2;
elseif(c==thirdgrammerpoint)
return3;
elsereturn0;
/*判断符号函数*/
boolifmark(charc)
if(c=='
+'
||c=='
-'
*'
/'
returntrue;
else
returnfalse;
voidstackdata(stack<
char>
a)
charc[100];
intj=0;
/*如果栈顶元素不是’;
‘,将栈顶元素逐个弹出*/
while(a.top()!
='
c[j]=a.top(),a.pop();
j++;
j=j-1;
while(j>
=0)
if(ifmark(c[j]))
{
outp[series][row]=c[j];
row++;
a.push(c[j]);
j--;
}
else
outp[series][row]=c[j];
row++;
a.push(c[j]);
j--;
/*如果e是栈中最后一个元素,将e-push到栈b中,并返回true*/
boolcheck(stack<
b)
chara;
a=b.top();
b.pop();
if(b.top()=='
&
a=='
e'
b.push(a);
returntrue;
/*分析函数*/
voidanalysis()
stack<
s;
temp;
charch[20],t;
stringq="
aaa"
inti;
inty=x;
intz=x;
intd;
intjg=1;
intyou=0;
m=x;
/*从文件中读取文法*/
ifstreaminfile("
E:
\\aaa.txt"
ios_base:
:
in);
charline[45];
infile.getline(line,100,'
);
//e
stringop1(line);
firstgrammerpoint=op1[0];
|'
//e+t
stringf(line);
infile.getline(line,100);
//e-t
stringa(line);
//t
stringop2(line);
secondgrammerpoint=op2[0];
//t*i
stringg(line);
//t/i
stringn(line);
//i
stringop3(line);
thirdgrammerpoint=op3[0];
stringop4(line);
infile.close();
/*输出规则*/
cout<
<
"
规则如下:
endl;
firstgrammerpoint<
="
f<
|"
a<
secondgrammerpoint<
g<
n<
thirdgrammerpoint<
op4<
endl<
推导过程树如下:
/*推导过程*/
/*输出式子*/
intmn=0;
while(mn<
x)
if((re[mn]))
outp[series][row]=re[mn];
row++;
mn++;
series++;
row=0;
/*将式子加入‘;
’后push进原栈*/
temp.push('
while(x>
s.push(re[x]);
x--;
while(!
check(s))
/*将原栈元素压入临时栈*/
while(s.top()!
t=s.top();
s.pop();
/*如果临时栈栈顶元素不是符号,将该元素压入临时栈*/
if(!
ifmark(temp.top()))
temp.push(t);
/*否则将临时栈的栈顶两个元素弹出,与原栈弹出元素组成数组q*/
q[2]=t;
q[1]=temp.top(),temp.pop();
q[0]=temp.top(),temp.pop();
/*数组q中元素为e+t*/
if(pare(f)==0)
stackdata(temp);
outp[series][row]='
t'
stackdata(s);
series++;
row=0;
you=1;
temp.push(firstgrammerpoint);
/*数组q中元素为e-t*/
elseif(pare(a)==0)
you=1;
/*数组q中元素为t*i*/
elseif(pare(g)==0)
i'
temp.push(secondgrammerpoint);
/*数组q中元素为t/i*/
elseif(pare(n)==0)
/*否则将数组中的元素压入temp栈中*/
temp.push(q[0]);
temp.push(q[1]);
temp.push(q[2]);
i=0;
intm=0;
/*将临时栈元素压入临时数组*/
while(temp.top()!
t=temp.top(),temp.pop();
ch[i]=t;
i++;
z=i-1;
i=i-1;
d=degree(ch[0]);
/*数组向上级变换*/
do
if(degree(ch[i])==d&
jg==1)
if(ch[i]==thirdgrammerpoint)
ch[i]=secondgrammerpoint;
elseif(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 final
![提示](https://static.bingdoc.com/images/bang_tan.gif)