武汉理工大学编译原理课程设计.docx

学 号：课程设计题目24点速算游戏学院计算机科学与技术学院专业软件工程班级软件zy1302班姓名指导教师饶文碧2016年1月8日课程设计任务书学生姓名：专业班级： 软件zy1302班 指导教师： 饶文碧 工作单位： 计算机科学与技术学院 题目:24点速算游戏1．目的通过设计、编制、调试一个24点速算程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。2．设计内容及要求程序输入：1-12中的4个数字；程序输出：由上述4个数字及“+，-，*，/”组成的计算结果为24的算术表达式；学号5，16，27的同学选择任意方法完成以上任务，最终输出正确的算术表达式。写出算术表达式的符合分析方法要求的文法，给出分析方法的思想，完成分析程序设计。编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。3．上机时间安排设计时间：第18周，周四上午8：00-12：00，周五下午2：00-5：30。指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日引言课程设计是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，设计题中的问题比平时的练习题要复杂，也更接近实际。编译原理这门课程安排的课程设计的目的是旨在要求学生进一步巩固课堂上所学的理论知识，深化理解和灵活掌握教学内容，选择合适的数据逻辑结构表示问题，然后编制算法和程序完成设计要求，从而进一步培养学生独立思考问题、分析问题、解决实际问题的动手能力。要求学生在上机前应认真做好各种准备工作，熟悉机器的操作系统和语言的集成环境，独立完成算法编制和程序代码的编写。随着科技发展和社会进步，尤其是计算机大范围的普及，计算机应用逐渐由大规模计算的海量数据处理转向大规模的事物处理和对工作流的管理，这就产生以台式计算机为核心的管理系统。本次课程设计的题目是速算24点，是在80年代成为一种流行的游戏，在中国把这游戏叫做“24点游戏”。计算24点游戏：任意输入4位数字，利用+,-,*,/四则运算使之得到结果 24。输出所有不同算法的计算表达式，可为运算优先级而使用括号。速算24点游戏始于何年何月已无从考究，但它以自己独具的数学魅力和丰富的内涵正逐渐被越来越多的人们所接受。这种游戏方式简单易学，能健脑益智，是一项极为有益的活动。笔者抛弃常用的编程方式（直接根据表达式进行求值判断是否值为24），采用构造编译器的模式，对表达式进行词法分析、语法分析和语义分析，进而得到表达式的值，尽管这样有些大材小用，但是对于我理解编译原理有极大的帮助。文法及中间代码形式的描述2.1文法的描述自己根据表达式的特点归纳了一个初始文法G[E]：E – E+T | E-T | TT – T*F | T/F | FF – (E) | d但据观察，上述文法有左递归性，将上述文法消除左递归可得出下面的文法：E – TE’E’ – +TE’ | -TE’ | εT – *FT’ | /FT’ | εF – (E) | d词法分析方法词法分析时编译的第一个阶段，他的主要任务是从左至右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析。执行词法分析的程序称为词法分析程序或扫描程序。自定义类Token存放识别出的单词属性，Token数据结构如下：public class Token{ private String tokenType; // 单词种别码 private String tokenValue; // 单词值 public Token(String tokenType, String tokenValue) { this.tokenType = tokenType; this.tokenValue = tokenValue; } public String getTokenType() { return tokenType; } public String getTokenValue() { return tokenValue; }}该词法分析器能够识别运算符：+-*/，能够识别界符：()，能够识别数字，其DFA在下面的词法分析详细描述部分有介绍。语法分析方法语法分析是编译程序的核心部分。语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子，目前语法分析常用的方法有自顶向下分析和自底向上分析两大类。本文采用自顶向下分析中的递归下降法来分析条件表达式。递归子程序法是比较简单直观易于构造的一种语法分析