表达式计算器的设计与实现-白红宇

表达式计算器的设计与实现

阅读量：4688 次

发布时间：2019-06-09

本文共 7671 字，大约阅读时间需要 25 分钟。

一、 字符集定义

1． <字符> → <数字>│<单界符>│.

2． <数字> → 0│<非零数字>

3． <非零数字>→ 1│2│…│9

4． <单界符> →<运算符>│(│)

5． <运算符> → +│-│*│/

二、 单词集定义

6．<单词> → <单界符>│<常数>

7．<常数> → <无符号整数>│<无符号浮点数>

8．<无符号整数> →0│<非零整数>

9．<非零整数> → <非零数字> <数字串>

10．<数字串> → <数字> <数字串>│NULL

11．<无符号浮点数> →<无符号整数>. <数字> <数字串>

三、 数据类型定义

12．<类型> → int│double

四、 表达式定

13．<算术表达式> → <项> + <算术表达式>│<项> - <算术表达式>│<项>

14．<项> → <因子> * <项>│<因子> / <项>│<因子>

15．<因子> → <算数量>│- <因子>

16．<算术量> → <常数>│（ <算术表达式> ）

E T E E T T

<算术表达式> → <项> + <算术表达式>│<算术表达式>-<项>│<项>

T F T F T F

<项> → <因子> * <项>│<因子> / <项>│<因子>

F i F

<因子> → <常数>│- <因子>

核心代码：

（词法分析类Build.java）

1 package util;  2   3   4   5   6 public class Build {  7   //下标   8   private int i;  9    10   //存储读取的字符 11   private char ch; 12    13   //将输入自符串转为字符数组 14   private char[] input_array; 15    16   //截取存储字符串 17   private String s; 18   //记录上一次运算符出现的位置 19   private int lastSingle; 20   private String input; 21   public Build(String input){ 22       this.input_array = input.toCharArray(); 23       this.input=input; 24       ch=input_array[0]; 25       this.i=0; 26       this.lastSingle=-1; 27   } 28    29    30    31   //词法分析函数 32   public int getsym(){ 33        34        35        36     //i=0时，首字符为小数点,+,-，*，/抛出错误 37     if(BuildUtils.throwFirstSigleError(ch)){ 38     //将此次非法标识符出现的位置存储到lastSingle 39     lastSingle=0; 40     i++; 41     } 42      43      44      while(i
     
      ='0'&&ch<='9'){ //检测是否为数字，如果为数字测需要分段存储数字串 54               if(ch=='0'){
   //如果为0 55                   i++; 56                   if(i
      
       ='0'&&ch<='9'){
   //取下一个字符到ch//小数点后面的数字 67                               i++; 68                               if(i
       
        ='0'&&ch<='9'){ 73                                   while(ch>='0'&&ch<='9') {     74                                       i++; 75                                       if(i
        
         ='0'&&ch<='9'){106                       while(ch>='0'&&ch<='9') {    107                           i++;108                           if(i
         
          ='0'&&ch<='9'){
   //取下一个字符到ch//小数点后面的数字122                               123                               i++;124                             if(i
          
           ='0'&&ch<='9'){130 while(ch>='0'&&ch<='9') { 131 i++;132 if(i
           
            ='0'&&ch<='9'){ //取下一个字符到ch//小数点后面的数字165 166 i++;167 if(i
            
             ='0'&&ch<='9'){173 while(ch>='0'&&ch<='9') { 174 i++;175 if(i

（语法法分析类：Analyze.java）

package util;import java.util.ArrayList;import bean.Node;public class Analyze {        private Node particularNode=new Node(null, "#", null, null);    private ArrayList
     
       inputStack=new ArrayList
      
       ();//输入串    private ArrayList
       
         inputQueue=new ArrayList
        
         ();//输入栈    private ArrayList
         
           singleQueue=new ArrayList
          
           ();//符号栈 private ArrayList
           
             analyzeQueue=new ArrayList
            
             ();//分析栈(状态栈) private static Analyze analyze=null; private int statuSum=16;//该文法涉及了16个状态 private int Action=8;//8个动作 private int Turn=3;//3个转移 public static boolean lastAnayScuccess=true; int act = 0 ;//动作 int turn=0;//转移 int status=0;//初始状态 int actionIndex=-1; int turnIndex=-1; int index;//输入串的字符下标 int SUCCESS=0; int FAILE=1; int sindex; int aindex; Node reduceNode = null;//规约后压入符号栈的单词结点 private Analyze(){ this.inputQueue.add(particularNode);//输入串在进行语法分析前要先将结束符压入栈底 this.singleQueue.add(particularNode);//符号栈初始状态下为# this.analyzeQueue.add(0); //result = new StringBuilder(); } public static Analyze getAnalyze(){ if(analyze==null){ analyze=new Analyze(); } return analyze; } public void addNode(Node node){ //初始化输入串 inputStack.add(node); } public void shiftNode(Node node){ //将待匹配的node移进符号栈 singleQueue.add(node); } public void addNodeToSQ(Integer Istatus){ //状态栈添加状态 analyzeQueue.add(Istatus); } public int divceProgram(){ //驱动程序 exchange(inputStack, inputQueue); index=inputQueue.size()-1; int ti=1;//t1,t2,t3... if(lastAnayScuccess){ //在上一步词法分析没有出错的情况下往下进行语法分析 System.out.println("开始进行语法分析"); while(true){ //从输入串的首单词开始判断是否移入符号栈 //该单词节点执行的状态跳转 while(turnIndex
             
              =0){ for(int j=0;j
              
               0){ status=turn;//状态跳转到goto表true所对应的值 turnIndex=-1; index--;//跳转到turn步骤之后匹配下一个输入单词 System.out.println("输入串剩余长度"+index); break; }else{ //等于0时出错 ProcError(); return FAILE; } }else { break; } } //该单词节点执行的动作 while(actionIndex
               
                0){ for(int i=1;i
                
                 0){ //进行移进操作，然后转向状态act //移进操作，将待分析的单词压入符号栈 singleQueue.add(inputQueue.get(index)); analyzeQueue.add(act); System.out.println(inputQueue.get(index)+"加入符号栈"); System.out.println(act+"加入状态栈"); System.out.println("符号栈："+singleQueue.toString()); System.out.println("状态栈："+analyzeQueue.toString()); status=act; actionIndex=-1; index--; continue; }else{ //进行规约操作 //此时act值小于0，取绝对值之后即为规约所用的文法产生式序号Math.abs(act); for(P p:ParserType.pset){ //寻找产生式 if(p.getNum()== Math.abs(act)){ int noZeroNum=0; aindex=analyzeQueue.size()-1; sindex=singleQueue.size()-1; ArrayList
                 
                   reduceNodeList=new ArrayList
                  
                   ();//规约中间结果存储列表 // ArrayList
                   
                     saveNodeList=new ArrayList
                    
                     ();//规约中间变量存储列表 StringBuilder result=new StringBuilder(); for(int i=0;i
                     
                      0){ //存储需要规约的单词 reduceNodeList.add(singleQueue.get(sindex)); System.out.println(singleQueue.get(sindex)+"被规约"); //状态栈和符号栈要移除的结点 singleQueue.remove(singleQueue.get(sindex)); if(sindex>0) sindex--; analyzeQueue.remove(analyzeQueue.get(aindex));//符号栈和状态的操作需同步 if (aindex>0) aindex--; noZeroNum--; } V ch=p.getLeftV();//获取规约后的单词， int leftVindex=0; //找到在goto表对应的turnIndex值 for(V v:ParserType.vn){ if(!v.equals(ch)){ leftVindex++; }else break; } for(String str:p.getRigthExp()){ result.append(str); } String rigthExp=result.toString(); System.out.println("rigthExp："+rigthExp); if(rigthExp.contains("+")||rigthExp.contains("-")||rigthExp.contains("*")||rigthExp.contains("/")){ //规约后的单词四元式 Node saveNode=new Node(p.getRigthExp()[1].toString(),reduceNodeList.get(2).getValue().toString(), reduceNodeList.get(0).getValue().toString(),"t"+(ti++)); // saveNodeList.add(saveNode); //输出中间四元式 System.out.println(saveNode.toString()); //将单词串转换成真实的字符运算并用reduceNode存储中间结果 switch(p.getRigthExp()[1].toString()){ case "+": reduceNode=ReduceTools.reduceByAdd(reduceNodeList, p);break; case "-": reduceNode=ReduceTools.reduceByJian(reduceNodeList, p); break; case "*": reduceNode=ReduceTools.reduceByCheng(reduceNodeList, p);break; case "/": reduceNode=ReduceTools.reduceByChu(reduceNodeList, p); break; default: break; } }else if(rigthExp.contains("i")){ reduceNode=ReduceTools.reduceFromi(reduceNodeList, p); }else if(rigthExp.contains("(")&&rigthExp.contains(")")){ reduceNode=ReduceTools.reduceByKuoHao(reduceNodeList, p); }/*else if(rigthExp.contains("-F")){//F->-F reduceNode=ReduceTools.reduceByFu(reduceNodeList, p); }*/else{ //T->F//E->T//S->E reduceNode=ReduceTools.reduceFromOther(reduceNodeList, p); } singleQueue.add(reduceNode);//规约之后将中间结果压入符号栈 sindex++; status=ParserType.go[analyzeQueue.get(aindex)][leftVindex]; analyzeQueue.add(status);//向状态栈添加规约后的状态 aindex++; System.out.println(singleQueue.get(sindex)+"加入符号栈"); System.out.println(analyzeQueue.get(aindex)+"加入状态栈"); System.out.println("符号栈："+singleQueue.toString()); System.out.println("状态栈："+analyzeQueue.toString()); actionIndex=-1; break; } } //规约阶段涉及goto操作 } }else{ break; } } } }else{ WorldError(); } return 0; } private void ProcError() { // TODO Auto-generated method stub System.out.println("语法错误"); } private void WorldError() { // TODO Auto-generated method stub System.out.println("存在词法错误，无法进行语法分析"); } //栈数据倒灌 public void exchange(ArrayList
                      
                        list1,ArrayList
                       
                         list2){ for(int i=list1.size()-1;i>=0;i--){ list2.add(list1.get(i)); } } }