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

学 号： 0121210680121课 程 设 计题 目简单优先分析程序的设计学 院计算机科学与技术学院专 业软件工程班 级软件工程1201班姓 名范维指导教师何九周2014年12月26日课程设计任务书学生姓名： 范维 专业班级： 软件1201班 指导教师： 何九周 工作单位：计算机科学与技术学院题 目: 初始条件：程序设计语言:主要使用C语言的开发工具，或者采用LEX、YACC等工具，也可利用其他熟悉的开发工具。算法：可以根据编译原理课程所讲授的算法进行设计。要求完成的主要任务: （包括课程设计工作量及其技术要求，说明书撰写等具体要求）1. 明确课程设计的目的和重要性，认真领会课程设计的题目，读懂课程设计指导书的要求，学会设计的基本方法与步骤，学会如何运用前修知识与收集、归纳相关资料解决具体问题的方法。严格要求自己，要独立思考，按时、独立完成课程设计任务。2.主要功能包括：对教材P104中的上下文无关文法，实现它的简单优先分析程序，给出符号串b(aa)b的分析过程。（参考教材P103106）3.进行总体设计，详细设计：包括算法的设计和数据结构设计。系统实施、调试，合理使用出错处理程序。4.设计报告：要求层次清楚、整洁规范、不得相互抄袭。正文字数不少于0.3万字。包含内容：课程设计的题目。目录。正文：包括引言、需求分析、总体设计及开发工具的选择，设计原则（给出语法分析方法及中间代码形式的描述、文法和属性文法的设计），数据结构与模块说明（功能与流程图）、详细的算法设计、软件调试、软件的测试方法和结果、有关技术的讨论、收获与体会等。结束语。参考文献。附录：软件清单（或者附盘）。时间安排：消化资料、系统调查、形式描述1天系统分析、总体设计、实施计划3天撰写课程设计报告书1天指导教师签名： 2014年 12月 26日系主任（或责任教师）签名： 2014年 12月 26日 目录1 引言12 需求分析13 总体设计23.1 简单优先关系的定义23.2 简单优先分析法流程图33.3 简单优先关系矩阵流程图43.4 分析器构造54 开发工具的选择65 详细的算法设计65.1用二维数组存取优先级矩阵65.2字符串移进规约分析75.3简单优先关系矩阵输出算法75.4移近-规约算法85.5字符串优先关系判断106 软件调试117 软件的测试方法和结果128 收获与体会139 结束语1310 参考文献14本科生课程设计成绩评定表15武汉理工大学编译原理课程设计说明书简单优先分析程序的设计1 引言简单优先分析法是预先在文法的各种符号 (终结符号和非终结符号)之间建立所谓优先关系，而在分析一个句型 (指规范句型，下同)时，从左到右依次扫视其中的符号，且每扫视一个符号都检查它和后继符号间的优先关系，以期找到句柄之尾，然后再从此尾符号处回头，进行反向扫描，且每扫视一个符号都检查它和其前的符号间的优先关系，直到找到句柄之头为止。本文将采用简单优先分析法对一个上下文无关文法进行分析，给出文法的简单关系优先矩阵，并对测试用例进行分析。2 需求分析对教材P104中的上下文无关文法，实现它的简单优先分析程序，给出符号串b(aa)b的分析过程。（参考教材P103106）上下文无关文法GS：S:=bAbA:=(B|aB:=Aa)测试字符串：b(aa)b3 总体设计本文采用简单优先分析法实现指定上下文无关文法的分析程序，对于任意字符串给出其分析过程。然后判断正确，正确显示分析成功，错误显示分析失败。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先于Sj被归约。此时，我们就说符号Si优于Sj，且记为Si Sj。此外，由于Sj出现在规范句型的句柄之右，故可知Sj必为终结符号。 (2) 若Si与Sj同时处于的句柄之中 (如图42(b)所示)，则G中必有形如ASiSj的产生式，使Si和Sj同时被归约。此时，我们就说Si和Sj有相同的优先关系，且记为Si=Sj。 (3) 若Sj在句柄中，而Si不在句柄之中 (如图42(c)所示)，则Sj显然为句柄的头符号，故G中必有形如ASj的产生式，使Sj先于Si被归约。此时就Si和Sj的优先关系而言，我们说Si低于Sj且记为SiSj。 (4) 若Si和Sj均不在句型的句柄之中，由于Si和Sj已相邻地在中出现，则必有G的另一规范句型，使Si和Sj在中相邻地出现，且与的句柄的关系有上述三种情况之一。然而，也可能有这样的情况，对G中的某些符号序偶(Sr,St)而言，G中并不存在任何使Sr和St相邻出现的句型，此时我们就说Sr和St间不存在任何优先关系。3.2 简单优先分析法流程图S1-#,i,jTRj?K-iSk-1sk?a=SkSK+1Sia是句柄，用它来查产生式表a与一产生式右部相同？Si=#且TRj=#？errori-k Si-U U是该产生式左部符号K-k-1errori-i+1Si-TRijj+1YNYNYYNYNN3.3 简单优先关系矩阵流程图输入欲分析文法判定是否是简单优先文法分析等于关系分析小于关系分析大于关系构造矩阵关系表NY3.4 分析器构造分析栈 输入流 ST语法分析程序优先关系矩阵产生式表4 开发工具的选择开发环境：eclipse 开发语言：Java5 详细的算法设计5.1用二维数组存取优先级矩阵static for(int i=0;itoken.length;i+)map.put(tokeni, i);for(int i=0;itoken.length;i+)for(int j=0;j;relation12=;relation13=;relation15=;relation21=;relation25=;relation32=;relation33=;relation34=;relation35=;relation45=;relation51=;relation55=;relation56=;relation61=;relation65=;relation70=;relation71=;relation77=;5.2字符串移进规约分析while(!s.isEmpty()char pre = s.pop();if(compare(pre,ci)/移进s.push(pre);s.push(ci);System.out.println(移进+ci);else/规约s.push(pre);System.out.println(规约);i-;statute();i+;5.3简单优先关系矩阵输出算法for(int i=1;i9;i+)a0i=tokeni-1; for(int j=1;j9;j+) aj0=tokenj-1; for(int i=1;i9;i+) for(int j=1;j9;j+) aij=relationi-1j-1; for(int i=0;i9;i+) for(int j=0;j)return false;if(rel=|rel=)return true;return false;6 软件调试使用eclipse对程序进行调试7 软件的测试方法和结果1.程序界面:2.给定测试字符串:b(aa)b#3.测试任意字符串:bababa8 收获与体会 通过本次课程设计，我学会了将理论知识运用到实际编码中，同时也知道严谨细心对于一个程序员来说有多么重要。这次课程设计在让我对编译原理更加熟悉的同时也训练了我的耐心和毅力。虽然程序写得很一般，有的地方甚至有些小错误，但是我仍然收获了很多平时学习中没有学到的知识，锻炼了平时学习中没有的学习和实践能力。9 结束语 本次课程设计可以说是对编译原理课程本学期所学内容的一次综合应用，虽然称不上一个完整的编译程序，但已经展现了一个完整编译程序的雏形。通过本次课程设计，不仅进一步熟悉了编译程序所涉及的各方面知识，更掌握了一个编译程序的整体架构方式以及编译程序构造的整体流程。并且，从中认识到，编译程序模块化(词法分析、语法分析、语义分析等)的重要，更是程序设计模块化的重要。但，在其过程中也暴漏了自身知识的匮乏，包括，编译原理知识学习不扎实，不能很好的运用；编程语言运用不熟练，导致频繁因查找编程语言语法知识耗费大量时间等等。但总的来说，本次编程还是收获不少，不仅仅是实现了课程设计所要求的内容，更为以后深入的学习（包括课程相关与不相关）打下了坚实的基础。10 参考文献1编译原理（第二版） 主编：张素琴 吕映芝 出版社：清华大学出版社2数据结构（C语言版） 主编：严蔚敏 吴伟民 出版社：清华大学出版社3Java语言程序设计主编：吕凤翥 马皓 出版社：清华大学出版社15本科生课程设计成绩评定表班级：软件1201班