编译原理课设3

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

2、#/.NET 。2课程设计的任务及要求1）课程设计任务：对文法G的句子进行确定的自顶向下语法分析的充分必要条件是，G的任意两个具有相同左部的产生式A>| 满足下列条件：（1）如果、均不能推导出，则 FIRST() FIRST() = 。（2） 和 至多有一个能推导出 。（3）如果 *> ，则 FIRST() FOLLOW(A) = 。将满足上述条件的文法称为LL(1)文法。2）创新要求：3）课程设计论文编写要求（1）课程设计任务及要求（2）设计思路-工作原理、功能规划（3）详细设计-数据分析、算法思路、功能实现（含程序流程图、主要代码及注释）、界面等。（4）运行调试与分析讨论-给出

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

4、大学出版社6）课程设计进度安排1准备阶段（4学时）：选择设计题目、了解设计目的要求、查阅相关资料2程序模块设计分析阶段（4学时）：程序总体设计、详细设计3代码编写调试阶段（8学时）：程序模块代码编写、调试、测试4撰写论文阶段（4学时）：总结课程设计任务和设计内容，撰写课程设计论文学生签名： 2016 年 6 月 24 日课程设计(论文)评审意见（1）学习态度（20分）：优（）、良（）、中（）、一般（）、差（）； （2）系统设计（20分）：优（ ）、良（）、中（）、一般（）、差（）； （3）编程调试（20分）：优（）、良（）、中（）、一般（）、差（）；（4）回答问题（20分）：优（）、良（）、中

5、（）、一般（）、差（）；（5）论文撰写（20分）：优（）、良（）、中（）、一般（）、差（）； 评阅人： 职称： 副教授 2016 年 6 月 日中文摘要对文法G的句子进行确定的自顶向下语法分析的充分必要条件是，G的任意两个具有相同左部的产生式A>| 满足下列条件：（1）如果、均不能推导出，则 FIRST() FIRST() = 。（2） 和 至多有一个能推导出 。（3）如果 *> ，则 FIRST() FOLLOW(A) = 。将满足上述条件的文法称为LL(1)文法。概要第一个L代表从左向右扫描输入符号串，第二个L代表产生最左推导，1代表在分析过程中执行每一步推导都要向前查看一个输

6、入符号当前正在处理的输入符号。LL(1)文法既不是二义性的，也不含左递归，对LL(1)文法的所有句子均可进行确定的自顶向下语法分析。需要注意的是，并不是所有的语言都可以用LL(1)文法来描述，而且不存在判定某语言是否是LL(1)文法的算法。也就是说，确定的自顶向下分析只能实现一部分上下文无关语言的分析，这就是LL(1)文法所产生的语言。另外，在上述LL(1)文法的条件中，要求： FIRST(1)， FIRST(2)， FIRST(n) 中至多有一个成立。 目录一、课程设计任务及要求1二、需求分析2三、设计思路3四、详细设计5五、运行调试与分析讨论10六、设计体会与小结11七、参考文献12-第

7、5 页 -一、课程设计任务及要求题目：LL(1)分析过程模拟【问题描述】 设计一个给定LL（1）分析表，输入一个句子，能由依据LL（1）分析表输出与句子对应的语法树。能对语法树生成过程进行模拟。(算法参见教材)【基本要求】 动态模拟算法的基本功能是：输入LL（1）分析表和一个句子；输出LL（1）总控程序；输出依据句子构成的对应语法树的过程；【测试数据】输入句子：i*i+i输入LL（1）分析表®(E)®iF®e® e®*FT '® eT'®FT '®FT'T®e®

8、e®+TE'E'®TE'®TE'E#)(*+i【实现提示】用结构体数组存储多行正规式，用LIST控件显示算法，用CDC类依据进行算法进行作图。并实现算法与生成过程的关联。二、需求分析问题理解用数据库存储多行文法，用LIST控件显示算法，用GRID类依据算法进行作图。并实现算法与生成过程的关联。问题分析求出First集和Follow集，是求出Select集的基础，因此本程序也做了些完善，功能扩展发面，在出First集和Follow集的基础上求Select集，判断是否为LL1文法，构造预测分析表。判断是在LL1分析文法中通过Select

9、集判断是否是LL1文法，求出预测分析表之后，实现了字符串，依据LL1分析表单步输出字符串的分析过程。三、设计思路1、设计原理（1）、LL（1）文法的定义LL(1)分析法属于确定的自顶向下分析方法。LL(1)的含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第2个L表明分析过程中将使用最左推导，1表明只需向右看一个符号便可决定如何推导，即选择哪个产生式(规则)进行推导。LL(1)文法的判别需要依次计算FIRST集、FOLLOW集和SELLECT集,然后判断是否为LL(1)文法,最后再进行句子分析。（2）、预测分析表构造LL(1)分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式

10、进行推导。它的行对应文法的非终极符，列对应终极符，表中的值有两种：一是产生式的右部的字符串，一是null。若用M表示LL(1)分析表，则M可表示如下：M: VN×VTàPErrorM(A, t) = Aà，当tÎselect(Aà) ，否则M(A, t) = Error其中P表示所有产生式的集合。（2）、语法分析程序构造LL(1)分析中X为符号栈栈顶元素，a为输入流当前字符，E为给定测试数据的开始符号，#为句子括号即输入串的括号。分析表用一个二位数组M表示，数组元素MA，a中的下标A表示非终结符，a为终结符或句子括号#，二维数组中存放的是一条关

11、于A 的产生式，表明当非终结符A向下推导时，面临输入符a时，所采用的候选产生式，当元素内容无产生式时，则表明用A 的左部向下推导时出现了不该出现的符号，因此元素内容转向出错处理的信息。2、主要算法思想（1）、 分析开始时，首先将标志符号#和文法开始符号E依次压入符号栈；输入流指针指向分析串的第一个输入符号，即由符号栈和输入流构成的初始格局为：(#E,a1a2.an#)然后，反复执行第2步所列的工作。（2）、设在分析的某一步，符号栈及剩余的输入流处于如下的格局：(#A12.Am-1Am,aiai+1.an#)其中，A1A2.Am-1Am为分析栈中的文法符号，此时，可视栈顶符号Xm的不同情况，分别

12、作如下动作：若AmÎVN，则以Am及ai组成的符号对(Am，ai)查分析表M。设M(Am，ai)为一产生式，假设是AmàUVW，此时将Am从分析栈中弹出，并将UVW逆序压入栈中，从而得到新的格局：(#A1A2.Am-1WVU,aiai+1.an#)但若T(Am，ai)=NULL或null，则调用出错处理程序进行处理；。四、详细设计总体思路分析及流程图给定一个正规文法G，在LL(1)预测分析中，必须先求出First集和Follow集，然后求出Select集，通过Select集判断是否是LL1文法，如果是的话，构造预测分析表。求出预测分析表之后，再输入一个字符串，依据LL1分析

13、表单步输出字符串的分析过程。功能模块分解图（1）主程序流程图（2）核心算法流程图 1.计算非终结符的First集的算法及流程：First集合的构造算法：（1）若XVT，则First（X）=X。（2）若XVN，且有产生式Xa，则把a加入到First (X)中；若X也是一条产生式，则把也加到First (X)中。（3）若XY是一个产生式且YVN，则把First (Y)中的所有非-元素都加到First (X)中；若XY1Y2Yk是一个产生式，Y1，Yi-1都是非终结符，而且，对于任何j，1ji-1，First (Yj)都含有（即Y1Yi-1* ），则把First (Yj)中的所有非-元素都加到Fir

14、st (X)中；特别是，若所有的First (Yj)均含有，j=1,2,，k，则把加到First (X)中。连续使用上面的规则，直至每个集合First不再增大为止。2.计算非终结符的Follow集：Follow集合的具体构造算法如下：（1）对于文法的开始符号S，置#于Follow(S)中；（2）若AB是一个产生式，则把First()|加至Follow(B)中；（3）若AB是一个产生式，或AB是一个产生式而 （即First()），则把Follow(A)加至Follow(B)中。连续使用上面的规则，直至每个集合Follow不再增大为止。3.预测分析控制程序的算法流程2、测试数据i*i+i 的语法树

15、 关键代码计算非终结符的First集：void first(edge ni,edge *n,int x)/ni为一个产生式，n为整个文法int i,j;for(j=0;j<SUM;j+)if(ni.getlf()=nj.getlf()if(NODE.find(nj.getro()<NODE.length()/非终结符的情况for(i=0;i<SUM;i+)if(ni.getlf()=nj.getro()first(ni,n,x);elsenx.newfirst(nj.getro();/终结符的情况计算非终结符的Follow集：void follow(edge ni,edge

16、*n,int x) /计算followint i,j,k,s;string str;for(i=0;i<ni.getrlen();i+) s=NODE.find(ni.getrg()i);if(s<NODE.length()&&s>-1) /是非终结符if(i<ni.getrlen()-1) /不在最右for(j=0;j<SUM;j+)if(nj.getlf().find(ni.getrg()i)=0)if(NODE.find(ni.getrg()i+1)<NODE.length() for(k=0;k<SUM;k+)if(nk.get

17、lf().find(ni.getrg()i+1)=0) nj.newfollow(nk.getfirst(); if(nk.getfirst().find("*")<nk.getfirst().length() nj.newfollow(ni.getfollow();elsestr.erase(); str+=ni.getrg()i+1; nj.newfollow(str);五、运行调试与分析讨论第 9 页 六、设计体会与小结对于此次的课设，我得出一句话：纸上得来终觉浅，绝知此事要躬行。只有你亲手去做了，你才有资格说这件事的难易。即使你失败了，也是受益匪浅的。由于实验失败的原因，本次实验对于我个人来说，成就没有多大意义。不过对于失败后的一些感触及心得体会如下。1。准备越充分，实验越顺利。2。交流是最好的老师。实验过程中，多多少少会遇到问题，多咨询老师或者会做实验的同学。这样才能将难题一一化解。3。一半时