FIRST集和FOLLOW集生成算法模拟

课程设计(论文)任务书软件学院学院软件测试专业1班一、课程设计(论文)题目first集和follow集生成算法模拟二、课程设计(论文)工作自2015年6月16日起至2013年6月19日止。三、课程设计(论文)地点:软件学院实训中心四、课程设计(论文)内容要求：1．本课程设计的目的进一步培养学生编译器设计的思想，加深对编译原理和应用程序的理解，针对编译过程的重点和难点内容进行编程，独立完成有一定工作量的程序设计任务，同时，强调好的程序设计风格，并综合使用程序设计语言、数据结构和编译原理的知识,熟悉使用开发工具VC/JAVA/C#/.NET。2．课程设计的任务及要求1）课程设计任务：设计一个由正规文法生成First集和Follow集并进行简化的算法动态模拟。2）创新要求：动态模拟算法的基本功能是：（１）输入一个文法Ｇ（２）输出由文法G构造的FIRST集算法（３）输出FIRST算法（４）输出由文法G构造的FOLLOW集算法（５）输出FOLLOW集3）课程设计论文编写要求（1）课程设计任务及要求（2）设计思路--工作原理、功能规划（3）详细设计---数据分析、算法思路、功能实现（含程序流程图、主要代码及注释）、界面等。（4）运行调试与分析讨论---给出运行屏幕截图，分析运行结果，有何改进想法等。（5）设计体会与小结---设计遇到的问题及解决办法，通过设计学到了哪些新知识，巩固了哪些知识，有哪些提高。（6）报告按规定排版打印，要求装订平整，否则要求返工；编译原理课程设计-第2页-（7）课设报告的装订顺序如下：封面---任务书---中文摘要---目录----正文---附录(代码及相关图片)（8）严禁抄袭，如有发现，按不及格处理。4）课程设计评分标准：（1）学习态度：20分；（2）系统设计：20分；（3）编程调试：20分；（4）回答问题：20分；（5）论文撰写：20分。5）参考文献：（1）张素琴，吕映芝.编译原理[M].,清华大学出版社（2）蒋立源、康慕宁等，编译原理（第2版）[M]，西安：西北工业大学出版社6）课程设计进度安排1．准备阶段（4学时）：选择设计题目、了解设计目的要求、查阅相关资料2．程序模块设计分析阶段（4学时）：程序总体设计、详细设计3．代码编写调试阶段（8学时）：程序模块代码编写、调试、测试4．撰写论文阶段（4学时）：总结课程设计任务和设计内容，撰写课程设计论文学生签名：2015年6月19日课程设计(论文)评审意见（1）学习态度（20分）：优（）、良（）、中（）、一般（）、差（）；（2）系统设计（20分）：优（）、良（）、中（）、一般（）、差（）；（3）编程调试（20分）：优（）、良（）、中（）、一般（）、差（）；（4）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（5）论文撰写（20分）：优（）、良（）、中（）、一般（）、差（）；评阅人：职称：讲师2015年6月19日编译原理课设-第3页-中文摘要随着计算机科学的飞速发展，形式语言与自动机理论和方法研究也越来越收到人们的重视，但前者已经成为计算机科学的理论基础。此次的课程设计主要任务是研究自动机在编译方面的应用，并将重点放在求FIRST集和FOLLOW集。根据构造FIRST集的算法和FOLLOW集的算法，编写一个程序，程序具有通用性，即编制的愈发程序能够适用于不同的文法。基本思想描述，通过对输入的文法进行判断，进而根据构造的FIRST集和FOLLOW集的算法。并把计算所得的FIRST集和FOLLOW集输出。构造FIRST集的算法和FOLLOW集的算法的核心算法教材上已经给出了，因此要做的事只是将他们实现。关键字：FIRST集，FOLLOW集，算法。编译原理课程设计-第4页-目录一、课程设计任务及要求....................................................................1二、需求分析........................................................................................2三、设计思路........................................................................................3四、详细设计........................................................................................7五、运行调试与分析讨论....................................................................8六、设计体会与小结..........................................................................10七、参考文献......................................................................................11八、附录.......................................11编译原理课设第1页一、课程设计任务及要求1.任务：设计一个由正规文法生成First集和Follow集并进行简化的算法动态模拟。First集和Follow集生成模拟算法的基本功能：（1）输入一个文法G（2）输入由文法G构造First集的算法（3）输出First集（4）输入由文法Ｇ构造Follow集的算法（5）输出Follow集2.实验目的：输入：任意的上下文无关文法。输出：所输入的上下文无关文法一切非终结符的first集合和follow集合。3.设文法G[S]＝（VN，VT，P，S），则首字符集为：FIRST（α）＝{a|α*aβ，a∈VT，α,β∈V*}。若α*ε，ε∈FIRST（α）。由定义可以看出，FIRST（α）是指符号串α能够推导出的所有符号串中处于串首的终结符号组成的集合。所以FIRST集也称为首符号集。设α＝x1x2…xn，FIRST（α）可按下列方法求得：令FIRST（α）＝Φ，i＝1；（1）若xi∈VT，则xi∈FIRST（α）；（2）若xi∈VN；①若εFIRST（xi），则FIRST（xi）∈FIRST（α）；②若ε∈FIRST（xi），则FIRST（xi）－{ε}∈FIRST（α）；（3）i＝i+1，重复（1）、（2），直到xi∈VT，（i＝2，3，…，n）或xi∈VN且若εFIRST（xi）或in为止。当一个文法中存在ε产生式时，例如，存在A→ε，只有知道哪些符号可以合法地出现在非终结符A之后，才能知道是否选择A→ε产生式。这些合法地出现在非终结符A之后的符号组成的集合被称为FOLLOW集合。下面我们给出文法的FOLLOW集的定义。设文法G[S]＝（VN，VT，P，S），则编译原理课程设计-第2页-FOLLOW（A）＝{a|S…Aa…，a∈VT}。若S*…A，#∈FOLLOW（A）。由定义可以看出，FOLLOW（A）是指在文法G[S]的所有句型中，紧跟在非终结符A后的终结符号的集合。FOLLOW集可按下列方法求得：（1）对于文法G[S]的开始符号S，有#∈FOLLOW（S）；（2）若文法G[S]中有形如B→xAy的规则，其中x，y∈V*，则FIRST（y）－{ε}∈FOLLOW（A）；（3）若文法G[S]中有形如B→xA的规则，或形如B→xAy的规则且ε∈FIRST（y），其中x，y∈V*，则FOLLOW（B）∈FOLLOW（A）；3.实验内容：计算FIRST集和FOLLOW集4.二、需求分析1.基本要求：动态模拟算法的基本功能是：（1）输入一个文法G；（2）输出由文法G构造FIRST集的算法；（3）输出First集；（4）输出由文法G构造FOLLOW集的算法；（5）输出FOLLOW集。2.测试数据：输入文法Ｇ[E]：E→TE’E’→+TE’|εεii))((**++FF的的firstfirst集集TT的的firstfirst集集EE的的firstfirst集集111111111111111111编译原理课设第3页T→FT’T’→*FT’|εεF-(E)|i3.实现提示：用数据库存储多行文法，用LIST控件显示算法，用GRID类依据算法进行作图。并实现算法与生成过程的关联。三、设计思路1.识别终结符集和非终结符集开始输入要分析的文法G\计算产生式的总数N结束编译原理课程设计-第4页-YN识别终结符集识别非终结符集2.计算所有非终结符的First集读取一条产生式n=n+1识别产生式左部的字符V并添加到非终结符集合Vn开始输入n=0Nn结束开始识别所有符号集合Z终结符集合Vt=Z-Vn结束输出Vn输出Vt编译原理课设第5页NYYN开始结束读取Vn中的一个非终结符V从语法G中查找左部是V的所有产生式取出其中的一条产生式产生式的右部第一个符号V*是终结符或者V*→εεV*右部的第一个非终结符V可以推导将该终结符加入V的First集中还有未计算的非终结符编译原理课程设计-第6页-3.计算所有非终结符的Follow集NYNYＹ开始读取Vn中的一个非终结符V从语法G中查找左部是V的所有产生式V是最后一个字符添加#到V的Follow集中V的后一个字符V*为终结符添加V*到V的Follow集中添加V*的First集到V的Follow集中是否遍历完所有右部含有Ｖ的产生式有未求过的非终结符Ｖ完成编译原理课设第7页四、详细设计1.操作界面的控制流图2.具体设计通过分析输入的文法，分析出文法肿的非终结符和终结符，然后计算出每个非终结符的FIRST集和FOLLOW集。在输出的结果上应该显示文法中的非终结符和终结符，FIRST集和FOLLOW集表格。根据表格中的每个非终结符后面的１表示的是：相对应的终结符是属于该非终结符的。开始输入文法计算所有的非终结符Vn和终结符Vt并显示计算所有非终结符的First集和Follow集并显示结束编译原理课程设计-第8页-五、运行调试与分析讨论1.运行程序2.输入文法编译原理课设第9页3.输出非终结符和终结符4.计算First集并输出编译原理课程设计-第10页-计算Follow集并输出六、设计体会与小结这次的编译原理的课程设计历时两天，进过不断的查看课本从网上差资料解决问题，让我对文法的FIRST集和FOLLOW集有了更多的了解。虽然做课程设计是一个比较辛苦的过程，但是从它的过程中我们还是可以学到很多东西的，比如思维的方式，锻炼自己的耐心，写文档时的逻辑能力。在写课设的过程中遇到了以下的问题：1．终结符V和V’，多了个带’的终结符，但是它在处理的时候只能当一个符号来识别，而用程序设计语言表示时它能表示成两个字符，如果处理不当的话，V’就可能被认为是终结符号V和非终结符‘。这无疑给处理过程添加了难度。2．还有一些自认为理所当然能实现的，却实际并不可取的方法。如：本来JAVAAPI有个方法String.split(Strings);用于以s为分割字符，将指定的字符分成字符数组。但是s为括号时（无论左右括号，大小括号，方框括号），都不能分割，并且抛异常。这是个很难理解的问题。迫不得已，我不得不想其他的方法来实现分割算法。编译原理课设第11页3．再有就是对编译原理中FirstFollow算法设计时，采取何种策略效率最高的问题。最后我想到了用递归方式。下面总结此次课程设计的一些收获：1.对程序设计理解，算法的设计，有了进一不的提高。2.对程序调试的技巧收获不小。因为该程序主要是算法研究，所以程序分支较复杂。断点调试是必不可缺并且很实用的工作。3．对程序到软件过程的理解。这次也是我第一次将自己做的程序制作成一个可自定义安装过程的小软件。从而将程序的运行与IDE脱离开来。4．毫无疑问，就是对编译原理的理解。能够很好地理解