first集和follow集生成算法模拟

/课程设计（论文）任务书软件学院学院软件测试专业1班一、课程设计(论文）题目first集和follow集生成算法模拟二、课程设计(论文)工作自20１5年6月16日起至２0１３年６月１9日止。三、课程设计(论文）地点：软件学院实训中心四、课程设计（论文)内容要求：１。本课程设计的目的进一步培养学生编译器设计的思想，加深对编译原理和应用程序的理解，针对编译过程的重点和难点内容进行编程，独立完成有一定工作量的程序设计任务，同时,强调好的程序设计风格，并综合使用程序设计语言、数据结构和编译原理的知识，熟悉使用开发工具VＣ／ＪAＶＡ/C＃/。ＮET。2．课程设计的任务及要求1）课程设计任务:设计一个由正规文法生成First集和Foｌｌow集并进行简化的算法动态模拟。2）创新要求：动态模拟算法的基本功能是：输入一个文法G输出由文法G构造的FIRST集算法输出ＦIRST算法输出由文法G构造的ＦOＬLOW集算法输出FOLLOW集3）课程设计论文编写要求（1）课程设计任务及要求(2）设计思路——工作原理、功能规划(3)详细设计－-—数据分析、算法思路、功能实现(含程序流程图、主要代码及注释）、界面等.(4)运行调试与分析讨论－-—给出运行屏幕截图，分析运行结果，有何改进想法等。（5）设计体会与小结—－－设计遇到的问题及解决办法,通过设计学到了哪些新知识,巩固了哪些知识，有哪些提高.(6)报告按规定排版打印，要求装订平整，否则要求返工;（7)课设报告的装订顺序如下：封面—-—任务书－--中文摘要——-目录—－-—正文－--附录（代码及相关图片)(8）严禁抄袭，如有发现,按不及格处理。４）课程设计评分标准：(1）学习态度:２0分；(2）系统设计:2０分；(３）编程调试：20分；（4）回答问题：2０分;（5)论文撰写：2０分.5）参考文献：（１）张素琴,吕映芝．编译原理［M］。,清华大学出版社（2)蒋立源、康慕宁等,编译原理(第2版）［Ｍ］，西安：西北工业大学出版社6）课程设计进度安排1．准备阶段(４学时）：选择设计题目、了解设计目的要求、查阅相关资料2．程序模块设计分析阶段（4学时）：程序总体设计、详细设计3.代码编写调试阶段(8学时）：程序模块代码编写、调试、测试4.撰写论文阶段(４学时）：总结课程设计任务和设计内容，撰写课程设计论文学生签名：２0１5年6月１9日课程设计（论文)评审意见（1）学习态度（20分)：优(）、良()、中（）、一般（)、差（）；(２）系统设计(20分）：优(）、良（)、中（）、一般（)、差()；（３)编程调试（2０分)：优(）、良（）、中（）、一般（)、差();(4）回答问题（２0分）:优（）、良（）、中()、一般（）、差(）;（５）论文撰写(２0分）:优（）、良(）、中(）、一般（）、差（）;评阅人：职称：讲师2015年６月１9日ﻬ中文摘要随着计算机科学的飞速发展,形式语言与自动机理论和方法研究也越来越收到人们的重视，但前者已经成为计算机科学的理论基础。此次的课程设计主要任务是研究自动机在编译方面的应用，并将重点放在求FIRST集和FＯLLＯW集。根据构造FＩＲＳT集的算法和FOLLOＷ集的算法,编写一个程序，程序具有通用性，即编制的愈发程序能够适用于不同的文法。基本思想描述,通过对输入的文法进行判断，进而根据构造的FIRSＴ集和ＦOLLＯW集的算法。并把计算所得的ＦIRST集和FOＬＬOＷ集输出。构造FIRST集的算法和FOLＬOW集的算法的核心算法教材上已经给出了，因此要做的事只是将他们实现.关键字：FIRST集，FOLLOW集，算法.ﻬ目录TOC\o”1-3"\h＼ｚ\uHYPERLIＮＫ＼l"_Ｔoc278８３５８３0"一、课程设计任务及要求ﻩPＡGEREF＿Toc2７88358３0\h1HYPERLINK\l”＿Ｔｏｃ278835８3１"二、需求分析ﻩＰＡGERＥＦ_Toｃ2７88３５８31\h2HYＰERLINK\l”_Toｃ27883５8３2”三、设计思路ﻩPAＧEREF_Toc2788358３２\ｈ３ＨYPERLIＮK\l”_Toc2７8835833＂四、详细设计 7HＹＰERLINK＼l"_Ｔoc27883583４＂五、运行调试与分析讨论 8HＹPEＲLINＫ＼l”_Toc2788３5835＂六、设计体会与小结ﻩ1０HＹPERLIＮK\l"_Tｏc2７883５８36”七、参考文献ﻩ１1八、附录。。。.．。..。。．．.。.．。.。.．．。。...。．．.。。..。。.．11一、课程设计任务及要求1.任务：设计一个由正规文法生成Ｆirst集和Folloｗ集并进行简化的算法动态模拟.Fｉrsｔ集和Foｌlow集生成模拟算法的基本功能：输入一个文法G输入由文法G构造Ｆirst集的算法输出Firｓt集输入由文法Ｇ构造Folloｗ集的算法输出Fｏllｏw集实验目的：输入：任意的上下文无关文法。输出:所输入的上下文无关文法一切非终结符的firｓｔ集合和followﻩﻩ 集合。3.设文法G[S］=(ＶＮ，VT，P,S）,则首字符集为：ＦIＲST（α）＝{a|αaβ，ａ∈VT，α,β∈V＊}。若αε，ε∈FIRST(α）。由定义可以看出，FIRST（α）是指符号串α能够推导出的所有符号串中处于串首的终结符号组成的集合。所以FIRST集也称为首符号集。设α＝ｘ1x2…xn，FＩRST(α）可按下列方法求得：令FIＲSＴ（α）＝Φ，i=1；若ｘi∈VT，则xｉ∈FIRSＴ（α）；若xi∈VＮ;①若εFIＲST（xi)，则ＦIRＳT（xi)∈FＩＲST（α）；②若ε∈FIRST(ｘi），则FIRSＴ(ｘｉ）－{ε｝∈FIＲST（α)；ｉ=i＋1,重复（1)、(２），直到ｘi∈VT，(i＝2,3，…,n）或xi∈ＶN且若εＦＩRSＴ(xｉ）或ｉ〉n为止。当一个文法中存在ε产生式时，例如,存在Ａ→ε,只有知道哪些符号可以合法地出现在非终结符Ａ之后，才能知道是否选择A→ε产生式。这些合法地出现在非终结符A之后的符号组成的集合被称为ＦOＬLOＷ集合。下面我们给出文法的FＯLLＯＷ集的定义。设文法G[Ｓ]＝（VN,VＴ，P，S），则FOLLOW(Ａ)={a｜S…Aa…，ａ∈VT｝。若S…A,＃∈FOLLOW（A）.由定义可以看出，ＦOＬLOW(A）是指在文法G［Ｓ]的所有句型中，紧跟在非终结符A后的终结符号的集合。FOLＬＯＷ集可按下列方法求得：对于文法G[S]的开始符号S，有#∈ＦOＬLOW(S）;若文法G［S]中有形如B→ｘＡｙ的规则，其中x,y∈V＊,则FＩRST（y)-｛ε｝∈FOLＬＯW（A）；若文法Ｇ[S］中有形如B→xA的规则，或形如Ｂ→ｘAy的规则且ε∈ＦＩRＳT(y),其中x,y∈V*，则FOLLＯW（B）∈ＦOLLＯW（A)；实验内容：计算FIＲST集和FOLLOW集二、需求分析１.基本要求:ﻩﻩ动态模拟算法的基本功能是：输入一个文法G;输出由文法G构造FIＲＳT集的算法;输出Firｓt集；ii)(*+F的first集T的first集E的first集111111111输出由文法G构造FＯLLOW集的算法；输出FOＬLOW集。ﻩ２．测试数据：输入文法Ｇ［E］：Ｅ→TE'E’→+TE’|εT→FT’T’→＊FT'｜εF—〉（E)|ｉ实现提示:用数据库存储多行文法，用LIST控件显示算法，用GRID类依据算法进行作图。并实现算法与生成过程的关联。三、设计思路１.识别终结符集和非终结符集开始结束计算产生式的总数N输入要分析的文法G\ﻬ开始开始结束计算产生式的总数N输入要分析的文法G\开始开始输入n=0输入n=0识别所有符号集合Z读取一条产生式n=n+1识别所有符号集合Z读取一条产生式n=n+1终结符集合Vt=Z-Vn终结符集合Vt=Z-Vn识别产生式左部的字符V并添加到非终结符集合Vn输出Vt输出VtN>nN>nY结束结束N输出Vn输出Vn识别终结符集结束结束识别非终结符集计算所有非终结符的First集开始读取Vn中的一个非终结符V读取Vn中的一个非终结符V从语法G中查找左部是V的所有产生式从语法G中查找左部是V的所有产生式产生式的右部第一个符号V*是终结符或者V*产生式的右部第一个符号V*是终结符或者V*→ε取出其中的一条产生式取出其中的一条产生式NV*右部的第一个非终结符V可以推导ＹV*右部的第一个非终结符V可以推导YN将该终结符加入V的First集中将该终结符加入V的First集中还有未计算的非终结符还有未计算的非终结符结束结束计算所有非终结符的Follow集开始开始读取Vn中的一个非终结符V读取Vn中的一个非终结符V从语法G中查找左部是V的所有产生式从语法G中查找左部是V的所有产生式V的后一个字符V*为终结符V是最后一个字符V的后一个字符V*为终结符V是最后一个字符ＮYN添加V*到V的Follow集中添加#到V的Follow集中Y添加V*到V的Follow集中添加#到V的Follow集中是否遍历完所有右部含有Ｖ的产生式是否遍历完所有右部含有Ｖ的产生式添加V*的First集到V的Follow集中添加V*的First集到V的Follow集中有未求过的非终结符Ｖ有未求过的非终结符Ｖ完成完成Ｙ四、详细设计开始1。操作界面的控制流图开始输入文法输入文法计算所有的非终结符Vn和终结符Vt并显示计算所有的非终结符Vn和终结符Vt并显示计算所有非终结符的First集和Follow集并显示计算所有非终结符的First集和Follow集并显示结束结束具体设计通过分析输入的文法，分析出文法肿的非终结符和终结符，然后计算出每个非终结符的FIRST集和ＦOＬLOW集.在输出的结果上应该显示文法中的非终结符和终结符,FＩRＳT集和FOＬＬOW集表格。根据表格中的每个非终结符后面的1表示的是：相对应的终结符是属于该非终结符的.五、运行调试与分析讨论1.运行程序2．输入文法3.输出非终结符和终结符4．计算Fｉｒst集并输出计算Foｌlｏｗ集并输出六、设计体会与小结这次的编译原理的课程设计历时两天，进过不断的查看课本从网上差资料解决问题，让我对文法的FIRST集和FＯLLＯW集有了更多的了解.虽然做课程设计是一个比较辛苦的过程,但是从它的过程中我们还是可以学到很多东西的,比如思维的方式，锻炼自己的耐心，写文档时的逻辑能力。在写课设的过程中遇到了以下的问题:终结符V和Ｖ’，多了个带’的终结符，但是它在处理的时候只能当一个符号来识别,而用程序设计语言表示时它能表示成两个字符，如果处理不当的话，V'就可能被认为是终结符号Ｖ和非终结符‘。这无疑给处理过程添加了难度。还有一些自认为理所当然能实现的,却实际并不可取的方法。如：本来JAＶAAPＩ有个方法String。split（Stｒings);用于以ｓ为分割字符，将指定的字符分成字符数组。但是s为括号时（无论左右括号，大小括号，方框括号）,都不能分割，并且抛异常.这是个很难理解的问题。迫不得已，我不得不想其他的方法来实现分割算法.再有就是对编译原理中FｉrstＦｏllow算法设计时，采取何种策略效率最高的问题。最后我想到了用递归方式。下面总结此次课程设计的一些收获:１．对程序设计理解，算法的设计,有了进一不的提高。2．对程序调试的技巧收获不小.因为该程序主要是算法研究，所以程序分支较复杂。断点调试是必不可缺并且很实用的工作。３．对程序到软件过程的理解。这次也是我第一次将自己做的程序制作成一个可自定义安装过程的小软件。从而将程序的运行与IＤE脱离开来。4．毫无疑问，就是对编译原理的理解。能够很好地理解程序设计与编译原理的关系.七、参考文献张素琴。编译原理。北京：清华大学出版社,2005付京周.JAVA程序设计语言。北京:人民邮电出版社,2０07附录//求ＶN和VＴvoidVNVT(ＳTR＊p）{inｔi，j;foｒ(i=0;ｉ〈Ｎ；i++){ｆoｒ（ｊ=0；ｊ<(int)p[i］。lefｔ．lｅnｇtｈ（）；j++){if（（p[ｉ].left［j］〉=＇A'&＆p［i].lｅfｔ［j］〈='Z'））｛iｆ（Ｖn。fiｎd（ｐ［i]．left［ｊ］）〉100）Vn+＝p［ｉ]。left[j］;}else{iｆ(Vｔ.find（p[i]。lｅｆt［j])〉100）Vt+＝p[ｉ]。ｌｅft［ｊ]；}}ｆｏr(j=0；ｊ<（ｉｎt)ｐ[ｉ］.rｉght.ｌeｎgth(）;j++){if(！（p［i].rigｈt[j］>＝’A'＆＆p［i］.right[ｊ]〈=’Z'）){if(Ｖt。find（p[i]．righｔ［ｊ])>１0０）Vt＋=p[ｉ]。ｒight[j］；｝else｛ｉf（Ｖn.find（p[ｉ］.ｒiｇhｔ［j］)〉10０）Vn+＝ｐ［i]。riｇｈｔ［j］;｝｝}｝voidgetlr(STR*ｐ,iｎti）｛iｎtj;for（j=0;j〈ｓtriｎｇs。lengｔh（);ｊ++)ﻩ｛ｉf(sｔriｎｇs［j]=='—'＆＆stｒings[j+1］＝='>'){p[ｉ］.leｆt=strｉｎgs．substr（0，j）；p[i］。righｔ=stｒｉngs．ｓuｂstr(ｊ+2,strｉngs．lｅngｔh()—j）;｝ ｝}／/对每个文法符号求fiｒst集stｒingLetter_Fiｒst（STＲ*p，cｈarｃh){ﻩiｎｔt;ﻩiｆ(!（Vｔ．find（ch）〉100)) { first[Vt。fiｎｄ（ch）]＝＂ch”；ﻩﻩreturｎfirsｔ[Vｔ。fｉnd（ch）-1]；ﻩ｝ﻩif（!（Vn。fiｎｄ（ch）＞1０0））ﻩ｛ ﻩｆoｒ(inti=0;i〈N；i++） {ﻩ ｉf(ｐ[i]。left[０]=＝cｈ）ﻩ {ﻩ ﻩｉf（！（Vt。find（p［ｉ]．right［0]）〉10０）） ﻩ{ ﻩﻩiｆ（Fｉrst[Vn．finｄ(ch)]。fiｎd（p[i］.riｇhｔ[０]）>100） ｛ﻩ ﻩ ﻩFｉrｓt［Vn.fiｎd（cｈ)］+=p［i]。rigｈt[０]; ﻩﻩﻩ｝ ﻩ ｝ if（p［ｉ］．ｒight［０]==’*'） {ﻩ if(Fｉｒst［Ｖn.ｆind（cｈ）]．fｉnd('*')＞100)ﻩﻩﻩ ｛ ﻩﻩﻩFｉrst［Vn.fｉｎd（ch)]＋='＊'; ﻩ ｝ﻩ ｝ﻩﻩﻩif（！（Ｖn．ｆinｄ（p［i］。riｇhｔ［０］）〉100)）ﻩﻩ ｛ﻩﻩﻩﻩif(p［i].rｉｇht.leｎgｔｈ()==１) ﻩ ﻩ{ ﻩﻩﻩ strinｇｆf；ﻩ ﻩﻩ ff=Letｔeｒ_Fｉrsｔ(p，p［i］.ｒight［0］）； ﻩ ﻩ for（inti_i=0;i＿ｉ〈ff.leｎｇtｈ（);i_i＋+) ﻩﻩ ｛ﻩ ﻩﻩﻩﻩif(Ｆｉrst［Vn.fｉｎd(ch)]．ｆind(ｆf[i_i］）＞１00)ﻩﻩﻩ { ﻩ Fｉrsｔ[Ｖn.fiｎd（ch)］+=ｆf[i_ｉ]；ﻩﻩﻩﻩﻩﻩ}ﻩﻩﻩﻩﻩ｝ﻩ }ﻩ ﻩﻩeｌseﻩ ﻩ｛ﻩﻩﻩﻩﻩfor(inｔｊ=0；j<p[i］。right．length(）;ｊ＋+) ｛ ﻩﻩstrｉngTＴ；ﻩ ﻩ TT=Letｔｅr＿Firｓt(ｐ，ｐ[i］。riｇht［ｊ]）;ﻩ ﻩﻩ ﻩif(!(TT．fiｎd('*＇）>１00)&＆（ｊ+1)＜ｐ[i]。right.length（））ﻩﻩﻩ {ﻩﻩ ﻩｓort(TT.bｅｇin（)，ＴT．end(）); ﻩﻩﻩｓtringtt；ﻩ ﻩﻩfor（intt＝１；t＜TT.lｅngth(）；ｔ++） ｛ﻩ ﻩ ｔt＋=TＴ［ｔ］; ﻩ } ﻩﻩﻩTＴ=ｔt；ﻩ ﻩ ﻩ tt=＂"; ﻩ ﻩ ﻩfor（t=０；t<TT。lengtｈ()；t++） ﻩ ｛ﻩ ﻩ ﻩ ﻩiｆ（Fiｒst［Vn．fiｎｄ(ｃｈ）］.fiｎd（ＴＴ［ｔ])〉10０） ﻩﻩ ﻩﻩ｛ ﻩ Fｉrst[Ｖn．fｉnd(cｈ）]+=TＴ［t］； ﻩﻩ ﻩ ﻩ｝ﻩ ﻩﻩ}ﻩﻩ ｝ ﻩﻩ ﻩ eｌse ﻩ ｛ ﻩﻩﻩﻩ for(t=0;ｔ＜TT．length(）;t+＋)ﻩﻩﻩ ﻩﻩﻩ{ﻩ ﻩﻩﻩﻩﻩif（Firsｔ［Ｖn。find(ch)］。fiｎd(TT[t]）＞１00) ﻩ ﻩﻩ ﻩ｛ﻩﻩ ﻩ Fiｒst[Vn。finｄ(cｈ)]+=ＴＴ[t]；ﻩﻩﻩﻩﻩ ﻩﻩ}ﻩﻩ ﻩ ﻩﻩ}ﻩﻩ ﻩﻩﻩ breａk; ﻩﻩﻩ ﻩ} ﻩﻩ ｝ ﻩﻩ ｝ ﻩﻩ ﻩ ｝ﻩﻩ}｝ﻩﻩｒetuｒｎFiｒst[Ｖｎ.ｆｉnd（ch）]； ｝ﻩ｝/／求每个非终结符的Folｌow集stｒｉngLetｔer_Folｌｏw(SＴR＊p，ｃhaｒch）｛ ｉntｔ，k; NＯNＥ[Vn．fｉｎd(ｃh）]＋+； if(NONE[Vn.finｄ（ｃh）］==2）ﻩ｛ NOＮE[Vn.finｄ（ch）]=0;ﻩﻩrｅturnFoｌｌｏｗ[Ｖn.find（ch）］;ﻩ} ｆoｒ（ｉnti=0;i<Ｎ;i++) {ﻩ for（iｎｔj=0；ｊ〈p[i].ｒigｈt。leｎgth（)；j+＋) ﻩ｛ ﻩif（p［ｉ].right［j］==ｃh） ﻩﻩ｛ ﻩﻩﻩif(j+1==p［i］.right．ｌｅnｇth()）ﻩ ﻩﻩ｛ ﻩ ﻩﻩstｒinｇｇg; ﻩ ｇg=Leｔｔeｒ_Folｌow（p,p[i］．lｅｆｔ[0]）；ﻩﻩ ﻩﻩNOＮＥ［Ｖn．finｄ(ｐ[i］.ｌeft［０］）]=0; ｆor（intk=0；k〈gg。ｌｅｎgtｈ()；ｋ＋＋) ﻩ ﻩﻩ｛ ﻩﻩ ｉf(Ｆollｏw［Vn。fiｎd（ｃｈ）］。fｉnd（gg[k］）>100) ﻩﻩ ﻩ{ ﻩ Folloｗ［Ｖn．find（ch）］＋=gｇ［k]； ﻩ ﻩ} ﻩ ｝ ﻩ ｝ﻩ elsｅﻩﻩ ﻩ{ﻩﻩﻩ stringＦＦ; ﻩfor（ｉｎtｊｊ=j+1;jj＜p[ｉ］.rｉght.leｎgtｈ(）；jｊ+＋) ﻩﻩﻩﻩ{ ﻩﻩ ﻩsｔriｎgTT；ﻩ TＴ=Letter_Fｉrst(p,ｐ［i］。rｉghｔ［jj］); ﻩ ﻩif（！（TＴ．find（’＊’）＞100)＆＆(jｊ+１）〈p［ｉ］．rｉght.lengｔh（）） ﻩ { ﻩﻩ sorｔ（TT.ｂegｉn(）,TT.enｄ（))； ﻩ ﻩ sｔrｉｎgtｔ; ﻩ foｒ(intt＝1;t<TT．leｎgｔｈ(）；t＋＋） ﻩ ﻩ ｛ ﻩﻩ tt＋=TT［t];ﻩ ﻩ ﻩ} ﻩﻩﻩﻩTT