tablemaker.java

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

/**
 * <p>Title: </p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2006</p>
 * <p>Company: </p>
 * @author not attributable
 * @version 1.0
 */
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.io.*;
import java.util.*;
//产生规约动作的产生式
class Formula{ //一条产生式
   int number; //序号
   int right; //左边文法符号
   LinkedList left; //右边符号串
   LinkedList motionList; //语义动作
   int motion; // 归约动作, -1无效
   Formula(int number, int right){
      this.number = number;
      this.right = right;
      left = new LinkedList();
      motionList = new LinkedList();
      motion = -1;
   }

   void add(int a){
      left.add(new Integer(a));
   }

   void addMotion(int a){
      motionList.add(new Integer(a));
   }

   int get(int i){
      return((Integer)left.get(i)).intValue();
   }

   int getMotion(int i){
      return((Integer)motionList.get(i)).intValue();
   }

   int size(){
      return left.size();
   }
}
//产生移近动作的产生式
class LRItem{
   int number; //产生式序号
   int division; //点的位置, the index of the last sign before '.', division = -1 when A->.a
   LinkedList searchString; //向前搜索串,-1 means '#'
   int motion = -1;
   LRItem(int number, int division){
      this.number = number;
      this.division = division;
      searchString = new LinkedList();
   }

   void add(int a){
      searchString.add(new Integer(a));
   }

   void addAll(LinkedList a){
      int i;
      for(i = 0; i < a.size(); i++){
         Integer tInt = (Integer)a.get(i);
         if(!searchString.contains(tInt)){
            searchString.add(tInt);
         }
      }
   }

   boolean isContain(LRItem item){
      if(this.division != item.division || this.number != item.number){
         return false;
      }
      if(this.size() < item.size()){
         return false;
      }
      int i;
      for(i = 0; i < item.size(); i++){
         int a = item.get(i);
         if(!this.contains(a)){
            return false;
         }
      }
      return true;
   }

   boolean isEqual(LRItem item){
      if(this.division != item.division || this.number != item.number){
         return false;
      }
      int i;
      if(this.size() != item.size()){
         return false;
      }
      for(i = 0; i < this.size(); i++){
         int a = this.get(i);
         if(!item.contains(a)){
            return false;
         }
      }
      return true;
   }

   int get(int a){
      return((Integer)searchString.get(a)).intValue();
   }

   int getFirst(){
      return((Integer)searchString.getFirst()).intValue();
   }

   int size(){
      return searchString.size();
   }

   boolean contains(Integer a){
      return searchString.contains(a);
   }

   boolean contains(int a){
      return searchString.contains(new Integer(a));
   }

   LRItem(int number, int division, LinkedList searchString){
      this.number = number;
      this.division = division;
      this.searchString = searchString;
   }
}

class Tools{//产生LALR1分析表
   LinkedList formulaSet; //contains Formulas
   Tools(LinkedList formulaSet){
      this.formulaSet = formulaSet;
   }

   int isContainItemCore(LinkedList a, LRItem b){
      int i;
      for(i = 0; i < a.size(); i++){
         LRItem t = (LRItem)a.get(i);
         if(t.division == b.division && t.number == b.number){
            return i;
         }
      }
      return -1;
   }

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

   int findSameCoreSet(LinkedList c, LinkedList itemSet){
      int i;
      for(i = 0; i < c.size(); i++){
         LinkedList tar = (LinkedList)c.get(i);
         boolean temp = this.isSameCore(tar, itemSet);
         if(temp){
            return i;
         }
      }
      return -1;
   }

   LinkedList addItemSet(LinkedList c, LinkedList itemSet){
      int i;
      for(i = 0; i < c.size(); i++){
         LinkedList tar = (LinkedList)c.get(i);
         LinkedList temp = this.combination(tar, itemSet);
         if(temp != null){
            c.set(i, temp);
            return c;
         }
      }
      c.add(itemSet);
      return c;
   }

   LinkedList combination(LinkedList itemSet1, LinkedList itemSet2){
      if(itemSet1.size() != itemSet2.size()){
         return null;
      }
      int i;
      LinkedList temp = new LinkedList();
      for(i = 0; i < itemSet1.size(); i++){
         LRItem tItem = (LRItem)itemSet1.get(i);
         int index;
         if((index = this.isContainItemCore(itemSet2, tItem)) == -1){
            return null;
         }
         else{
            LRItem t1 = (LRItem)itemSet2.get(index);
            t1.addAll(tItem.searchString);
            itemSet2.set(index, t1);
         }
      }
      return itemSet2;
   }

   boolean isSameCore(LinkedList itemSet1, LinkedList itemSet2){
      if(itemSet1.size() != itemSet2.size()){
         return false;
      }
      int i;
      for(i = 0; i < itemSet1.size(); i++){
         LRItem tItem = (LRItem)itemSet1.get(i);
         if(this.isContainItemCore(itemSet2, tItem) == -1){
            return false;
         }
      }
      return true;
   }

   LinkedList addNewItem(LinkedList target, LRItem item){
      int i;
      for(i = 0; i < target.size(); i++){
         LRItem temp = (LRItem)target.get(i);
         if(item.division == temp.division && item.number == temp.number){
            temp.addAll(item.searchString);
            target.set(i, temp);
            return target;
         }
      }
      target.add(item);
      return target;
   }

   LinkedList CLOSURE(LinkedList itemSet){
      LinkedList target = new LinkedList(itemSet);
      int i;
      for(i = 0; i < target.size(); i++){
         LRItem item = (LRItem)target.get(i);
         Formula f = (Formula)formulaSet.get(item.number);
         if(item.division + 1 == f.size()){
            continue;
         }
         if(item.division == -1 && f.right == f.get(0)){
            continue;
         }
         int sign = f.get(item.division + 1);
         if(item.division + 2 == f.size()){
            Formula t;
            int j;
            for(j = 0; j < formulaSet.size(); j++){
               t = (Formula)formulaSet.get(j);
               if(t.right == sign){
                  LRItem tItem = new LRItem(t.number, -1,
                                            new LinkedList(item.searchString));
                  tItem.motion = item.motion;
                  target = this.addNewItem(target, tItem);
               }
            }
         }
         else{
            int nextSign = f.get(item.division + 2);
            LinkedList terminal = FIRST(nextSign);
            int j;
            Formula t;
            for(j = 0; j < formulaSet.size(); j++){
               t = (Formula)formulaSet.get(j);
               if(t.right == sign){
                  int k;
                  LRItem tItem = new LRItem(t.number, -1,
                                            terminal);
                  tItem.motion = item.motion;
                  target = this.addNewItem(target, tItem);
               }
            }
         }
      }
      return target;
   }

   LinkedList getJSet(LinkedList itemSet, int sign){
      LinkedList jSet = new LinkedList();
      int i;
      for(i = 0; i < itemSet.size(); i++){
         Formula t;
         LRItem item = (LRItem)itemSet.get(i);
         t = (Formula)formulaSet.get(item.number);
         if(item.division + 1 < t.size() && t.get(item.division + 1) == sign){
            LRItem tItem = new LRItem(t.number, item.division + 1,
                                      new LinkedList(item.searchString));
            tItem.motion = t.getMotion(item.division + 1);
            jSet = this.addNewItem(jSet, tItem);
         }
      }
      return jSet;
   }

   LinkedList GO(LinkedList itemSet, int sign){
      //LinkedList jClousure;
      LinkedList jSet = new LinkedList();
      int i;
      for(i = 0; i < itemSet.size(); i++){
         Formula t;
         LRItem item = (LRItem)itemSet.get(i);
         t = (Formula)formulaSet.get(item.number);
         if(item.division + 1 < t.size() && t.get(item.division + 1) == sign){
            LRItem tItem = new LRItem(t.number, item.division + 1,
                                      item.searchString);
            tItem.motion = t.getMotion(item.division + 1);
            jSet = this.addNewItem(jSet, tItem);
         }
      }
      return CLOSURE(jSet);
   }

   LinkedList FIRST(int sign){
      LinkedList terminal = new LinkedList();
      Formula t;
      boolean isTerminal = true;
      int i;
      for(i = 0; i < formulaSet.size(); i++){
         t = (Formula)formulaSet.get(i);
         int firstSign = t.get(0);
         if(t.right == sign){
            isTerminal = false;
            if(firstSign != sign){
               LinkedList temp = FIRST(firstSign);
               int j;
               for(j = 0; j < temp.size(); j++){
                  Integer tInt = (Integer)temp.get(j);
                  if(!terminal.contains(tInt)){
                     terminal.add(tInt);
                  }
               }
            }
         }
      }
      if(isTerminal){
         terminal.add(new Integer(sign));
      }
      return terminal;
   }
}

public class TableMaker{//输出LALR1分析表
   LinkedList formulaSet;
   LinkedList tSignSet; //终结符 -1 means '#'
   LinkedList untSignSet; //非终结符
   LinkedList c; //项目集族
   Integer GOTO[][];
   String ACTION[][];
   Tools tools;
   public TableMaker(){
      formulaSet = new LinkedList();
      untSignSet = new LinkedList();
      tSignSet = new LinkedList();
      c = new LinkedList();
   }

   int getStateNum(){
      return c.size();
   }

   Integer[][] getGOTO(){
      return GOTO;
   }

   String[][] getACTION(){
      return ACTION;
   }

   LinkedList getFormulaSet(){
      return formulaSet;
   }