




已阅读5页,还剩9页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
课程论文 递归下降分析器的实现递归下降分析器的实现 课程名称 所属学院 班 级 学生姓名 学 号 二零一四年十二月二零一四年十二月 目录 1 递归下降分析器的设计思想 1 1 1 自顶向下的语法分析方法 1 1 2 递归下降分析法 1 1 3 递归下降分器意义 1 1 4 递归下降分析器思想 1 1 5 递归下降分析器的作用 1 1 6 递归下降分析器的形成过程 2 2 递归向下分析器实现 2 2 2 待分析的简单词法 2 2 3 要求构造的递归下降程序 3 2 4 主函数分析 3 3 输入串运行分析 4 4 关键代码分析及运行过程 5 4 1 关键代码分析 5 4 2 文法函数调用过程 6 5 程序测试 6 5 1 当程序运行时出现如下输入程序界面 6 5 2 当程序运行时出现如下输入程序界面 7 总结 8 参考文献 8 附录 9 信息工程学院编译原理课程论文 第 1 页 共 12 页 递归下降分析器的实现 摘要摘要 本文分析了递归下降分析器的实现以及具体的功能 所谓递归下降分析法 就是对 文法中的每个非终结符编写一个函数 子程序 每个函数 子程序 的功能是识别由该非 终结符所标示的语法成分 由于描述语言的文法通常是递归定义的 因此相应的这组函数 子程序 一定是相互递归的方式进行调用 所以将此种分析方法称为递归下降分析法 关键词关键词 递归下降分析器 消除递归 非终结符 1 1 递归下降分析器的设计思想 递归下降分析器的设计思想 1 11 1 自顶向下的语法分析方法自顶向下的语法分析方法 自顶向下分析法也称面向目标的分析方法 也就是从文法的开始符号出发 企图推导出与输入的单词串完全相匹配的句子 若输入串是给定文法的句子 则必能推出 反之必然出错 自顶向下的确定分析方法需对文法有一定的限制 但由于实现方法简答 直观 便于手工构造或自动生成语法分析器 因而仍是 目前常用的方法之一 而自顶向下的不确定分析方法是带回溯的分析方法 这 种方法实际上是一种穷举的试探方法 因此效率低 代价高 因而极少使用 1 21 2 递归下降分析法递归下降分析法 递归下降分析法是确定的自上而下分析法 它要求文法是 LL 1 文法 它的 基本思想是 对文法中的每个非终结符编写一个函数或子程序 每个函数或子 程序的功能是识别由该非终结符所表示的语法成分 并且由递归下降分析法 得出了递归下降分析器 1 31 3 递归下降分器意义递归下降分器意义 递归下降分析器 可以使已经消除左递归 回溯的文法 迅速判断出输入 串是否满足该文法 并按照递归的方法 算出终结符 此分析器解决的手工计算 繁琐问题 1 41 4 递归下降分析器思想递归下降分析器思想 递归下降分析法是一种自顶向下的分析法 文法中的每一个非终结符对应 一个递归过程 函数 分析过程就是从文法开始符出发执行一组递归过程 函 信息工程学院编译原理课程论文 第 2 页 共 12 页 数 这样向下推到直到推出句子 或者是从根节点出发 自顶向下为输入串寻 找一个最左匹配序列 建立一个语法树 1 51 5 递归下降分析器的作用 递归下降分析器的作用 1 读入输入的符号串 2 对输入的符号串逐个与栈中的终结符比较 3 识别出匹配的输入字符 4 确定文法是否能推导出输入串 1 61 6 递归下降分析器的形成过程 递归下降分析器的形成过程 实现递归下降分析器 首先要消除产生式的左递归 其次要消除产生式的 回溯 得到可以编写递归下降分析器的文法如 图 1 图图 1 1 递归下降分析器形成过程递归下降分析器形成过程 2 2 递归向下分析器 递归向下分析器实现实现 2 2 待分析的简单词法待分析的简单词法 开始 输入串进 入 消除左递归 消除回溯 根据文法编写递归 下降分析器 通过递归下 降分析器确定输 入串是否正确 结束 是 否 信息工程学院编译原理课程论文 第 3 页 共 12 页 1 非终结符 E E T T F 代码中 T 用 T1 代替 代码中 E 用 E1 代替 2 终结符 i 2 3 要求构造的递归下降程序要求构造的递归下降程序 文法 G E E E T T T T F F F E i 首先 消除该文法的左递归 得到文法 G E E TE E TE T FT T FT F E i 然后 根据 LL 1 文法的判断条件 对非终结符 S 和 T 的不同产生式的集 进行考察 经验证改进后的文法已经是 LL 1 文法 最后构造递归下降分析程序 每个函数名是相应的非终结符 函数体则是根据 规则右部符号串的结构编写 非终结符在这里统称为 A 输入的字符串以 结束 1 当遇到终结符 a 时 则编写语句 If 当前读到的输入符号 a 读入下一个输入符号 2 当遇到非终结符 A 时 则编写语句调用 A 3 当遇到 A 规则时 则编写语句 If 当前读到的输入符号不属于 Follow A error 退出 4 当某个非终结符的规则有多个候选式时 按 LL 1 文法的条件能唯一地选 择一个候选式进行推导 2 4 主函数分析主函数分析 信息工程学院编译原理课程论文 第 4 页 共 12 页 此文发一共可分为个函数 分别为 E E T T F 其中在 E 函 数中可调用 T E 两个函数 在 E 函数中可以判断输出串 并调用 T E 两个函数 在 T 函数中可以调用 F T 两个函数 在 T 函数中可以判断输入串 并调用 F 和 T 两个函数 在 F 函数中可以 调用 E 函数并判断输入串 或判断输入串是否为 i 通过递归 调用实现进栈 匹配出栈 最终达到检测效果 3 3 输入串运行分析 输入串运行分析 当输入串为 i i i 时 用栈的形式表现出运行过程以 为结束 首先将 E 和分文法开始符 E 压入栈中 开始分析 首先将 和文法开始符 E 压入栈 可以从词条文法中的到终结符 并判 断终结符是否与输入串的的字符相符合 如果符合出栈 并判断在栈中的下一 个非终结符 在文法中找到对应的产生式 判断期栈顶的终结符是否与输入串 一致 一致出栈 不一致则跳出 此文法无法得到输入串 如最后栈底剩 并且输入串最后剩 此输入串符合文法 语法分析成功如 图 2 信息工程学院编译原理课程论文 第 5 页 共 12 页 图图 2 2 输入串运行分析输入串运行分析 在图中第五步执行函数 F 时 因当前扫描的字符为 所以匹配后 应执行 E 用栈模型将 E 压栈 并且 在执行完 E 后还应执行其后的判 断 与匹配 语句 这在栈的模拟中则是标出此时 E 压栈之前的位置如 图步骤 7 14 即出栈至此 14 步结束并执行这个判断 与匹配 语句 4 4 关键代码分析及运行过程 关键代码分析及运行过程 4 14 1 关键代码分析关键代码分析 void E 文法中调用 E if SIGN 0 T 并在 E 中分别调用 T E1 调用 E void E1 进入 E if SIGN 0 if s i 判断输入串是否是非终结符 如果是则出栈 readin T 并继续调用 T 函数进入文法 T 信息工程学院编译原理课程论文 第 6 页 共 12 页 E1 出 T 函数进去 E 中判断是否是 else if s i SIGN 1 readin void T if SIGN 0 F T1 4 24 2 文法函数调用过程文法函数调用过程 如 图 3 中用二叉树表示出递归下降分析器的递归过程 可得出详细的分 析过程 E E F E T F T E T T 图图 3 3 文法函数调用过程文法函数调用过程 信息工程学院编译原理课程论文 第 7 页 共 12 页 5 5 程序测试 程序测试 5 15 1 当程序运行时出现如下输入程序界面 当程序运行时出现如下输入程序界面 如 图 4 图 5 所示时匹配成功 图图 4 4 第一个输入串匹配第一个输入串匹配 图图 5 5 第二个输入串匹配第二个输入串匹配 5 25 2 当程序运行时出现如下输入程序界面 当程序运行时出现如下输入程序界面 如 图 6 所示时匹配失败 文法无法得到输入串 信息工程学院编译原理课程论文 第 8 页 共 12 页 图图 6 6 匹配失败匹配失败 总结总结 首先遇到的困难是对递归下降的分析法的不理解 虽然课上老师曾细致讲 解过但还是生疏 所以 花费大量时间重新学习递归 重点回顾了进栈 匹配 出栈等知识 让我更清楚的认识到自顶向下的语法分析并且清楚的知道了递归 向下分析器的分析法的用法 加深了 C 语言编译器的用法 并更加清楚的熟练 的运用了消除递归 和消除回溯的用法 并自己进行了消除递归 消除回溯的 计算 并运用了递归的方法实现了算法 我对语法分析有了深入的认识 并在 最后对算法进行了改进 不结束程序的情况下继续分析 其次就是课程设计报 告的书写 我也也需要很大的精力 查找资料 请教同学 强老师请求帮助 在对 word 的排版方面 有很多的细节需要认真注意 虽然已经对代码有了清楚 的认识 但在论文方面还是遇到了很多问题 比如专业术语欠缺 分析不够详 细 但是在我请教了吴刚老师后 对概念有了更加深刻的认识 自己独立完成 课程设计 熟悉程序设计中出现的所有问题以及解决方案 这无疑加深了程序 设计人员对设计的项目的印象 并重现拾起了很久不使用的 C 语言 为以后的 的课程设计和大作业打下了基础 信息工程学院编译原理课程论文 第 9 页 共 12 页 参考文献 参考文献 1 张素琴等编著 编译原理 M 清华大学出版社 2005 2 胡元义主编 编译原理教程 M 西安电子科技大学出版社 2003 3 李文生编著 编译程序设计原理与技术 M 北京邮电大学出版社 2002 4 程妍 编译原理 实验教学体系综述与改革探讨 J 福建电脑 2008 05 5 李峰 提高 编译原理 实验效果的实践 J 重庆三峡学院学报 2007 03 信息工程学院编译原理课程论文 第 10 页 共 12 页 附录 附录 include void E void T void E1 void T1 void F void readin char s 100 int i SIGN n void main n 1 while n printf 请输入一个语句 以 号结束语句 n SIGN 0 i 0 scanf s if s 0 printf 无语句输入 n continue E if s i else if s i else printf 结束语句符号不正确 n printf 是否继续输入 1 为继续 0 为推出 n scanf d printf n 信息工程学院编译原理课程论文 第 11 页 共 12 页 void E if SIGN 0 T E1 void E1 if SIGN 0 if s i readin T E1 else if s i SIGN 1 readin void T if SIGN 0 F T1 void T1 if SIGN 0
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 备品临时存放管理制度
- 公司借用人员管理制度
- 工厂加班值班管理制度
- 宿舍值班制度管理制度
- 小学艺术设备管理制度
- 小区供水供电管理制度
- 城镇污水运行管理制度
- 国企财务管理管理制度
- 医院药材储存管理制度
- 医院药品冷库管理制度
- 简易机器人课程设计报告
- MATLAB仿真课程设计-对磁盘驱动读取系统校正部分的设计
- 动作经济原则手边化POU改善
- 农村公路基础设施统计调查制度
- (完整版)(excel版)工信部通信2016451号定额-修正版
- 医学的社会文化史学习通超星课后章节答案期末考试题库2023年
- 土壤学-土壤分类和调查课件
- 华为公司质量管理手册
- 妇科护理查房教学课件
- 枣庄学院教师招聘考试历年真题
- 日本玩全攻略(图文全彩版)
评论
0/150
提交评论