generation.java

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

                for(int j=0;j<temp.length;j++)
                {
                    boo=boo&&(this.Contain(Vt2, temp[j])||this.Contain(Vn2, temp[j])||temp[j]==Emp);
                }
                if(boo)
                    tempPar[p++]=Par[i].copyProductionTo();
            }
        }
        intVn=n;
        intVt=t;
        intPar=p;
        Vn=Vn2.clone();
        Vt=Vt2.clone();
        Par=tempPar.clone();
     }
     
     public void algorithm2_3(){//检查一个文法是否产生空符号窜  //算法2.3的实现
        for(int i=0;i<intPar;i++)
        {
             if(Par[i].y.charAt(0)==Emp)
                 {if(!this.Contain(W, Par[i].x))
                      W[intw++]=Par[i].x;
                 }
                 else
                     System.out.print(Par[i].y+"\n");
        }
        int t=0;
        while(t<intw)
        {
            t=intw;
            for(int j=0;j<intPar;j++)
            {
                if(this.Contain(W, Par[j].y))
                    if(!this.Contain(W,Par[j].x))
                        W[intw++]=Par[j].x;
            }
        }
     }
     
     public void algorithm2_4(){//算法2.4的实现
        if(this.Contain(Vt, Emp))
            Vt=this.deleteEmp(Vt);
         boolean boo=false;
         for(int i=0;i<intPar;i++)
            {
                if(this.Contain(this.stringToChars(Par[i].getY()), Start))//判断Start是否出现产生式的右边
                    boo=true;//出现则boo为true
            }
         if(!this.Contain(W, Start)||(this.Contain(W, Start)&&!boo))//e不属于LG
         {
            Production tmpar[];
            int tmpp=0;
            tmpar=new Production[Par.length];
            for(int i=0;i<tmpar.length;i++)
                tmpar[i]=new Production();
            for(int i=0;i<intPar;i++)
            {
                 int count=0;
                 for(int j=0;j<Par[i].y.length();j++)
                     if(this.Contain(W,Par[i].y.charAt(j)))//查看有多少个X属于W
                         count++;
                 System.out.print("count"+count+":"+count+"\n");
                 char [][] chars=new char[(int)Math.pow(2, count)][Par[i].y.length()];
                 
                 int kth=0;
                for(int j=0;j<Par[i].y.length();j++)
                {
                    char ch=Par[i].y.charAt(j);
                    if(this.Contain(W, ch))//如果Xi属于W
                    {
                        kth++;
                          int q=(int)Math.pow(2, kth-1);
                       for(int m=0;m<q;m++)
                           for(int n=0;n<j;n++)
                               chars[m+q][n]=chars[m][n];
                       for(int k=0;k<q;k++)
                           chars[k][j]=ch;
                    }
                    else if(this.Contain(Vt, ch)||(this.Contain(Vn, ch)))
                    {
                            for(int k=0;k<(int)Math.pow(2, kth);k++)
                                 chars[k][j]=ch;
                    }
                }
               
                /////添加P到P‘//////////////////////////////
               for(int k=0;k<Math.pow(2, count);k++)
               {
                    if(tmpp>=tmpar.length)
                    {
                        Production p[]=tmpar.clone();
                        tmpar=new Production[p.length+15];
                        for(int m=0;m<tmpar.length;m++)
                            tmpar[m]=new Production();
                        for(int m=0;m<p.length;m++)
                            tmpar[m]=p[m].copyProductionTo();
                    }
                    else
                    {
                        boolean boo1=false;
                        for(int m=0;m<chars[k].length;m++)//判断是否为全空的空串
                            if((int)chars[k][m]!=0)
                            {
                                boo1=true;break;
                            }
                        if(boo1)
                        {
                            tmpar[tmpp].x=Par[i].x;
                            tmpar[tmpp++].y=this.charsToString(chars[k]);//转换为字符串
                        }
                    }
               }
            }
            int count=0;
            
            for(int p=0;p<tmpar.length;p++)
            {
                boolean bo=false;
                 for(int q=0;q<count;q++)//判断tt是否已经在P1中
                     if(Par[q].isEqual(tmpar[p]))
                           {bo=true;break;}
                 if(!bo) Par[count++]=tmpar[p].copyProductionTo();
            }
            intPar=count;
            if(this.Contain(W, Start))
                this.addProduction(new Production(Start,""+Emp));
         }
        if(this.Contain(W, Start)&&boo)//Emp属于LG并且出现在产生式的右边
        {
           algorithm2_5();
        //   this.addProduction(new Production(Start,""+Emp));
        }
     }

     public void algorithm2_5(){//算法 2.5的实现
         char newStart='①';
         int n=intPar;
         char SS=Start;
         for(int i=0;i<n;i++)
         {
            if(Par[i].x==Start)
            {
                addProduction(new Production(newStart,Par[i].y));
            }
         }
         setStart(newStart);
         this.addVn(newStart);
         for(int i=0;i<intw;i++)
            if(W[i]==SS)
                W[i]=newStart;
         algorithm2_4();
     }
     
     public void algorithm2_6(){
        char Wi[]=new char[intVn];
        Production P1[]=new Production[Maxlength];
        int p=0;
        Production Prod[]=new Production[Maxlength];
        int pro=0;
        int change=0,n=0;
        
        for(int i=0;i<Prod.length;i++)
            Prod[i]=new Production();
        
        for(int i=0;i<intVn;i++ )
        {
            n=1;  Wi[0]=Vn[i];
            while(change<n){
                change=n;
                for(int j=0;j<n;j++)
                {
                    for(int k=0;k<intPar;k++)
                        if(Par[k].x==Wi[j]) //如果A属于Wk
                            if(Par[k].y.length()==1&&this.Contain(Vn, Par[k].y.charAt(0)))//长度为1，并且属于Vn
                                if(!this.Contain(Wi, Par[k].y.charAt(0)))//Wi中还没有 
                                  Wi[n++]=Par[k].y.charAt(0);
                }
            }
            for(int j=0;j<n;j++)
            {
                for(int k=0;k<intPar;k++)
                    if(Par[k].x==Wi[j])
                        if(Par[k].y.length()>1)//将Ai->a|B->a属于P且B属于Wi且a不属于Vn加入P1
                        {
                            boolean bo=false;
                            Production tt=new Production(Wi[0],Par[k].y);
                            for(int q=0;q<p;q++)//判断tt是否已经在P1中
                                if(P1[q].isEqual(tt))
                                {bo=true;break;}
                            if(!bo) P1[p++]=tt.copyProductionTo();
                        }
                        else if(Par[k].y.length()==1&&!this.Contain(Vn,Par[k].y.charAt(0)))
                         {
                            boolean bo=false;
                            Production tt=new Production(Wi[0],Par[k].y);
                            for(int q=0;q<p;q++)
                                if(P1[q].isEqual(tt))
                                {bo=true;break;}
                            if(!bo) P1[p++]=tt.copyProductionTo();
                        } 
            }
            
            for(int z=0;z<p;z++)
            {
                if((pro+1)>Prod.length)
                {
                    Production temp[]=new Production[Prod.length+Maxlength];
                    for(int zz=0;zz<Prod.length;zz++)
                        temp[zz]=Prod[zz].copyProductionTo();
                    Prod=temp.clone();
                    {
                            boolean bo=false;
                            for(int q=0;q<pro;q++)
                                if(Prod[q].isEqual(P1[z]))
                                {bo=true;break;}
                            if(!bo) Prod[pro++]=P1[z].copyProductionTo();
                     } 
                    
                }
                else
                   {
                            boolean bo=false;
                            for(int q=0;q<pro;q++)
                                if(Prod[q].isEqual(P1[z]))
                                {bo=true;break;}
                            if(!bo) Prod[pro++]=P1[z].copyProductionTo();
                   } 
            }
        }
        intPar=pro;
        Par=Prod.clone();
     }
     
    public void printW(){
        System.out.print("===========W================\n");
        for(int i=0;i<intw;i++)
            System.out.print(W[i]);
        System.out.print("\n===========W================\n");
    }
    
   public void printGeneration(){
             System.out.print("开始结符号:{");
             System.out.printf("%c", Start);
              System.out.print("}\n");
              
             System.out.print("非终结符号:{");
             for(int i=0;i<intVn;i++ )
            {
                System.out.print(Vn[i]);
                 if(i<intVn-1)
                {
                     System.out.print(',');
                 }
            }
             System.out.print("}\n"); 
             System.out.print("终结符号:{");
              for(int i=0;i<intVt;i++ )
            {
                  if(Vt[i]!=Emp)
                    System.out.printf("%c",Vt[i]);
                 if(i<intVt-1)
                {
                    System.out.print(',');
                 }
            }
              System.out.print("}\n");
              System.out.print("产生式集:{");
              for(int i=0;i<intPar;i++ )
            {
                System.out.print(Par[i].getX()+"->"+Par[i].getY());
                if(i<intPar-1)
                    System.out.print(",");
            }         
              System.out.print("}\n");
       }
}