#include"stdlib.h"
#include"stdio.h"
#include"string.h"
#include <windows.h>
typedef struct
{
    char R;
    char r;
    int flag;
}array;
array F[30];

typedef struct
{
    char E;
    char e;
}charLode;

typedef struct
{
    charLode *base;
    int top;
}charstack;

char str[80][80],arr[80][80],brr[80][80];

int m,kk,p,ppp,FF=1;
char r[20];
int crr[30][30],FLAG=0;
char ccrr1[1][30],ccrr2[30][1];
void Initstack(charstack *s)
{
 s->base=(charLode *)malloc(30*sizeof(charLode));
    s->top=-1;
}

void push(charstack *s,charLode w)
{
   s->top++;
   s->base[s->top].E=w.E;
   s->base[s->top].e=w.e;
}

void pop(charstack *s,charLode *w)
{
   w->E=s->base[s->top].E;
   w->e=s->base[s->top].e;
   s->top--;
}

int IsEmpty(charstack s)
{
    if(s.top==-1)
        return 1;
    else
     return 0;
}
int IsLetter(char ch)
{
    if(ch>='A'&&ch<='Z')
       return 1;
    else
  return 0;
}

int judge1(int n)
{
    int j=3,flag=1,i;
    for(i=0;i<=n;i++)
  while(str[i][j]!='\0')
  {
            char a=str[i][j];
            char b=str[i][j+1];
            if(IsLetter(a)&&IsLetter(b))
   {
    flag=0;
    break;
   }
            else
    j++;
  }
  return flag;
}

void judge2(int n)
{
 int i;
    for(i=0;i<=n;i++)
    if(str[i][3]=='~'||judge1(n)==0||FLAG==1)
    {
  printf("grammar G is not operator priority grammar!\n");
  FF=0;
  break;
 }
    if(i>n)
  printf("grammar G is operator priority grammar!\n");
}

int search1(char r[],int kk,char a)
{
 int i;
    for(i=0;i<kk;i++)
        if(r[i]==a)
            break;
    if(i==kk)
  return 0;
    else
  return 1;
}

void createF(int n)
{
    int k=0,i=1;
    char c;
    int j;
    char t[10];
    t[0]=str[0][0];
    while(i<=n)
 {
        if(t[k]!=str[i][0])
  {
   k++;
   t[k]=str[i][0];
   i++;
  }
        else
   i++;
 }
    kk=0;
    for(i=0;i<=n;i++)
 {
  j=3;
        while(str[i][j]!='\0')
  {
            c=str[i][j];
            if(IsLetter(c)==0)
   {
                if(!search1(r,kk,c))
                r[kk]=c;
    kk++;
   }
            j++;
  }
    }
    m=0;
    for(i=0;i<k;i++)
        for(j=0;j<kk-1;j++)
  {
            F[m].R=t[i];
            F[m].r=r[j];
            F[m].flag=0;
            m++;
  }
}

void search(charLode w)
{
 int i;
    for(i=0;i<m;i++)
        if(F[i].R==w.E&&F[i].r==w.e)
  {
   F[i].flag=1;
   break;
  }
}

void FirstVT(int n)
{
    charstack sta;
    charLode ww;
    charLode w;
    int i=0,k;
    char a,b;
    Initstack(&sta);
    while(i<=n)
 {
        k=3;
        w.E=str[i][0];
        a=str[i][k];
       b=str[i][k+1];
        if(!IsLetter(a))
  {
            w.e=a;
            push(&sta,w);
            search(w);
            i++;
  }
        else if(IsLetter(a)&&b!='\0'&&!IsLetter(b))
  {
            w.e=b;
            push(&sta,w);
            search(w);
            i++;
  }
        else
   i++;
 }
    while(!IsEmpty(sta))
 {
        pop(&sta,&ww);
        for(i=0;i<=n;i++)
  {
            w.E=str[i][0];
            if(str[i][3]==ww.E&&str[i][4]=='\0')
   {
                w.e=ww.e;
                push(&sta,w);
                search(w);
                break;
   }
   else if(str[i][3]==ww.E&&w.E!=ww.E)
   {
    w.e=ww.e;
                push(&sta,w);
                search(w);
                break;
   }
   
  }
 }
    p=0;
   k=1;i=1;
    while(i<m)
 {
        if(F[i-1].flag==1)
  {
            arr[p][0]=F[i-1].R;
            arr[p][k]=F[i-1].r;
  }
        while(F[i].flag==0&&i<m)
            i++;
        if(F[i].flag==1)
  {
            if(F[i].R==arr[p][0])
                k++;
            else
   {
    arr[p][k+1]='\0';
    p++;
    k=1;
   }
            i++;
  }
 }  
}

void LastVT(int n)
{
    charstack sta;
    charLode w;
    charLode ee;
    char a,b;
    int k,i;
    for(i=0;i<m;i++)
        F[i].flag=0;
    i=0;
    Initstack(&sta);
    while(i<=n)
 {
        int k=strlen(str[i]);
        w.E=str[i][0];
        a=str[i][k-1];
        b=str[i][k-2];
        if(!IsLetter(a))
  {
            w.e=a;
            push(&sta,w);
            search(w);
            i++;
  }
        else if(IsLetter(a)&&!IsLetter(b))
  {
            w.e=b;
            push(&sta,w);
            search(w);
            i++;
  }
        else
   i++;
 }

    while(!IsEmpty(sta))
 {
        pop(&sta,&ee);
        for(i=0;i<=n;i++)
  {
            w.E=str[i][0];
            if(str[i][3]==ee.E&&str[i][4]=='\0')
   {
                w.e=ee.e;
                push(&sta,w);
                search(w);
   }
  }
 }
   k=1;
 i=1;
    ppp=0;
    while(i<m)
 {
        if(F[i-1].flag==1)
  {
            brr[ppp][0]=F[i-1].R;
            brr[ppp][k]=F[i-1].r;
  }
        while(F[i].flag==0&&i<m)
            i++;
        if(F[i].flag==1)
  {
            if(F[i].R==arr[ppp][0])
                k++;
            else
   {
    brr[ppp][k+1]='\0';
    ppp++;
    k=1;
   }
            i++;
  }
 }  
}

void createYXB(int n)
{
    int i,j;
    int I,mm,pp,J;
    for(j=1;j<=kk;j++)
        ccrr1[0][j]=r[j-1];
    for(i=1;i<=kk;i++)
        ccrr2[i][0]=r[i-1];
    for(i=1;i<=kk;i++)
        for(j=1;j<=kk;j++)
            crr[i][j]=0;
    I=0,J=3;
    while(I<=n)
    {
        if(str[I][J+1]=='\0')
  {
   I++;
   J=3;
  }
        else
  {
            while(str[I][J+1]!='\0')
   {
                char aa=str[I][J];
                char bb=str[I][J+1];
                if(!IsLetter(aa)&&!IsLetter(bb))
    { 
                    for(i=1;i<=kk;i++)
     {
                        if(ccrr2[i][0]==aa)
                            break;
                    }
                    for(j=1;j<=kk;j++)
     {
                        if(ccrr1[0][j]==bb)
                            break; 
                    }
                    if(crr[i][j]==0)
                        crr[i][j]=1;
                    else
     {
      FLAG=1;
      I=n+1;
     }
                    J++;
    }
                if(!IsLetter(aa)&&IsLetter(bb)&&str[I][J+2]!='\0'&&!IsLetter(str[I][J+2]))
    { 
                    for(i=1;i<=kk;i++)
     {
                        if(ccrr2[i][0]==aa)
                            break;
                    }
                    for(j=1;j<=kk;j++)
     {
                        if(ccrr1[0][j]==str[I][J+2])
                            break;
                    }
                    if(crr[i][j]==0)
                        crr[i][j]=1;
                    else
     {
      FLAG=1;
      I=n+1;
     }
    }
                if(!IsLetter(aa)&&IsLetter(bb))
    { 
                    for(i=1;i<=kk;i++)
     {
                        if(aa==ccrr2[i][0])
                            break;
                    }
                    for(j=0;j<=p;j++)
     {
                        if(bb==arr[j][0])
                            break;
                    }
                    for(mm=1;arr[j][mm]!='\0';mm++)
     {
                        for(pp=1;pp<=kk;pp++)
      {
                            if(ccrr1[0][pp]==arr[j][mm])
                                break;
      }
                        if(crr[i][pp]==0)
                            crr[i][pp]=2;
                        else
      {
       FLAG=1;
       I=n+1;
      }
     }
                    J++;
    }
                if(IsLetter(aa)&&!IsLetter(bb))
    {
                    for(i=1;i<=kk;i++)
     {
                        if(ccrr1[0][i]==bb)
                            break;
     }
                    for(j=0;j<=ppp;j++)
     {
                        if(aa==brr[j][0])
                            break;
     }
                    for(mm=1;brr[j][mm]!='\0';mm++)
     { 
                        for(pp=1;pp<=kk;pp++)
      {
                            if(ccrr2[pp][0]==brr[j][mm])
                                break;
      }
                        if(crr[pp][i]==0)
                            crr[pp][i]=3;
                        else
      {
       FLAG=1;
       I=n+1;
      }
      
     }
     J++;
    }
            }
        }
    }
}

int judge3(char s,char a)
{
    int i=1,j=1;
    while(ccrr2[i][0]!=s)
        i++;
    while(ccrr1[0][j]!=a)
        j++;
    if(crr[i][j]==3)
  return 3;
    else if(crr[i][j]==2)
        return 2;
    else if(crr[i][j]==1)
        return 1;
    else return 0;
}

void print(char s[],char STR[][20],int q,int u,int ii,int k)
{
 int i;
 printf("%d\t\t",u);
    for(i=0;i<=k;i++)
       
  printf("%c",s[i]);
      
 printf("\t\t");
    for(i=q;i<=ii;i++)
      
  printf("%c",STR[0][i]);
  
 printf("\t\t");
}

void process(char STR[][20],int ii)
{
    int k=0,q=0,u=0,b,i,j;
    char s[40],a;
    printf("step\t\tcharstack\tinputstring\tAction\n");
    s[k]='#';
    print(s,STR,q,u,ii,k);
 printf("ready\n");
    k++;
 u++;
    s[k]=STR[0][q];
    q++;
    print(s,STR,q,u,ii,k);
 printf("shift\n");
    while(q<=ii)
 {
        a=STR[0][q];
        if(!IsLetter(s[k]))
   j=k;
        else
   j=k-1;
        b=judge3(s[j],a);
        if(b==3)
  {
            while(IsLetter(s[j-1]))
                j--;
            for(i=j;i<=k;i++)
                s[i]='\0';
            k=j;s[k]='G';u++;
            print(s,STR,q,u,ii,k);
   printf("reduce\n");
  }
        else if(b==2||b==1)
  {
            k++;
            s[k]=a;
            u++;
            q++;
            print(s,STR,q,u,ii,k);
            if(s[0]=='#'&&s[1]=='N'&&s[2]=='#')
                printf("shift\n");
            else
    printf("accept\n");
  }
        else
  {
   printf("error\n");
   break;
  }
 }
    if(s[0]=='#'&&s[1]=='N'&&s[2]=='#')
  printf("Reduction is successful\n");
    else
  printf("Reduction fails\n");
}

void main()
{
    int n,i,j,o;
    int ii;
    printf("please input the number of grammer G defined:");
    scanf("%d",&n);
    printf("please input the grammer G ");
    printf("\n");
    for(i=0;i<n;i++)
 {
      scanf("%s",str[i]);
      j=strlen(str[i]);
      str[i][j]='\0';
 }
    str[i][0]='Q';
    str[i][1]='-';
    str[i][2]='>';
    str[i][3]='#';
    str[i][4]=str[0][0];
    str[i][5]='#';
    str[i][6]='\0';
 printf("Creation style that you define as follows:\n");
    for(i=0;i<=n;i++)
  printf("%s\n",str[i]);
    if(judge1(n)==0)
  printf("Grammar G is not operator grammar !\n");
    if(judge1(n)==1)
 {
  printf("grammar G is the operator of grammar !\n");
        createF(n);
        FirstVT(n);
        LastVT(n);
        createYXB(n);
 }
    judge2(n);
    if(FLAG==0)
    {
        for(i=0;i<=p;i++)
        {
   printf("FirstVT(%c)={",arr[i][0]);
            for(o=1;arr[i][o+1]!='\0';o++)
    printf("%c,",arr[i][o]);
   printf("%c}\n",arr[i][o]);
        }
 }
  printf("FirstVT(Q)={#}\n");
        for(i=0;i<=ppp;i++)
  {
   printf("LastVT(%c)={",arr[i][0]);
            for(o=1;brr[i][o+1]!='\0';o++)
    printf("%c,",brr[i][o]);
   printf("%c}\n",brr[i][o]);
  }
  printf("LastVT(Q)={#}\n");
  printf("Priority table is as follows:\n");
        for(i=1;i<kk;i++)
  {
   printf("   ");
   printf("%c",ccrr1[0][i]);
  }
  printf("\n");
        for(i=1;i<kk;i++)
  {
   printf("%c  ",ccrr2[i][0]);
            for(j=1;j<kk;j++)
   {
                if(crr[i][j]==0)
     printf(" ");
                else if(crr[i][j]==1)
     printf("=");
                else if(crr[i][j]==2)
     printf("<");
                else if(crr[i][j]==3)
                    printf(">");
    printf("   ");
   }
   printf("\n");
  }
  
 
   if(FF==1)
   {
        char STR[1][20];
  printf("Please input the string to the Statute:\n");
  scanf("%s",STR[0]);
  //getchar();
        //gets(STR[0]);
        ii=strlen(STR[0]);
        STR[0][ii]='#';
  printf("the Analysis  are as follow:\n");
        process(STR,ii);
   }
}