逆波兰式的生成.docVIP

淮阴工学院

编译原理课程设计报告

选题名称:逆波兰式的生成

2011年6

设计任务书

课题名称

逆波兰式的生成

设计

目的

通过一周的课程设计，对逆波兰式的生成过程有了深刻的理解。整体过程是实现对输入合法的中缀表达式进行词法分析、语法分析，并构造相应的逆波兰式，计算逆波兰式的值并输出结果。到达了稳固理论知识、锻炼实践能力的目的。

实验环境

任务要求

1.对算术表达式进行词法、语法、逆波兰式的分析；

2.编写代码，实现逆波兰式的生成；

3.撰写课程设计报告；

4.参加辩论。

工作进度方案

序号

起止日期

工作内容

1

2011.06.20～2011.06.20

理论辅导，搜集资料

2

2011.06.21～2011.06.22

编写代码，上机调试

3

2011.06.22～2011.06.23

撰写课程设计报告

4

2011.06.24~2011.06.25

辩论，完善报告

指导教师〔签章〕：

年月日

摘要：

编译原理旨在介绍编译程序构造的一般原理和根本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。它是计算机科学与技术专业最重要的一门专业根底课程，内容庞大，涉及面广，知识点多。为了把理论知识更加牢固地掌握，同时也是为了培养我们的实践能力，安排了这次课程设计。这次课程设计的主要任务是编程实现对输入合法的中缀表达式进行词法分析、语法分析，并构造相应的逆波兰式，计算逆波兰式的值并输出结果。逆波兰式也叫后缀表达式，是为了纪念波兰数学家鲁卡谢维奇〔JanLukasiewicz〕而命名的。比方中缀表达式：A*(B+C)，其后缀表达式为：ABC+*。后缀表达式的优点是显而易见的，编译器在处理时候按照从左至右的顺序读取逆波兰表达式，遇到运算对象直接压入堆栈，遇到运算符就从堆栈提取后进的两个对象进行计算，这个过程正好符合了计算机计算的原理。所以以逆波兰式为课程设计题目有一定的必要性。这也不仅使编译原理相关知识内容得以应用于实践之中。

关键词：中缀表达式；逆波兰表达式；编译原理

目录

TOC\o1-2\h\z\u1课题综述 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

实验设计思想及算法 5

4文法 6

5代码编写 6

6程序调试 11

7运行与测试 11

总结 13

致谢 14

参考文献 15

1课题综述

1.1课题来源

编译原理这门课在理论、技术、方法上都对学生提供了系统而有效的训练，有利于提高软件人员的素质和能力。对中缀表达式的计值，并非按运算符出现的自然顺序来执行其中的各个运算，而是根据算符间的优先关系来确定运算的次序，此外，还应顾及括号规那么。逆波兰式在计算机看来却是比拟简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。将一个普通的中序表达式转换为逆波兰表达式的一般算法是：首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原那么。读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，那么分析到该数字串的结束并将该数字串直接输出。如果不是数字，该字符那么是运算符，此时需比拟优先关系。

1.2课题意义

中缀表达式是一个通用的算术或逻辑公式表示方法，操作符是以中缀形式处于操作数的中间〔例：1+2〕，中缀表达式是人们常用的算术表示方法。与逆波兰式相比，中缀表达式不容易被电脑解析。那是因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。由此要从中缀表达式直接产生目标代码一般比拟麻烦。而逆波兰式规定把运算符放在两个运算对象的后面。在逆波兰式中，不存在运算符的优先级问题，也不存在任何括号，计算的顺序完全按照运算符出现的先后次序进行。比中缀表达式的求值要简单得多。

1.3预期目标

在本次课程设计时间内，利用网络了解了有关逆波兰式的知识，同时还去图书馆查阅资料，最后编写出了能够实现逆波兰式的生成和计算的程序。此程序能实现如下功能：能够对输