generation.java

实现2型文法的化简包括：无符号和无用产生式的删除、ε-产生式的消除、单产生式的消除算法实现

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package languageclear;
/**
 *
 * @author L^_^
 */
public class Generation{
  static  final char Emp='ε';
    
        char []Vn;
      int intVn=0;
        char []Vt;
       int intVt=0;
        Production []Par;
      int intPar=0;
       char Start='S';
       
       char []W;
     int intw=0;
       final int  Maxlength=25;
       Generation(){
        Vn=new char[Maxlength];
        Vt=new char[Maxlength];
        Par=new Production[Maxlength];
        W=new char[Maxlength];
         for(int i=0;i<Maxlength;i++)
            Par[i]=new Production();
       }
       
       Generation(int intVn_val,int intVt_val,int intPar_val){
         Vn=new char[intVn_val];
         W=new char[intVn_val];
        Vt=new char[intVt_val];  
        Par=new Production[intPar_val];
        for(int i=0;i<intPar_val;i++)
            Par[i]=new Production();
     
       }
       
       void setStart(char start_val){
            Start=start_val;
       }
       
      public  void addProduction(Production p_val){
           if((Par.length-intPar)<1)
          {
                Production []p=Par.clone();
                Par=new Production[10+intPar];
                this.addProduction(p);
          }
            Par[intPar]=p_val.copyProductionTo();
            intPar++;
       }
      
      public  void addProduction(char x_val,String y_val){
            if((Par.length-intPar)<1)
          {
                Production []p=Par.clone();
                Par=new Production[10+intPar];
                this.addProduction(p);
          }
            Par[intPar].x=x_val;
            if(y_val.length()==1&&this.Contain(y_val.toCharArray(), '^'))
                Par[intPar].y=Emp+new String();
            Par[intPar].y=y_val;
                intPar++;
       }
      
      public  void addProduction(Production []par){
          if(par.length>(Par.length-intPar))
          {
                Production []p=Par.clone();
                Par=new Production[par.length+intPar];
                this.addProduction(p);
          }
            for(int i=0;i<par.length;i++)
            {
                Par[i].x=par[i].x;
                Par[i].y=par[i].y;
            }
            intPar=par.length;
      }
  ////////////////////////////////////////////////////////////     
       public void addVn(char vn){
            Vn[intVn]=vn;
            intVn++;
       }
       public void addVn(char []vn){
            for(int i=0;i<vn.length;i++)
                Vn[i]=vn[i];
            intVn=vn.length;
       }
       
     public   void addVt(char vt){
            Vt[intVt++]=vt;
      }
     public void addVt(char []vt){
            for(int i=0;i<vt.length;i++)
                Vt[intVt++]=vt[i];
            intVt=vt.length;
     }
     public boolean Contain(char []FaStr,String Str){//判断Str是否属于FaStr的正闭包
         char []temp=Str.toCharArray();
         boolean boo=true;
        for(int i=0;i<temp.length;i++)
        {
               boo=boo&&this.Contain(FaStr, temp[i]); 
        }
        return boo;
     } 
     
     public boolean Contain(char FaStr[],char ch){//判断ch是否属于FaStr
        for(int i=0;i<FaStr.length;i++)
        {
               if(FaStr[i]==ch)
                   return true;
        }
        return false;
     }
     
     public void  replaceEmp(){
        char []tmp;
        for(int i=0;i<intPar;i++)
        {
            tmp=Par[i].y.toCharArray();
            for(int j=0;j<tmp.length;j++)
               if(tmp[j]=='^')
                   tmp[j]=Emp;
            Par[i].y=new String(tmp);
        }
        for(int i=0;i<intVt;i++)
        {
            if(Vt[i]=='^')
                Vt[i]=Emp;
        }
     }
     
     public String charsToString(char ch[]){
        String Str=new String();
        for(int i=0;i<ch.length;i++)
            Str=Str+ch[i];
            return Str;
     }
     
     public char [] stringToChars(String Str)
     {
         char tmpChars[];
         tmpChars=new char[Str.length()];
        for(int i=0;i<Str.length();i++)
        {
            tmpChars[i]=Str.charAt(i);
        }
         return tmpChars;
     }
     
     public char [] deleteEmp(char []Vt){
         int k=0;
         char newVt[]=new char[intVt-1];
        for(int i=0;i<intVt;i++)
        {
            if(Vt[i]!=Emp)
            {
                newVt[k++]=Vt[i];
            }
        }
         intVt--;
         return newVt;
     }
     
     public char [] addEmp(char []Vt){
         int i=0;
         char newVt[]=new char[intVt+1];
        for(i=0;i<intVt;i++)
        {
              newVt[i]=Vt[i];
        }
         newVt[i]=Emp;
         intVt++;
         return newVt;
     }
 
//=========================以上为基本函数==================
     
//=========================一下为各算法的实现==============
     void algorithm2_1(){//算法2.1的实现
        char []Vn1=new char[Maxlength];
        Production []tmpPar=new Production[Maxlength];
        int n=0,p=0;
       for(int i=0;i<intPar;i++)
       {
           if(this.Contain(Vt, Par[i].y)||(Par[i].y.length()==1&&Par[i].y.charAt(0)==Emp))
           {
               Vn1[n]=Par[i].x;    //将直接可终止符号加入Vn1
               n++;
           }
       }
        int change=0;
      while(change!=n)
      {
          change=n;
          for(int i=0;i<intPar;i++)
          {
              char []temp=Par[i].y.toCharArray();
              boolean boo=true;
              for(int j=0;j<temp.length;j++)
              {
                  boo=boo&&(this.Contain(Vt, temp[j])||this.Contain(Vn1,temp[j]));//判断A-》X1X2X3……Xn中是否每个Xi都属于Vt或者Vn1
              }
              if(boo)
                  if(!this.Contain(Vn1, Par[i].x)) 
                  {
                      Vn1[n]=Par[i].x;      //将间接可终止符号加入Vn1
                      n++;
                  }
          }
      }
       for(int i=0;i<intPar;i++) 
       {
           if(this.Contain(Vn1, Par[i].x))
           {
               char []temp=Par[i].y.toCharArray();
               boolean boo=true;
               for(int j=0;j<temp.length;j++)
                   boo=boo&&(this.Contain(Vt, temp[j])||this.Contain(Vn1,temp[j])||temp[j]==Emp);//判断B-》Y1Y2Y3……Yn中的每一个Y是否属于Vn1并Vt
               if(boo)
               {
                       tmpPar[p]=Par[i].copyProductionTo();p++;
               }
           }
       }
       Vn=Vn1.clone();
       intVn=n;
       Par=tmpPar.clone();
       intPar=p;
     }
     
     void algorithm2_2(){//算法2.2的实现
        char []Vn2=new char[Maxlength];
        int n=0;
        char []Vt2=new char[Maxlength];
        int t=0;
        Production []tempPar=new Production[Maxlength];
        int p=0;
        Vn2[0]=Start;n++;//将开始符号置于Vn2
       int change=0;
        while(change!=n)
        {   
            change=n;
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<intPar;j++)
                {
                    if(this.Contain(Vn2, Par[j].x))
                    {
                        char []temp=Par[j].y.toCharArray();
                        for(int k=0;k<temp.length;k++)
                        {
                             if(this.Contain(Vt, temp[k])&&!this.Contain(Vt2, temp[k]))
                                 {Vt2[t]=temp[k];t++;}
                             if(this.Contain(Vn, temp[k])&&!this.Contain(Vn2, temp[k]))
                                {Vn2[n]=temp[k];n++;}
                         }
                     }
                 }
           }   
        }
        boolean boo=true;
        for(int i=0;i<intPar;i++)
        {
            if(this.Contain(Vn2, Par[i].x))
            {
                boo=true;
                char []temp=Par[i].y.toCharArray();