tablemaker.java

上海复旦大学计算机系学子写的JAVA版本编译原理LALR1完整分析表生成程序,Eclipse开发

   LinkedList getC(){
      return c;
   }

   void clearFormulaSet(){
      formulaSet.clear();
   }

   int getState(LinkedList itemSet){
      int i;
      for(i = 0; i < c.size(); i++){
         LinkedList t = (LinkedList)c.get(i);
         if(this.isContain(t, itemSet)){
            return i;
         }
      }
      return -1;
   }

   LinkedList getAllRight(LinkedList itemSet){
      int i;
      LinkedList allRight = new LinkedList();
      Tools tools = new Tools(formulaSet);
      LinkedList cItemSet = tools.CLOSURE(itemSet);
      for(i = 0; i < cItemSet.size(); i++){
         LRItem temp = (LRItem)cItemSet.get(i);
         Formula f = (Formula)formulaSet.get(temp.number);
         Integer r = new Integer(f.right);
         if(!allRight.contains(r)){
            allRight.add(r);
         }
      }
      return allRight;
   }

   void makeTable(){
      Tools tool = new Tools(formulaSet);
      ACTION = new String[c.size()][tSignSet.size()];
      GOTO = new Integer[c.size()][untSignSet.size()];
      int i, j;
      for(i = 0; i < c.size(); i++){
         for(j = 0; j < tSignSet.size(); j++){
            ACTION[i][j] = "err";
         }
      }
      for(i = 0; i < c.size(); i++){
         for(j = 0; j < untSignSet.size(); j++){
            GOTO[i][j] = new Integer( -1);
         }
      }
      for(i = 0; i < c.size(); i++){
         LinkedList itemCore = (LinkedList)c.get(i);
         LinkedList itemSet = tools.CLOSURE((LinkedList)c.get(i));
         int state;
         for(j = 0; j < itemSet.size(); j++){
            LRItem item = (LRItem)itemSet.get(j);
            Formula f = (Formula)formulaSet.get(item.number);
            if(item.division + 1 < f.size()){ //(1)
               Integer a = new Integer(f.get(item.division + 1));
               int index = tSignSet.indexOf(a);
               state = this.getState(tool.getJSet(itemSet, a.intValue()));
               if(index != -1){
                  System.out.println("in " + i + "th state of " + a + "is " +
                                     state);
                  output(tool.GO(itemSet, a.intValue()));
                  if(state != -1){
                     int v = item.motion;
                     String str = "";
                     if(v != -1){
                        str = v + "";
                     }
                     str = str.concat("s" + state);
                     ACTION[i][index] = str;
                  }
               }
            }
            else if(item.division + 1 == f.size()){
               int k;
               for(k = 0; k < item.size(); k++){
                  Integer a = new Integer(item.get(k));
                  state = item.number;
                  int index = tSignSet.indexOf(a);
                  if(index != -1){ 
                     ACTION[i][index] = "r" + state;
                  }
               }
            }
            if(f.right == 0 && item.division == 0 && item.contains( -1)){
               int index = tSignSet.indexOf(new Integer( -1));
               ACTION[i][index] = "acc";
            }
            if((state = this.getState(tool.getJSet(itemSet, f.right))) != -1){
               int index = untSignSet.indexOf(new Integer(f.right));
               if(index != -1){
                  GOTO[i][index] = new Integer(state);
               }
            }
         }
      }
   }

   void output(LinkedList itemSet){
      int i;
      //  System.out.println("***");
      for(i = 0; i < itemSet.size(); i++){
         LRItem tItem = (LRItem)itemSet.get(i);
         Formula f = (Formula)formulaSet.get(tItem.number);
         System.out.print(f.right + "->");
         int j;
         for(j = 0; j < f.size(); j++){
            if(tItem.division + 1 == j){
               System.out.print(". ");
            }
            System.out.print(f.get(j) + " ");
         }
         System.out.print("^^" + tItem.searchString + " \n");
      }
   }

   

   boolean isEq(LinkedList a, LinkedList b){
      int j;
      if(a.size() != b.size()){
         return false;
      }
      for(j = 0; j < b.size(); j++){
         LRItem t = (LRItem)b.get(j);
         if(!tools.isContainItem(a, t)){
            return false;
         }
      }
      return true;
   }

   boolean inItemSet(LinkedList target, LRItem item){
      int i;
      for(i = 0; i < target.size(); i++){
         LRItem t = (LRItem)target.get(i);
         if(t.isContain(item)){
            return true;
         }
      }
      return false;
   }

   boolean isContain(LinkedList target, LinkedList itemSet){
      int j;
      if(target.size() != itemSet.size()){
         return false;
      }
      for(j = 0; j < itemSet.size(); j++){
         LRItem t = (LRItem)itemSet.get(j);
         if(!this.inItemSet(target, t)){
            return false;
         }
      }
      return true;
   }

   boolean isInC(LinkedList itemSet){
      int i;
      for(i = 0; i < c.size(); i++){
         LinkedList t = (LinkedList)c.get(i);
         if(isContain(t, itemSet)){
            return true;
         }
      }
      return false;
   }

   void makeItemClosure(){
      c.clear();
      tools = new Tools(formulaSet);
      LinkedList iSet = new LinkedList();
      LRItem first = new LRItem(0, -1);
      first.add( -1);
      iSet.add(first);
      c.add(iSet);
      int i;
      for(i = 0; i < c.size(); i++){
         System.out.println(i + "!!!\n");
         LinkedList itemSet = tools.CLOSURE((LinkedList)c.get(i));
         output(itemSet);
         int j;
         int index = -2;
         for(j = 0; j < tSignSet.size(); j++){
            int sign = ((Integer)tSignSet.get(j)).intValue();
            LinkedList newItemSet = tools.getJSet(itemSet, sign);
            if(newItemSet.size() > 0){
               System.out.println(":::::");
               output(newItemSet);
            }
            if(newItemSet.size() > 0 && !this.isInC(newItemSet)){
               System.out.println("\nIN");
               index = tools.findSameCoreSet(c, newItemSet);
               System.out.println("index = " + index);
               if(index > 0){
                  LinkedList l = tools.combination((LinkedList)c.get(index),
                        newItemSet);
                  c.set(index, l);
                  if(index <= i){
                     break;
                  }
               }
               else{
                  c.add(newItemSet);
               }
               System.out.println("###");
               System.out.println();
            }
         }
         if(index > -1 && index <= i){
            i = index - 1;
            continue;
         }
         for(j = 0; j < untSignSet.size(); j++){
            int sign = ((Integer)untSignSet.get(j)).intValue();
            LinkedList newItemSet = tools.getJSet(itemSet, sign);
            if(newItemSet.size() > 0){
               System.out.println(":::::");
               output(newItemSet);
            }
            if(newItemSet.size() > 0 && !this.isInC(newItemSet)){
               System.out.println("\nIN");
               index = tools.findSameCoreSet(c, newItemSet);
               System.out.println("index = " + index);
               if(index > 0){
                  LinkedList l = tools.combination((LinkedList)c.get(index),
                        newItemSet);
                  c.set(index, l);
                  if(index <= i){
                     i = index - 1;
                     break;
                  }
               }
               else{
                  c.add(newItemSet);
               }
            }
         }
      }
   }

   LinkedList getTSign(){
      return tSignSet;
   }

   LinkedList getUTSign(){
      return untSignSet;
   }

   void getSignSet(){
      int i;
      for(i = 0; i < formulaSet.size(); i++){
         Formula f = (Formula)formulaSet.get(i);
         Integer tInt = new Integer(f.right);
         if(!untSignSet.contains(tInt)){
            untSignSet.add(tInt);
         }
      }
      for(i = 0; i < formulaSet.size(); i++){
         Formula f = (Formula)formulaSet.get(i);
         int j;
         for(j = 0; j < f.size(); j++){
            Integer tInt = new Integer(f.get(j));
            if(!untSignSet.contains(tInt) && !tSignSet.contains(tInt)){
               tSignSet.add(tInt);
            }
         }
      }
      tSignSet.add(new Integer( -1));
   }

   boolean readFormulaSet(String directory, String name){
      try{
         BufferedReader in = new BufferedReader(new FileReader(new File(
               directory,
               name)));
         String str;
         int index = 0;
         while((str = in.readLine()) != null){
            StringTokenizer parse = new StringTokenizer(str, " ");
            if(parse.countTokens() < 1){
               continue;
            }
            String tStr = parse.nextToken();
            int right = Integer.parseInt(tStr);
            Formula f = new Formula(index++, 0); //the second 0 means S'
            f.add(Integer.parseInt(tStr));
            f.addMotion(-1);
            formulaSet.add(f);
            while(parse.hasMoreTokens()){
               f = new Formula(index, right);
               tStr = parse.nextToken();
               while(!tStr.equals("-1")){
                  int sign = Integer.parseInt(tStr);
                  //       f.addWithMotion(sign);
                  if(sign >= 100){
                     f.motionList.removeLast();
                     f.addMotion(sign);
                  }
                  else{
                     f.add(sign);
                     f.addMotion( -1);
                  }
                  if(parse.hasMoreTokens()){
                     tStr = parse.nextToken();
                  }
                  else{
                     break;
                  }
               }
               if(f.size() != 0){
                  int m = f.getMotion(f.size() - 1);
                  if(m != -1){
                     f.motionList.removeLast();
                     f.addMotion( -1);
                     f.motion = m;
                  }
                  formulaSet.add(f);
                  index++;
               }
            }
            break;
         }
         while((str = in.readLine()) != null){
            StringTokenizer parse = new StringTokenizer(str, " ");
            if(parse.countTokens() < 1){
               continue;
            }
            String tStr = parse.nextToken();
            int right = Integer.parseInt(tStr);
            Formula f;
            while(parse.hasMoreTokens()){
               f = new Formula(index, right);
               tStr = parse.nextToken();
               while(!tStr.equals("-1")){
                  int sign = Integer.parseInt(tStr);
                  if(sign >= 100){
                     f.motionList.removeLast();
                     f.addMotion(sign);
                  }
                  else{
                     f.add(sign);
                     f.addMotion( -1);
                  }
                  if(parse.hasMoreTokens()){
                     tStr = parse.nextToken();
                  }
                  else{
                     break;
                  }
               }
               if(f.size() != 0){
                  int m = f.getMotion(f.size() - 1);
                  if(m != -1){
                     f.motionList.removeLast();
                     f.addMotion( -1);
                     f.motion = m;
                  }
                  formulaSet.add(f);
                  index++;
               }
            }
         }
         if(formulaSet.size() == 0){
            return false;
         }
         this.getSignSet();
         in.close();
         return true;
      }
      catch(Exception e){
         return false;
      }
   }
}