rnd.h

正则表达式转换为NFA再转换为DFA

 Nfa->pStart=Pop_StateStack();
 Destory_StateStack();
}
 


//Nfa的初始化
void Init_Nfa()
{
    Nfa->NodeTable=(PState *)malloc((Max_State)*sizeof(State));
    Nfa->numOfStates=0;
    Nfa->numOfTrans=0;
    Nfa->pStart=NULL;
    Nfa->pFinal=NULL;
}


//申请新的状态点，初始化一些数据
void NewState(PState x)
{
    Nfa->NodeTable[Nfa->numOfStates]=x;
    x->id=++Nfa->numOfStates;
    x->numOfTrans=0;
    x->trans=NULL;    
}

//在状态s1和s2之间添加以x为输入symbol的转换弧
void AddTrans(PState s1,PState s2,char x)
{    
    Trans *temp=(Trans *) malloc(sizeof(Trans));
    s1->numOfTrans++;
    Nfa->numOfTrans++;
    temp->dest=s2->id;
    temp->sign=x;
    temp->next=NULL;
    temp->next=s1->trans;
    s1->trans=temp;
} 


/*______________________________输出NFA_____________________________*/
void OutputNFA()
{
    int i;
    PState *s;
    State temp;
    printf(" _________________________Infomation of NFA_________________________\n");
    printf(" NFA's number of States is: %d\n NFA's start state is: q%d\n NFA's final state is: q%d \n",Nfa->numOfStates,Nfa->pStart->id,Nfa->pFinal->id);
    printf("The transnations of NFA is format as [State1 --Symbol--> State2].  ~ means ε\n ");
    fprintf(fpout," _________________________Infomation of NFA_________________________\n");
    fprintf(fpout," NFA's number of States is: %d\n NFA's start state is: q%d \nNFA's final state is: q%d \n",Nfa->numOfStates,Nfa->pStart->id,Nfa->pFinal->id);
    fprintf(fpout,"The transnations of NFA is format as [State1 --Symbol--> State2].  ~ meansε\n");
    s=Nfa->NodeTable;
    for (i=0;i<Nfa->numOfStates;i++)
    { printf("\n");
        temp=*(s[i]);
        while(temp.trans)

        {
            printf("   q%-2d --%c--> q%-2d",temp.id,temp.trans->sign,temp.trans->dest);
            fprintf(fpout,"    q%-2d --%c--> q%-2d",temp.id,temp.trans->sign,temp.trans->dest);
            temp.trans=temp.trans->next;
        }
        printf("\n");
        fprintf(fpout,"\n");
    }
}


/*______________________________构造DFA_____________________________*/
//采用子集构造法
void ConstructDFA()
{    
    int i, j, k=0;
    int *T=(int*) malloc((Nfa->numOfStates+1)*sizeof(int));
    int *temp=(int*) malloc((Nfa->numOfStates+1)*sizeof(int));

// 对DFA及DStates、Dtrans、AcceptSet数组进行初始化操作
    Dfa.numofDStates=0;
    Dfa.DStates=(int**) malloc((Nfa->numOfStates+1)*sizeof(int));
    for (i=0; i<Nfa->numOfStates+1; i++)//
       Dfa.DStates[i]=(int*) malloc((Nfa->numOfStates+1)*sizeof(int));//
    Dfa.Dtrans=(int**) malloc((Nfa->numOfStates+1)*sizeof(int));
    for (i=0; i<Nfa->numOfStates+1; i++)
    {
        Dfa.Dtrans[i]=(int*) malloc((NumOfSymbol+1)*sizeof(int));
        for (j=0; j<NumOfSymbol+1; j++)
            Dfa.Dtrans[i][j]=-1;
    }
    Dfa.AcceptSet=(int*) malloc((Nfa->numOfStates+1)*sizeof(int));
    for (i=0; i<Nfa->numOfStates+1; i++)
        Dfa.AcceptSet[i]=0;

// 调用ε闭包函数和移动函数构造DStates和Dtrans及AcceptSet数组
    T[0]=Nfa->pStart->id;
    T[1]=-1;
    Dfa.DStates[0]=Closures(T);
    BubbleSort(Dfa.DStates[0]);//
    Dfa.numofDStates++;
    while (k < Dfa.numofDStates)
    {
        for (i=0; i<NumOfSymbol; i++)
        {
            temp=Closures(TransX(T, Alphabet[i]));
            if (temp[0] != -1)
            {
                for (j=0; j<Dfa.numofDStates; j++)
                {
                    if (CompArray(temp, Dfa.DStates[j])==1)
                    {
                        Dfa.Dtrans[k][i]=j;
                        break;
                    }
                }
                if (j==Dfa.numofDStates)
                {
                    Dfa.DStates[Dfa.numofDStates]=temp;
                    Dfa.Dtrans[k][i]=Dfa.numofDStates;
                    Dfa.numofDStates++;
                }
            }
        }
        k++;
        T=Dfa.DStates[k];
    }
//标记出DFA所有的接受状态
    for (i=0; i<Dfa.numofDStates; i++)
    {
        for (j=0; Dfa.DStates[i][j]!= -1; j++)
        {
            if (Dfa.DStates[i][j]==Nfa->pFinal->id)
            {
                Dfa.AcceptSet[i]=1;
                break;
            }
        }
    }
}


 


int* Closures(int *T)//对状态集T中包含的某个NFA状态S求ε闭包
{
    int i=0,j,k=0,len=0;
    int *temp=(int*)malloc(200*sizeof(int));
    Trans *q;

    while (T[len] != -1)
    {
        temp[len]=T[len];
        len++;
    }
    k=len;
    while (T[i] != -1)
    {
        q=Nfa->NodeTable[T[i]-1]->trans;
        while (q)
        {
            if (q->sign=='~')
            {
                for (j=0; j<k; j++)
                {
                    if (q->dest==temp[j])
                        break;
                }
                if (j==k)
                {
                    temp[k]=q->dest;
                    k++;
                    T[len++]=q->dest;
                    T[len]=-1;
                }
            }
            q=q->next;
        }
        i++;
    }
    temp[k]=-1;
    BubbleSort(temp);
    return temp;
}

// 对状态集T中包含的某个NFA状态求 x 转换的状态集合
int* TransX(int *T, char x)
{
    int i=0, j, k=0;
    int *temp=(int*)malloc(200*sizeof(int));
    Trans *q;

    while (T[i] != -1)
    {
        q=Nfa->NodeTable[T[i]-1]->trans;
        while (q)
        {
         if (q->sign==x)
            {
                for (j=0; j<k; j++)
                {
                    if (q->dest==temp[j])
                        break;
                }
                if (j==k)
                {
                    temp[k]=q->dest;
                    k++;
                }
            }
            q=q->next;
        }
        i++;
    }
    temp[k]=-1;
    BubbleSort(temp);
    return temp;
}

// 对状态集进行排序，方便比较数组，使输出形式更好看。
void BubbleSort(int *array)
{//冒泡排序
    int i,j,len=0,flag=1;
    char temp;
    
    while (array[len] != -1)
        len++;

    for(i=0;i<len&&flag==1;i++)
    {
        flag=0;
        for(j=len-1;j>=i;j--)
            if(array[j]<array[j-1]) 
            { 
                temp=array[j]; 
                array[j]=array[j-1]; 
                array[j-1]=temp;
                flag=1;
            }
    }
}

// 比较两个一维数组是否含有完全相同的元素，是返回1，否返回0。
int CompArray(int *t1, int *t2)
{
    int i = 0, len1=0, len2=0;
    while (t1[len1] != -1) 
    {
        len1++; 
    } 
//    len1 = i;
    while (t2[len2] != -1)
    { 
        len2++;  
    } 
//    len2 = j; 
    if (len1 != len2) 
    {
        return 0; 
    }
    for (i=0; i<len1; i++)                               
    { 
        if (t1[i] != t2[i])                              
        return 0;                                        
      } 
    return 1;                                            
}                                                      


 


/*______________________________输出DFA_____________________________*/

void OutputDFA()//输出原始的DFA概要，并调用void OutputDFA()输出DFA
{
    printf("_________________________Infomation of DFA_________________________\n");
    fprintf(fpout,"_________________________Infomation of DFA_________________________\n");
    printf("              ___________Subset Construct DFA___________            \n");
    fprintf(fpout,"              ___________Subset Construct DFA___________            \n");
    OutputDFATable();

//输出优化后的DFA概要，并调用void OutputDFATable();输出DFA

    printf("              ______________Optimized DFA_______________            \n");
    fprintf(fpout,"              ______________Optimized DFA_______________            \n");

    if(Optimize())//去掉只有入度没有出度的非接受状态//将DFA优化__去掉无效状态
        OutputDFATable();
    else 
    {
        printf(" Optimize is unnecessary!\n");
        fprintf(fpout," Optimize is unnecessary!\n");
    }
//输出最简化的DFA概要，并调用void OutputDFATable();输出DFA

    printf("              ______________Simplifyed DFA______________            \n");
    fprintf(fpout,"              ______________Simplifyed DFA______________            \n");

    if(Simplify())//将DFA化简__树形分割法
        OutputDFATable();
    else 
    {
        printf(" It's already the simpliest DFA!\n");
        fprintf(fpout," It's already the simpliest DFA!\n");
    }
}

void OutputDFATable()//输出DFA
{
    int i,j;    

    printf(" DFA's number of States is: %d\n",Dfa.numofDStates);
    printf(" DFA's start state is: s1 \n");
    printf(" DFA's final state are: ");
    fprintf(fpout," DFA's number of States is: %d\n",Dfa.numofDStates);
    fprintf(fpout," DFA's start state is: s1 \n");
    fprintf(fpout," DFA's final state are: ");
    for(i=0; i<Dfa.numofDStates; i++)
        if(Dfa.AcceptSet[i]==1)
        {
            printf("s%-2d \n",i+1);
            fprintf(fpout,"s%-2d \n",i+1);
        }
//表头
    printf(" DFA's States                                      ");
    fprintf(fpout," DFA's States                                      ");
    for(i=0;i<NumOfSymbol;i++)
    {
        printf("  %-3c",Alphabet[i]);
        fprintf(fpout,"  %-3c",Alphabet[i]);
    }
	printf("\n");
	fprintf(fpout,"\n");
//内容
    for (i=0; i<Dfa.numofDStates; i++)
    {   //输出DFA状态集 共计50个字符位
        printf(" s%-2d:",i+1);
        fprintf(fpout," s%-2d:",i+1);
        OutputSet_Array(Dfa.DStates[i]);
        // 输出转移函数
        for (j=0; j<NumOfSymbol; j++)
            if(Dfa.Dtrans[i][j]!=-1)
            {
                printf("  s%-2d",Dfa.Dtrans[i][j]+1);
                fprintf(fpout,"  s%-2d",Dfa.Dtrans[i][j]+1);
            }
		
            else
            {
                printf("   ");
                fprintf(fpout,"   ");
            }
		printf("\n");
	    fprintf(fpout,"\n");
    }
}

void OutputSet_Array(int* array)//输出数组 共计47个字符位
{
    int i,j=0,num=0;
    printf("{");
    fprintf(fpout,"{");
    while(array[j]!=-1)
        j++;
    for(i=0;i<j-1;i++)
    {
        printf("q%d,",array[i]);
        fprintf(fpout,"q%d,",array[i]);
        if(array[i]>9)
            num=num+2;
        else
            num++;
    }
    printf("q%d}",array[i]);
    fprintf(fpout,"q%d}",array[i]);
    num=41-num-2*i;
    for(i=0;i<num;i++)
    {
        printf(" ");
        fprintf(fpout," ");
    }
}

 


/**//*______________________________优化DFA_____________________________*/
int Optimize()//去掉只有入度没有出度的非接受状态
{
    int i,j,flag=0;

    for(i=0; i<Dfa.numofDStates; i++)
        if(Dfa.AcceptSet[i]==0)
        {
            for(j=0;j<NumOfSymbol;j++)
            {
                if(Dfa.Dtrans[i][j]!=-1)
                    break;
            }
            if(j==NumOfSymbol)
            {
                for(j=i;j<Dfa.numofDStates;j++)
                {
                    Dfa.DStates[j]=Dfa.DStates[j+1];
                }
                Dfa.numofDStates--;
                flag=1;
            }
        }
    return flag;
}

/**//*___________________________最大等价状态集法简化DFA__________________________*/
/**//*具体算法如下:
  (1)首先将DFA所有的状态分割成可接受状态和不可接受状态集;
  (2)依次输入字母进行判断,找最大等价状态集并将其合并;
  (3)直到求出所有的最大等价状态集为止;
*/

int Simplify()//将DFA最简化__最大等价状态集法
{
    int i,j,k,len1=0,len2=0,*accept,*deny;

    accept=(int*) malloc((Nfa->numOfStates+1)*sizeof(int));
    deny=(int*) malloc((Nfa->numOfStates+1)*sizeof(int));
    //把状态集合分为两个子集——接受集合、非接受集合
    for(i=0; i<Dfa.numofDStates; i++)
    {
        if(Dfa.AcceptSet[i]!=1)
        {
            deny[len1++]=i;
        }
        else 
        {
            accept[len2++]=i;
        }
    }
    //分别对子集求最大状态集
    for(i=0;i<len1;i++)
    {
        for(j=i+1;j<len1;j++)
        {
            for(k=0;k<NumOfSymbol;k++)
            {
                if(Dfa.Dtrans[deny[i]]!=Dfa.Dtrans[deny[j]])
                    break;
            }
            if(k==NumOfSymbol)//找到最大集
            {
                //记录1
            }
        }
    }
//处理1
    for(i=0;i<len2;i++)
    {
        for(j=i+1;j<len2;j++)
        {
            for(k=0;k<NumOfSymbol;k++)
            {
                if(Dfa.Dtrans[accept[i]]!=Dfa.Dtrans[accept[j]])
                    break;
            }
            if(k==NumOfSymbol)//找到最大集
            {
                //记录2
            }
        }
    }
//处理2

    return 1;
}