FirstVT集和LastVT集生成算法模拟

课程设计 论文 任务书 软软 件件 学学 院院 学 院 软件工程软件工程 专 业 3 班 一 课程设计 论文 题目 FirstVTFirstVT 集和集和 LastVTLastVT 集生成算法模拟集生成算法模拟 二 课程设计 论文 工作自 20132013 年 6 6 月 1717 日起至 20132013 年 6 6 月 2121 日止 三 课程设计 论文 地点 软软 件件 学学 院院 实实 训训 中中 心心 四 课程设计 论文 内容要求 1 本课程设计的目的 本课程设计的目的 进一步培养学生编译器设计的思想 加深对编译原理和应用程序的理解 针对编 译过程的重点和难点内容进行编程 独立完成有一定工作量的程序设计任务 同时 强调好的程序设计风格 并综合使用程序设计语言 数据结构和编译原理的知识 熟 悉使用开发工具 VC JAVA C NET 2 课程设计的任务及要求 课程设计的任务及要求 1 课程设计任务 课程设计任务 设计一个由正规文法生成设计一个由正规文法生成 FirstVT 集和集和 LastVT 集的算法动态模拟集的算法动态模拟 2 创新要求 创新要求 3 课程设计论文编写要求 课程设计论文编写要求 1 课程设计任务及要求 2 设计思路 工作原理 功能规划 3 详细设计 数据分析 算法思路 功能实现 含程序流程图 主要代码及注 释 界面等 4 运行调试与分析讨论 给出运行屏幕截图 分析运行结果 有何改进想法等 5 设计体会与小结 设计遇到的问题及解决办法 通过设计学到了哪些新知识 巩固了哪些知识 有哪些提高 6 报告按规定排版打印 要求装订平整 否则要求返工 7 课设报告的装订顺序如下 封面 任务书 中文摘要 目录 正文 附录 代码及相关图片 编译原理课程设计 第 2 页 8 严禁抄袭 如有发现 按不及格处理 4 课程设计评分标准 课程设计评分标准 1 学习态度 20 分 2 系统设计 20 分 3 编程调试 20 分 4 回答问题 20 分 5 论文撰写 20 分 5 参考文献 参考文献 1 张素琴 吕映芝 编译原理 M 清华大学出版社 2 蒋立源 康慕宁等 编译原理 第 2 版 M 西安 西北工业大学出版社 6 课程设计进度安排 课程设计进度安排 1 准备阶段 4 学时 选择设计题目 了解设计目的要求 查阅相关资料 2 程序模块设计分析阶段 4 学时 程序总体设计 详细设计 3 代码编写调试阶段 8 学时 程序模块代码编写 调试 测试 4 撰写论文阶段 4 学时 总结课程设计任务和设计内容 撰写课程设计论文 学生签名 2013 年 6 月 21 日 课程设计课程设计 论文论文 评审意见评审意见 1 学习态度 20 分 优 良 中 一般 差 2 系统设计 20 分 优 良 中 一般 差 3 编程调试 20 分 优 良 中 一般 差 4 回答问题 20 分 优 良 中 一般 差 5 论文撰写 20 分 优 良 中 一般 差 评阅人 职称 副教授 2013 年 6 月 日 司房昭 FirstVT 集和 LastVT 集生成算法模拟 第 3 页 中文摘要中文摘要 随着计算机科学的飞速发展 形式语言与自动机理论和方法的研究也越 来越受到人们的重视 但前者已经成为计算机科学的理论基础 本课程设计 主要研究自动机在编译方面的应用 并将讨论重点放在算符优先分析法上 并用此理论完成算数表达式的正确与否的判断 根据算符优先分析算法 编写一个语法程序 程序具有通用性 即编制 的语法缝隙程序能够适用于不同文法以及各种输入的单词串 基本思想描述 语法分析前首先要对输入的文法和句子进行词法分析 去除多余的自负 并 将产生式和终结符 非终结符填入有关数组 为语法分析做前期准备 算符 优先分析算法的核心算法教材上已给出 因此所要做的事只是将其变成实现 计算非终结符的 FIRSTVT 集和 LASTVT 集是构造算符优先分析表的基础 而算 符优先分析表的构造又是算符优先分析算法的基础 因此 本程序的实现可以说是算 符优先分析算法实现的基础 编译原理课程设计 第 4 页 目 录 一 课程设计任务及要求 1 二 需求分析 2 三 设计思路 3 四 详细设计 4 五 运行调试与分析讨论 5 六 设计体会与小结 6 七 参考文献 7 司房昭 FirstVT 集和 LastVT 集生成算法模拟 第 5 页 一 课程设计任务及要求 课设目的课设目的 进一步培养学生编译器设计的思想 加深对编译原理和应用程序的理 解 针对编译过程的重点和难点内容进行编程 独立完成有一定工作量的 程序设计任务 同时强调好的程序设计风格 并综合使用程序设计语言 数据结构和编译原理的知识 熟悉使用开发工具 VC JAVA C NET 总体要求总体要求 1 思想的正确性 采用合适的数据存储结构等 2 程序实现的正确性 程序整体结构合理 编程风格规范等 3 程序功能的完善程度 包括功能的基本实现 基本完善 完全实现 4 工作认真 独立完成课设 基本要求基本要求 设计一个由正规文法生成 FirstVT 集和 LastVT 集的算法动态模拟 实 现以下功能输入一个文法 G 1 输出由文法 G 构造 FIRSTVT 集的算法 2 输出 FirstVT 集 3 输出由文法 G 构造 LastVT 集的算法 4 输出 LastVT 集 具体步骤具体步骤 1 问题理解和分析 充分地分析和理解问题本身 弄清要求做什么 2 确定解决问题的方法 设计 主要是找到解决问题的主要思路 是怎么做 在此阶段可考虑系 统的功能和模块划分等 3 详细设计和编码 确定算法的主要流程 再进行编程 在此阶段应提醒学生程序可 先在纸上写 尽量想清楚了再动手上机 在编程过程中注意程序结构的 清晰性 避免出现很多明显的程序逻辑错误和语法错误 提高后面程序 调试效率 编译原理课程设计 第 6 页 4 程序调试和运行 使学生掌握程序调试和排错的基本方法 增加编程的感觉和解决问 题的成就感 5 完成课程设计报告 使用华东交通大学课程设计报告 需学生自己购买 司房昭 FirstVT 集和 LastVT 集生成算法模拟 第 7 页 二 需求分析 本课程设计的题目为 FirstVT 集和 LastVT 集生成算法模拟 它是算 符优先分析算法中判断三种优先关系的关键 算符优先分析算法是自底向 上分析方法的一种 所谓自底向上分析 也称移近 规约分析 粗略地 说它的实现思想是对输入符号串自左向右进行扫描 并将输入符逐个移入 一个后进先出的栈中 边移进边分析 一旦栈顶符号串形成某个句型的句 柄或可规约串 就用该产生式的左部非终结符代替相应右部的文法符号串 这称为一部规约 重复这一过程直到规约到栈中只剩文法的开始符号则为 分析成功 也就确认输入串是该文法的句子 而算符优先分析算法的基本 思想只是规定算符之间的优先关系 也就是只考虑终结符之间的优先关系 本课程设计的要求只是构造 FirstVT 集和 LastVT 集 在此基础上扩充 建造算符优先关系表 编译原理课程设计 第 8 页 三 设计思路 3 1 基本算法基本算法 构造集合 FIRSTVT P 的算法 按 FIRSTVT P 的定义 可以用如下两条归则来构造 1 若有产生式 P a 或 Qa 则 a FIRSTVT P 2 若 a FIRSTVT Q 且有产生式 P Q 则 a FIRSTVT P 构造算法 建立一个二维布尔数组 F P a 使得 F P a 为真的条件适当且仅当 a FIRSTVT P 构造算法 再用一个栈 STACK 把所有初值为真的数组元素 F P a 的符号对 P a 全都放到栈中 算法如下 1 将布尔矩阵各元素置假 栈置空 2 按照归则 1 查看产生式 对于 P a 或 P Qa 置相应 F P a 为 真 符号对 P a 入栈 3 按规则 2 对栈施加如下操作 弹出栈定符号对记作 Q a 查看所 有产生式是否有形如 P Q 产生式 若有 且 a FIRSTVT P 则将 F P a 置为真 并把 P a 入栈 4 重复 3 直到栈空为止 用类似的方法来构造 LASTVT P 可根据 LASTVT P 的定义来构造 两条规则 1 若有产生式 P a 或 aQ 则 a LASTVT P 2 若 a LASTVT P 且有产生式 P Q 则 a LASTVT P 构造算法同 FIRSTVT P 的构造算法 3 2 定义数据结构定义数据结构 在程序中 用两个字符数组 vn M 和 vt N 分别用来存储所有的非终结 字符集与终结字符集 为了记录非终结符的 FIRSTVT 集和 LASTVT 集 为此建立两个布尔数组 F M N 和 L M N 分别记录非终结符的 司房昭 FirstVT 集和 LastVT 集生成算法模拟 第 9 页 FIRSTVT 集和 LASTVT 集 比如 F i j true 表示 vt j 属于 FIRSTVT vn i L i j true 表示 vt j 属于 LASTVT vn i 值为 false 表 示相应的终结符不属于非终结符的 FIRSTVT 集和 LASTVT 集 为了简便起见 程序中又构造了两个两维布尔数组 first M M N 和 last M M N 来表示推导关系 数组第一维的 M 个字符代表非终结符 数 组第二维的前 M 个字符代表非终结符 后 N 个字符代表终结符 以 first 数组为例 fist i M j 代表非终结符 vn i P 与非终结符 vt j a 有推导关系 P a fist i j 代表非终结符 vn i P 与非终结符 vt j Q 有推导关系或 P Qa 相关的数据结构定义如下 char vn M vt N 非终结字符与终结字符数组 bool first M M N last M M N 以布尔数组形式定义推导关系 char vn M vt N 非终结字符与终结字符数组 int stp 堆栈栈顶指针 符号栈的数据结构 struct relation 结构体用来说明终结符 vt 与非终结符 vn 之间的关 系 若关系存在说明 vt 属于 FIRSTVT vn 或 LASTVT vn int vn int vt 编译原理课程设计 第 10 页 四 详细设计 存储 firstvt 4 个 case 对 FIRSTVT 进行存储 void setFIRSTVT char X int T int i int t 0 switch T case 0 for i 0 i N i if X FIRSTVT0 i break else if FIRSTVT0 i 0 t i break FIRSTVT0 t X break case 1 for i 0 i N i if X FIRSTVT1 i break else if FIRSTVT1 i 0 t i break FIRSTVT1 t X break case 2 for i 0 i N i 司房昭 FirstVT 集和 LastVT 集生成算法模拟 第 11 页 if X FIRSTVT2 i break else if FIRSTVT2 i 0 t i break FIRSTVT2 t X break case 3 for i 0 i N i if X FIRSTVT3 i break else if FIRSTVT3 i 0 t i break FIRSTVT3 t X break case 4 for i 0 i N i if X FIRSTVT4 i break else if FIRSTVT4 i 0 t i break FIRSTVT4 t X 编译原理课程设计 第 12 页 break default break 判定 firstvt void FIRSTVT char X int S int i j 0 k int T 0 X position int L 0 X offspring length int t 1 char C N for i 0 i N i if INPUT i 0 X T i break for i 4 i N i if INPUT T i INPUT T i n t 1 printf c C 0 L j j 0 for k 0 k 97 else if INPUT T i j if INPUT T i n break 对于 LASTVT 也是类似的存储和判定 编译原理课程设计 第 14 页 五 运行调试与分析讨论 测试数据采用编译原理 P110 例 6 3 进行测试 实验数据 S E E E T T T T F F F P F P P E i 上截图中 FirstVT 集或 LastVT 中的关系矩阵中的 1 表示相对应的 终结字符属于对应的终结字符的 FirstVT 集或 LastVT 集 我们从上面两个 步骤可得得到用程序运算的结果和我分析得到的 FirstVT 集和 LastVT 集相 符合 司房昭 FirstVT 集和 LastVT 集生成算法模拟 第 15 页 六 设计体会与小结 经过一个星期的编译原理课程设计的实践 我重新复习了自底向上的 分析方法 其中重点复习了算符优先分析算法 对词法 文法的判断有了 较深刻的认识 对算符优先分析算法的 FirstVT 集和 LastVT 集的构造有了 更加深刻的认识 对其中数据的流向和数据的输出操作有了很清晰的认识 对数据在该课程设计中的存储和运算有了深刻的理解 本程序还有很多缺陷 为了简化问题 本程序分析的是一个特定文法 限制了程序的推广 如果只是为了分析特定文法的算符优先算法构造程序 非终结符的 FIRSTVT