自顶向下语法分析教学辅助软件的开发.doc

河南大学2007届本科毕业论文自顶向下语法分析教学辅助软件的开发development of a teaching aid software of top-down syntax analysis论文作者姓名：韩罡 所在学院：计算机与信息工程学院 所学专业：计算机科学与技术 导师姓名职称：张连堂(教授)袁彩虹(助教) 论文完成时间：2007年5月20日 2007年5月20日河南大学2007届毕业论文（设计、创作）开题报告（由学生本人认真填写）学号03023192姓名韩罡导师姓名职称张连堂(教授)袁彩虹(助教)开题时间2006年12月1日课题题目自顶向下语法分析教学辅助软件的开发课题来源导师指定 自定 其他来源课题的目的、意义以及和本课题有关的国内外现状分析：1、目的：开发一个自顶向下语法分析教学辅助软件。2、意义：自顶而下的语法分析是编译原理课程中的一个核心理论，由于理论的抽象性，常规的教学手段很收到理想的教学效果，而教学辅助软件能以更形象化的方式把内容表达出来。因此，自顶向下语法分析教学辅助软件的开发有利于提高教学质量，帮助学生自学。3、现状：随着大学教育的改革，更多课程采用了先进教学手段，教学软件的开发在学校教育领域成为了一种潮流和趋势。研究目标、研究内容和准备解决的问题：自顶而下的语法分析是编译原理课程中一个十分重要的部分，同时它也是考试的重点和难点。因此，本着辅助教学的目的，软件总体上要有友好的界面，良好的交互性，较强的实用性。内容方面，ll（1）文法是一种能够进行确定、无回溯自顶而下语法分析的描述工具，软件要能够把整个ll（1）的分析过程清晰、准确、直观的展示出来。给定一个文法，首先应实现first集合和follow集合的求解，实现预测分析表的构造，然后进行ll（1）文法确定性的判断，最后，给定输入串，进行预测分析。拟采取的方法、技术或设计（开发）工具：在设计过程中，拟采用队列帮助first集合和follow集合的求解，采用栈作为自顶向下语法分析过程中核心的数据结构。拟采用的开发工具：visual studio 2005预期成果：1、毕业设计成果自顶向下语法分析教学辅助软件2、毕业论文自顶向下语法分析教学辅助软件的开发进度计划：2006.12.1 - 2007.4.1：查找资料、搜集相关素材2007.4.2 - 2007.4.11：完成总体界面部分的设计2007.4.12 - 2007.4.21：完成first和follow的程序实现部分的设计2007.4.22 - 2007.4.30：完成预测分析表和分析过程部分的设计2007.5.1 - 2007.5.20：整理资料、撰写毕业论文2007.5.20 - 2007.5.25：根据导师要求，完善毕业设计和论文指导教师对选题报告的意见： 同意开题 指导教师签名： 2006年12月 1日开题报告ii河南大学2007届毕业论文（设计、创作）任务书学号03023192姓名韩罡导师姓名张连堂（教授）袁彩虹（助教）任务书起止日期2006年12月8日 至 2007年5月20日论文提要：在完成课题调研的基础上，论文打算分四部分来介绍：第一部分介绍本软件的开发背景、开发目标，以及开发平台。第二部分介绍自顶向下语法分析中的一些相关理论，如ll(1)文法的概念、预测分析程序等。第三部分介绍软件的具体开发过程，包括界面设计、核心算法的实现和相关类的介绍。最后，介绍测试结果。课题任务要求：1、深刻理解自顶向下语法分析中的理论。2、应实现first集合和follow集合的求解，实现预测分析表的构造，然后进行ll（1）文法确定性的判断，最后给定输入串，进行预测分析。3、软件要有友好的界面，良好的交互性，较强的实用性。主要参考文献：1陈火旺、刘春林编著，编译原理，国防工业出版社，2000年1月2(英)john sharp 著，周靖译，visual c# 2005从入门到精通，清华大学出版社，2006年6月3陈志泊、李冬梅等著，数据库原理及应用教程，人民邮电出版社，2002年3月4张敬和著，编译原理实用教程，清华大学出版社，2005年4月5严蔚敏著，数据结构，清华大学出版社，2002年3月河南大学2007届毕业设计（论文、创作）中期检查表学院名称：计算机与信息工程学院题目名称自顶向下语法分析教学辅助软件的设计学号03023192所学专业计算机科学与技术指导教师姓 名张连堂袁彩虹姓名韩罡一、毕业设计进展情况截止4月10日为止：1、查找资料、搜集相关素材已经完成2、软件的总体框架和思路已确定3、软件界面也已经完成 二、存在问题1、没有很好的理解相关算法的精髓，阻碍了设计进度2、界面的设计效果不是特别的理想三、下一阶段的研究方法或设计思路1、根据总体设计流程和框架结构，进行核心部分的实现。2、重点研究first集和follow集的算法实现问题，3、利用比较合理的数据结构，设计好的实现方法。四、指导教师对学生设计（论文、创作）进展等方面的评语该生能按计划完成资料、素材的收集，并进行了界面设计，但是，对算法本身理解不透，设计的界面不够友好，应注意改进，并注意进度。 指导教师签字： 2007年4月10日 此表除第四项外由学生填写指导教师签名河南大学2007届毕业论文（设计、创作）综合成绩表（一）学院名称：计算机与信息工程学院学 号03023192姓名韩罡专业计算机科学与技术指导教师张连堂（副教授）、袁彩虹（助教）综合得分82论文题目自顶向下语法分析教学辅助软件的开发指导教师评语及得分指导教师评语该生论文结构清晰，逻辑合理，描述准确，符合本科生毕业论文标准。评分项目分值指导教师对毕业论文（设计、创作）评分撰写开题报告、文献综述15调查研究查阅整理资料10学习态度与规范要求10数据处理、文字表达10论文（设计、创作）质量和创新意识55合计100得分128874681指导教师签名 2007年5月20日评阅教师评语及评分评阅教师评语该生论文语言通顺，表达清晰、准确，结构合理，符合本科生毕业论文标准。评分项目分值评阅毕业论文（设计、创作）评分撰写开题报告、文献综述15调查研究查阅整理资料10学习态度与规范要求10数据处理、文字表达10论文（设计、创作）质量和创新意识55合计100得分138874783评阅教师签名 2007年5月22日此表由教师填写河南大学2007届毕业论文（设计、创作）综合成绩表（二）学号03023192姓名韩罡所在学院计算机与信息工程学院答辩委员会评语及评分答辩委员会评语该生回答问题思路清晰，表达准确。 答辩委员签字： 2007年5月26日评分 项目 分值论文答辩小组评分答辩情况论文质量合计（100）内容表达情况（15）答辩问题情况（25）规范要求与文字表达（20）论文（设计、创作）质量和创新意识（40）得分1220153582答辩委员会主任签字： 2007年5月26日毕业论文（设计、创作）成绩综合评定： 82 分综合评定等级：良备注：一、论文的质量评定，应包括对论文的语言表达、结构层次、逻辑性理论分析、设计计算、分析和概括能力及在论文中是否有新的见解或创新性成果等做出评价。从论文来看学生掌握本专业基础理论和基本技能的程度。二、成绩评定采用结构评分法，即由指导教师、评阅教师和答辩委员会分别给分（以百分计），评阅教师得分乘以20%加上指导教师得分乘以20%加上答辩委员会得分乘以60%即综合成绩。评估等级按优、良、中、差划分，优90-100分；良76-89分；中60-75分；差60分以下。三、评分由专业教研室或院组织专门评分小组（不少于5人），根据指导教师和答辩委员会意见决定每个学生的分数，在有争议时，应由答辩委员会进行表决。四、毕业论文答辩工作结束后，各院应于6月20日前向教务处推荐优秀论文以汇编成册，推荐的篇数为按当年学院毕业生人数的1.5%篇。五、各院亦可根据本专业的不同情况，制定相应的具有自己特色的内容。须报教务处备案。六、书写格式要求：1、目录；2、内容提要须书写200左右汉字，开题报告（文科除外）的内容要根据不同专业的课题任务要求，阐述查阅文献、文案论证、解题思路、工作步骤等；3、正文（含引言、结论等）；4、参考文献（或资料）河南大学本科生毕业论文（设计、创作）承诺书论文题目自顶向下语法分析教学辅助软件的开发姓 名韩罡所学专业计算机科学与技术学 号03023192完成时间2007年5 月20日指导教师姓名职称张连堂（教授）、袁彩虹（助教）承诺内容：1、本毕业论文（设计、创作）是学生韩罡在导师张连堂、袁彩虹的指导下独立完成的，没有抄袭、剽窃他人成果，没有请人代做，若在毕业论文（设计、创作）的各种检查、评比中被发现有以上行为，愿按学校有关规定接受处理，并承担相应的法律责任。2、学校有权保留并向上级有关部门送交本毕业论文（设计、创作）的复印件和磁盘。备注：学生签名： 指导教师签名： 2007年5月20日 2007年5月20日说明：学生毕业论文（设计、创作）如有保密等要求，请在备注中明确，承诺内容第2条即以备注为准。目 录摘 要iabstractii第1章 绪论11.1 开发背景11.2 开发目标11.3 开发平台2第2章 基本原理概述32.1 基本知识32.2 ll(1)文法的概念32.3 预测分析程序4第3章 软件设计与实现53.1 界面设计53.2 核心算法的实现73.2.1 first集合求解算法实现73.2.2 follow集合求解算法实现83.2.3 select集合求解算法实现93.2.4 ll(1)文法的判定实现93.2.5 语法正确性判断实现103.2.6 预测分析表构造和分析过程实现103.3 相关类的介绍11第4章 系统的运行与测试124.1 界面的运行效果124.2 系统的测试14结 论17参考文献18河南大学本科毕业生学士学位论文摘 要自顶而下语法分析是编译原理课程中的一个核心理论，由于理论的抽象性，常规的教学手段很难收到理想的教学效果，而教学辅助软件能以更形象化的方式把内容表达出来，因此教学辅助软件的开发十分必要。本论文以介绍该教学辅助软件的开发为核心，首先介绍开发背景、开发目标、开发平台及软件的基本功能；然后简单介绍软件开发中用到的基础理论，其中包括ll（1）文法等概念；接下来详细阐述软件的具体开发过程，其中，first集合、follow集合算法的实现是核心，这个实现的过程中用到了队列，在进行语法分析时用到了栈；最后对软件进行简单的测试，检查是否达到了预期目的。关键词 自顶向下语法分析，first集合，follow集合，预测分析表abstracttop-down syntax analysis is a core theory in the compiler principle . because this theory is abstract , conventional teaching means can not receive very good teaching results. but, teaching aid software can be a more figurative way to convey the content of expression.so development of a teaching aid software is very necessary.this paper mainly introduces the process of development. firstly, it introduces the background, the objective, the platform and the basic functions.secondly, basic theory, such as ll(1) syntax analysis concepts ,etc, which is used in this paper is simply introduced.thirdly, it elaborates specific process of the development, in which implementation of the algorithm of first sets and follow sets is the core. queue is used to it and in the process of syntax analysis stack is applied. finally, it is a simple test,which can check the effect of the teaching aid software.keywords top-down syntax analysis,first sets, follow sets, predicting and analyzing table第 18 页第1章 绪论自顶而下的语法分析是编译原理课程中的一个重要内容，其教学辅助软件的开发对编译原理教学有着重要作用。本章介绍本软件的开发背景、开发目标，以及开发平台。1.1 开发背景随着计算机的迅速普及，计算机软件的发展也正是方兴未艾，它已经渗透到社会的各个领域和各个行业，并率先应用于大学教学领域。考虑到让这些现代化教育资源的投资发挥应有的作用，大家都很重视计算机辅助教学的推广和应用。教师和学生都希望能得到高质量、使用方便的教学软件。而厂商也看到计算机教学辅助软件将会形成有潜力的市场，而积极投入了教学软件的开发和经营。教学辅助软件正是在这个大环境下逐渐有了一定的市场的，正因为它具有良好的图形界面，交互性更强，更容易被人们所接受，所以受到了教育界的普遍欢迎。在计算机专业课的学习过程中，由于所涉及的内容比较抽象，理解起来比较困难，教学辅助软件可以把抽象化的概念用更加形象的方式表达出来，从而激发学生的学习兴趣，提高学习效率。1.2 开发目标自顶而下的语法分析是编译原理课程中一个十分重要的部分，同时它也是考试的重点和难点。因此，本着辅助教学的目的，软件总体上要有友好的界面，良好的交互性，较强的实用性。内容方面，ll（1）文法是一种能够进行确定、无回溯自顶而下语法分析的描述工具，软件要能够把整个ll（1）的分析过程清晰、准确、直观的展示出来。给定一个文法，首先应实现first集合和follow集合的求解，实现预测分析表的构造，然后进行ll（1）文法确定性的判断，最后给定输入串，进行预测分析。1.3 开发平台在开发的过程中使用了visual studio 2005开发平台。visual studio 2005是.net 2003的优化版和改进版，具有改进的可视化设计器。因为ll(1)分析器的核心内容是一些复杂算法的实现，选择这个平台可以方便界面设计，把精力集中于算法实现。另外visual studio 2005自带打包工具，在开发出来一个软件以后更加利于后期的管理，无需使用专门的打包软件，就可以进行打包。只要安装了framework sdk v2.0就可以直接运行打过包的软件，使用起来方便、简单。随着c#2.0的问世，语言新增了几个重要的特性，例如arraylist类、迭带器以及正则表达式，本设计中就用到了这些。第2章 基本原理概述本章介绍自顶向下语法分析中的基本原理和概念，为后面的具体开发打下基础。2.1 基本知识在进行软件的设计过程中，需要了解以下基本的知识和概念。1、终结符号：是组成语言的基本符号，终结符号是一个语言的不可再分的基本符号，即单词符号，一般用英文小写字母表示。终结符号集通常用vt表示。2、非终结符号：一个非终结符号代表一个一定的语法概念，是一个类记号，它表示一定符号串的集合，通常用大写英文字母表示。非终结符号集通常用vn表示。3、开始符号：是一个特殊的非终结符号，是进行分析的入口。4、产生式：是定义语法范畴的一种书写规则。5、上下文无关文法：是文法的一种，用来定义语言的语法结构，所定义的语法范畴完全独立于这种范畴可能出现的环境。表示为（vt, vn,s,p），其中vt代表终结符号集，vn代表非终结符号集，s代表开始符号，p代表产生式集合，一个产生式的形式是“a”，其中a是非终结符号，是由终结或非终结符号组成的字符串，即（vtvn）*。2.2 ll(1)文法的概念在自顶向下语法分析中，会出现回溯以及虚假匹配问题，并且由于文法的左递归性，会造成死循环。为避免以上问题，进行确定的、无回溯的自上而下分析，引入了ll(1)文法。它属于上下文无关文法的范畴，该文法满足以下特点：1、文法不含左递归；2、对于文法中每一个非终结符号a的各个产生式的侯选首符集两两不相交。即若a1|2|n，则first(i)first(j)=；3、对于文法的每个非终结符号a,若它存在某个侯选首符集含（空字）,则first (a)follow(a)=。2.3 预测分析程序预测分析表是一个ma,a形式的矩阵。其中a为非终结符，a是终结符或#，#不是文法符号，我们总是把它当成输入串的结束符。矩阵元素ma,a中也存放着一条关于a的产生式，指出当a面临输入符号a时应采用的侯选。ma,a中也可能存放一个“出错标志”，指出a根本不该面临输入符号a。预测分析过程的每一步，都是取出栈顶符号和当前输入符号，并查看预测分析表进行的。预测分析器结构如图2-1所示。第3章 软件设计与实现本章主要介绍软件的具体开发过程，包括界面设计、核心算法的实现和相关类的介绍。3.1 界面设计按照软件的设计流程，首先进行界面的设计。作为教学辅助软件，界面应简明、小巧、实用，软件总体界面如图3-1所示。图3-1 系统总体界面1、界面中的“帮助说明”以电子书(chm格式)的形式展现出，需要先设计一个chm文档，以便作为模版使用。system.diagnostics.process.start(path);/打开帮助说明文档软件的输入界面，用一个tabepage控件来进行设计，分别是终结符和非终结符、文法规则、自顶而下的语法分析三个页面。2、在输入终结符和非终结符的页面中用到了两个textbox的文本框，分别用来显示终结符号和非终结符号，或者可以自行编辑，在打开文件的过程中需要用流来读取文件，它的实现方法如下。private void btnloadsymbols_click(object sender, eventargs e)/打开文件的单击事件。tryusing (streamreader sr=new streamreader(ofiledlg.filename)textboxendall.appendtext(strtaskitem + rn);symbolset.getinstance().endallset.add(strtaskitem) sr.colse()在输入终结符号和非终结符号的时候规定一个字符占一行，这样使格式更加清晰。3、在文法规则的页面上用了一个listbox控件来显示文法，可以把编辑好的文法保存到一个文件中，保存操作的实现方法如下。private void btnsaveproducts_click(object sender, eventargs e) /存文件的单击事件。sfiledlg.filter = (*.txt)|*.txt|*.*|*.*;sfiledlg.showdialog();if (sfiledlg.filename != )using (streamwriter sw = new streamwriter(sfiledlg.filename)sw.close();/实现保存文件操作4、运行页面的设计过程和上面的相同，最大的特点就是运用到了一个webbrower的组件。它可以把网页模版和最后结果显示在到这个控件上，使得界面效果更加的美观。outresult(arrayfirst,arrayfollow,arraysellect,hashanalysis) /输出结果3.2 核心算法的实现程序的核心是first集合和follow集合的构造算法以及预测分析表的实现问题。3.2.1 first集合求解算法实现1、若xvt，则first(x)=x；2、若xvn，且有产生式xa，avt，则afirst(x)；3、若xvn，且有产生式x，则first(x)；4、若xvn， y1，y2，yi都属于vn，且有产生式xy1y2yn，当y1,yi-1=(1in)时，则把 first(yi) 去掉后的部分（first(yi)中有的话）放入first(x)中，记为first(yi)/first(x)；当y1,yn*=时，则最终把放入first(x)，即first(x)。在实现的过程中最主要的是第四步的判定，前三步容易实现，不做介绍。在第四步的实现过程中，首先判断第一个字符是否为非终结符，设定一个布尔型扫描标志flag，赋初值true，然后就要扫描后面的每一个字符了，可能会出现以下几种情况。1、yi如果是非终结符号，并且能推出空字符串，那么就把first(yi)/加入到first(x)中。2、yi如果是非终结符号，并且不能推出空字符，那么就把first(yi)直接加入到first(x)中。并且停止对后面字符串的扫描工作。3、yi如果是最后一个符号，那么不管它能否能推出空字符，直接把first(yi)加入到first(x)中。在实现的过程中，为了记录first(x)用到了哪些其他非终结符号的first集，引入队列这种数据结构，同时设置一组布尔型变量记录first集是否完成，也就是说是否还需要用到其它非终结符的first集。把那些已经完成集合求解的非终结符号的first集放入到没有完成集合求解的非终结符号的first集中去，没有完成first集求解的非终结符号放入队列。first集的实现用public arraylist firstset()方法：x属于vt，则first(x)=x 。if (symbolset.getinstance().isinendset(product.leftitem) lstfirsti.add(product.leftitem); 若xvn，且有产生式xa，avt，则afirst(x)。if(symbolset.getinstance().isinendset(strfirstletter) if(!tools.isinlist(strfirstletter,lstfirsti) lstfirsti.add(strfirstletter) 若xvn，且有产生式x，则first(x)。if(!tools.isinlist(,lstfirsti)lstfirsti.add();上面所说的第四步出现的情况较多，但基本实现过程和前三步类似，使用了5个if语句，不再详细列举代码。private bool checkemptysymbol(string strchar)/检测空字符public arraylist finishfirst(arraylist firstlist,queue queuefirst)./完成first集的计算,把未求出first集的非终结符求出public void outfirst(arraylist arylst) /输出first集3.2.2 follow集合求解算法实现在求follow集时按照以下步骤来进行：1、x是开始符号，把#加入到follow(x)；2、ab是一个产生式，则把first()/加到follow(b)；3、ab是一个产生式，或ab是一个产生式而=，则把follow(a)加入到follow(b)中。follow集合求解算法的实现和first集的类似。在求某个非终结符first集时先扫描产生式左部不同的产生式，然后扫描左部相同的产生式的每一个右部。而在求follow集的时候，则需要扫描每一个产生式，第一次扫描可以确定哪些first集或follow集属于所求的follow集，由于first集已经求出，所以第一次扫描就可以把相应的first集加入到follow集中，设置follow集完成标记位，设置队列，把未完成的非终结符送入队列，依次取出队列元素，把求出follow集的非终结符的follow集加入到相应的follow集中，把未求出的送回队列。主要的实现方法如下所示：public arraylist followset(arraylist aryfirst)/得到follow集private arraylist followletter(string strchar,arraylistarylstfollow)/ 返回所有产生式右部指定的字符后边的字母public void outfollow(arraylist arylst)/输出follow集public string outfirstfollow(arraylist irst,arraylist follow)/输出first集和follow集到网页表格3.2.3 select集合求解算法实现1、若是终结符，那么sellect(a)=。2、若是，则select(a)=follow(a)。3、若是非终结符那么 若*=，则select(a)= first()follow(a)。 若*=，select(a)=first()。主要的实现方法如下所示：public arraylist selectset(arraylist aryfirst, arraylist aryfollo