《编译原理》课程设计--生成LR分析表的算法实现.DOC

学 号： 课 程 设 计 题 目 生成LR分析表的算法实现 学 院 计算机科学与技术学院 专 业 软件工程 班 级 姓 名 指导教师 2011 年 12 月 30 日 课程设计任务书 学生姓名： 专业班级： 软件0903班 指导教师： 工作单位： 计算机学院 题 目: 生成LR分析表的算法实现 初始条件： 程序设计语言:主要使用C语言的开发工具，或者采用LEX、YACC等工具，也可利用其他熟悉的开发工具。算法：可以根据《编译原理》课程所讲授的算法进行设计。 要求完成的主要任务: （包括课程设计工作量及其技术要求，说明书撰写等具体要求） 明确课程设计的目的和重要性，认真领会课程设计的题目，读懂课程设计指导书的要求，学会设计的基本方法与步骤，学会如何运用前修知识与收集、归纳相关资料解决具体问题的方法严格要求自己，要独立思考，按时独立完成课程设计任务。，构造项目集规范族，最后输出文法的分析表。 进行总体设计，详细设计：包括算法的设计和数据结构设计。系统实施、调试，合理使用出错处理程序。 设计报告：要求层次清楚、整洁规范、不得相互抄袭。正文字数不少于0.3万字。包含内容： ①课程设计的题目。 ②目录。 ③正文：包括引言、需求分析、总体设计及开发工具的选择，设计原则（给出语法分析方法及中间代码形式的描述、文法和属性文法的设计），数据结构与模块说明（功能与流程图）、详细的算法设计、软件调试、软件的测试方法和结果、有关技术的讨论、收获与体会等。 ④结束语。 ⑤参考文献。 ⑥附录：软件清单（或者附盘）。 时间安排： 消化资料、系统调查、形式描述 1天 系统分析、总体设计、实施计划 3天 撰写课程设计报告书 1天 指导教师签名： 2011年 12月 30日 系主任（或责任教师）签名： 2011年 12月 30日 1、 引言 1 2、 系统概述 2 2.1 目的 2 2.2 设计任务 2 2.3 设计环境与工具 2 3、总体设计 3 3.1 设计原理 3 3.1.1 识别文法活前缀的及的状态图 3 3.1.2 项目集规范族的构造 4 3.1.2 分析表的构造 4 3.2 简要的分析与概要设计 5 4、详细的算法描述 7 4.1模块说明 7 4.2 程序具体设计 8 5、测试方法和测试结果 9 6 个人总结 12 生成LR分析表的算法实现 引言 作为计算机专业的一门重要的专业课程，《编译原理》旨在介绍编译程序构造的一般原理和基本方法 。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。 项目集族，并且在此基础上进一步构造其分析表。希望通过设计、编制、调试一个 语法分析程序，加深对语法及语义分析程序的理解，加深对编译原理的理解，培养自己动手能力。 通过实现输入一个给定的文法生成分析表，从而实现语言的语法分析，也为后面的语义分析做基础。 2.2 设计任务 利用语法分析中LR分析法的原理和思想对给定的文法进行分析，识别出文法活前缀的，构造项目集规范族，最后输出文法的分析表。 2.3 设计环境与工具 程序开发环境：Eclipse 程序设计语言：java 3、总体设计 3.1 设计原理 总的来说，分析表构造的主要问题如下： 识别文法活前缀的及的状态图 项目集规范族的构造； 分析表的构造； 它们的主要设计原理如下： 3.1.1 识别文法活前缀的及的状态图 活前缀 如果一个规范句型的前缀中不含句柄后的任何符号，则称它是该规范句型的一个活前缀。换句话说，活前缀是一个或若干个规范句型的前缀，在规范归约过程中的任何时刻只要已分析过的部分即在符号栈中的符号串均为规范句型的活前缀，则表明输入串已被分析过的部分是该文法某规范句型的一个正确部分。 项目 为了构造活前缀的，我们首先需要构造文法的项目级。在文法的每个文法的右部适当位置添加一个圆点构成项目。对于文法中的每个产生式的项目集的大小是由其产生式的长度决定的，长度是其右部符号的长度加1。例如产生式：A→aBC，有4个LR(0)项目： 活前缀的DFA 一般构造识别活前缀的NFA的两种方法： 第一种方法是求出文法的所有产生式的LR(0)项目，每个项目都为NFA的一个状态，按一定规则构造识别活前缀的NFA，再确定化为DFA。 第二种方法是把拓广文法的第一个项目{S′→ ? S}作为初态集的核，通过求核的闭包和转换函数，求出LR(0)项目集规范族，再由转换函数建立状态之间的连接关系得到识别活前缀的DFA。 在此，我采用的是第二种方式求的状态图。 3.1.2