编译原理论文.pdf

学号 0121010680514 实验成绩 武汉理工大学武汉理工大学 课程设计课程设计 实验课程名称： 编 译 原 理 开 课 学 院 ： 计算机科学学院 课 程 题 目 ： 24点速算游戏 指导老师姓名： 饶 文 碧 学 生 姓 名 ： 桂 江 亨 学生专业班级： 软件工程sy1001班 2012 2013 学年 第 一 学期 课程设计任务书课程设计任务书 学生姓名学生姓名： 桂桂 江江 亨亨 专业班级专业班级： 软软 件件 sy1 sy1001 001 班班 指导教师指导教师： 饶饶 文文 碧碧 工作单位工作单位： 计计 算算 机机 学学 院院 题目题目: 24: 24 点速算游戏点速算游戏 1目的 通过设计、编制、调试一个 24 点速算程序，加深对语法及语义分析原 理的理解，并实现词法分析程序对单词序列的词法检查和分析。 2.设计内容及要求 程序输入：1-12 中的 4 个数字； 程序输出：由上述 4 个数字及“+，-，*，/”组成的计算结果为 24 的 算术表达式； （1） 学号 3，22 的同学按顺序分别选择递归下降法、算符优先分析法完成 以上任务，最终输出正确的算术表达式。 （2） 写出算术表达式的符合分析方法要求的文法，给出分析方法的思想， 完成分析程序设计。 （3） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程 序。 上机时间安排上机时间安排： 18 周一 五 08：00 12：00 指导教师签名指导教师签名： 年年 月月 日日 系主任系主任（或责任教师或责任教师）签名签名： 年年 月月 日日 24点速算游戏点速算游戏 124点速算游戏点速算游戏问题简介问题简介： 程序输入 1 到 12 中的四个数字，然后由上面四个数字及“+、-、*、/”组成 的计算结果为 24 的算术表达式。 1.1）对输入输出的说明对输入输出的说明： 因为没有考虑四个数字有重复的情况，出现重复的数字可能会使得输出有冗 余：比如输入 6、6、6、6，四个数字可能会输出多个 6 + 6 + 6 + 6。所以不允许 输入重复的数字。 而且也没有考虑输出冗余的问题，比如：1 * 2 * 3 * 4 和 2 * 1 * 3 * 4 被认为 是不同的。 此外，所有的数据都被当成浮点数，因此 3 / 8 + 4 * 6 的结果不是 24，因为 3 / 8 不是等于 0。 2. 24点游戏算法设计点游戏算法设计 求解 24 点速算游戏需要对给入的 4 个数字，以及四则运算中的三个（可以 重复）组合成一个表达式，然后计算表达式的值，判断是否等于 24。如果相等 输出该表达式。 因此速算游戏涉及到计算一个表达式的值。求解一个表达式的方法有很多， 按照任务书，我要利用算符优先来计算表达式。 根据算符优先计算表达式的算法， 需要两个栈， 一个是操作数栈 vector nums，一个是操作符栈 vector opts。操作符栈首先要压入一个#进行 初始化，表示开始接受输入。然后对每一个操作符都需要比较其与栈顶操作符的 优先级关系： 如果小于的话，操作数栈末尾的两个操作数需要出栈，同时操作符栈末尾的 元素出栈，然后进行四则运算将结果压入操作数栈。此时还要比较当前读入的操 作符和栈顶的操作符优先级关系，如果小于则在此进行上面同样的操作，然后才 将该操作符压入栈，之后再读取一个操作数并压入操作数栈。否则的话直接将该 操作符压入栈，然后读取一个操作数压入栈。 如果大于的话，直接将该操作符压入栈，然后读取一个操作数将其压入操作 数栈。 这样一直读取表达式，直到表达式中所有的运算符都已将读入，这时需要对 操作符栈进行判断，因为可能还有运算符留在栈中，而没有进行运算，这时要不 停的将操作数操作符出栈进行四则运算然后将结果亚入回操作数栈直至操作符 栈为空， 操作数栈中唯一的一个元素既是整个表达式的结果。 下面是具体的代码： / 对表达式进行解析计算 float calculate() int num_k = 0, opt_k = 0; opts.push_back( # ); nums.push_back( _numsnum_k+ ); for( int i = 0; i 1 ) calback(); float result = nums.back(); nums.clear(); opts.clear(); return result; 2.1 构造算符优先表构造算符优先表 首先需要给出一个表达式的文法，下面是一个表示简单四则运算的表达式的 文法： （0）s e （1）e e + t （2）e e - t （3）e t （4）t t * f （4）t t / f （4）t f （6）f i 该文法用非终结符 t 表示相乘的结果是为了使 * 和 / 的优先级高于 + 和- 。 按照规则，接下来将构造一张表对终结符的优先级关系进行描述： + - * / # + - * / # #include #define len 3 using namespace std; float _nums4; char _opts3; char fouropt4 = +, -, *, /; vector nums; vector opts; bool isprior( char a, char b ) if( a = b ) return false; else if( b = # ) return true; else if( b = + | b = - ) if( a = * | a = / ) return true; else return false; else return false; float arithmetic( float a, float b, char opt ) switch( opt ) case +: return a + b; case -: return a - b; case *: return a * b; case /: return a / b; void calback() float b = nums.back(); nums.pop_back(); float a = nums.back(); nums.pop_back(); char opt = opts.back(); opts.pop_back(); nums.push_back( arithmetic( a, b, opt ) ); float calculate() int num_k = 0, opt_k = 0; opts.push_back( # ); nums.push_back( _numsnum_k+ ); for( int i = 0; i 1 ) calback(); float result = nums.back(); nums.clear(); opts.clear(); return result; void swap( float a = b; b = c; void printexpression() int i; for( i = 0; i != len; +i ) cout _nums0 _nums1 _nums2 _nums3; combine( 0 ); system( “pause“ ); return 0; 4. 运行结果截图运行结果截图 下面是程序运行结果的一些截图 截图（1） ，没有能够得到 24 的组合 截图（2） 截图（3） 5. 课程小结课程小结 位置不多，只有一句：真心感谢饶文碧老师的耐心指导和悉心教学。 本科生课程设计成绩评定表本科生课程设计成绩评定表 班级： 姓名： 学号： 序号 评分项目 满分 实得分 1 学习态度认真、遵守纪律 10 2 设计