基于算符优先分析方法01

1、 PAGE24 / NUMPAGES24基于算符优先分析方法的表达式语法分析器年 级：2007级 班 级：计算机科学与技术四班姓 名：欧 垚 学 号：指导老师：段 明 秀 年 月 日目录摘要2关键字2构造算符优先表3构造优先分析器6分析归约流程图7运行8测试9参考文献12附加代码13摘要：算符优先分析法是Floyd在1963年首先提出来的，是一种古典而又实用的方法，用这种方法在分析程序语言中的各类表达式时尤为有效。不少编译程序中都使用这种方法分析表达式。算符优先分析法就是仿照算术表达式的运算过程而提出的一种自底向上的语法分析方法。其基本思想是：首先规定算符，这里是文法的终极符之间的优先关系，然

2、后根据这种优先关系，通过比较相邻算符的优先次序来确定句型中的“句柄”，然后进行归约。算符优先分析法的关键：算符优先分析法的关键就是寻找当前句型中的最左素短语，并归约它。关键字：小于、大于、等于、句柄、归约、一、对表达式文法G E构造算符优先关系表。计算算符优先只针对于终结符，终结符之间的优先关系有三种，在计算优先关系之前我们先定义两个集合，对于任意两个终结符（a,b）FIRSTVT（B）=b|B=b或B=Cb,其中表示V中的符号串。LASTVT（B）=a|B=a或B=aC三种优先关系：（1）等于关系:可直接查看产生式的右部,对如下形式的产生式A-ab A- aBb则有a=b成立。（2）小于关系

3、：求出每个非终结符B的FIRSTVT（B）， 观察如下形式的产生式A-aB对每一bFIRSTVT(B)有ab成立（3）大于关系：计算每个非终结符B的LASTVT（B），观察如下形式的产生式A-Bb对每一aLASTVT(B)有ab成立表达式文法G E：E# E #E E + Q | QQ Q - T | TT T* F | FF F/ MMM M PPP ( E )i根据上面的规则手工构造上述文法的算符优先表如下：+-*/（）i#+-*/（=）i#=package .op.core;/* * 简单表达式文法G E构造算符优先关系表。 * E# E # * E E + Q | Q * Q Q -

4、T | T * T T * F | F * F F / MM * M M PP * P ( E )i * author */public class PriorityTable private static char table = / + * / i ( ) # , , , , , , , , , , , , , , , , , , , , , $, $, , , , / i , , , , , =, $, , , , $, $, , , , / ) , , , , , $, =, , , , , , , , / ; / 算符优先表/* * 判断一个符号在算符优先表中位置 * * param

5、 c * return */private static int judgePriority(char 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 pri

6、ority;/* * 判断两个算术符的优先级 * * param m * 为符号栈的栈顶元素 * param n * 为当前输入算术符 * return */public static char getPriority(char m, char n) return PriorityTable.tablejudgePriority(m)judgePriority(n);二、根据算符优先表用栈结构来实现算符优先分析设置两个栈：存放运算符的OPTR栈和存放操作数或运算结果的OPND栈。具体算法描述如下：（1）首先置操作数OPND栈为空栈，将#入运算符OPTR栈。（2）依次读入表达式中每个单词，若是操

7、作数则进OPND栈，若是运算符则转（3）。（3）当前设读入的运算符为2，查找算符优先关系表，比较2与OPTR栈顶元素1 ：若12,则2进OPTR栈，转（2）； 若12, 如2为#，则分析成功，否则OPTR栈顶元素1出栈，并转（2）；若12，则出栈OPND栈顶元素存放到b，又出栈其新栈顶元素存放到a，再出栈OPTR栈顶元素至t，进行运算r=a t b (t为运算符)，并将结果r存入栈OPND后转（2）；（4）若1和2之间无优先关系，则报错。public class OperatorPriority private Stack optrStack; /符号栈private Stack opndSt

8、ack; /操作数栈private String input; /键盘输入字符串/* * 构造函数 * param input */public 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(floa

9、t a, float b, char op) BigDecimal da = new BigDecimal(Float.toString(a); 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.R

10、OUND_HALF_UP).floatValue(); /除不尽的情况取7位精确值。case :return db.pow(int)a).floatValue();return 0;/* * 判断是否为操作符 * param ch 被判断字符 * return 布尔值 */public boolean isOperator(char ch) if (ch = + | ch = - | ch = * | ch = / | ch = (| ch = ) | ch = #|ch=)return true;elsereturn false;/* * 扫描字符串，判断是否对应文法，并计算出结果 * re

11、turn 计算结果 * throws Exception 如果不符合文法，或者除数等于0，都将抛出异常 */public String scanner() 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) / 需要进行运

12、算符的比较if (!optrStack.isEmpty() if (PriorityTable.getPriority(optrStack.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().

13、charValue(), exppostion.charAt(0) = =) optrStack.pop();if (exppostion.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();三、分析归约流程图：Y

14、NYNYNYNYNYNNYYN置初值K：=1，SK：=#当前输入符读入aSK VTJ:=kJ:=k-1SjaSK a?Q:= SjJ:=j-1Sj-1 VTJ:=j-2SjQSj = a ?Sj =#检查是否正常结束K:=k+1Sk = a出错出错结束Sj+1SK归约为NK:=j+1 SK:=N四、运行从键盘输入表达式串，利用算符优先法求出其值，如输入表达式有错，则给出报错提示。表达式以“#”结尾。从键盘输入句子：package .op.util;import java.io.BufferedReader;import java.io.IOException;import java.io.In

15、putStreamReader;public class IOUtil /* * 得到从键盘输入的字符串 * return 字符串 */ public static String getStringFromKeyBoard() try BufferedReader reader=new BufferedReader(new InputStreamReader(System.in); System.out.print(请输入一个表达式以#号结束：); String str=reader.readLine(); /获取字符串 / System.out.println(您输入的字符串是：+str);

16、 return str; catch (IOException e) e.printStackTrace(); return null; 五、测试1、句子前有空格符2、综合所有文法的句子3不以#号结束的句子4、加减按从左至右5、先乘后减6、有括号的先算括号里面的7、乘方的优先级大于除法的8、先乘方后乘除9、乘除按从左至右法则10、输入串含有不是指定文法的句子测试人欧垚测试时间2010-06-27错误个数3序号路径输入输出实际结果1在句子前面输入一个空格符号（6-3+52*2/10）/2#4.0您输入的表达式（6-3+52*2/10）/2#有误2一个包含所有文法的句子（6-3+52*2/10）/

17、2#4.04.03不以#号结束的句子3+4+512.0您输入的表达式3+4+5有误4先减后加6-3+2#5.05.05先加后减3+4-2#5.05.06先乘后减6-3*2#0.00.07有括号先算括号里面的(6-3)*2#6.06.08乘方的优先级最大25/52#1.01.09先乘方再从左至右3*2/62#0.16666670.166666710先除后乘25/5*2#10.010.011先乘后除3*2/2#3.03.012输入串含有不是指定文法的句子3+2-2*2-(3-2)#2.0您输入的表达式3+2-2*2-(3-2)#有误六、参考文献：1、黄贤英,贞 ,全利; HYPERLINK :/

18、cnki .cn/Article/CJFDTOTAL-CQGY200503030.htm%09%09%09%09%09%09%09%09%09%09%09%09%09 t _blank “编译原理”课程的地位与教改思路J;科技学院学报(社会科学版);2005年03期2、素琴，吕映芝，维杜，戴桂兰; 编译原理（第二版）;清华大学;2009年5月第12次印刷3、王雷，志成，周晶 ； HYPERLINK :/d.wanfangdata .cn/ExternalResource-syjsygl200912043%5e3.aspx 编译原理课程设计；20054、期刊论文 HYPERLINK :/d.wa

19、nfangdata .cn/Periodical_gdgydxxb-shkxb2005z1047.aspx 浅谈编译原理课程教学 - 工业大学学报(社会科学版)2005,5附加代码：package .op.core;import java.math.BigDecimal;import java.util.Stack;import .op.util.StringUtil;import .op.util.IOUtil;public class OperatorPriority private Stack optrStack; /符号栈private Stack opndStack; /操作数栈pr

20、ivate String input; /键盘输入字符串/* * 构造函数 * param input */public 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

21、, char op) BigDecimal da = new BigDecimal(Float.toString(a); 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

22、).floatValue(); /除不尽的情况取7位精确值。case :return db.pow(int)a).floatValue();return 0;/* * 判断是否为操作符 * param ch 被判断字符 * return 布尔值 */public boolean isOperator(char ch) if (ch = + | ch = - | ch = * | ch = / | ch = (| ch = ) | ch = #|ch=)return true;elsereturn false;/* * 扫描字符串，判断是否对应文法，并计算出结果 * return 计算结果 *

23、throws Exception 如果不符合文法，或者除数等于0，都将抛出异常 */public String scanner() 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 (!op

24、trStack.isEmpty() if (PriorityTable.getPriority(optrStack.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(),

25、 exppostion.charAt(0) = =) optrStack.pop();if (exppostion.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

26、args */public static void main(String args) OperatorPriority 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(您输入的表达式 +

27、 op.input + 有误!);package .op.core;/* * 简单表达式文法G E构造算符优先关系表。 * E# E # * E E + Q | Q * Q Q - T | T * T T * F | F * F F / MM * M M PP * P ( E )i * author */public class PriorityTable private static char table = / + * / i ( ) # , , , , , , , , , , , , , , , , , , , , , $, $, , , , / i , , , , , =, $, ,

28、, , $, $, , , , / ) , , , , , $, =, , , , , , , , / ; / 算符优先表/* * 判断一个符号在算符优先表中位置 * * param c * return */private static int judgePriority(char 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;br

29、eak;case ):priority = 5;break;case #:priority = 6;break;case :priority = 7;break;return priority;/* * 判断两个算术符的优先级 * * param m * 为符号栈的栈顶元素 * param n * 为当前输入算术符 * return */public static char getPriority(char m, char n) return PriorityTable.tablejudgePriority(m)judgePriority(n);package .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