简单优先析法编译原理课程设计.docVIP

学 号： 课 程 设 计 题 目 简单优先分析程序的设计 学 院 计算机科学与技术学院 专 业 软件工程专业 班 级 软件工程1002班 姓 名 指导教师 何九周 2013 年 1 月 12 日 课程设计任务书 学生姓名： 专业班级： 软件工程1002班 指导教师： 何九周 工作单位： 计算机科学与技术学院 题 目:简单优先分析程序的设计 初始条件： 程序设计语言:主要使用C语言的开发工具，或者采用LEX、YACC等工具，也可利用其他熟悉的开发工具。算法：可以根据《编译原理》课程所讲授的算法进行设计。 要求完成的主要任务:（包括课程设计工作量及其技术要求，说明书撰写等具体要求） 1.明确课程设计的目的和重要性，认真领会课程设计的题目，读懂课程设计指导书的要求，学会设计的基本方法与步骤，学会如何运用前修知识与收集、归纳相关资料解决具体问题的方法严格要求自己，要独立思考，按时独立完成课程设计任务。 1天 系统分析、总体设计、实施计划 3天 撰写课程设计报告书 1天 指导教师签名： 2013年 1月 12日 系主任（或责任教师）签名： 2013年 1月 12日 目录 1 引言 - 3 - 2 需求分析 - 3 - 3 总体设计 - 3 - 3.1 简单优先关系的定义 - 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 - 10 结束语 - 14 - 11 参考文献 - 15 - 12 附录 - 15 - 简单优先分析程序的设计 引言 上下文无关文法是形式语言理论中一种重要的变换文法，用来描述上下文无关语言，在乔姆斯基分层中称为2型文法。由于程序设计语言的语法基本上都是上下文无关文法，因此应用十分广泛。简单优先分析法是预先在文法的各种符号 (终结符号和非终结符号)之间建立所谓优先关系，而在分析一个句型 (指规范句型，下同)时，从左到右依次扫视其中的符号，且每扫视一个符号都检查它和后继符号间的优先关系，以期找到句柄之尾，然后再从此尾符号处回头，进行反向扫描，且每扫视一个符号都检查它和其前的符号间的优先关系，直到找到句柄之头为止。设G=(VN，VT,P,S)是一已化简的文法，V=VN∪VT，并设Si和Sj是V中的任意两个符号，若G中存在这样的规范句型 　　α=…SiSj… 　　则此相邻的两个符号Si，Sj和α的句柄之间的关系必然是下述情况之一： 　　(1) 若Si在句柄中，而Sj不在句柄中 (如图42(a)所示)，则Si显然为句柄的尾符号，故G中必有形如A→…Si的产生式，使Si先于Sj被归约。此时，我们就说符号Si优于Sj，且记为Si· Sj。此外，由于Sj出现在规范句型的句柄之右，故可知Sj必为终结符号。 　　(2) 若Si与Sj同时处于α的句柄之中 (如图42(b)所示)，则G中必有形如A→…SiSj…的产生式，使Si和Sj同时被归约。此时，我们就说Si和Sj有相同的优先关系，且记为Si=·Sj。 　　(3) 若Sj在句柄中，而Si不在句柄之中 (如图42(c)所示)，则Sj显然为句柄的头符号，故G中必有形如A→Sj…的产生式，使Sj先于Si被归约。此时就Si和Sj的优先关系而言，我们说Si低于Sj且记为Si·Sj。 (4) 若Si和Sj均不在句型α的句柄之中，由于Si和Sj已相邻地在α中出现，则必有G的另一规范句型β，使Si和Sj在β中相邻地出现，且与β的句柄的关系有上述三种情况之一。然而，也可能有这样的情况，对G中的某些符号序偶(Sr,St)而言，G中并不存在任何使Sr和St相邻出现的句型，此时我们就说Sr和St间不存在任何优先关系。读入一“＃”为止。此时识别正确。可分点描述如下: （1）、对句型中相邻的文法符号规定优先关系，以寻找句型中的句柄; （2）、规定句柄内各相邻符号之间具有相同的优先级; （3）、规定句柄两端符号优先级要比位于句柄之外而又和句柄相邻的符号的优先级高，以先归约句柄; （4）、对于文法中所有