编译原理课设2

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

2、具VC /JAVA/C#/.NET 。2课程设计的任务及要求1）课程设计任务： 设计一个由正规文法生成FirstVT集和LastVT集的算法动态模拟。 动态模拟算法的基本功能是：（1）输入一个文法G；（2）输出由文法G构造FIRSTVT集的算法；（3）输出FirstVT集； （4）输出由文法G构造LastVT集的算法；（5）输出LastVT集。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，西安：西北工业大学出版社6）课程设计进度安排1准备阶段（

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

5、0分）：优（）、良（）、中（）、一般（）、差（）； 评阅人： 职称： 副教授 2016 年 6 月 日中文摘要随着计算机科学的飞速发展，形式语言与自动机理论和方法的研究也越来越受到人们的重视，但前者已经成为计算机科学的理论基础。本课程设计主要研究自动机在编译方面的应用，并将讨论重点放在算符优先分析法上，并用此理论完成算数表达式的正确与否的判断。算符优先分析算法通过编写一个语法程序，使程序具有通用性。其基本思想描述，语法分析前首先要对输入的文法和句子进行词法分析，去除多余的自负，并将产生式和终结符、非终结符填入有关数组，为语法分析做前期准备。本课程设计的题目为“FirstVT集和LastVT集生

6、成算法模拟”，它是算符优先分析算法中判断三种优先关系的关键。算符优先分析算法是自底向上分析方法的一种。计算非终结符的FirstVT集和LastVT集是构造算符优先分析表的基础，而算符优先分析表的构造又是算符优先分析算法的基础。因此，本程序的实现可以说是算符优先分析算法实现的基础。目录一、课程设计任务及要求1二、需求分析2三、设计思路3四、详细设计4五、运行调试与分析讨论8六、设计体会与小结9七、参考文献10-第 3 页 -一、课程设计任务及要求课设目的进一步培养学生编译器设计的思想，加深对编译原理和应用程序的理解，针对编译过程的重点和难点内容进行编程，独立完成有一定工作量的程序设计任务，同时强

7、调好的程序设计风格，并综合使用程序设计语言、数据结构和编译原理的知识，熟悉使用开发工具VC /JAVA/C#/.NET 。总体要求1、 问题理解和分析充分地分析和理解问题本身，弄清要求做什么。2、确定解决问题的方法（设计）主要是找到解决问题的主要思路，是怎么做。在此阶段可考虑系统的功能和模块划分等。 3、详细设计和编码确定算法的主要流程，再进行编程。在此阶段应提醒学生程序可先在纸上写，尽量想清楚了再动手上机，在编程过程中注意程序结构的清晰性，避免出现很多明显的程序逻辑错误和语法错误，提高后面程序调试效率。4、程序调试和运行使学生掌握程序调试和排错的基本方法，增加编程的感觉和解决问题的成就感。基

8、本要求设计一个由正规文法生成FirstVT集和LastVT集的算法动态模拟，实现以下功能输入一个文法G； 1. 输出由文法G构造FIRSTVT集的算法； 2. 输出FirstVT集； 3. 输出由文法G构造LastVT集的算法； 4. 输出LastVT集。二、需求分析本课程设计的题目为“FirstVT集和LastVT集生成算法模拟”，它是算符优先分析算法中判断三种优先关系的关键。算符优先分析算法是自底向上分析方法的一种。所谓自底向上分析，也称移近规约分析，粗略地说它的实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出的栈中，边移进边分析，一旦栈顶符号串形成某个句型的句柄或可

9、规约串，就用该产生式的左部非终结符代替相应右部的文法符号串，这称为一部规约。重复这一过程直到规约到栈中只剩文法的开始符号则为分析成功，也就确认输入串是该文法的句子。而算符优先分析算法的基本思想只是规定算符之间的优先关系，也就是只考虑终结符之间的优先关系。 本课程设计的要求只是构造FirstVT集和LastVT集，在此基础上扩充建造算符优先关系表。同时我们可以用数据库存储多行文法，用LIST控件显示算法，用GRID类依据算法进行作图。并实现算法与生成过程的关联。三、设计思路3.1基本算法1. FirstVT集的构造 FIRSTVT(P）=a|P=+a或P=+Qa，aVT而QVN 若有产生式：Pa

10、或PQa,则aFIRSTVT(P)； 若aFIRSTVT(Q)，且有产生式PQ，则aFIRSTVT(P)。 步骤如下： 首先按规则对每个数组元素附初值。观察这些初值，若FiA,ia的值是真，则将（A，a）推入栈中，直至对所有数组的初值都按此处理完。然后对栈做如下运算。 将栈顶项弹出，则令其变为真，且将（A，a）推进栈，如此重复直到栈弹空为止。 2.LastVT集的构造 LASTVT(P)= a|P=+a或P=+aQ，aVT而QVN 若有产生式：Ua或UaV, 则aLASTVT(U)； 若aLASTVT(V)，且有产生式UV，则aLASTVT(U)。步骤同FirstVT集构造步骤相同。 当我们有

11、了这二个集合之后，就可以通过检查每个产生式的候选式确定满足关系的“”和“”的所有终结符对。 我们假定有产生式的一个侯选式形为aP，那么，对任何bFIRSTVT(P），ab； 假定有产生式的一个候选形为Pb，那么，对任何aLASTVT(P)，有ab。3. 构造算符优先关系表 在我们有了每个非终结符P的FIRSTVT(P）和LASTVT(P)集合之后，就能够构造文法G的优先表。3.2语法定义本次课设题目以文法GE为测试数据；文法GE：E-TEE-+TE|T-FTT-*FT|F-(E)|i3.3计算FirstVT集和LastVT集该文法有对应集合：FirstVT(E)= +, * ,( ,i Las

12、tVT(E)= +，*，),i FirstVT(E)= +LastVT(E)= +，*，),i FirstVT(T)= * ,( ,i LastVT(T)= *，),i FirstVT(T)= * LastVT(T)= *，),i FirstVT(F)= ( ,i LastVT(F)= ),i 4、 详细设计4.1.1课设基本代码char data2020;char s100; char lable20;/文法终极符集char input100;/文法输入符号串char string2010;int k; char a; int j; char q; int r;int r1;char st1

13、030;char first1010;/文法非终结符FIRSTVT集char last1010;/文法非终结符LASTVT集int fflag10=0;int lflag10=0;int deal();/对输入串的分析int zhongjie(char c);/判断字符c是否是终极符int xiabiao(char c);void out(int j,int k,char *s);void firstvt(char c);/求非终结符c的FIRSTVT集void lastvt(char c); /求非终结符c的LASTVT集void table(); /创建文法优先关系表4.1.2主要数据存储

14、存储结构void FirstVT(char c) /求FirstVT集int i,j,k,m,n;for(i=0;ir;i+)if(sti0=c)break;if(fflagi=0)n=firsti0+1;m=0;doif(m=2|stim=|)if(zhongjie(stim+1)firstin=stim+1;n+;elseif(zhongjie(stim+2)firstin=stim+2;n+;if(stim+1!=c)FirstVT(stim+1);for(j=0;jr;j+)if(stj0=stim+1)break;for(k=0;kfirstj0;k+)int t;for(t=0;t

15、n;t+)if(firstit=firstjk+1)break;if(t=n)firstin=firstjk+1;n+;m+;while(stim!=0);firstin=0;firsti0=-n;fflagi=1;void lastvt(char c) /求LASTVT集int i,j,k,m,n;for(i=0;ir;i+)if(sti0=c)break;if(lflagi=0)n=lasti0+1;m=0;doif(stim+1=0|stim+1=|)if(zhongjie(stim)lastin=stim;n+;elseif(zhongjie(stim-1)lastin=stim-1;

16、n+;if(stim!=c)lastvt(stim);for(j=0;jr;j+)if(stj0=stim)break;for(k=0;klastj0;k+)int t;for(t=0;tTEE-+TE|T-FTT-*FT| F-(E)|i 2、运行结果截图：第 7 页 6、 设计体会与小结经过为期三天的编译原理课程设计上机和实践，加深了我对编译原理这门课的理解，同时由于课设题目的要求，我对自底向上的分析方法和算符优先文法也有了更深一层次的理解，明白了在编码过程中需要构建两个优先关系函数：FirstVT和LastVT以及语法的输入函数和输出函数，同时也运用到了进栈、入栈知识点。虽然最后完成了课设的总体目标，但是在课设进行的过程中还是遇到了很多麻烦，例如不知道运用什么函数来记录