编译原理大作业

课程论文 递归下降分析器的实现递归下降分析器的实现 课程名称 所属学院 班 级 学生姓名 学 号 二零一四年十二月二零一四年十二月 目录 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