1、学学 号：号： 课课 程程 设设 计计 题题 目目 简单优先分析程序的设计 学学 院院 计算机科学与技术学院 专专 业业 软件工程专业 班班 级级 软件工程 1002 班 姓姓 名名 指导教师指导教师 2013 年 1 月 12 日 - 1 - 课程设计任务书课程设计任务书 题题 目目: :简单优先分析程序的设计简单优先分析程序的设计 初始条件：初始条件： 程序设计语言:主要使用 C 语言的开发工具，或者采用 LEX、YACC 等工具，也可利用其 他熟悉的开发工具。算法：可以根据编译原理课程所讲授的算法进行设计。 要求完成的主要任务要求完成的主要任务: :（包括课程设计工作量及其技术要求， 说
2、明书撰写等具体要求） 1.明确课程设计的目的和重要性，认真领会课程设计的题目，读懂课程设计指导书的要求， 学会设计的基本方法与步骤， 学会如何运用前修知识与收集、 归纳相关资料解决具体问题的 方法。严格要求自己，要独立思考，按时按时、独立独立完成课程设计任务。 2. 主要功能包括：对教材 P104 中的上下文无关文法，实现它的简单优先分析程序，给出符 号串 b(aa)b 的分析过程。 （参考教材 P103106） 3.进行总体设计，详细设计：包括算法的设计和数据结构设计。系统实施、调试，合理使用 出错处理程序。 4. 设计报告：要求层次清楚、整洁规范、不得相互抄袭。正文字数不少于 0.3 万字
3、。包含 内容： 课程设计的题目。 目录。 正文：包括引言、需求分析、总体设计及开发工具的选择，设计原则（给出语法分析方 法及中间代码形式的描述、文法和属性文法的设计） ，数据结构与模块说明（功能与流程图） 、详 细的算法设计、软件调试、软件的测试方法和结果、有关技术的讨论、收获与体会等。 结束语。 参考文献。 附录：软件清单（或者附盘） 。 时间安排：时间安排： 消化资料、系统调查、形式描述 1 天 系统分析、总体设计、实施计划 3 天 撰写课程设计报告书 1 天 - 2 - 目录目录 1 引言.- 3 - 2 需求分析.- 3 - 3 总体设计.- 3 - 3.1 简单优先关系的定义. -
4、4 - 3.2 简单优先分析法的基本思想 - 4 - 3.3 简单优先关系矩阵流程图 - 5 - 3.4 简单优先分析法流程图 . - 6 - 3.5 分析器构造. - 7 - 4 开发工具的选择.- 7 - 5 详细的算法设计.- 7 - 5.1 简单优先关系矩阵输出算法 - 7 - 5.2 字符串读入. - 8 - 5.3 字符串分析算法 - 8 - 5.4 优先关系判断算法 - 9 - 5.5 移近-规约算法 - 9 - 5.6 分析结果判断 - 11 - 6 软件调试.- 11 - 7 软件的测试方法和结果.- 12 - 8 有关技术的讨论.- 13 - 9 收获与体会.- 14 -
5、10 结束语.- 14 - 11 参考文献- 15 - 12 附录- 15 - - 3 - 简单优先分析程序的设计简单优先分析程序的设计 1 引言 上下文无关文法是形式语言理论中一种重要的变换文法，用来描述上下文无关语 言，在乔姆斯基分层中称为 2 型文法。由于程序设计语言的语法基本上都是上下文无 关文法，因此应用十分广泛。 简单优先分析法是预先在文法的各种符号 (终结符号和非终结符号)之间建立所 谓优先关系，而在分析一个句型 (指规范句型，下同)时，从左到右依次扫视其中的 符号，且每扫视一个符号都检查它和后继符号间的优先关系，以期找到句柄之尾，然 后再从此尾符号处回头，进行反向扫描，且每扫视
6、一个符号都检查它和其前的符号间 的优先关系，直到找到句柄之头为止。 本文将采用简单优先分析法对一个上下文无关文法进行分析，给出文法的简单关 系优先矩阵，并对测试用例进行分析。 2 需求分析 本课程设计的目的是为了实现给定上下文无关文法的简单优先分析程序，并给出 字符串的分析过程。 上下文无关文法 GS： S:=bAb A:=(B|a B:=Aa) 测试字符串：b(aa)b 3 总体设计 本文采用简单优先分析法实现指定上下文无关文法的分析程序，对于任意字符串 - 4 - 给出其分析过程。 3.1 简单优先关系的定义 设 G=(VN，VT,P,S)是一已化简的文法，V=VNVT，并设 Si 和 Sj 是 V 中的 任意两个符号，若 G 中存在这样的规范句型 =SiSj 则此相邻的两个符号 Si，Sj 和 的句柄之间的关系必然是下述情况之一： (1) 若 Si 在句柄中，而 Sj 不在句柄中 (如图 42(a)所示)，则 Si 显然为句 柄的尾符号，故 G 中必有形如 ASi 的产生式，使 Si 先于 S
