#include<stdio.h>
#include<conio.h>
#define MAX 30
#define TRUE 1
#define FALSE 0
#define ACC 3
#define SHIFT 1
#define RED 2
struct grammar
{
	int tot;	//total no. of rules
	int rules[MAX][MAX];//[i][0]-no of symbols in rule i,[i][[i][0]+1]-whether added rule or not
};
struct first_set
{
	int tot;
	int sym[MAX];
       //	int tag_sym[MAX];
	int set[MAX][MAX];
};
struct closure_set
{
	int set_tot[MAX];
	int prod[MAX][MAX];
	int dot[MAX][MAX];
	int tot;
};
struct goto_struc
{
	int tot;
	int set[MAX];
	int sym[MAX];
	int dest[MAX];
};
struct
{
	int action[MAX][MAX];
	int action_state[MAX][MAX];
	int goto_state[MAX][MAX];
}table;
struct fol_set
{
	int tot;
	int sym[MAX];
	int set[MAX][MAX];
};
struct goto_struc goto_set;
struct closure_set closure;
struct fol_set follow;
struct first_set first;
struct grammar gram;        //input grammar
int nt[MAX],ntcnt=0;//list of non terminals
int t[MAX],tcnt=0; //list of terminals
void getinp();
void find_terminals();
void first_calc();
void follow_calc();
void copy1(int,int);
void set_const();
int find_closure(int);
void find_goto(int,int);
void table_const();
void main()
{
 int ch;
 clrscr();
 getinp();
 /*augmenting the grammar*/
 gram.rules[0][0]=2;
 gram.rules[0][1]=gram.rules[1][1];
 gram.rules[0][2]=gram.rules[1][1];
 first_calc();
 follow_calc();
 set_const();
 table_const();
 do
 {
  if(simulation())
	printf("Accepted\n");
  else
	printf("Rejected\n");
  printf("Do you want to simulate more y/n? ");
  fflush(stdin);
  ch=getchar();
 }while(ch=='y');
 getch();
}
void getinp()
{
 int ch,ch2,i=1,j,ntflg=1;
 gram.tot=1;
 printf("Enter the grammar rules..\n");
 gram.rules[0][0]=0;
 while((ch=getchar())!='x')
 {
	if(ntflg==1)
	{
	 if(is_NT(ch)==-1)
	  nt[ntcnt++]=ch;
	 ntflg=0;
	}
	if(ch=='\n')
	{
	 gram.rules[++gram.tot][0]=0;
	 i=1;
	 ntflg=1;
	}
	else if(ch=='-')
	{
	 if((ch2=getchar())=='>');
	 else
	 {
	  ungetc(ch2,stdin);
	  gram.rules[gram.tot][i++]=ch;
	  gram.rules[gram.tot][0]++;
	 }
	}
	else
	{
	 gram.rules[gram.tot][i]=ch;
	 i++;
	 gram.rules[gram.tot][0]++;
	}
 }
 find_terminals();
 /*for(i=1;i<gram.tot;i++)
 {
  for(j=1;j<=gram.rules[i][0];j++)
	printf(" %c",gram.rules[i][j]);
  printf("\n");
 }
 printf("Terminals\n");
 for(i=0;i<tcnt;i++)
  printf("%c\t",t[i]);*/
}
int is_T(int n)
{
 int i;
 for(i=0;i<tcnt;i++)
 {
  if(t[i]==n)
   return i;
 }
 return -1;
}
void find_terminals()
{
 int i,j;
 for(i=0;i<gram.tot;i++)
 {
  for(j=2;j<=gram.rules[i][0];j++)
  {
   if((is_NT(gram.rules[i][j])==-1) && (is_T(gram.rules[i][j])==-1))
    t[tcnt++]=gram.rules[i][j];
  }
 }
}
int is_NT(int n)
{
 int i;
 for(i=0;i<ntcnt;i++)
 {
  if(nt[i]==n)
   return i;
 }
 return -1;
}
void first_calc()
{
 int i,j,pos,pos1,k,epflg,lp;
 for(i=1;i<gram.tot;i++)
 {
  for(j=1;j<=gram.rules[i][0];j++)
  {
   if(gram.rules[i][j]==-1)
   {
    pos=find_sym(gram.rules[i][1]);
	 if(pos==-1)
    {
     first.set[first.tot][0]=1;
     first.set[first.tot][1]=-1;
     first.sym[first.tot]=gram.rules[i][1];
     first.tot++;
    }
    else
    {
     if(!search_first(pos,-1))
     {
      first.set[pos][0]++;
      first.set[pos][first.set[pos][0]]=-1;
     }
    }
   }
   if((is_NT(gram.rules[i][j])==-1) && (gram.rules[i][j]!=-1))
   {
    pos=find_sym(gram.rules[i][j]);
    if(pos==-1)
    {
     first.set[first.tot][0]=1;
     first.set[first.tot][1]=gram.rules[i][j];
	  first.sym[first.tot]=gram.rules[i][j];
     first.tot++;
    }
    else
    {
     if(!search_first(pos,gram.rules[i][j]))
     {
      first.set[pos][0]++;
      first.set[pos][first.set[pos][0]]=gram.rules[i][j];
     }
    }
   }
  }
 }
 lp=1;
 while(lp<=2){
 for(i=(gram.tot-1);i>=0;i--)
 {
  pos=find_sym(gram.rules[i][1]);
  if((is_NT(gram.rules[i][2])==-1) && (gram.rules[i][2]!=-1))
  {
   if(pos!=-1)
   {
    if(!search_first(pos,gram.rules[i][2]))
    {
     first.set[pos][0]++;
	  first.set[pos][first.set[pos][0]]=gram.rules[i][2];
    }
   }
   else
   {
    first.set[first.tot][0]=1;
	 first.set[first.tot][1]=gram.rules[i][2];
    first.sym[first.tot]=gram.rules[i][1];
    first.tot++;
   }
  }
  else if(gram.rules[i][2]!=-1)
  {
   k=2;
   do
   {
   epflg=0;
   pos1=find_sym(gram.rules[i][k]);
	if(pos!=-1)
   {
    for(j=1;j<=first.set[pos1][0];j++)
    {
     if(first.set[pos1][j]==-1)
      epflg=1;
	  if(!search_first(pos,first.set[pos1][j]))
     {
      first.set[pos][0]++;
      first.set[pos][first.set[pos][0]]=first.set[pos1][j];
     }
    }
	}
   else if(pos1)
   {
    for(j=0;j<=first.set[pos1][0];j++)
    {
     if(first.set[pos1][j]==-1)
      epflg=1;
	  first.set[first.tot][j]=first.set[pos1][j];
    }
    first.sym[first.tot]=gram.rules[i][1];
    first.tot++;
   }
	k++;
   }while(epflg==1);
  }
 }
 lp++;
 }
/* printf("FIRST SET..\n");
 for(i=0;i<first.tot;i++)
 {
  printf("%c",first.sym[i]);
  printf(" - ");
  for(j=1;j<=first.set[i][0];j++)
  {
   if(first.set[i][j]==-1)
    printf("ep\t");
   else
    printf("%c\t",first.set[i][j]);
  }
  printf("\n");
 }*/
}
int find_sym(int no)
{
 int i;
 for(i=0;i<first.tot;i++)
 {
  if(first.sym[i]==no)
   return i;
 }
 return -1;
}
int search_first(int pos,int n)
{
 int i;
 for(i=1;i<=first.set[pos][0];i++)
 {
  if(first.set[pos][i]==n)
   return 1;
 }
 return 0;
}
void set_const()
{
 int i,j,k,p;
 goto_set.tot=0;
 closure.set_tot[0]=1;
 closure.tot=0;
 closure.prod[0][0]=0;
 closure.dot[0][0]=0;
 find_closure(0);
 for(i=0;i<closure.tot;i++)
 {
  for(j=0;j<closure.set_tot[i];j++)
  {
	if(closure.dot[i][j]<(gram.rules[closure.prod[i][j]][0]-1))
	 find_goto(i,gram.rules[closure.prod[i][j]][closure.dot[i][j]+2]);
  }
 }
/* printf("Goto\n");
 for(i=0;i<goto_set.tot;i++)
   printf("I%d,%c=I%d\n",goto_set.set[i],goto_set.sym[i],goto_set.dest[i]);
 getch();
 printf("Tot no of sets: %d\n",closure.tot);
 getch();*/
 for(i=0;i<closure.tot;i++)
 {
  printf("\nSet %d",i);
  for(j=0;j<closure.set_tot[i];j++)
  {
   p=closure.prod[i][j];
   if(p==0)
    printf("\t%c'->",gram.rules[p][1]);
   else
    printf("\t%c->",gram.rules[p][1]);
   for(k=2;k<=gram.rules[p][0];k++)
   {
    if(closure.dot[i][j]==(k-2))
     printf(" . %c",gram.rules[p][k]);
    else
     printf("%c",gram.rules[p][k]);
   }
   if(closure.dot[i][j]==gram.rules[p][0]-1)
    printf(".");
  }
 }
  getch();
}
int find_closure(int n)
{
 int i,j,nxt,p,new_set;
 /*copying prodns from old closure to new closure*/
 for(i=0;i<closure.set_tot[n];i++)
 {
  closure.prod[closure.tot][i]=closure.prod[n][i];
  closure.dot[closure.tot][i]=closure.dot[n][i];
 }
 closure.set_tot[closure.tot]=closure.set_tot[n];
 j=closure.set_tot[closure.tot];
 for(i=0;i<j;i++)
 {
  if(closure.dot[n][i]<(gram.rules[closure.prod[n][i]][0]-1))
  {
   nxt=gram.rules[closure.prod[n][i]][closure.dot[n][i]+2];
   if(is_NT(nxt)!=-1)
   {
    p=1;
	 while(p<gram.tot)
    {
     if(gram.rules[p][1]==nxt)
     {
      if(!chk_closure(closure.tot,p,0))
      {
       closure.prod[closure.tot][j]=p;
       closure.dot[closure.tot][j++]=0;
       closure.set_tot[closure.tot]=j;
      }
     }
     p++;
    }
	}
  }
 }
 new_set=closure_dup(closure.tot);
 if(new_set==-1)
 {
   closure.tot++;
   return(closure.tot-1);
 }
 else
  return(new_set);
}
int chk_closure(int set,int p,int dot)
{
 int i;
 for(i=0;i<closure.set_tot[set];i++)
 {
  if((closure.prod[set][i]==p) && (closure.dot[set][i]==dot))
   return TRUE;
 }
 return FALSE;
}
int closure_dup(int set)
{
 int i=0,j;
 if(set==0)
  return -1;
 do
 {
  j=0;
  if(closure.set_tot[i]==closure.set_tot[set])
  {
   for(j=0;j<closure.set_tot[i];j++)
   {
    if((closure.prod[i][j]==closure.prod[set][j]) && (closure.dot[i][j]==closure.dot[set][j]))
     continue;
	 else
     break;
   }
  }
  if(j==closure.set_tot[i])
   return i;
  else
   i++;
 }while(i<closure.tot);
 return -1;
}
void find_goto(int set,int sym)
{
 int i,j,x,arg;
 j=0;
 if(chk_goto(set,sym)==-1)
 {
  for(i=0;i<closure.set_tot[set];i++)
  {
   if(closure.dot[set][i]<(gram.rules[closure.prod[set][i]][0]-1))
   {
    x=gram.rules[closure.prod[set][i]][closure.dot[set][i]+2];
    if(x==sym)
    {
     closure.prod[closure.tot][j]=closure.prod[set][i];
     closure.dot[closure.tot][j++]=closure.dot[set][i]+1;
    }
   }
  }
  closure.set_tot[closure.tot]=j;
//  printf("goto %d %d %d\n",set,sym,j);
  goto_set.set[goto_set.tot]=set;
  goto_set.sym[goto_set.tot]=sym;
  arg=closure.tot;
  goto_set.dest[goto_set.tot++]=find_closure(arg);
 }
}
int chk_goto(int set,int sym)
{
 int i;
 for(i=0;i<goto_set.tot;i++)
 {
  if((goto_set.set[i]==set) && (goto_set.sym[i]==sym))
	return goto_set.dest[i];
 }
 return -1;
}
void table_const()
{
 int i,j,k,b,sym,pos;
 t[tcnt++]='$';
 for(i=0;i<closure.tot;i++)
 {
  for(j=0;j<closure.set_tot[i];j++)
  {
   if(closure.dot[i][j]==(gram.rules[closure.prod[i][j]][0]-1))//dot at the end
   {
    if(closure.prod[i][j]==0)//accept action
     table.action[i][tcnt-1]=ACC;
    else //reduce action
    {
     pos=find_fol(gram.rules[closure.prod[i][j]][1]);
     for(k=1;k<=follow.set[pos][0];k++)
     {
      b=is_T(follow.set[pos][k]);
      table.action[i][b]=RED;
		table.action_state[i][b]=closure.prod[i][j];
     }
    }
   }
   else           //shift action
   {
    sym=gram.rules[closure.prod[i][j]][closure.dot[i][j]+2];
    if((pos=is_T(sym))!=-1)        //chk for terminal after dot
    {
     table.action[i][pos]=SHIFT;
     table.action_state[i][pos]=chk_goto(i,sym);
    }
   }
  }
 }
 for(i=0;i<goto_set.tot;i++)
 {
  pos=is_NT(goto_set.sym[i]);
  if(pos!=-1)
   table.goto_state[goto_set.set[i]][pos]=goto_set.dest[i];
 }
 printf("Parsing table..\n");
 for(i=0;i<tcnt;i++)
  printf("\t%c",t[i]);
 for(i=0;i<ntcnt;i++)
  printf("\t%c",nt[i]);
// printf("\n");
 for(i=0;i<closure.tot;i++)
 {
  printf("\n%d\t",i);
  for(j=0;j<tcnt;j++)
  {
   if(table.action[i][j]==3)
    printf("ACC\t");
   else if(table.action[i][j]==1)
    printf("S%d\t",table.action_state[i][j]);
   else if(table.action[i][j]==2)
    printf("R%d\t",table.action_state[i][j]);
   else
    printf("-\t");
  }
  for(j=0;j<ntcnt;j++)
  {
   if(table.goto_state[i][j]==0)
    printf("-\t");
   else
    printf("%d\t",table.goto_state[i][j]);
  }
 }
}
void follow_calc()
{
 int i,j,k,pos,pos1,pos2,lp=1,flg;
 follow.tot=2;
 follow.set[0][0]=1;
 follow.set[0][1]='$';
 follow.sym[0]=gram.rules[0][1];
 follow.set[1][0]=1;
 follow.set[1][1]='$';
 follow.sym[1]=gram.rules[0][1];
 do{
 for(i=1;i<gram.tot;i++)
 {
  for(j=2;j<=gram.rules[i][0];j++)
  {
	if((is_NT(gram.rules[i][j])!=-1) && (j<gram.rules[i][0]))
	{
	 pos=find_fol(gram.rules[i][j]);
	 if(pos!=-1)
	 {
	  k=1;
	  while(copy(pos,gram.rules[i][j+k]))
		k++;
	 }
	 else
	 {
	  follow.set[follow.tot][0]=0;
	  follow.sym[follow.tot]=gram.rules[i][j];
	  k=1;
	  while(copy(follow.tot,gram.rules[i][j+k]))
		k++;
	  follow.tot++;
	 }
	}
	else if((is_NT(gram.rules[i][j])!=-1) && (j==gram.rules[i][0]))
	{
	 pos=find_fol(gram.rules[i][1]);
	 pos1=find_fol(gram.rules[i][j]);
	 if(pos1!=-1)
	  copy1(pos1,pos);
	 else
	 {
	  follow.set[follow.tot][0]=0;
	  follow.sym[follow.tot]=gram.rules[i][j];
	  copy1(follow.tot,pos);
	  follow.tot++;
	 }
	}
  }
 }
 lp++;}while(lp<=2);
/* printf("FOLLOW SET..\n");
 for(i=0;i<follow.tot;i++)
 {
  printf("%c",follow.sym[i]);
  printf(" - ");
  for(j=1;j<=follow.set[i][0];j++)
  {
	if(follow.set[i][j]==-1)
	 printf("ep ");
	else
	 printf("%c ",follow.set[i][j]);
  }
  printf("\n");
 }*/
}
int copy(int dest,int src)
{
 int pos,i,j,flg=0;
 pos=find_sym(src);
 j=1+follow.set[dest][0];
 for(i=1;i<=first.set[pos][0];i++)
 {
  if(first.set[pos][i]==-1)
	flg=1;
  else if(!search_fol(dest,first.set[pos][i]))
  {
	follow.set[dest][j++]=first.set[pos][i];
	follow.set[dest][0]++;
  }
 }
 return(flg);
}
void copy1(int dest,int src)
{
 int pos,i,j;
 pos=src;
 j=1+follow.set[dest][0];
 for(i=1;i<=follow.set[pos][0];i++)
 {
  if(!search_fol(dest,follow.set[pos][i]))
  {
	follow.set[dest][j++]=follow.set[pos][i];
	follow.set[dest][0]++;
  }
 }
}
int find_fol(int no)
{
 int i;
// printf("@%d",name);
 for(i=1;i<follow.tot;i++)
 {
  if(follow.sym[i]==no)
   return i;
 }
 return -1;
}
int search_fol(int pos,int n)
{
 int i;
 for(i=1;i<=follow.set[pos][0];i++)
 {
  if(follow.set[pos][i]==n)
   return 1;
 }
 return 0;
}
int simulation()
{
 int stack[MAX],top=-1,a,pos,act,lhs,state;
 stack[++top]='$';
 stack[++top]=0;
 printf("Enter a string: ");
 a=getchar();
 while(a!='x')
 {
  if(a==' ' || a=='\n')
	a=getchar();
  else
  {
	pos=is_T(a);
	act=table.action[stack[top]][pos];
	if(act==0)
	 return 0;
	else if(act==1)
	{
	 state=stack[top];
	 stack[++top]=table.action_state[state][pos];
	 a=getchar();
	}
	else if(act==2)
	{
	 lhs=gram.rules[table.action_state[stack[top]][pos]][1];
	 top=top-gram.rules[table.action_state[stack[top]][pos]][0]+1;
	 state=stack[top];
	 pos=is_NT(lhs);
	 stack[++top]=table.goto_state[state][pos];
	}
	else if(act==3)
	 return 1;
  }
 }
 a='$';
 while(top>=0)
 {
  pos=is_T(a);
  act=table.action[stack[top]][pos];
  if(act==0)
	return 0;
  else if(act==1)
  {
	state=stack[top];
	stack[++top]=table.action_state[state][pos];
  }
  else if(act==2)
  {
	lhs=gram.rules[table.action_state[stack[top]][pos]][1];
	top=top-gram.rules[table.action_state[stack[top]][pos]][0]+1;
	state=stack[top];
	pos=is_NT(lhs);
	stack[++top]=table.goto_state[state][pos];
  }
  else if(act==3)
	return 1;
 }
 return 0;
}