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