《编译原理课程设计任务书2016(软件测试)》由会员分享，可在线阅读，更多相关《编译原理课程设计任务书2016(软件测试)（19页珍藏版）》请在金锄头文库上搜索。
1、课程设计(论文)任务书 软软 件件 学学 院院学院13-软件测试软件测试专业2班 一、课程设计(论文)题目FirstFirst 集和集和 FollowFollow 集生成算法模拟集生成算法模拟 二、课程设计(论文)工作自20162016 年6 6 月 2020 日起至20162016 年 6 6 月 2424 日止。 三、课程设计(论文) 地点:软软 件件 学学 院院 实实 训训 中中 心心 四、课程设计(论文)内容要求： 1本课程设计的目的本课程设计的目的 进一步培养学生编译器设计的思想，加深对编译原理和应用程序的理解，针对编 译过程的重点和难点内容进行编程，独立完成有一定工作量的程序设计任
2、务，同时， 强调好的程序设计风格，并综合使用程序设计语言、数据结构和编译原理的知识, 熟 悉使用开发工具 VC /JAVA/C#/.NET 。 2课程设计的任务及要求课程设计的任务及要求 动态模拟算法的基本功能是： （1）输入一个文法 G； （2）输出由文法 G 构造 FIRST 集的算法； （3）输出 First 集； （4）输出由文法 G 构造 FOLLOW 集的算法； （5）输出 FOLLOW 集。 2）创新要求：）创新要求： 在基本要求达到后，可进行创新设计在基本要求达到后，可进行创新设计 3）课程设计论文编写要求）课程设计论文编写要求 （1）课程设计任务及要求 （2）设计思路-工作原
3、理、功能规划 （3）详细设计-数据分析、算法思路、功能实现（含程序流程图、主要代码及注 释）、界面等。 （4）运行调试与分析讨论-给出运行屏幕截图，分析运行结果，有何改进想法等。 （5）设计体会与小结-设计遇到的问题及解决办法，通过设计学到了哪些新知识， 巩固了哪些知识，有哪些提高。 （6）报告按规定排版打印，要求装订平整，否则要求返工； （7） 课设报告的装订顺序如下： 封面-任务书-中文摘要-目录-正文-附录 (代码及相关图片) （8）严禁抄袭，如有发现，按不及格处理。 编译原理课程设计 4）课程设计评分标准：）课程设计评分标准： （1）学习态度：20 分； （2）系统设计：20 分； （
4、3）编程调试：20 分； （4）回答问题：20 分； （5）论文撰写：20 分。 5）参考文献：）参考文献： （1）张素琴，吕映芝. 编译原理M., 清华大学出版社 （2）蒋立源、康慕宁等，编译原理（第 2 版）M，西安：西北工业大学出版社 6）课程设计进度安排）课程设计进度安排 1准备阶段（4 学时） ：选择设计题目、了解设计目的要求、查阅相关资料 2程序模块设计分析阶段（4 学时） ：程序总体设计、详细设计 3代码编写调试阶段（8 学时） ：程序模块代码编写、调试、测试 4撰写论文阶段（4 学时） ：总结课程设计任务和设计内容，撰写课程设计论文 学生签名： 2016 年6月24 日 课程设
5、计课程设计( (论文论文) )评审意见评审意见 （1）学习态度（20 分） ：优（） 、良（） 、中（） 、一般（） 、差（） ； （2）系统设计（20 分） ：优（） 、良（） 、中（） 、一般（） 、差（） ； （3）编程调试（20 分） ：优（） 、良（） 、中（） 、一般（） 、差（） ； （4）回答问题（20 分） ：优（） 、良（） 、中（） 、一般（） 、差（） ； （5）论文撰写（20 分） ：优（） 、良（） 、中（） 、一般（） 、差（） ； 评阅人：职称：副教授 2016 年6月日 编译原理课程设计 中文摘要中文摘要 编译原理是国内外各高等院校计算机科学技术类专业，特别是
6、计算机 软件专业的一门重要专业课程。该课程系统地向学生介绍编译程序的结构、 工作流程及编译程序各组成部分的设计原理和实现技术。由于该课程理论 性和实践性都比较强，内容较为抽象复杂，涉及到大量的软件设计算法， 因此，一直是一门比较难学的课程。为了使学生更好地理解和掌握编译技 术的基本概念、基本原理和实现方法，实践环节非常重要，只有通过上机 进行程序设计，才能使学生对比较抽象的教学内容产生具体的感性认识， 增强学生综合分析问题、解决问题的能力，并对提高学生软件设计水平大 有益处。 本课程设计正是选择了编译原理里面的 FIRST 和 FOLLOW 的算法来进行 设计，主要是模拟编译原理算法的过程，使
7、我们更好的理解和掌握编译技 术的基本概念、基本原理和实现方法，理论和实践轩昂结合，增强我们的 理论知识和编程能力。 进一步培养学生编译器设计的思想，加深对编译原理和应用程序的理 解，针对编译过程的重点和难点内容进行编程，独立完成有一定工作量的 程序设计任务，同时强调好的程序设计风格，并综合使用程序设计语言、 数据结构和编译原理的知识，熟悉使用开发工具 VC6.0 。 编译原理课程设计 目录目录 一、课程设计任务及要求1 二、需求分析2 三、设计思路2 四、详细设计3 4.1、总体思路分析3 4.2、设计原理4 五、运行调试与分析讨论11 六、设计体会与小结14 七、参考文献15 编译原理课程设
8、计 1 一、课程设计任务及要求 First 集和 Follow 集生成算法模拟 【问题描述】 设计一个由正规文法生成 First 集和 Follow 集并进行简化的算法动态模 拟。(算法参见教材) 【基本要求】 动态模拟算法的基本功能是： 输入一个文法 G； 输出由文法 G 构造 FIRST 集的算法； 输出 First 集； 输出由文法 G 构造 FOLLOW 集的算法； 输出 FOLLOW 集。 【测试数据】 输入文法： E-TE E-+TE| T-FT T-*FT| F-(E)|i 【实现提示】 用数据库存储多行文法，用 LIST 控件显示算法，用 GRID 类依据算法进 行作图。并实现
9、算法与生成过程的关联。 i i ) ) ( ( * * + + F F的的firstfirst集集 T T的的firstfirst集集 E E的的firstfirst集集 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 编译原理课程设计 2 求出 First 集和 Follow 集，是求出 Select 集的基础，因此本程序也做 了些完善，功能扩展发面，在出 First 集和 Follow 集的基础上求 Select 集，判断是否为 LL1 文法，构造预测分析表。判断是在 LL1 分析文法中通 过 Select 集判断是否是 LL1 文法，求出预测分析表之后，实现了字符
10、串， 依据 LL1 分析表单步输出字符串的分析过程。 二、需求分析 求出 First 集和 Follow 集，是求出 Select 集的基础，因此本程序也做 了些完善，功能扩展发面，在出 First 集和 Follow 集的基础上求 Select 集，判断是否为 LL1 文法，构造预测分析表。判断是在 LL1 分析文法中通 过 Select 集判断是否是 LL1 文法，求出预测分析表之后，实现了字符串， 依据 LL1 分析表单步输出字符串的分析过程。 其实要知道一串符号是不是该文法的一个句子， 只要判断是否能从文法 的开始符号出发推导出这个输入串。语法分析可以分为两类，一类是自上 而下的分析法
11、，一类是自下而上的分析法。自上而下的主旨是，对任何输 入串，试图用一切可能的办法，从文法开始符号出发，自上而下的为输入 串建立一棵语法树。或者说，为输入串寻找一个最左推倒，这种分析过程 的本质是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程我 主要是自上而下的过程。 三、设计思路 在自上而下的分析法中，主要是研究 LL(1)分析法。它的解决步骤是首 先接收到用户输入的一个文法，对文法进行检测和处理，消除左递归，得 到 LL(1)文法，这个文法应该满足：无二义性无二义性，无左递归无左递归，无左公因子无左公因子。当 文法满足条件后，再分别构造文法每个非终结符的 FIRST 和 FOLLOW
12、 集合， 然后根据 FIRST 和 FOLLOW 集合构造 LL（1）分析表，最后利用分析表，根 据 LL(1)语法分析构造一个分析器。LL（1）的语法分析程序包含了三个部 分，总控程序，预测分析表函数，先进先出的语法分析栈。 编译原理课程设计 3 四、详细设计 4 4.1.1、总体思路分析、总体思路分析 给定一个正规文法 G，在 LL(1)预测分析中，必须先求出 First 集和 Follow 集，然后求出 Select 集，通过 Select 集判断是否是 LL1 文法，如 果是的话，构造预测分析表。求出预测分析表之后，再输入一个字符串， 依据 LL1 分析表单步输出字符串的分析过程。 图
13、 4-1 功能模块分解图 总控程序流程图 编译原理课程设计 4 图 4-2 控制流程图 4.24.2、设计原理、设计原理 所谓 LL （1） 分析法， 就是指从左到右扫描输入串， 同时采用最左推导， 且对每次直接推导只需向前看一个输入符号，便可确定当前所应当选择的 规则。实现 LL（1）分析的程序又称为 LL（1）分析程序或 LL1（1）分析器。 我们知道一个文法要能进行 LL（1）分析，那么这个文法应该满足：无 二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每 个非终结符的 FIRST 和 FOLLOW 集合，然后根据 FIRST 和 FOLLOW 集合构造 编译原理课程设计
14、 5 LL（1）分析表，最后利用分析表，根据 LL(1)语法分析构造一个分析器。 LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先 进先出的语法分析栈。 LL（1）预测分析程序的总控程序在任何时候都是按 STACK 栈顶符号 X 和当前的输入符号 a 做哪种过程的。对于任何（X，a），总控程序每次都 执行下述三种可能的动作之一： （）若 X = a =#，则宣布分析成功，停止分析过程。 （）若 X = a #，则把 X 从 STACK 栈顶弹出，让 a 指向下一个输 入符号。 （）若 X 是一个非终结符，则查看预测分析表 M。若 MA，a中存放 着关于 X 的一个产生式，那
15、么，首先把 X 弹出 STACK 栈顶，然后，把产生 式的右部符号串按反序一一弹出 STACK 栈（若右部符号为，则不推什么 东西进 STACK 栈）。若 MA，a中存放着“出错标志”，则调用出错诊断程 序 ERROR。 事实上，LL（1）的分析是根据文法构造的，它反映了相应文法所定义 的语言的固定特征，因此在 LL（1）分析器中，实际上是以 LL（1）分析表 代替相应方法来进行分析的。 2构造 LL(1)分析表 （1）文法 GE： EE+T | T TT*F | F F( E ) | i | x | y 我们容易看出此文法没有左公因子也没有二义性，但却存在两个直接 左递归，这里我们利用引入新
16、非终结符的方法来消除它使方法满足要求， 即： 对形如：UUx|y 的产生式（其中 x,y V+ ，y 不以 U 开头），引入一 个新的非终结符 U后，可以等价地改写成为： UyU Ux U| 编译原理课程设计 6 显然改写后，U 和 U都不是左递归的非终结符。因此文法 GE按上 述方法消去左递归后可等价地写成： ETP P+TP | TFQ Q*FQ | F( E ) | i | x | y 在构造 LL(1)预测分析表之前，首先要构造该文法的每个非终结符的 FIRST 和 FOLLOW 集合，按照下面描述的算法来构造这两个集合。 (2）计算非终结符的 First 集的算法及流程： FIRST 集合的构造算法： （1）若 XVT，则 FIRST（X）=X。 （2）若 XVN，且有产生式 Xa，则把 a 加入到 FIRST(X)中；若 X也是一条产生式，则把也加到 FIRST(X)中。 （3）若 XY是一个产
