编译原理课程设计终结版

1、 基于算符优先分析方法 的表达式语法分析器 年 级： 2007班 级： 级计算机科学与技术 4班组 长： 刘思佳组 员： 欧 垚 毛群晖 袁小仨 徐碧红 邓文杰 孙苗苗 顿 硕 伍小军 曾 洁 孙 梁 吉顺昌指导老师： 段明秀二二一二二一年四月二十六日目 录前 言1第1章 课程设计计划41.1员与工作分配41.2课程计划41.3资源需求4第2章 功能需求分析52.1 功能需求清单5第3章 设计、分析与编码63.1 总体设计63.1.1 模块划分63.1.2程序分包63.2 详细设计73.2.1 类图73.3 程序流程图93.4 分析与编码实现103.4.1表达式文法GE构造算符优先关系表103

2、.4.2 根据算符优先表用栈结构来实现算符优先分析133.4.3 辅助工具类设计18第4章 测试用例及程序截图214.1第一版测试214.1第二版测试254.2 第三版测试28第5章 用户使用说明325.1 使用步骤32附录1. 参考文献33附录2. 总结33前 言1摘要编译原理是计算机专业的一门重要专业课，旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。编译原理是计算机专业设置的一门重要的专业课程。虽然只有少数人从事编译方面的工作，但是这门课在理论、技术、方法上都对学生提供了系统而有效的训练，有利

3、于提高软件人员的素质和能力。算符优先分析法是一种简单直观、特别方便于表达式分析，易于手式实现的方法。算符优先法只考虑算符（广义为终结符号）之间的优先关系，它是一种自底向上的归约过程，但这种归约未必严格按照句柄归约。它是一种不规范归约法。算符优先分析法的关键是比较两个相继出现的终结符号的优先级而决定应采取的动作。要完成算符间的优先级比较，就要先定义各种可能出相继出现的运算符的优先级，并将其表示成矩阵形式，在分析过程中通过查询矩阵元素而得出算符间的优先关系。2问题描述给出该文法E # E #E E + Q | QQ Q - T | TT T * F | FF F/ MMM M PPP ( E )i

4、用算符优先分析法实现对表达式的计算。3项目开发平台语言：Java开发平台：MyEclipse第1章 课程设计计划1.1组员与工作分配组长：刘思佳资料组：毛群晖，邓文杰，曾洁代码组：刘思佳，孙梁，孙苗苗，顿硕测试组：欧垚，吉顺昌，徐碧红，袁小仨，伍小军1.2课程计划表1.2.1 课程设计计划清单序号内容需求计划时间实际时间状态1问题定义对课程设计要求分析6月15日6月15日已完成2查询资料对课程设计做必要的资料查询6月16日-6月17日6月17日已完成3概要设计确定课程设计的总体框架与分包6月18日6月18日已完成4详细设计具体分析设计每个类与接口6月19日-6月20日6月20日已完成5编码实现

5、程序6月21日6月21日已完成6测试并修改测试程序BUG并进行修改6月22日-6月26日6月26日已完成1.3资源需求 表1.3.1开发资源序号资源作用占用时间当前可用状态获得途径1MyEclipse平台设计平台贯穿整个设计阶段可用网上下载第2章 功能需求分析2.1 功能需求清单表2.1.1 需求清单功能编号功能名称备注1键盘输入用户能从键盘输入字符串2表达式切分切分算术表达式，结果存入字符串数组，如： 字符串：1.5+3*2# 将被切分为 1.5,+,3,*,2,#3扫描表达式检测是否符合给定的文法4出错处理不符合文法的给出错误提示5计算表达式合法的算术表达式将计算出结果6输出将计算结果输出

6、给用户第3章 设计、分析与编码3.1 总体设计3.1.1 模块划分该语法分析器可分为以下几个主要模块：1. 词法分析并计算模块其中应有一个操作符栈和一个操作数栈，用于分析输入的文法和句子，并提供方法检验该表达式是否为给出的文法，如果是则运算出结果，否则提示错误2. 算符优先表构建模块用于构建输入文法的算符优先表，并对其中的算符优先表进行各种操作。3. 输入功能模块提供从键盘输入功能。3.1.2程序分包com.op.core 该包下为核心类，完成核心功能com.op.util 该报为工具包，包含一些输入，字符串处理等程序之间应该保持低耦合，高内聚。包之间的依赖关系为core-util,核心包依赖

7、于util， util不依赖其他包。3.2 详细设计 3.2.1 类图com.op.core.OperatorPrority类：该类为核心类，实现所有核心功能。com.op.core.ProrityTable类：该类为存放算符优先级表，以及对算符优先级表查询等操作。com.op.core.StringUtil类：该类实现必要的字符串操作。com.op.core.IOUtil类：该类实现输入输出等常用操作类之间的依赖关系：OperatorPriority将依赖于其他三个类，而其他的类互不依赖。输入待分析的表达式切分表达式扫描表达式中的项是否为运算符优先级是否大于操作符栈栈顶元素优先级YY当前操作

8、符进入操作符栈N是否小于操作符栈栈顶元素优先级操作数栈弹出两个元素，操作符栈弹出一个元素，进行运算，计算结果存入操作数栈Y 符号栈弹出栈顶元素N压入操作数栈是否为#N入口出口N3.3 程序流程图3.4 分析与编码实现3.4.1表达式文法GE构造算符优先关系表计算算符优先只针对于终结符，终结符之间的优先关系有三种，在计算优先关系之前我们先定义两个集合，对于任意两个终结符（a,b）FIRSTVT（B）=b|B=b或B=Cb,其中表示V中的符号串。LASTVT（B）=a|B=a或B=aC三种优先关系： （1）等于关系:可直接查看产生式的右部,对如下形式的产生式A-ab A- aBb则有a=b成立。

9、（2）小于关系：求出每个非终结符B的FIRSTVT（B），观察如下形式的产生式A-aB对每一bFIRSTVT(B)有ab成立 （3）大于关系：计算每个非终结符B的LASTVT（B），观察如下形式的产生式A-Bb对每一aLASTVT(B)有ab成立关系表：通常用矩阵的形式存放文法中各种可能的优先关系。大小：矩阵是nn的，其中n是文法中终结符的个数。表达式文法G E：E # E #E E + Q | QQ Q - T | TT T * F | FF F/ MMM M PPP ( E )i根据上面的规则手工构造上述文法的算符优先表如下：+-*/（）i#+-*/（=）i#=代码清单package co

10、m.op.core;public class PriorityTable private static char table = / + * / i ( ) # , , , , , , , , , , , , , , , , , , , , , $, $, , , , / i , , , , , =, $, , , , $, $, , , , / ) , , , , , $, =, , , , , , , , / ; / 算符优先表/* * 判断一个符号在算符优先表中位置 * * param c * return */private static int judgePriority(char

11、c) int priority = 0;switch (c) case +:priority = 0;break;case *:priority = 1;break;case /:priority = 2;break;case i:priority = 3;break;case (:priority = 4;break;case ):priority = 5;break;case #:priority = 6;break;case :priority = 7;break;return priority;/* * 判断两个算术符的优先级 * * param m * 为符号栈的栈顶元素 * par

12、am n * 为当前输入算术符 * return */public static char getPriority(char m, char n) return PriorityTable.tablejudgePriority(m)judgePriority(n);3.4.2 根据算符优先表用栈结构来实现算符优先分析设置两个栈：存放运算符的OPTR栈和存放操作数或运算结果的OPND栈。具体算法描述如下：（1）首先置操作数OPND栈为空栈，将#入运算符OPTR栈。（2）依次读入表达式中每个单词，若是操作数则进OPND栈，若是运算符则转（3）。（3）当前设读入的运算符为2，查找算符优先关系表，比较

13、2与OPTR栈顶元素1 ：若1aSK a?Q:= SjJ:=j-1Sj-1 VTJ:=j-2SjQSj = a ?Sj =#检查是否正常结束K:=k+1Sk = a出错出错结束Sj+1SK归约为NK:=j+1 SK:=N分析归约流程图在分析过程中，利用分析栈存放已识别的那部分句型，而句型的其余部分由剩余输入串组成，通过比较栈顶符号和下一个输入符号之间的关系，如果是小于或等于则将输入串一次逐个存入符号栈中，直到遇到栈顶符号的优先关系大于下一个待输入符号为止，此时可以判别栈顶符号是否为句柄尾符号。如果是句柄尾，则沿栈顶向下，在栈内寻找句柄头（利用文法的某条规则），然后把它们弹出栈，并代之以归约后的

14、非终结符。这样就完成了一次归约过程。代码清单package com.op.core;import java.math.BigDecimal;import java.util.Stack;import com.op.util.StringUtil;import com.op.util.IOUtil;public class OperatorPriority private Stack optrStack; /符号栈private Stack opndStack; /操作数栈private String input; /待分析的算术表达式/* * 构造函数 * param input */publ

15、ic OperatorPriority(String input) super();optrStack = new Stack();opndStack = new Stack();optrStack.push(#);this.input = input;/* * 操作两个数 * param a 操作数1 * param b 操作数2 * param op 操作符 * return 运算结果 */public float operateTwoNum(float a, float b, char op) BigDecimal da = new BigDecimal(Float.toString(a

16、); BigDecimal db = new BigDecimal(Float.toString(b); switch (op) case *:return da.multiply(db).floatValue();case +:return da.add(db).floatValue();case -:return db.subtract(da).floatValue();case /:return db.divide(da,7,BigDecimal.ROUND_HALF_UP).floatValue(); /除不尽的情况取7位精确值。case :return db.pow(int)a).f

17、loatValue();return 0;/* * 判断是否为操作符 * param ch 被判断字符 * return 布尔值 */public boolean isOperator(char ch) if (ch = + | ch = - | ch = * | ch = / | ch = (| ch = ) | ch = #|ch=)return true;elsereturn false;/* * 扫描字符串，判断是否对应文法，并计算出结果 * return 计算结果 * throws Exception 如果不符合文法，或者除数等于0，都将抛出异常 */public String sc

18、anner() throws Exception int postion = 0; / 字符串上指示的指针char operator = 0; / 操作符float a = 0, b = 0; / 操作数String exp = StringUtil.splitExp(input);while (true) / 判断是否为运算符if (exppostion.length()=1&isOperator(exppostion.charAt(0) / 需要进行运算符的比较if (!optrStack.isEmpty() if (PriorityTable.getPriority(optrStack.

19、peek().charValue(),exppostion.charAt(0) = ) a = opndStack.pop();b = opndStack.pop();operator = optrStack.pop().charValue();opndStack.push(operateTwoNum(a, b, operator);continue; else if (PriorityTable.getPriority(optrStack.peek().charValue(), exppostion.charAt(0) = =) optrStack.pop();if (exppostion.

20、charAt(0) = #) return opndStack.pop().toString(); elseoptrStack.push( exppostion.charAt(0);/ 为运算数时else opndStack.push(Float.valueOf(exppostion).floatValue();postion+;if (postion = exp.length)break;throw new Exception();/* * 程序入口，启动函数 * param args */public static void main(String args) OperatorPriori

21、ty op = new OperatorPriority(IOUtil.getStringFromKeyBoard(); /实例化 构造函数参数从键盘获得try System.out.println(您输入的表达式: + op.input + = + op.scanner(); catch (Exception e) / TODO Auto-generated catch block/e.printStackTrace();System.out.println(您输入的表达式 + op.input + 有误!);3.4.3 辅助工具类设计a. 通过键盘输入表达式。程序清单package com

22、.op.util;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class IOUtil /* * 得到从键盘输入的字符串 * return 字符串 */ public static String getStringFromKeyBoard() try BufferedReader reader=new BufferedReader(new InputStreamReader(System.in); System.out.print(请输入一个表达

23、式以#号结束：); String str=reader.readLine(); /获取字符串 / System.out.println(您输入的字符串是：+str); return str; catch (IOException e) e.printStackTrace(); return null; b. 字符串处理类将从键盘输入的字符串表达式进行简单的切分，存入字符串数组。这个类是为了在扫描表达式时能对其中的操作数与操作符进行方便的操作。程序清单package com.op.util;import java.util.Vector;public class StringUtil /* *

24、切分算术表达式，结果存入字符串数组，如： 字符串：1.5+3*2# 将被切分为 1.5,+,3,*,2,# * param str * return */public static String splitExp(String str) Vector v = new Vector();int beginIndex = 0;for (int i = 0; i 32 & str.charAt(i) 48&str.charAt(i)!=46)|str.charAt(i)=94) if(beginIndex!=i)v.add( str.substring(beginIndex, i);v.add( S

25、tring.valueOf(str.charAt(i);beginIndex = i + 1;if(beginIndex!=str.length()v.add(str.substring(beginIndex, str.length();String result=new Stringv.size();for(int i=0;iv.size();i+)resulti=v.get(i);return result;第4章 测试用例及程序截图本次设计经过三次测试形成最终版本4.1第一版测试1、如果正确输入表达式应能正确得出结果当输入10+15*4#后，预计结果为70，实际结果为：70.0之所以会出

26、现70.0是因为输出结果的精度不一样。提示“请按任意键继续”，当按下任意键时，退出了程序。程序应该跳到开始处，提醒用户再次输入表达式并以#号结束。2、如果输入一个错误的表达式应能给出错误信息从图中所输入的表达式跟文法进行分析可以得出10不是文法的句子，故输出的结果为：您输入的表达式10+*15+有误！3、对负号的处理经过对文法的分析并没有对负数的处理，在这里他会认为是减号，而在减号的左边缺少一个元素，故输出的结果为：您输入的表达式（-10）*2有误！4、对于单个的整数5、测试除法优先操作测试结果与预计的结果不符合，经过分析得出，之所以上图的结果会是11是因为他的算法步骤为：（1）、2*4=8

27、（2）、（6/2）=3 （3）、3/2=1 （4）、8+3*1=11 在这里出现了两个错误：第一个错误在计算整数除的时候3/2=1出现错误；第二个错误为在计算（6/2）*3/2的问题上出现处理错误，他这里计算除法优先于乘法运算了，在乘法与除法之间的优先为谁先出现就先计算谁。正确的算法为：（1）、2*4=8 （2）、（6/2）=3 （3）、3*3=9 （4）、9/2=4.5 （5）、8+4.5=12.56、乘方的测试测试结果与预计的结果不符合，经过对文法的分析得出此语句为方法的句子，这时可以确定为在编写程序代码时没有完成此功能。7、对于不是方法句子的表达式情况下8、在输入时不加“#”测试报告测试

28、人姓名：测试组测试时间：2010/6/20错误个数：0序号路径输入预计输出实际结果1.如果正确输入表达式应能正确得出结果10+15*4#7070.02.如果输入一个错误的表达式应能给出错误信息10+*15+#给出错误提示您输入的表达式10+*15+有误！3对负号的处理（-10）*（-5）#给出错误提示您输入的表达式（-10）*（-5）有误!4对于单个的整数10#1010.05测试除法优先操作2*4+（6/2）*3/2#12.5116对乘方的测试27#128您输入的表达式27有误!7多“（“括号的情况下（9-6）*3#给出错误提示您输入的表达式（9-6）*3有误!8输入时没有输入“#“号3+4+

29、5错误提示您输入的表达式3+4+5有误!本次测试中发现设计中并未涉及到乘方运算，且除法运算的并非是自左向右而是自右向左的，且除法运算优先级大于乘法运算，需作修改维护4.2第二版测试根据第一版中的问题进行测试测试报告测试人姓名：测试组测试时间：2010/6/28错误个数：6序号任务输入预计输出实际结果1.对于单个的浮点数10#101.02.浮点运算 1+2*3/6213测试除法优先操作2*4+（6/2）*3/2#12.512.54对乘方的测试27#128您输入的表达式27有误!1、对于版本1中没有解决的问题己经解决了，主要是对浮点数的处理。2针对于符点操作与浮点优先测试3、针对乘除法优先操作的测试4、针对乘方问题的测试，依旧没有解决需要进一步改进程序1110987654321输入待分析的表达式切分表达式扫描表达式中的项是否为运算符优先级是否大于操作符栈栈顶元素优先级YY当前操作符进入操作符栈N是否小于操作符栈栈顶元素优先级操作数栈弹出两个元素，操作符栈弹出一个元素，进行运算，计算结果存入操作数栈Y 符号栈弹出栈顶元素N压入操作数栈是否为#N入口出口N4.3第三版测试（根据上述版本错误进行测试且对全部进入回溯测试）根据右边流程图进行路径测试测试报告测试人姓名：测试组测试时间：2010/6/28错误个数：3序号路径输入预期结果