逆波兰式的生成.doc

淮阴工学院 编译原理课程设计报告 选题名称: 逆波兰式的生成设计任务书 课题 名称 逆波兰式的生成 设计 目的 通过一周的课程设计，对逆波兰式的生成有深刻的理解实现对输入合法的中缀表达式进行词法分析、语法分析，构造相应的逆波兰式，计算逆波兰式的值输出结果。达到了巩固理论知识、锻炼实践能力的目的。 实验环境 Windows2000以上操作系统，Visual C++6.0以上编译环境 任务要求 1.对算术表达式进行词法、语法、逆波兰式的分析； 2.编写代码，实现逆波兰式的生成； 3.撰写课程设计报告； 4.参加答辩。 工作进度计划 序号 起止日期 工 作 内 容 1 201.06.20～201.06.20 理论辅导，搜集资料 2 201.21～201.06.22 编写代码，上机调试 3 201.06.22～201.06.23 撰写课程设计报告 2011.06.24~2011.06.25 答辩，完善报告 指导教师（签章）： 年 月 日 摘要： 编译原理旨在介绍构造的一般原理和基本方法。内容包括语言和、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。是计算机科学与技术专业最重要的一门专业基础课程，内容庞大，涉及面广，知识点多。这次课程设计的主要任务是编程实现对输入合法的中缀表达式进行词法分析、语法分析，构造相应的逆波兰式，计算逆波兰式的值输出结果。逆波兰式也叫后缀表达式，是为了纪念波兰数学家鲁卡谢维奇（Jan Lukasiewicz）而命名的比如中缀表达式：，其后缀表达式为：。后缀表达式的优点是显而易见的，编译器在处理时候按照从左至右的顺序读取逆波兰表达式，遇到运算对象直接压入堆栈，遇到运算符就从堆栈提取后进的两个对象进行计算，这个过程正好符合了计算机计算的原理。 关键：编译原理 1 课题综述 1 1.1 课题来源 1 1.2 课题意义 1 1.3 预期目标 1 1.4 所面对的问题 2 1.5 所需解决的关键技术 2 2 系统分析 2 2.1 基础知识 2 2.2 解决问题的基本思路 3 2.3 总体方案 3 3 系统设计 4 3.1 算法实现 4 3.2实验设计思想及算法 5 4 文法 6 5代码编写 6 6 程序调试 11 7 运行与测试 11 总 结 13 致 谢 14 参考文献 15 1 课题综述 编译原理这门课在理论、技术、方法上都对学生提供了系统而有效的训练，有利于提高软件人员的素质和能力对中缀表达式的计值，并非按运算符出现的自然顺序来执行其中的各个运算，而是根据算符间的优先关系来确定运算的次序，此外，还应顾及括号规则。逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。 1.2 课题意义 中缀表达式是一个通用的算术或逻辑公式表示方法，操作符是以中缀形式处于操作数的中间（例： + 2），中缀表达式是人们常用的算术表示方法。与式相比，中缀表达式不容易被电脑解析因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。 1.3 预期目标 。锻炼编写程序、调试程序的能力， 1.4 所面对的问题 对输入的表达式进行词法分析、语法分析及得出正确的逆波兰式，根据逆波兰式得出表达式的结果。通过递归下降方法分析表达式，并且输出词法分析、语法分析过程及结果。实现把中缀表达式转换成后缀表达式，并计算表达式的结果。 1.5 所需解决的关键技术 本次课程设计中的关键是：通过递归下降方法分析表达式，主要有词法分析和语法分析，输出分析结果，判断表达式是否合法。如何确定操作符的优先顺序，确定数据的进栈及出栈顺序，根据后缀表达式计算表达式的结果。课程设计 2 系统分析 2.1 基础知识 2.1.1 词法分析基本原理 词法分析阶段是编译过程的第一个阶段，是编译的基础。这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。2.1.2 递归下降的原理 递归下降法是语法分析中最易懂的一种方法。它的主要原理是，对每个非终极符按其产生式结构构造相应语法分析子程序，其中终极符产生匹配命令，而非终极符则产生过程调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。 2.1. 递归下降分析的文法要求 递归下降法要满足的条件：假设A的全部产生式为A(α1|α2|……|αn ，则必须满足如下条件才能保证可以唯一的选择合适的产生式 predict(A(αi)∩pre