逆波兰式的生成.doc

淮阴工学院 编译原理课程设计报告编译原理课程设计报告 选题名称选题名称 逆波兰式的生成 2011 年 6月 24 日 设计任务书设计任务书 课题 名称 逆波兰式的生成 设计 目的 通过一周的课程设计 对逆波兰式的生成过程有了深刻的理解 整体过 程是实现对输入合法的中缀表达式进行词法分析 语法分析 并构造相 应的逆波兰式 计算逆波兰式的值 并输出结果 达到了巩固理论知识 锻 炼实践能力的目的 实验 环境 Windows2000 以上操作系统 Visual C 6 0 以上编译环境 任务 要求 1 对算术表达式进行词法 语法 逆波兰式的分析 2 编写代码 实现逆波兰式的生成 3 撰写课程设计报告 4 参加答辩 工作进度计划 序号起止日期工 作 内 容 12011 06 20 2011 06 20 理论辅导 搜集资料 22011 06 21 2011 06 22 编写代码 上机调试 32011 06 22 2011 06 23撰写课程设计报告 42011 06 24 2011 06 25答辩 完善报告 指导教师 签章 年 月 日 摘要 编译原理旨在介绍编译程序构造的一般原理和基本方法 内容包括语言和 文法 词法分析 语法分析 语法制导翻译 中间代码生成 存储管理 代码 优化和目标代码生成 它是计算机科学与技术专业最重要的一门专业基础课程 内容庞大 涉及面广 知识点多 为了把理论知识更加牢固地掌握 同时也是 为了培养我们的实践能力 安排了这次课程设计 这次课程设计的主要任务是 编程实现对输入合法的中缀表达式进行词法分析 语法分析 并构造相应 的逆波兰式 计算逆波兰式的值 并输出结果 逆波兰式也叫后缀表达式 是为了纪念波兰数学家鲁卡谢维奇 Jan Lukasiewicz 而命名的 比如中缀表 达式 A B C 其后缀表达式为 ABC 后缀表达式的优点是显而易见的 编译器在处理时候按照从左至右的顺序读取逆波兰表达式 遇到运算对象直接 压入堆栈 遇到运算符就从堆栈提取后进的两个对象进行计算 这个过程正好 符合了计算机计算的原理 所以以逆波兰式为课程设计题目有一定的必要性 这也不仅使编译原理相关知识内容得以应用于实践之中 关键词 中缀表达式 逆波兰表达式 编译原理 目目 录录 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 课题综述课题综述 1 1 课题来源课题来源 编译原理这门课在理论 技术 方法上都对学生提供了系统而有效的训练 有利于提高软件人员的素质和能力 对中缀表达式的计值 并非按运算符出现 的自然顺序来执行其中的各个运算 而是根据算符间的优先关系来确定运算的 次序 此外 还应顾及括号规则 逆波兰式在计算机看来却是比较简单易懂的 结构 因为计算机普遍采用的内存结构是栈式结构 它执行先进后出的顺序 将一个普通的中序表达式转换为逆波兰表达式的一般算法是 首先构造一个运 算符栈 此运算符在栈内遵循越往栈顶优先级越高的原则 读入一个用中缀表 示的简单算术表达式 为方便起见 设该简单算术表达式的右端多加上了优先级 最低的特殊符号 从左至右扫描该算术表达式 从第一个字符开始判断 如果该字符是数字 则分析到该数字串的结束并将该数字串直接输出 如果不 是数字 该字符则是运算符 此时需比较优先关系 1 2 课题意义课题意义 中缀表达式是一个通用的算术或逻辑公式表示方法 操作符是以中缀形式 处于操作数的中间 例 1 2 中缀表达式是人们常用的算术表示方法 与逆 波兰式相比 中缀表达式不容易被电脑解析 那是因为计算机普遍采用的内存 结构是栈式结构 它执行先进后出的顺序 由此要从中缀表达式直接产生目标 代码一般比较麻烦 而逆波兰式规定把运算符放在两个运算对象的后面 在逆 波兰式中 不存在运算符的优先级问题 也不存在任何括号 计算的顺序完全 按照运算符出现的先后次序进行 比中缀表达式的求值要简单得多 1 3 预期目标预期目标 在本次课程设计时间内 利用网络了解了有关逆波兰式的知识 同时还去 图书馆查阅资料 最后编写出了能够实现逆波兰式的生成和计算的程序 此程 序能实现如下功能 能够对输入的合法表达式进行词法分析及语法分析 并能 够对此逆波兰式进行计算操作并得出正确的结果 同时通过本次课程设计 学 会了认识问题 分析问题 解决问题的能力 锻炼了编写程序 调试程序的能 力 并能够发挥团队优势 从而完成了此次有关逆波兰式的生成的课程设计任 2 务 1 4 所面对的问题所面对的问题 对输入的表达式进行词法分析 语法分析及得出正确的逆波兰式 根据逆 波兰式得出表达式的结果 通过递归下降方法分析表达式 并且输出词法分析 语法分析过程及结果 实现把中缀表达式转换成后缀表达式 并计算表达式的 结果 1 5 所需解决的关键技术所需解决的关键技术 本次课程设计中的关键是 通过递归下降方法分析表达式 主要有词法分 析和语法分析 输出分析结果 判断表达式是否合法 如何确定操作符的优先 顺序 确定数据的进栈及出栈顺序 根据后缀表达式计算表达式的结果 此次有关逆波兰式的生成的课程设计的转换过程需要两个栈 一个运算符 号栈和一个后缀表达式输出符号栈 1 读入操作数 直接送输出符号栈 2 读入运算符 压入运算符号栈 3 括号处理 遇到开括号 进运 算符号栈 遇到闭括号 则把最靠近的开括号 以及其后进栈的运算 符依次弹出到输出符号栈 但括号均不压入输出符号栈 4 遇到结束符 则把运算符号栈内的所有运算符号依次弹出 并压入输出符号栈 5 若输入 为 的单目运算符 改为 0 与运算对象在前 运算符在后 2 系统分析系统分析 2 1 基础知识基础知识 2 1 1 词法分析基本原理 词法分析阶段是编译过程的第一个阶段 是编译的基础 这个阶段的任务 是从左到右一个字符一个字符地读入源程序 即对构成源程序的字符流进行扫 描然后根据构词规则识别单词 也称单词符号或符号 2 1 2 递归下降的原理 递归下降法是语法分析中最易懂的一种方法 它的主要原理是 对每个非 终极符按其产生式结构构造相应语法分析子程序 其中终极符产生匹配命令 而非终极符则产生过程调用命令 因为文法递归相应子程序也递归 所以称这 种方法为递归子程序下降法或递归下降法 3 2 1 3 递归下降分析的文法要求 递归下降法要满足的条件 假设 A 的全部产生式为 A 1 2 n 则 必须满足如下条件才能保证可以唯一的选择合适的产生式 predict A i predict A j 当 i j 2 1 4 后缀表达式基础知识 逆波兰记号是最简单的一种中间代码表示形式 早在编译程序出现之前 它就用于表示算术表达式 是波兰逻辑学家卢卡西维奇发明的 将运算对象写在前面 把运算符写在后面 叫后缀表达式 后缀表示法表 示表达式 其最大优点是易于计算机处理表达式 利用一个栈 自左向右扫描 算术表达式 每碰到运算对象 就把它推进栈 碰到运算符 若该运算符是二 目的 则对栈顶部的两个运算对象实施运算 并将运算结果代替运算对象而进 栈 若是一目运算符 则对栈顶元素执行该运算 并以运算结果代替元素进栈 最后的结果留在栈顶 逆波兰记号是最简单的一种中间代码表示形式 早在编译程序出现之前 它就用于表示算术表达式 2 2 解决问题的基本思路解决问题的基本思路 系统设计题目的要求是使用堆栈 完成算术表达式的由中缀表达式转换成 后缀表达式 为以后的表达式求值做准备 根据课程设计的要求 程序应具有 如下功能 对输入的表达式进行分析并输出逆波兰式 由于对算数表达式的分 析过程比较简单 这里采用递归下降的分析方法 首先对输入的表达式进行词 法分析 分析的结果作为语法分析的输入 然后进行语法分析 语法分析采用 递归下降的分析方法 最后输出生成的逆波兰式并进行运算 2 3 总体方案总体方案 启动 VC 新建源程序并进行编程 程序的功能模块图如图 2 1 所示 4 逆波兰式的生成 拆分输入串 词法分析 逆波兰式的生成 求表达式的值并输出 语法分析 图 2 1 程序功能模块图 3 系统设计系统设计 3 1 算法实现算法实现 将一个普通的中序表达式转换为逆波兰表达式的一般算法是 1 首先构造一个运算符栈 此运算符在栈内遵循越往栈顶优先级越高的原 则 2 读入一个用中缀表示的简单算术表达式 为方便起见 设该简单算术表达 式的右端多加上了优先级最低的特殊符号 3 从左至右扫描该算术表达式 从第一个字符开始判断 如果该字符是数 字 则分析到该数字串的结束并将该数字串直接输出 4 如果不是数字 该字符则是运算符 此时需比较优先关系 做法如下 将该字符与运算符栈顶的运算符的优先关系相比较 如果 该 字符优先关系高于此运算符栈顶的运算符 则将该运算符入栈 倘若不是的话 则将栈顶的运算符从栈中弹出 直到栈顶运算符的优先级低于当前运算符 将 该字符入栈 5 重复上述操作 1 2 直至扫描完整个简单算术表达式 确定所有字符都得 到正确处理 我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的 简单算术表达式 5 图 3 1 程序流程图 3 2 实验设计思想及算法实验设计思想及算法 转换的基本思路 1 在表达式字符串的末尾加一个代表结束的辅助符 比如 2 从头开始扫描表达式 并判断当前的每一个字符 3 取当前的一个字符 如果当前字符是代表数字 则进逆波兰式的栈 如 果是运算符 则转入 4 如果是 则结束 4 比较当前运算符与临时栈中的栈顶运算符 如果栈顶运算符比当前运算 符优先级高 则弹出一个运算符放进逆波兰式栈中 并继续 4 否则把当前运 算符进临时栈 转入 2 6 3 2 程序设计流程图 4 文法文法 本程序使用的文法是 E TG T FS G TG G F E F i S FS S 5 代码编写代码编写 在此次课程设计过程中 我主要负责的对输入的表达式进行语法分析 并 得出输入表达式的推导式 部分代码如下 void input int j 0 for j i1 flag j i1 0 flag 1 时 i1 flag 0 所以循环不执行 7 printf c b j 每次输出一个分析串 printf t t printf c t t ch 输出分析字符 void input1 int j for j i1 1 flag j d n 2 n n 2 i n i i 2 while d i i i 1 while d i e 0 i i 1 q i m q k q while d m m m 1 m m 1 while m q d n d m m m 1 n n 1 d n for j 3 e j j d n e j n n 1 k k 1 while d k d n d k n n 1 k k 1 d n int E1 int f t printf d tE TG t total total total 存放分析步骤 flag 1 8 input input1 f T if f 0 return 0 t G if t 0 return 0 else return 1 int E int f t printf d tE TG t total total e 0 E e 1 e 2 e 3 T e 4 G e 5 output flag 1 input input1 f T if f 0 return 0 t G if t 0 return 0 else return 1 int T int f t printf d tT FS t total total e 0 T e 1 e 2 e 3 F e 4 S e 5 output flag 1 input input1 f F if f 0 return 0 t S if t 0 return 0 else return 1 int G int f if ch b i1 ch printf d tG TG t total total 9 e 0 G e 1 e 2 e 3 e 4 T e 5 G e 6 output flag 0 input input1 ch a1 i1 f T if f 0 return 0 G return 1 printf d tG t total total e 0 G e 1 e 2 e 3 e 4 output flag 1 input input1 return 1 int S int f t if ch b i1 ch printf d tS FS t total total e 0 S e 1 e 2 e 3 e 4 F e 5 S e 6 output flag 0 input input1 ch a1 i1 f F if f 0 return 0 t S if t 0 return 0 else return 1 printf d tS t total total e 0 S e 1 e 2 e 3 e 4 output flag 1 a1 i1 ch input input1 return 1 int F int f if ch 10 b i1 ch printf d tF E t total total e 0 F e 1 e 2 e 3 e 4 E e 5 e 6 output flag 0 input input1 ch a1 i1 f E if f 0 return 0 if ch b i1 ch printf d tF E t total total flag 0 input input1 ch a1 i1 else printf error n return 0 else if ch i b i1 ch printf d tF i t total total e 0 F e 1 e 2 e 3 i e 4 output flag 0 input input1 ch a1 i1 else printf error n return 0 return 1 void yufa 递归分析 int f p j 0 char x d 0 E d 存 文法 d 1 d 2 d 3 T d 4 G d 5 j strlen a1 j 输入串长度 a1 j n1 j ch b 0 a1 0 把串的第一字符赋给 ch b 存放 分析字符 cout endl 语法分析 endl printf 步骤 t 文法 t 分析串 t t 分析字符 t 剩余串 n 11 f E1 if f 0 return if ch printf accept n p 0 x d p while x printf c x p p 1 x d p 输出推导式 else printf error n getchar return printf n getchar 6 程序调试程序调试 由于程序采用递归下降的分析方法 首先对输入的表达式进行词法分析 分析的结果作为语法分析的输入 然后进行语法分析 语法分析采用递归下降 的分析方法 最后输出生成的逆波兰式并进行运算 程序中调用了许多函数 编写代码时会出现调用的错误 使在程序运行时无法正确判断以致程序运行出 错 因此 在编程时需要保持清醒思路 按照解决问题的基本思路一步步地编 写程序 而在程序出现不良结果时 注意前后对照分析 排除程序编写的不合 理的地方 最终完成此次课程设计的相关任务与要求 7 运行与测试运行与测试 输入算术表达式 3 2 1 出现运行结果 如图 7 1 所示 12 图 7 1 程序运行结果图 13 总 结 通过本次课程设计让我对编译原理有了进一步的了解 但由于本人在知识 经验方面都存在着很多不足 所以系统必然会存在一些缺陷和不足之处 通过本次课程设计也让我认识到了要想开发一个软件自己必须要对所要开 发的软件的功能有很深刻地理解 并能找出功能之间的关系 从而建立相应的 系统模型 如编写逆波兰式的产生就是首先要对所输入的算术表达式进行词法 分析后 再进行语法分析 而语法分析采用递归下降的分析方法 最后再输出 生成的逆波兰式并进行运算 这次有关编译原理的逆波兰式的生成的课程设计 是我们将所学理论知识形成系统的一个锻炼的好机会 当然此过程是由在小组其他成员沈涵黎和王玲慧的帮助下完成的 也正因 为团队的力量及老师们的帮助 我们组才能顺利完成此次课程设计的相关任务 和目标 这也对今后进一步学习编译原理知识打下了一定的基础 通过这次课程设计使我认识到了以下几个方面 首先 我对编译原理这方面的知识掌握的还不够 在设计逆波兰式时并没 有少费功夫 最后我终于认识到问题的根源所在 认真细致地对开发过程进行 了规划和分析 才逐渐弄清了整个系统的流程 其次 对编程语言的熟悉程度不够 使我对整个编写过程并不是非常熟悉 在编写过程中总会出现错误 我就向精通 VC 的同学进行寻问 探讨 终于 解决了一些难题 在这次的课程设计中 让我深深地体现到编程不是一件简单的事情 它需 要设计者具有全面的专业知识 缜密的思维 严谨的工作态度以及较高的分析 问题 解决问题的能力 而我在很多方面还不足 通过这个课程设计让我有了 深刻的了解 提高了自己的动手能力 同时也认识到了团队合作的重要性 14 致 谢 首先 我要谢谢淮阴工学院计算机工程系给我们提供了实验室 感谢计算 机工程系给我们提