#include<string.h>

#include<stdio.h>

#include<stdlib.h>

int main()

{

    char p[30][30];//存放文法

    char q[30][30];

    int line=0;

    int n;

    int i,j;

    int count=0;

    int k,t=0;

    int flag=0;

    int l,m=0;

    char VN[30]={'\0'};//存放非终结符号

    char VT[30]={'\0'};//存放终结符号

    printf("请输入规则个数");

    scanf("%d",&n);

    line=n;

    for(i=0;i<30;i++)//给字符串数组p,q全部赋值为'\0'

        for(j=0;j<30;j++)

        {

            p[i][j]='\0';

            q[i][j]='\0';

        }

        printf("请输入文法:\n");

        for(i=0;i<line;i++)

        {

            scanf("%s",p[i]);

        }

        //把字符分为终结符和非终结符

        l=0;

        m=0;

        for(i=0;i<line;i++)

        {

            for(j=0;j<30&&(p[i][j]!='\0');j++) { //非终结符放入数组VN中

                if(p[i][j]<='z'&&p[i][j]>='a'||(p[i][j]<='9'&&p[i][j]>='0'))

                {

                    flag=0;

                    for(t=0;VN[t]!='\0';t++)

                    {

                        if(VN[t]==p[i][j])

                        {

                            flag=1;break;

                        }

                    }

                    if(flag==0)

                    {

                        VN[l]=p[i][j];

                        l++;

                    }

                }

                //终结符放在数组VT中

                if(p[i][j]<='Z'&&p[i][j]>='A')

                {

                    flag=0;

                    for(t=0;t<30&&(VT[t]!='\0');t++)

                    {

                        if(VT[t]==p[i][j])

                        {

                            flag=1;

                            break;

                        }

                    }

                    if(flag==0)

                    {

                        VT[m]=p[i][j];

                        m++;

                    }

                }

            }

        }

        //把规则右部分分离，放入数组q中

        count=0;

        k=0;

        for(i=0;i<line;i++)

        {

            for(j=4;j<30&&(p[i][j]!='\0');j++)

            {

                if((p[i][j]<='z'&&p[i][j]>='a')||(p[i][j]<='Z'&&p[i][j]>='A')||(p[i][j]<='9'&&p[i][j]>='0'))

                {

                    q[count][k]=p[i][j];

                    k++;

                }

                else

                {

                    count++;

                    k=0;

                }

            }

            count++;

            k=0;

        }

        //判断是确定的还是非确定的有穷状态自动机，并进行前半部分打印

        //判断依据：q数组中每一行字符串是否相同

        flag=0;

        for(i=0;i<count;i++)

        {

            for(j=i+1;j<count;j++)

            {

                if(strcmp(q[i],q[j])==0)

                {

                    flag=1;

                    break;

                }

            }

        }

        if(flag==1)

        {

            printf("是非确定的有穷状态自动机，即NFA\n\n");

            printf("构造的有穷状态自动机为:\n");

            printf("NFA   N=(K,E(总和的意思),M,{S},{Z})\n");

        }

        else

        {

            printf("是确定的有穷状态自动机，即DFA\n\n\n");

            printf("构造的有穷状态自动机为:\n");

            printf("DFA   N=(K,E(总和的意思),M,{S},{Z})\n");

        }

        printf("其中，\nK={S");

        for(i=0;i<30&&(VT!='\0');i++)

        {

            printf(",%c",VT[i]);

        }

        printf("}\n");

        printf("E={");

        for(i=0;i<30&&(VN[i]!='\0');i++)

        {

            printf("%c   ",VN[i]);

        }

        printf("}\n");

        //分离文法

        k=0;

        count=0;

        for(i=0;i<line;i++)

        {

            j=4;

            while(p[i][j]!='\0')

            {

                if(k<4)

                {

                    q[count][k]=p[i][k];

                    k++;

                }

                else

                {

                    if((p[i][j]<='z'&&p[i][j]>='a')||(p[i][j]<='Z'&&p[i][j]>='A')||(p[i][j]<='9'&&p[i][j]>='0'))

                    {

                        q[count][k]=p[i][j];

                        k++;

                        j++;

                    }

                    if(p[i][j]=='l')

                    {

                        count++;

                        k=0;

                        j++;

                    }

                }

            }

            count++;

            k=0;

        }

        printf("\n");

        //打印M后部分

        printf("M:\n");

        l=0;

        while(VN[l]!='\0')

        {

            printf("M(S,%c)={",VN[l]);

            for(i=0;i<30;i++)

            {

                for(j=4;j<30&&(q[i][j]!='\0');j++)

                {

                    if(VN[l]==q[i][j]&&(q[i][j+1]=='\0')&&(q[i][j-1]=='='))

                        printf("%c",q[i][0]);

                }

            }

            printf("}\t");

            l++;

        }

        printf("\n");

        l=0;k=0;

        while(VT[k]!='\0')

        {

            l=0;

            while(VN[l]!='\0')

            {

                printf("M(%c,%c)={",VT[k],VN[l]);

                for(i=0;i<30;i++)

                {

                    for(j=4;j<30&&(q[i][j]!='\0');j++)

                    {

                        if(VT[k]==q[i][j]&&VN[l]==q[i][j+1])

                            printf("%c",q[i][0]);

                    }

                }

                printf("}\t");

                l++;

            }

            k++;

            printf("\n");

        }

        system("pause");

}