Hello reader,
In this post I am posting implementation of FOLLOW in C.
Note:
If your production statements contain multiple terms connected by '|' then give these terms as separate productions
#include<stdio.h>
In this post I am posting implementation of FOLLOW in C.
Note:
If your production statements contain multiple terms connected by '|' then give these terms as separate productions
#include<stdio.h>
#include<string.h>
int n,m=0,p,i=0,j=0;
char a[10][10],followResult[10];
void follow(char c);
void first(char c);
void addToResult(char);
int main()
{
int i;
int choice;
char c,ch;
printf("Enter the no.of productions: ");
scanf("%d", &n);
printf(" Enter %d productions\nProduction with multiple terms should be give as separate productions \n", n);
for(i=0;i<n;i++)
scanf("%s%c",a[i],&ch);
// gets(a[i]);
do
{
m=0;
printf("Find FOLLOW of -->");
scanf(" %c",&c);
follow(c);
printf("FOLLOW(%c) = { ",c);
for(i=0;i<m;i++)
printf("%c ",followResult[i]);
printf(" }\n");
printf("Do you want to continue(Press 1 to continue....)?");
scanf("%d%c",&choice,&ch);
}
while(choice==1);
}
void follow(char c)
{
if(a[0][0]==c)addToResult('$');
for(i=0;i<n;i++)
{
for(j=2;j<strlen(a[i]);j++)
{
if(a[i][j]==c)
{
if(a[i][j+1]!='\0')first(a[i][j+1]);
if(a[i][j+1]=='\0'&&c!=a[i][0])
follow(a[i][0]);
}
}
}
}
void first(char c)
{
int k;
if(!(isupper(c)))
//f[m++]=c;
addToResult(c);
for(k=0;k<n;k++)
{
if(a[k][0]==c)
{
if(a[k][2]=='$') follow(a[i][0]);
else if(islower(a[k][2]))
//f[m++]=a[k][2];
addToResult(a[k][2]);
else first(a[k][2]);
}
}
}
void addToResult(char c)
{
int i;
for( i=0;i<=m;i++)
if(followResult[i]==c)
return;
followResult[m++]=c;
}
Sample output:
#include >
ReplyDelete#include >
#define MAXCOL 7
//bool checkterminal();
int i=0, j=0, k=0, n=0, check, rhs=2, itteration, firstindex=0, followindex=0, ii=0, jj=0;
char ch, prodn[10][10]={'\0'}, first[MAXCOL]={'\0'}, follow[MAXCOL]={'\0'}, currchar, nextchar;
char *pch, follownext;
void firstoff(char);
void followoff(char);
void print();
int checkterminal(char);
int main(){
clrscr();
printf("\n Enter no of productions : ");
scanf("%d",&n);
// prodn[n][MAXCOL] = '\0';
// get input and store in prodn[][];
for(i=0;i0){
//printf("\nepsilon recurssion n prev ch = %c",nextchar);
firstoff(nextchar);
//break;
}
}
else{
nextchar = prodn[j][i+1]; // to be used if epsilon
firstoff(currchar);
//break;
}
}
itteration++;
}
}
}
void followoff(char c){
if(c == prodn[0][0]){
follow[followindex]='$';
followindex++;
}
else{
for(ii=0; ii=2){ // if 'c' is on RHS of prodn
printf ("\nfound at %dth position in production no:%d",pch-prodn[ii], ii);
printf("******");
follownext = (char)(*pch+1); // next character of 'c'
printf(" --> fnext = %c",follownext);
// check whether follownext is garbage value OR NULL i.e. last symbol in prodn
check = checkterminal(follownext);
if(check!=2 || follownext==NULL){ // if not a valid symbol or NULL
followoff(prodn[ii][0]);
}
else{
check = checkterminal(follownext); // NT or T
if(check==1){
follow[followindex]=follownext; // if T then add to follow[]
followindex++;
}
else{
// find firstoff(follownext)
firstindex=0;
memset(first, '\0', sizeof first); // clear array
firstoff(follownext);
printf("\n firstoff(%c) = %s",follownext, first);
pch=strchr(first,'e');
if(pch!=NULL){ // first[] contains 'e'
// clear first[] and then find follow of LHS e`
firstindex=0;
memset(first, '\0', sizeof first); // clear array
followoff(prodn[ii][0]);
}
else{ // first[] doesnot contains 'e'
printf("\nadding firstoff(%c)",follownext);
printf("\n strcat [ %s + %s ] ",follow,first);
strcat(follow,first);
}
}
}
}
pch=strchr(pch+1,c); // scan further occurance of 'c'
}
}
}
}
int checkterminal(char character){
for(k=0; k<n; k++)
if(character == prodn[k][0])
return 2; //false i.e. NT
return 1; // true i.e. T
}
/*
trial input:
9
P=XYZ
X=a
X=b
X=e
Y=AB
A=c
A=d
B=e
Z=z
A
*/
S > ABa | bCA
ReplyDeleteA > CBCD | $
B > CdA | ad
C > cC | $
D > bSf | a
Pwned
Get a better algorithm
Uchiha: U can enter every production in a new line.
ReplyDelete@Vipin: Its not working for all set of productions:
ReplyDeleteS->iEtST
S->a
T->eS
T->$
E->b
In scanf("%s%c", prod[i],&ch);
ReplyDeletewhat is the role of &ch ??
In scanf("%s%c", prod[i],&ch);
ReplyDeletewhat is the role of &ch ??
@Anonymous
ReplyDeleteTo store enter key in ch, in order to avoid memory leak.
Does not work for
ReplyDelete5
E=TQ
T=FR
Q=+TQ|-TQ|E
R=*FR|/FR|E
F=(E)|i
T
0
This code is not correct.
Hello @Anonymous,
ReplyDeletePlease give input like this:
10
E=TQ
T=FR
Q=+TQ
Q=-TQ
Q=E
R=*FR
R=/FR
R=E
F=(E)
F=i
Hope this will help you.. please refer
sample output screenshot for more clarity..
it is not showing correct result eg->
ReplyDeleteS=aBCd
S=dCBe
B=bB
B=$
C=ca
C=ac
C=$
...for this follow of B is coming c,a but it should come c,a,d,e
Not Running for epsillon Productions
ReplyDelete@Anonymous
ReplyDeletehahahahahahahahha best of luck!
Your Follow Calculation is wrong.
ReplyDelete