/*----------------HEADER FILES----------------*/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
#define MAXT  15
#define MAXNT 10
#define MAX 20
/*----------------------FUNCTIONS-----------------*/
void split_prod();
void get_input();
int check(char,int,int);
void items_construction();
int check_prod(struct productions,int,int);
int check_items(int);
void closure(struct productions,int);
void compute_goto();
int check_first(char,char*,int);
void list_prod();
void construct_first();
void first(char,char*,int);
void construct_follow();
void follow(char,char*,int);
int find_mapid(char);
int find_mapid2(char);
int map_prod(int,int);
void construct_table();
void print_collections();
void print_parsetable();
void simulate();
void push(int);
int top_stack();
int pop();

/*--------------GLOBAL VARIABLES------------------------*/
int num_prod,nt_id,t_id,uplim=0,uplim_fol=0;
int total_item,parse_stack[MAX],top=0;
char terminal[MAXT],nonterminal[MAXNT];
char first_strings[MAX][MAXT],follow_strings[MAX][MAXT];

/*-----------------STRUCTURES----------------------*/
struct actionp       //ACTION PART
{
	char sorr;
	int val;
};

struct ptable        //PARSE TABLE
{
	int gotop[MAXNT];
	struct actionp action[MAXT];
}parse_table[MAX];

struct productions    //PRODUCTIONS
{
	char left;
	char right[MAX];
	int dot;
}prod[MAX];

struct itemlist     //COLLECTIONS
{
	int nprod;
	struct productions prod_in_item[MAX];
}items[MAX];

/*------------FUNCTION DEFINITIONS----------------*/
void get_input()
{                  //GETTING THE GRAMMAR INPUT
	int i;
	FILE *fp;
	fp=fopen("slr.txt","r");
	if(!fp)
	{
		printf("Cant open file\n");
		exit(1);
	}
	fscanf(fp,"%d\n",&num_prod);
	for(i=0;i<MAX;i++)
	{
		if(i>=num_prod)
			break;
		fscanf(fp,"%c %s\n",&prod[i+1].left,prod[i+1].right);
		if(i==0)
		{
			prod[i].left='M';
			prod[i].right[0]=prod[i+1].left;
			prod[i].right[1]='\0';
			prod[i].dot=0;
		}
		prod[i+1].dot=0;
	}
	num_prod++;
	split_prod();
}

void split_prod()//SPLITTING THE PRODUCTIONS INTO TERMINALS & NONTERMINALS
{
	int i=0,k=0,l=0,j=0;
	for(i=0;i<num_prod;i++)
	{
		if(check(prod[i].left,j,1)==1)
		{
			nonterminal[j]=prod[i].left;
			j++;
		}
		for(k=0;k<strlen(prod[i].right);k++)
		{
			if(prod[i].right[k]>64&&prod[i].right[k]<91)
			{
				if(check(prod[i].right[k],j,1)==1)
				{
					nonterminal[j]=prod[i].right[k];
					j++;
				}
			}
			else
			{
				if(check(prod[i].right[k],l,2)==2)
				{
					terminal[l]=prod[i].right[k];
					l++;
				}
			}
		}
	}
	nonterminal[j]='\0';
	terminal[l]='\0';
	nt_id=j;
	t_id=l;
}

int check(char search,int limit,int status)
{			//CHECK FOR TERMINAL OR NONTERMINAL
	int i=0;
	if(status==1)
	{
		for(i=0;i<limit;i++)
		{
			if(search==nonterminal[i])
				return 0;
		}
		return 1;
	}
	else
	{
		for(i=0;i<limit;i++)
		{
			if(search==terminal[i])
				return 0;
		}
		return 2;
	}
}

void items_construction()
{                          //CONSTRUCT I0
	items[0].nprod=0;
	closure(prod[0],0);
}
int check_prod(struct productions temp,int item_index,int nprod)
{                                 //CHECK 4 DUPLIACTE PRODUCTIONS
	int i=0;
	for(i=0;i<nprod;i++)
	{
		if(temp.left==items[item_index].prod_in_item[i].left)
		{
			if(strcmp(temp.right,items[item_index].prod_in_item[i].right)==0)
			{
				if(temp.dot==items[item_index].prod_in_item[i].dot)
					return 0;
			}
		}
	}
	return 1;
}

int check_items(int item_index)
{                             //CHECK 4 DUPLICATE ITEMS
	int i=0,flag,j;
	for(i=0;i<item_index;i++)
	{
		flag=items[i].nprod;
		for(j=0;j<items[i].nprod;j++)
		{
			if(items[i].prod_in_item[j].left==items[item_index].prod_in_item[j].left)
			{
				if(strcmp(items[i].prod_in_item[j].right,items[item_index].prod_in_item[j].right)==0)
				{
					if(items[i].prod_in_item[j].dot==items[item_index].prod_in_item[j].dot)
						flag--;
				}
			}
		}
		if(!flag)
			return i;
	}

	return 0;
}

void closure(struct productions temp,int item_index)
{
	int i=0;              //FINDING CLOSURE OF A PRODUCTION
	items[item_index].prod_in_item[items[item_index].nprod++]=temp;
	if(!check(temp.right[temp.dot],nt_id,1))
	{
		for(i=0;i<=num_prod;i++)
		{
			if(prod[i].left==temp.right[temp.dot])
			{
				if(check_prod(prod[i],item_index,items[item_index].nprod))
				{
					closure(prod[i],item_index);
				}
			}
		}
	}
}
void compute_goto()
{                     //COMPUTES GOTO PART
	int i=0,item_index=1,j=0,k=0,flag=0,flag1;
	struct productions temp;
	for(i=0;i<MAX;i++)
		for(j=0;j<MAXNT;j++)
			parse_table[i].gotop[j]=-1;
	for(i=0;i<item_index;i++)
	{
		 for(k=0;k<nt_id;k++)
		 {
			 flag=0;
			 for(j=0;j<items[i].nprod;j++)
			 {
				if(items[i].prod_in_item[j].right[items[i].prod_in_item[j].dot]==nonterminal[k])
				{
					temp=items[i].prod_in_item[j];
					temp.dot++;
					closure(temp,item_index);
					flag++;
				}
			 }
			 flag1=check_items(item_index);
			 if(flag1&&flag!=0)
				 parse_table[i].gotop[k]=flag1;
			 if(flag!=0&&flag1==0)
			 {
				 parse_table[i].gotop[k]=item_index;
				 item_index++;
			 }
			 else
				 items[item_index].nprod=0;
		 }
		 for(k=0;k<t_id;k++)
		 {
			 flag=0;
			 for(j=0;j<items[i].nprod;j++)
			 {
				if(items[i].prod_in_item[j].right[items[i].prod_in_item[j].dot]==terminal[k])
				{
					temp=items[i].prod_in_item[j];
					temp.dot++;
					closure(temp,item_index);
					flag++;
				}
			 }
			 flag1=check_items(item_index);
			 if(flag1&&flag!=0)
			 {
				 parse_table[i].action[k].sorr='s';
				 parse_table[i].action[k].val=flag1;
			 }
			 if(flag!=0&&flag1==0)
			 {
				 parse_table[i].action[k].sorr='s';
				 parse_table[i].action[k].val=item_index;
				 item_index++;
			 }
			 else
				items[item_index].nprod=0;
		 }
	}
	total_item=item_index;
}

void list_prod()
{                 //DISPLAY PRODUCTIONS
	int i=0;
	printf("\t\tSLR PARSER\n");
	printf("PRODUCTIONS:\n");
	for(i=0;i<num_prod;i++)
		printf("%d:%c->%s\n",i,prod[i].left,prod[i].right);
	printf("\nFIRST:");

}

void construct_first()
{
	int i=0;	//CONSTRUCTION OF FIRST
	char str[MAXT];
	list_prod();
	for(i=0;i<nt_id;i++)
	{
		first(nonterminal[i],str,0);
		printf("\nFIRST:%d->%s",i,str);
		strcpy(first_strings[i],str);
	}
}

void first(char ch,char*str,int lim)
{
	int i=0,k=0;	//FIRST FUNCTION
	uplim=lim;
	for(i=0;i<num_prod;i++)
	{
		if(ch==prod[i].left)
		{
			if(!check(prod[i].right[0],t_id,2))
			{
				if(check_first(prod[i].right[0],str,uplim))
				{
					str[uplim]=prod[i].right[0];
					uplim++;
				}
			}
			else
			{
				for(k=0;k<strlen(prod[i].right);k++)
				{
					first(prod[i].right[k],str,uplim);
					if(check_first('@',str,uplim))
						break;
				}
			}
		}
	}
	str[uplim]='\0';
}

int check_first(char ch,char*str1,int uplim)
{
	int i=0;	//CHECK FOR DUPLICATES IN FIRST STRING
	for(i=0;i<uplim;i++)
	{
		if(ch==str1[i])
			return 0;
	}
	return 1;
}

void construct_follow()
{
	int i=0;	//CONSTRUCTION OF FOLLOW
	char str[MAXT];
	getch();
	printf("\n\nFOLLOW:");
	for(i=0;i<nt_id;i++)
	{
		follow(nonterminal[i],str,0);
		printf("\nFOLLOW:%d->%s",i,str);
		fflush(stdout);
		strcpy(follow_strings[i],str);
	}
}

void follow(char ch,char*str,int lim)
{
	int i=0,len=0,j=0,map_id=0,k=0;	//FOLLOW FUNCTION
	char fchar;
	uplim_fol=lim;
	if(ch==nonterminal[0])
	{
		if(check_first('$',str,uplim_fol))
		{
			str[uplim_fol]='$';
			uplim_fol++;
		}
	}
	for(i=0;i<num_prod;i++)
	{
		len=strlen(prod[i].right);
		for(j=0;j<len;j++)
		{
			if(ch==prod[i].right[j])
			{
				if(j!=len-1)
				{
					if(!check(prod[i].right[j+1],t_id,2))
					{
					//can check for epsilon
						if(check_first(prod[i].right[j+1],str,uplim_fol))
						{
							str[uplim_fol]=prod[i].right[j+1];
							uplim_fol++;
						}
					}
					else
					{
						map_id=find_mapid(prod[i].right[j+1]);
						for(k=0;k<strlen(first_strings[map_id]);k++)
						{
							fchar=first_strings[map_id][k];
							if(fchar!='@')
							{
								if(check_first(fchar,str,uplim_fol))
								{
									str[uplim_fol]=fchar;
									uplim_fol++;
								}
							}
							else
							{
								if(prod[i].left!=prod[i].right[j+1])
									follow(prod[i].left,str,uplim_fol);
							}
						}
					}
				}
				else
				{
					if(prod[i].left!=prod[i].right[j])
						follow(prod[i].left,str,uplim_fol);
				}
			 }
		}
	}
	str[uplim_fol]='\0';
}

int find_mapid(char ch)
{
	int i=0; //MAPS THE NONTERMINAL
	for(i=0;i<nt_id;i++)
	{
		if(ch==nonterminal[i])
			return i;
	}
	return 0;
}
int map_prod(int i,int j)
{                       //MAPS THE PRODUCTION WITH INDEX
	int k;
	for(k=0;k<num_prod;k++)
	{
		if(prod[k].left==items[i].prod_in_item[j].left)
		{
			if(strcmp(prod[k].right,items[i].prod_in_item[j].right)==0)
				return k;
		}
	}
	return -1;
}
int find_mapid2(char ch)
{
	int i=0; //MAPS THE COPYTERMINAL
	for(i=0;i<t_id;i++)
	{
		if(ch==terminal[i])
			return i;
	}
	return 0;
}

void construct_table()
{                        //PARSE TABLE CONSTRUCTION
	int i=0,j=0,k,len1,len2,mapid,mapid1;
	strcat(terminal,"$");
	t_id++;
	for(i=0;i<total_item;i++)
	{
		for(j=0;j<items[i].nprod;j++)
		{
			len1=strlen(items[i].prod_in_item[j].right);
			len2=items[i].prod_in_item[j].dot;
			if(len1==len2)
			{
				mapid=find_mapid(items[i].prod_in_item[j].left);
				if(items[i].prod_in_item[j].left!='M')
				{
					for(k=0;k<strlen(follow_strings[mapid]);k++)
					{
						mapid1=find_mapid2(follow_strings[mapid][k]);
						parse_table[i].action[mapid1].sorr='r';
						parse_table[i].action[mapid1].val=map_prod(i,j);
					}
				}
				else
				{
					mapid1=find_mapid2(follow_strings[mapid][0]);
					parse_table[i].action[mapid1].sorr='A';
				}
			}
		}
	}
}
void print_collections()
{                     //DISPLAY THE COLLECTIONS
	int i,j;
	printf("\n\n");
	for(i=0;i<total_item;i++)
	{
		printf("ITEM%d:",i);
		for(j=0;j<items[i].nprod;j++)
		{
			printf(" ([%c->",items[i].prod_in_item[j].left);
			printf("%s],",items[i].prod_in_item[j].right);
			printf("%d)",items[i].prod_in_item[j].dot);
		}
		printf("\n");
	}
}
void print_parsetable()
{                     //DISPLAYS PARSE TABLE
	int i,j;
	printf("PARSE TABLE\n");
	printf("\tGOTO\t\t\tACTION\n");
	for(i=0;i<total_item;i++)
	{
		for(j=1;j<nt_id;j++)
			printf("\t%d",parse_table[i].gotop[j]);
		for(j=0;j<t_id;j++)
		{
			printf("\t%c",parse_table[i].action[j].sorr);
			printf("%d",parse_table[i].action[j].val);
		}
		printf("\n");
	}
}

void simulate()
{			//SIMULATE THE INPUT STRING FOR VALIDITY
	int i=0,mapid,topel,val,rlen,el;
	char parse_string[MAX],sorr,temp;
	printf("\nENTER THE STRING:");
	scanf("%s",parse_string);
	push(0);
	while(parse_string[i]!='\0')
	{
		mapid=find_mapid2(parse_string[i]);
		topel=top_stack();
		sorr=parse_table[topel].action[mapid].sorr;
		val=parse_table[topel].action[mapid].val;
		if(sorr=='s')
		{
			i++;
			push(val);
		}
		else if(sorr=='r')
		{
			temp=prod[val].left;
			rlen=strlen(prod[val].right);
			while(rlen!=0)
			{
				el=pop();
				rlen--;
			}
			if(el==-1)
			{
				printf("\nINVALID STRING\n");
				getch();					exit(1);
			}
			topel=top_stack();
			mapid=find_mapid(temp);
			val=parse_table[topel].gotop[mapid];
			push(val);
		}
		else if(sorr=='A')
		{
			printf("\nVALID STRING\n");
			getch();
			exit(1);
		}
		else
		{
			printf("\nINVALID STRING\n");
			getch();
			exit(1);
		}
	}
}


void push(int ch)
{		//PUSH INTO THE PARSESTACK
	parse_stack[top++]=ch;
}

int pop()
{		//POP FROM THE PARSESTACK
	top--;
	if(top<0)
		return -1;
	return(parse_stack[top]);
}
int top_stack()
{		//RETURNS TOP ELEM FROM THE PARSESTACK
	if(top<0)
		return -1;
	return(parse_stack[top-1]);
}

int main()
{
	clrscr();
	get_input();
	items_construction();
	compute_goto();
	construct_first();
	construct_follow();
	print_collections();
	construct_table();
	print_parsetable();
	simulate();
	getch();
	return 0;
}