《编译原理课程设计报告First、Follw求解报告书.doc》由会员分享，可在线阅读，更多相关《编译原理课程设计报告First、Follw求解报告书.doc（24页珍藏版）》请在三一办公上搜索。
1、淮阴工学院编译原理课程设计报告选题名称: FIRST、FOLLOW求解 系（院）: 计算机工程学院专 业:计算机科学与技术（软件工程方向）班 级: 软件1082 姓 名: 学 号: 指导教师: 高丽 王文豪 江波 于永彦学年学期: 2011 2012 学年 第 1 学期 2012 年 01 月 07 日设计任务书课题名称FIRST、FOLLOW求解设计目的1. 理解文法回溯等现象在语法分析中的不良影响；2. 掌握FIRST、FOLLOW集的定义、求解方法与算法思想；3. 掌握一般性通用算法存在的缺陷，例如右递归等；4. 学会使用VC+等开发工具编写FIRST、FOLLOW集的通用求解程序。5.
2、 学习开发资料的收集与整理，学会撰写课程设计报告。实验环境1. 微型电子计算机（PC）；2. Visual C+ 6.0、C#2003等以上版本开发环境。任务要求1. 根据用户输入的文本文件（*.txt）的名称，打开文件，并从文件中获取文法的产生式、非终结符、终结符、开始符等基本信息；2. 判断该文法是否存在左递归，若存在，则消除左递归；3. 根据文法基本信息，分别使用关系图法和通用算法求解单个非终结符和产生式右部符号串的FIRST、FOLLOW集。4. 结束后，及时提交课程设计报告（含纸质稿、电子稿）。工作进度计划序号起止日期工 作 内 容12012.01.022012.01.03在预设计的
3、基础上，进一步查阅资料，完善设计方案，形成书面材料。22012.01.032012.01.04设计总体方案，构建绘制流程框图，编写代码，上机调试。32012.04.022012.01.06测试程序，优化代码，增强功能，撰写设计报告。42012.01.072012.01.07提交软件代码、设计报告，参加答辩，根据教师反馈意见，修改、完善设计报告。指导教师（签名）： 年 月 日 摘要：编译原理是计算机科学与技术专业最重要的一门专业基础课程，内容庞大，涉及面广，知识点多。由于该课程教、学难度都非常大，往往费了大量时间而达不到预期教学效果俗语说：学习的最好方法是实践。本次课程设计的目的正是基于此，力求
4、为学生提供一个理论联系实际的机会，通过布置一定难度的课题，要求学生独立完成。我们这次课程设计的主要任务是编程实现对给定文法的FIRST集和FOLLOW集的求解。通过实践，建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验、探索前言知识的习惯，树立团队协作精神。同时，课程设计可以充分弥补课堂教学及普通实验中知识深度与广度有限的缺陷，更好地帮助学生从全局角度把握课程体系。关键词：编译原理；FIRST集；FOLLOW集目录1 课题综述11.1 课题来源11.2 课题意义11.3 预期目标11.4 面对的问题11.5 需解决的关键技术12 系统分析22.
5、1 基础知识22.1.1 FIRST集定义22.1.2FIRST集求解算法错误！未定义书签。2.1.3FOLLOW集的定义42.1.4 FOLLOW集算法42.2 解决问题的基本思路42.3 总体方案43 系统设计53.1 算法实现53.2 流程图64 代码编写105 程序调试156 运行与测试151 课题综述 1.1 课题来源文法：包含若干终结符，非终结符，由终结符与非终结符组成的产生式。本次课程设计就是对产生式进行左递归分析，待无左递归现象后进行FIRST集与FOLLOW集的求解。1.2 课题意义由文法产生的若干个句子有可能是合法的或者不合法的，也有可能产生歧义，所以要消除歧义先消除文法左
6、递归，然后根据求得的FIRST集与FOLLOW集构造分析表，分析给定句子的合法性。1.3 预期目标编写程序，实现对文法的读取，判定是否含左递归，然后消除左递归，并对消除左递归的文法进行拆分得到其所有终结符与非终极符。最后对每一个非终结符和产生式右部进行FIRST集与FOLLOW集的求解。1.4 面对的问题如何读取文法，并判断是否含有左递归，怎么得到每一个非终结符与产生式右部，消除左递归，FIRST集与FOLLOW集的求解算法。1.5 需解决的关键技术本次课程设计中的关键是：FIRST集与FOLLOW集的求解算法，终结符 V和V，多了个带 的终结符，但是它在处理的时候只能当一个符号来识别，而用程
7、序设计语言表示时它能表示成两个字符，如果处理不当的话，V就可能被认为是终结符号V和非终结符。这无疑给处理过程添加了难度。还有一些自认为理所当然能实现的，却实际并不可取的方法。如：本来JAVA API有个方法String.split(String s);用于以s 为分割字符，将指定的字符分成字符数组。但是s 为括号时（无论左右括号，大小括号，方框括号），都不能分割，并且抛异常。这是个很难理解的问题。迫不得已，我不得不想其他的方法来实现分割算法。再有就是对编译原理中First Follow算法设计时，采取何种策略效率最高的问题以及如何编写、调试、修改代码。还要了解一个题目有许多种解决方法。锻炼我们
8、的思维能力。 2 系统分析2.1 基础知识2.1.1 FIRST集定义一、关系图法求解FIRST：依次扫描文法每一条产生式I删除所有右部含终结符的产生式。若使得以某非终结符为左部的所有产生式都被删除，则置该非终结符的标记为“否”。II若某非终结符存在一条右部为的产生式，则置该非终结符的标志为“是”，并删除该非终结符的所有产生式。扫描产生式右部的每一符号I若某非终结符标志为“是”，则删去该非终结符，若进而使得某产生式右部为空，则置该式左部的非终结符标志为“是”，并删除该非终结符为左部的所有产生式，如“S”。II若某非终结符标志为“否”，则删去该产生式，若使得左部为该非终结符的产生式都被删去，则置
9、该非终结符标志为“否”。重复上述步骤，直到扫描完一遍文法的产生式，非终结符标志位不再改变为止。按下述步骤从关系图求解FIRST。凡是从FIRST(A)结点有路径可到达的终结符点所标记的终结符为FIRST(A)的成员。若某非终结符能够 ，则将加入该非终结符的FIRST集中。二、 根据通用算法构造FIRST（1）文法符号的FIRST对于文法中的每一个符号X（VNVT），构造FIRST（X）时，只要连续使用下列步骤，直至FIRST集不再扩大为止。步骤1若XVT，则FIRST（X）X；步骤2若XVN，则考查以X为左部的每一条产生式： 若X是一条产生式，则FIRST（X）； 若XY1Y2Yn是产生式：(
10、I)若Y1, , Yi-1都VN且都能（其中1in），则FIRST(Y1)-，FIRST(Y2)-，FIRST(Yi-1)-和FIRST(Yi)都包含在FIRST(X)中；(II)若所有的FIRST(Yi)均能，i1, 2, , k，则把加到FIRST(X)中。2.1.3FOLLOW集的定义FOLLOW(A)=a|ZA且aVt,aFIRST(),Vt*,V+AVn若Z A ,且 ，则#FOLLOW(A)该集合称为A的后继符号集合 或定义为：FOLLOW(A)=a| ZAa，aVtAVn,Z识别符号 特殊地：若Z .A 则 #FOLLOW(A)2.1.4 FOLLOW集算法设S, A, BVn
11、, 算法：连续使用以下规则，直至FOLLOW集合不再扩大。(1)若S为识别符号,则把“#”加入FOLLOW(S)中 ； (2)若AB ()，则FIRST()-加入FOLLOW(B) 。(3)若AB 或AB， 且，则把FOLLOW(A)加 入FOLLOW(B) 。2.2 解决问题的基本思路根据课程设计的要求，程序应具有如下功能：对输入的文法进行分析并判断是否为左递归文法。如果是则先消除左递归。然后求解FIRST集和FOLLOW集。2.3 总体方案First集Follow集求解从文件中读取文法进行分析读取用户输入的文法并分析分析文法的First集合分析文法的Follow集合3 系统设计3.1 算法
12、实现具体过程如下：1、 首先将文法显示在RichTextBox1上2、 若有左递归，将之消除左递归显示在RichTextBox2上3、对RichTextBox2上文法调用First类求FIRST集，显示在ListView1上。4、对RichTextBox2上文法调用Follow类求FOLLOW集，显示在ListView2上。3.2 流程图1).UI用户操作界面控制流图读取文法开始由文法处理单元计算出终结符，非终结符集计算出所有非终结符的First,Follow集在界面上显示出每个非终结符的First,Follow集和计算过程完成 2).识别非终结符集和终结符集读取一条产生式识别产生式的左部字符
13、V将V添加到非终结符集合开始结束开始还有未分析的产生式Y识别所有符号（Vt,Vn）去除非终结符号得到终结符集合结束 3).计算各个非终结符的First集开始读取一个非终结符V遍历所有产生式，查找左部是V的产生式取出得到的一条产生式产生式右部第一个符号V*是终结符？将该终结符V*加入V的First集中YV*是不是有推导规则V*-Y添加一个删除的标志为true标志为真删除，得到V的First集还有为计算的非终结符完成NY说明：在求First集合时，主要用的思想是递归求解。 4. 计算各个非终结符的Follow集开始取得一个非终结符V查找产生式的右部含有V的产生式V是不是最后一个字符添加#到V的Fo
14、llow集中是否遍历完所有右部含有V的产生式NY是否有未求解过的非终结符完成V后一个字符V*是否为终结符YN添加V*到V的Follow中Y将V*的First集加入到V的Follow集中YN4 代码编写部分代码如下： public partial class Form1 : Form Getlist gl = new Getlist(); private ArrayList firstl = new ArrayList(); private ArrayList resultfollowlist = new ArrayList(); private ArrayList alist = new Ar
15、rayList(); private ArrayList blist = new ArrayList(); private ArrayList phresultstringlist = new ArrayList(); public Form1() InitializeComponent(); private void Form1_Load(object sender, EventArgs e) try StreamReader m_streamReader = new StreamReader(文?法?txt); m_streamReader.BaseStream.Seek(0, SeekO
16、rigin.Begin); string strLine = m_streamReader.ReadLine(); String tempstrline = ; while (strLine != null) tempstrline += strLine + n; strLine = m_streamReader.ReadLine(); m_streamReader.Close(); this.listview.Text = tempstrline; catch /判D断?是?否?含?有瓺左哩?递蘗归 if (!IsExitLeftRecur() this.label2.Visible = t
17、rue; this.label3.Visible = true; this.inputbox.Visible = true; this.inputbox.Text = this.listview.Text; else private bool IsExitLeftRecur() return false; private void button1_Click(object sender, EventArgs e) listView1.Clear(); Getlist getset = new Getlist(); String str = inputbox.Text.ToString(); i
18、nt palist; First first = new First(); Follow follow = new Follo if (str.Length = 100000) MessageBox.Show(文?件t内容太?大洙?，?换?个?小?些?的?!); else if (str.Length = 0) MessageBox.Show(没?有瓺文?件t读入?!); else getset = first.firstscan(str); /显?示?部?分? alist = getset.getAlist(); blist = getset.getBlist(); firstl = get
19、set.getResultfirstlist(); resultfollowlist = follow.followscan(getset); gl.setResultfirstlist(firstl); gl.setResultfollowlist(resultfollowlist); gl.setAlist(alist); gl.setBlist(blist); listView1.Columns.Add(非?终?结符?.PadRight(4, ); listView1.Columns.Add(first集.PadRight(6, ); for (palist = 0; palist =
20、100000) MessageBox.Show(文?件t内容太?大洙?，?换?个?小?些?的?!); else if (str.Length = 0) MessageBox.Show(没?有瓺文?件t读入?!); else getset = first.firstscan(str); alist = getset.getAlist(); blist = getset.getBlist(); firstl = getset.getResultfirstlist(); resultfollowlist = follow.followscan(getset); gl.setResultfirstli
21、st(firstl); gl.setResultfollowlist(resultfollowlist); gl.setAlist(alist); gl.setBlist(blist); listView2.Columns.Add(非?终?结符?.PadRight(6, ); listView2.Columns.Add(follow集.PadRight(13, ); for (palist = 0; palist Sa）? private ArrayList alist = new ArrayList(); /存?放?箭y头?前字?母? private ArrayList blist = ne
22、w ArrayList(); /存?放?箭y头?后字?符?串? private ArrayList clist = new ArrayList(); /存?放?箭y头?后字?符?串?首骸?地?址 private ArrayList firstlist = new ArrayList();/存?放?first集的?表括? private ArrayList pointfirstlist = new ArrayList();/用?于?存?放?firstlist的?指?针?地?址 private ArrayList resultfirstlist = new ArrayList();/存?放?最?终
23、?结果?字?符?串?链?表括? private ArrayList resultfollowlist = new ArrayList();/存?放?最?终?结果?字?符?串?链?表括? public ArrayList getAlist() return alist; public void setAlist(ArrayList alist) this.alist = alist; public ArrayList getBlist() return blist; public void setBlist(ArrayList blist) this.blist = blist; public
24、ArrayList getClist() return clist; public void setClist(ArrayList clist) this.clist = clist; public String getStr() return str; public void setStr(String str) this.str = str; public ArrayList getFirstlist() return firstlist; public void setFirstlist(ArrayList firstlist) this.firstlist = firstlist; p
25、ublic ArrayList getPointfirstlist() return pointfirstlist; public void setPointfirstlist(ArrayList pointfirstlist) this.pointfirstlist = pointfirstlist; public ArrayList getResultfirstlist() return resultfirstlist; public void setResultfirstlist(ArrayList resultfirstlist) this.resultfirstlist = resu
26、ltfirstlist; public ArrayList getResultfollowlist() return resultfollowlist; public void setResultfollowlist(ArrayList resultfollowlist) this.resultfollowlist = resultfollowlist; /还有求解FIRST集和FOLLOW集的详细算法的代码较多未能附上。5 程序调试程序中调用了许多函数，编写代码时会出现调用的错误，使在程序运行时无法正确判断以致程序运行出错。在创建函数时会出现错误而无法得知，致使在程序运行时出错，需要很细心的
27、去编写代码，出现错误时，使用断点调试的方法逐一对每个函数监视。编程的时候一定要细心，对出现的错误要认真调整，反复修改，使函数前后相对应。 6 运行与测试运行界面如下： 得到产生式：消除左递归： FIRST集和FOLLOW集：总结在经过了一个星期的编译原理课程设计，我获益匪浅。本次课程设计是我们将所学理论知识形成系统的一个锻炼的好机会，也是学校和老师检验我们学习成果的一个方法。经过一周的设计，FIRST集和FOLLOW集的算法可以了然于心。这次的课程设计已经结束了，通过编程基本实现了预期的目标，我们只有不断的发现问题，不断的解决问题，才能使一个程序尽可能的完善。由于经验不足，时间有限，虽然在一周
28、的时间完成了系统的分析、设计和调试的工作，但是仍然有许多不足之处，会在以后的学习中努力改正。致谢在这次的课程设计中，让我深深地体现到编程不是一件简单的事情，它需要设计者具有全面的专业知识、缜密的思维、严谨的工作态度以及较高的分析问题、解决问题的能力，而我在很多方面还有欠缺。.感谢各位老师以及同学给我的指导。参 考 文 献1 编译原理（第2版）/张素琴，吕映芝，蒋维杜，戴桂兰编著 北京：清华大学出版社，20082 编译原理及实践教程/黄贤英, 王柯柯编著 北京:清华大学出版社,20083 编译原理学习辅导/张伟编著 北京:清华大学出版社,20054 编译原理/主编胡延忠, 刘建舟, 林姗 武汉:
29、华中科技大学出版社,20075 编译原理和技术/丁文魁, 杜淑敏编著 北京:电子工业出版社,2008指导教师评语学号1081305211姓名韩济鸿班级软件1082选题名称FIRST、FOLLOW求解序号评价内容权重（%）得分1考勤记录、学习态度、工作作风与表现。52自学情况：上网检索机时数、文献阅读情况。103论文选题是否先进，是否具有前沿性或前瞻性。54成果验收：是否完成设计任务；能否运行、可操作性如何等。205报告的格式规范程度、是否图文并茂、语言规范及流畅程度；主题是否鲜明、重心是否突出、论述是否充分、结论是否正确；是否提出了自己的独到见解。306文献引用是否合理、充分、真实。57答辩情况： 自我陈述、回答问题的正确性、用语准确性、逻辑思维、是否具有独到见解等。25合计指导教师（签名）： 年 月 日
