1、武汉理工大学编译原理课程设计学 号： 课 程 设 计题 目24点速算游戏学 院计算机科学与技术学院专 业软件工程班 级软件zy1302班姓 名指导教师饶文碧2016年1月8日课程设计任务书学生姓名： 专业班级： 软件zy1302班 指导教师： 饶文碧 工作单位： 计算机科学与技术学院 题目:24点速算游戏1目的通过设计、编制、调试一个24点速算程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。2设计内容及要求程序输入：1-12中的4个数字；程序输出：由上述4个数字及“+，-，*，/”组成的计算结果为24的算术表达式；（1） 学号5，16，27的同学选择任意方法
2、完成以上任务，最终输出正确的算术表达式。（2） 写出算术表达式的符合分析方法要求的文法，给出分析方法的思想，完成分析程序设计。（3） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。3上机时间安排设计时间：第18周，周四上午8：00-12：00，周五下午2：00-5：30。指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日1 引言课程设计是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，设计题中的问题比平时的练习题要复杂，也更接近实际。编译原理这门课程安排的课程设计的目的是旨在要求学生进一步巩固课堂上所学的理论知识，深化理
3、解和灵活掌握教学内容，选择合适的数据逻 辑结构表示问题，然后编制算法和程序完成设计要求，从而进一步培养学生独立 思考问题、分析问题、解决实际问题的动手能力。要求学生在上机前应认真做好各种准备工作，熟悉机器的操作系统和语言的 集成环境，独立完成算法编制和程序代码的编写。随着科技发展和社会进步，尤其是计算机大范围的普及，计算机应用逐渐由大规模计算的海量数据处理转向大规模的事物处理和对工作流的管理，这就产生以台式计算机为核心的管理系统。 本次课程设计的题目是速算24点，是在80年代成为一种流行的游戏，在中国把这游戏叫做“24点游戏”。计算24点游戏：任意输入4位数字，利用+,-,*,/四则运算使之得
4、到结果 24。输出所有不同算法的计算表达式，可为运算优先级而使用括号。速算24点游戏始于何年何月已无从考究，但它以自己独具的数学魅力和丰富的内涵正逐渐被越来越多的人们所接受。这种游戏方式简单易学，能健脑益智，是一项极为有益的活动。笔者抛弃常用的编程方式（直接根据表达式进行求值判断是否值为24），采用构造编译器的模式，对表达式进行词法分析、语法分析和语义分析，进而得到表达式的值，尽管这样有些大材小用，但是对于我理解编译原理有极大的帮助。2 文法及中间代码形式的描述2.1文法的描述自己根据表达式的特点归纳了一个初始文法GE：E E+T | E-T | TT T*F | T/F | FF (E) |
5、 d但据观察，上述文法有左递归性，将上述文法消除左递归可得出下面的文法：E TEE +TE | -TE | T *FT | /FT | F (E) | d3 词法分析方法词法分析时编译的第一个阶段，他的主要任务是从左至右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析。执行词法分析的程序称为词 法分析程序或扫描程序。自定义类Token存放识别出的单词属性，Token数据结构如下：public class Token private String tokenType; / 单词种别码 private String tokenValue; / 单词值 public Token(Stri
6、ng tokenType, String tokenValue) this.tokenType = tokenType; this.tokenValue = tokenValue; public String getTokenType() return tokenType; public String getTokenValue() return tokenValue; 该词法分析器能够识别运算符：+-*/，能够识别界符：()，能够识别数字，其DFA在下面的词法分析详细描述部分有介绍。4 语法分析方法语法分析是编译程序的核心部分。语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的
7、正确句子，目前语法分析常用的方法有自顶向下分析和自底向上分析两大类。本文采用自顶向下分析中的递归下降法来分析条件表达式。 递归子程序法是比较简单直观易于构造的一种语法分析方法。其实现思想：文法中每个非终结符对应一个递归过程（子程序），每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选式时能够符合 LL(1)文法形式可唯一地确定选择某个候选式进行推导。本课设还采用了语法制导翻译技术，在进行语法分析的同时进行语义分析，该表达式的语义也就是该表达式对应的值，对整个单词符号序列的语法分析进行完后，也就能够得到其所对应的值。5 详细的算法描述5.1词法分析词法分析阶段是编译过程的第
8、一个阶段，是编译的基础。这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词（也称单词符号或符号）。词法分析程序实现这个任务。词法分析程序可以使用Lex等工具自动生成。词法分析是编译程序的第一个阶段且是必要阶段；词法分析的核心任务是扫描、识别单词且对识别出的单词给出定性、定长的处理；实现词法分析程序的常用途径：自动生成，手工生成。本次课程设计采用手工生成，原因：表达式词法分析十分简单，不需要自动生成；笔者希望从此次构造词法分析器的过程中，加深对编译原理的认知。自定义类Token存放识别出的单词属性，其结构上文已有介绍。表达式的词法分析程序
9、对应的DFA如下：笔者为语法分析器构造了一个接口，凡是实现了此接口的类，都能够实现词法分析的功能，达到了低耦合的效果，下列代码是词法分析的核心代码：ExpressionLexer.java :public interface ExpressionLexer /* * 对给定的字符串，进行词法分析，返回单词队列 * param string 字符串，分析的对象 * return 单词队列 */ Queue scan(String string);ExpressionLexerImpl.java :public class ExpressionLexerImpl implements Expres
10、sionLexer String string; int index; private void init(String string) this.string = string; index = 0; private char peekChar() if (index = string.length() - 1 & string.charAt(index) != #) string = string + #; return string.charAt(index); private char pollChar() char c = string.charAt(index); index+;
11、return c; Override public Queue scan(String s) init(s); Queue tokens = new ArrayDeque(); while (index E+T | E-T | TT T*F | T/F | FF (E) | d消除左递归可得出下面的文法：E TEE +TE | -TE | T *FT | /FT | F (E) | d经推导证明，改写后的文法是LL（1）文法，可以使用递归下降法构造语法分析器，笔者为语法分析器也设定了接口，达到低耦合的目标，核心代码如下：ExpressionParser.java :public interfa
12、ce ExpressionParser /* * 对给定的token串进行语法分析，语义分析 * param tokens Token队列，分析的对象 * return 算术表达式的值，分析的结果 */ double parse(Queue tokens);ExpressionParserImpl.java :public class ExpressionParserImpl implements ExpressionParser private Queue tokens; private void init(Queue tokens) this.tokens = tokens; privat
13、e Token peekToken() return tokens.peek(); private Token pollToken() return tokens.poll(); Override public double parse(Queue t) init(t); return expression(); private double expression() double termValue = term(); return expression_(termValue); private double expression_(double termValue) double resu
14、lt = 0.0; switch (peekToken().getTokenType() case +: pollToken(); result = termValue + term(); result = expression_(result); break; case -: pollToken(); result = termValue - term(); result = expression_(result); break; case ): case end: result = termValue; break; default: try throw new Exception(exp
15、ression_(); catch (Exception e) System.out.println(expression_(): something wrong.); e.printStackTrace(); return result; private double term() double factorValue = factor(); return term_(factorValue); private double factor() double result = 0.0; switch (peekToken().getTokenType() case (: pollToken()
16、; result = expression(); pollToken(); break; case digit: result = Double.parseDouble(pollToken().getTokenValue(); break; default: try throw new Exception(factor(); catch (Exception e) System.out.println(factor(): something wrong.); e.printStackTrace(); return result; private double term_(double fact
17、orValue) double result = 0.0; switch (peekToken().getTokenType() case *: pollToken(); result = factorValue * factor(); result = term_(result); break; case /: pollToken(); result = factorValue / factor(); result = term_(result); break; case +: case -: case ): case end: result = factorValue; break; de
18、fault: try throw new Exception(term_(); catch (Exception e) System.out.println(term_(): something wrong.); e.printStackTrace(); return result; 6 源程序清单Token.java :public class Token private String tokenType; / 单词种别码 private String tokenValue; / 单词值 public Token(String tokenType, String tokenValue) th
19、is.tokenType = tokenType; this.tokenValue = tokenValue; public String getTokenType() return tokenType; public String getTokenValue() return tokenValue; ExpressionLexer.java :public interface ExpressionLexer /* * 对给定的字符串，进行词法分析，返回单词队列 * param string 字符串，分析的对象 * return 单词队列 */ Queue scan(String string
20、);ExpressionLexerImpl.java :public class ExpressionLexerImpl implements ExpressionLexer String string; int index; private void init(String string) this.string = string; index = 0; private char peekChar() if (index = string.length() - 1 & string.charAt(index) != #) string = string + #; return string.
21、charAt(index); private char pollChar() char c = string.charAt(index); index+; return c; Override public Queue scan(String s) init(s); Queue tokens = new ArrayDeque(); while (index string.length() switch (peekChar() case (: pollChar(); tokens.offer(new Token(, (); break; case ): pollChar(); tokens.of
22、fer(new Token(), ); break; case +: pollChar(); tokens.offer(new Token(+, +); break; case -: pollChar(); tokens.offer(new Token(-, -); break; case *: pollChar(); tokens.offer(new Token(*, *); break; case /: pollChar(); tokens.offer(new Token(/, /); break; case 9: case 8: case 7: case 6: case 5: case
23、4: case 3: case 2: case 1: case 0: String digit = + pollChar(); if (Character.isDigit(peekChar() digit += pollChar(); tokens.offer(new Token(digit, digit); break; case #: pollChar(); tokens.offer(new Token(end, #); return tokens; default: try throw new Exception(scan(); catch (Exception e) System.ou
24、t.println(scan(): something wrong.); e.printStackTrace(); return tokens; ExpressionParser.java :public interface ExpressionParser /* * 对给定的token串进行语法分析，语义分析 * param tokens Token队列，分析的对象 * return 算术表达式的值，分析的结果 */ double parse(Queue tokens);ExpressionParserImpl.java :public class ExpressionParserImpl implements ExpressionParser private Queue tokens; private void init(Queue tokens) this.tokens = tokens; private Token peekToken() return tokens.peek(); private Token po
