first集和follow集生成算法模拟

1、课程设计(论文)任务书 软 件 学 院 学院 软件测试 专业 1 班 一、课程设计(论文)题目 first集和follow集生成算法模拟 二、课程设计(论文)工作自 2015 年 6 月 16 日起至 2013 年 6 月 19 日止。三、课程设计(论文) 地点: 软 件 学 院 实 训 中 心 四、课程设计(论文)内容要求：1本课程设计的目的进一步培养学生编译器设计的思想，加深对编译原理和应用程序的理解，针对编译过程的重点和难点内容进行编程，独立完成有一定工作量的程序设计任务，同时，强调好的程序设计风格，并综合使用程序设计语言、数据结构和编译原理的知识, 熟悉使用开发工具VC /JAVA/C

2、#/.NET 。2课程设计的任务及要求1）课程设计任务：设计一个由正规文法生成First集和Follow集并进行简化的算法动态模拟。2）创新要求：动态模拟算法的基本功能是：（） 输入一个文法（） 输出由文法G构造的FIRST集算法（） 输出FIRST算法（） 输出由文法G构造的FOLLOW集算法（） 输出FOLLOW集3）课程设计论文编写要求（1）课程设计任务及要求（2）设计思路-工作原理、功能规划（3）详细设计-数据分析、算法思路、功能实现（含程序流程图、主要代码及注释）、界面等。（4）运行调试与分析讨论-给出运行屏幕截图，分析运行结果，有何改进想法等。（5）设计体会与小结-设计遇到的问题及

3、解决办法，通过设计学到了哪些新知识，巩固了哪些知识，有哪些提高。（6）报告按规定排版打印，要求装订平整，否则要求返工；（7）课设报告的装订顺序如下：封面-任务书-中文摘要-目录-正文-附录(代码及相关图片)（8）严禁抄袭，如有发现，按不及格处理。4）课程设计评分标准： （1）学习态度：20分；（2）系统设计：20分；（3）编程调试：20分；（4）回答问题：20分；（5）论文撰写：20分。5）参考文献：（1）张素琴，吕映芝. 编译原理M., 清华大学出版社（2）蒋立源、康慕宁等，编译原理（第2版）M，西安：西北工业大学出版社6）课程设计进度安排1准备阶段（4学时）：选择设计题目、了解设计目的要求

4、、查阅相关资料2程序模块设计分析阶段（4学时）：程序总体设计、详细设计3代码编写调试阶段（8学时）：程序模块代码编写、调试、测试4撰写论文阶段（4学时）：总结课程设计任务和设计内容，撰写课程设计论文学生签名： 2015 年 6 月 19 日课程设计(论文)评审意见（1）学习态度（20分）：优（）、良（）、中（）、一般（）、差（）； （2）系统设计（20分）：优（ ）、良（）、中（）、一般（）、差（）； （3）编程调试（20分）：优（）、良（）、中（）、一般（）、差（）；（4）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（5）论文撰写（20分）：优（）、良（）、中（）、一般（）

5、、差（）； 评阅人： 职称： 讲师 2015 年 6 月 19 日中文摘要随着计算机科学的飞速发展，形式语言与自动机理论和方法研究也越来越收到人们的重视，但前者已经成为计算机科学的理论基础。此次的课程设计主要任务是研究自动机在编译方面的应用，并将重点放在求FIRST集和FOLLOW集。根据构造FIRST集的算法和FOLLOW集的算法，编写一个程序，程序具有通用性，即编制的愈发程序能够适用于不同的文法。基本思想描述，通过对输入的文法进行判断，进而根据构造的FIRST集和FOLLOW集的算法。并把计算所得的FIRST集和FOLLOW集输出。构造FIRST集的算法和FOLLOW集的算法的核心算法教材

6、上已经给出了，因此要做的事只是将他们实现。关键字：FIRST集，FOLLOW集，算法。目录一、课程设计任务及要求1二、需求分析2三、设计思路3四、详细设计7五、运行调试与分析讨论8六、设计体会与小结10七、参考文献11八、附录.11一、课程设计任务及要求1.任务：设计一个由正规文法生成First集和Follow集并进行简化的算法动态模拟。First集和Follow集生成模拟算法的基本功能：（1） 输入一个文法G（2） 输入由文法G构造First集的算法（3） 输出First集（4） 输入由文法构造Follow集的算法（5） 输出Follow集2. 实验目的：输入：任意的上下文无关文法。输出：所

7、输入的上下文无关文法一切非终结符的first集合和follow 集合。3.设文法GS（VN，VT，P，S），则首字符集为： FIRST（）a | a，aVT，,V *。若，FIRST（）。由定义可以看出，FIRST（）是指符号串能够推导出的所有符号串中处于串首的终结符号组成的集合。所以FIRST集也称为首符号集。设x1x2xn，FIRST（）可按下列方法求得：令FIRST（），i1；（1） 若xiVT，则xiFIRST（）；（2） 若xiVN； 若FIRST（xi），则FIRST（xi）FIRST（）； 若FIRST（xi），则FIRST（xi）FIRST（）；（3） ii+1，重复（1）、（

8、2），直到xiVT，（i2，3，n）或xiVN且若FIRST（xi）或i>n为止。当一个文法中存在产生式时，例如，存在A，只有知道哪些符号可以合法地出现在非终结符A之后，才能知道是否选择A产生式。这些合法地出现在非终结符A之后的符号组成的集合被称为FOLLOW集合。下面我们给出文法的FOLLOW集的定义。设文法GS（VN，VT，P，S），则 FOLLOW（A）a | S Aa ，aVT。若SA，#FOLLOW（A）。由定义可以看出，FOLLOW（A）是指在文法GS的所有句型中，紧跟在非终结符A后的终结符号的集合。FOLLOW集可按下列方法求得：（1） 对于文法GS的开始符号S，有#FOL

9、LOW（S）；（2） 若文法GS中有形如BxAy的规则，其中x，yV *，则FIRST（y）FOLLOW（A）；（3） 若文法GS中有形如BxA的规则，或形如BxAy的规则且FIRST（y），其中x，yV *，则FOLLOW（B）FOLLOW（A）；3. 实验内容：计算FIRST集和FOLLOW集4.二、需求分析1.基本要求： 动态模拟算法的基本功能是：（1） 输入一个文法G；（2） 输出由文法G构造FIRST集的算法；（3） 输出First集；i)(*+F的first集T的first集E的first集111111111（4） 输出由文法G构造FOLLOW集的算法；（5） 输出FOLLOW集。

10、2.测试数据：输入文法E：E TEE +TE|T FTT *FT|F->(E)|i3. 实现提示：用数据库存储多行文法，用LIST控件显示算法，用GRID类依据算法进行作图。并实现算法与生成过程的关联。三、设计思路1.识别终结符集和非终结符集 开始 结束计算产生式的总数N输入要分析的文法G 开始 开始 输入n=0识别所有符号集合Z读取一条产生式n=n+1终结符集合Vt=Z - Vn识别产生式左部的字符V并添加到非终结符集合Vn输出Vt N>n Y 结束 N输出Vn 识别终结符集 结束 识别非终结符集 2. 计算所有非终结符的First集 开始读取Vn中的一个非终结符V从语法G中查找

11、左部是V的所有产生式 产生式的右部第一个符号V*是终结符或者V*取出其中的一条产生式 N V*右部的第一个非终结符V可以推导 Y Y N将该终结符加入V的First集中还有未计算的非终结符 结束3. 计算所有非终结符的Follow集 开始读取Vn中的一个非终结符V从语法G中查找左部是V的所有产生式V的后一个字符V*为终结符V是最后一个字符 N Y N添加V*到V的Follow集中添加#到V的Follow集中 Y 是否遍历完所有右部含有的产生式 添加V*的First集到V的Follow集中 有未求过的非终结符 完成四、详细设计 开始1.操作界面的控制流图输入文法计算所有的非终结符Vn和终结符Vt

12、并显示计算所有非终结符的First集和Follow集并显示 结束2. 具体设计通过分析输入的文法，分析出文法肿的非终结符和终结符，然后计算出每个非终结符的FIRST集和FOLLOW集。在输出的结果上应该显示文法中的非终结符和终结符，FIRST集和FOLLOW集表格。根据表格中的每个非终结符后面的表示的是：相对应的终结符是属于该非终结符的。五、运行调试与分析讨论1.运行程序2.输入文法3.输出非终结符和终结符4.计算First集并输出计算Follow集并输出六、设计体会与小结这次的编译原理的课程设计历时两天，进过不断的查看课本从网上差资料解决问题，让我对文法的FIRST集和FOLLOW集有了更多

13、的了解。虽然做课程设计是一个比较辛苦的过程，但是从它的过程中我们还是可以学到很多东西的，比如思维的方式，锻炼自己的耐心，写文档时的逻辑能力。在写课设的过程中遇到了以下的问题：1 终结符 V和V，多了个带 的终结符，但是它在处理的时候只能当一个符号来识别，而用程序设计语言表示时它能表示成两个字符，如果处理不当的话，V就可能被认为是终结符号V和非终结符。这无疑给处理过程添加了难度。2 还有一些自认为理所当然能实现的，却实际并不可取的方法。如：本来JAVA API有个方法String.split(String s);用于以s 为分割字符，将指定的字符分成字符数组。但是s 为括号时（无论左右括号，大小

14、括号，方框括号），都不能分割，并且抛异常。这是个很难理解的问题。迫不得已，我不得不想其他的方法来实现分割算法。3 再有就是对编译原理中First Follow算法设计时，采取何种策略效率最高的问题。最后我想到了用递归方式。下面总结此次课程设计的一些收获：1.对程序设计理解，算法的设计，有了进一不的提高。 2.对程序调试的技巧收获不小。因为该程序主要是算法研究，所以程序分支较复杂。断点调试是必不可缺并且很实用的工作。3对程序到软件过程的理解。这次也是我第一次将自己做的程序制作成一个可自定义安装过程的小软件。从而将程序的运行与IDE脱离开来。4毫无疑问，就是对编译原理的理解。能够很好地理解程序设计

15、与编译原理的关系。七、参考文献1 张素琴.编译原理. 北京:清华大学出版社,20052 付京周.JAVA程序设计语言. 北京:人民邮电出版社,20078、 附录/求VN和VTvoid VNVT(STR *p) int i,j; for(i=0;i<N;i+) for(j=0;j<(int)pi.left.length();j+) if(pi.leftj>='A'&&pi.leftj<='Z') if(Vn.find(pi.leftj)>100) Vn+=pi.leftj; else if(Vt.find(pi.lef

16、tj)>100) Vt +=pi.leftj; for(j=0;j<(int)pi.right.length();j+) if(!(pi.rightj>='A'&&pi.rightj<='Z') if(Vt.find(pi.rightj)>100) Vt +=pi.rightj; else if(Vn.find(pi.rightj)>100) Vn+=pi.rightj; void getlr(STR *p,int i) int j; for(j=0;j<strings.length();j+) if(s

17、tringsj='-'&&stringsj+1='>') pi.left=strings.substr(0,j); pi.right=strings.substr(j+2,strings.length()-j); /对每个文法符号求first集string Letter_First(STR *p,char ch)int t;if(!(Vt.find(ch)>100)firstVt.find(ch)="ch"return firstVt.find(ch)-1;if(!(Vn.find(ch)>100)for(i

18、nt i=0;i<N;i+) if(pi.left0=ch) if(!(Vt.find(pi.right0)>100) if(FirstVn.find(ch).find(pi.right0)>100) FirstVn.find(ch)+=pi.right0; if(pi.right0='*') if(FirstVn.find(ch).find('*')>100) FirstVn.find(ch)+='*' if(!(Vn.find(pi.right0)>100) if(pi.right.length()=1) str

19、ing ff; ff=Letter_First(p,pi.right0); for(int i_i=0;i_i<ff.length();i_i+) if( FirstVn.find(ch).find(ffi_i)>100) FirstVn.find(ch)+=ffi_i; else for(int j=0;j<pi.right.length();j+) string TT; TT=Letter_First(p,pi.rightj); if(!(TT.find('*')>100)&&(j+1)<pi.right.length() so

20、rt(TT.begin(),TT.end(); string tt; for(int t=1;t<TT.length();t+) tt+=TTt; TT=tt; tt="" for(t=0;t<TT.length();t+) if( FirstVn.find(ch).find(TTt)>100) FirstVn.find(ch)+=TTt; else for(t=0;t<TT.length();t+) if( FirstVn.find(ch).find(TTt)>100) FirstVn.find(ch)+=TTt; break; return

21、 FirstVn.find(ch);/ 求每个非终结符的Follow集string Letter_Follow(STR *p,char ch)int t,k;NONEVn.find(ch)+;if(NONEVn.find(ch)=2)NONEVn.find(ch)=0;return FollowVn.find(ch);for(int i=0;i<N;i+)for(int j=0;j<pi.right.length();j+)if(pi.rightj=ch)if(j+1=pi.right.length()string gg;gg=Letter_Follow(p,pi.left0);NONEVn.find(pi.left0)=0;for(int k=0;k<gg.length();k+)if(FollowVn.find(ch).find(ggk)>100)FollowVn.find(ch)+=ggk;else string FF; for(int jj=j+1;jj<pi.right.length();jj+) string TT; TT=Letter_First(p,pi.rightjj); if(!(TT.find('*')>100)&&a