rendered paste body/*----------------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;
}