Last active
November 3, 2018 18:34
-
-
Save AmalJossy/d342df2d3fda6d43b0e5cf13922eb6b2 to your computer and use it in GitHub Desktop.
Program to find first and follow of non terminals in a grammer
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include<stdio.h> | |
#include<string.h> | |
/*******/ | |
// row 1 : no of rules | |
// rows>1: production rules | |
/*******/ | |
int p; | |
char NTERM[20]; | |
char LHS[20]; | |
char RHS[20][10]; | |
int containsE(char *str){ | |
int contains=0,l=strlen(str); | |
while(l-->0){ | |
if(str[l]=='E'){ | |
contains=1; | |
break; | |
} | |
} | |
return contains; | |
} | |
void append(char *str, char ch){ | |
// printf("append(%s,%c)",str,ch); | |
int i=0,l=strlen(str); | |
for(i=0;i<l;i++){ | |
if(str[i]==ch){ | |
return; | |
} | |
} | |
str[l]=ch; | |
str[l+1]='\0'; | |
// printf("=%s\n",str); | |
} | |
void strcpyUnique(char *str1, char *str2 ,int blockE){ | |
// printf("strcpyUnique(%s,%s)",str1,str2); | |
int l1=strlen(str1); | |
int l2=strlen(str2); | |
int i,j,occurance; | |
for(i=0;i<l2;i++){ | |
if(str2[i]=='E' && blockE) continue; | |
occurance=0; | |
for(j=0;j<l1;j++){ | |
if(str1[j]==str2[i]) { | |
occurance=1; | |
break; | |
} | |
} | |
if(occurance==0) str1[l1++]=str2[i]; | |
} | |
str1[l1]='\0'; | |
// printf("=%s\n",str1); | |
} | |
void first(char lhs, char* RESULT){ | |
char FIRST[10]="",copy[10]; | |
int index=0,i,j; | |
for(i=0;i<p;i++){ | |
j=0; | |
if(lhs==LHS[i]){ | |
if(RHS[i][0]!='E'){ | |
if(RHS[i][0]<'A' || RHS[i][0]>'Z'){ | |
append(FIRST,RHS[i][0]); | |
} | |
else{ // rule gave non terminal | |
first(RHS[i][j],copy); | |
while(containsE(copy)){ | |
if(RHS[i][++j]=='\0'){ | |
strcpyUnique(FIRST,copy,0); | |
break; | |
} | |
strcpyUnique(FIRST,copy,1); | |
first(RHS[i][j],copy); | |
} | |
if(containsE(copy)==0){ | |
strcpyUnique(FIRST,copy,1); | |
} | |
} | |
} | |
else{ | |
append(FIRST,'E'); | |
} | |
} | |
} | |
strcpy(RESULT,FIRST); // done | |
// printf("first(%c)=%s\n",lhs,RESULT); | |
} | |
void follow(char nterm,char *RESULT){ | |
// printf("Follow(%c)\n",nterm); | |
char FOLLOW[10]="",copy[10]={0}; | |
if(nterm==LHS[0]) | |
append(FOLLOW,'$'); | |
int i,j,k=1; | |
for(i=0;i<p;i++){ | |
for(j=0;RHS[i][j]!='\0';j++){ | |
if(nterm==RHS[i][j]){ | |
while(1){ | |
if(RHS[i][j+1]=='\0'){ | |
if(LHS[i]!=RHS[i][j]){ | |
follow(LHS[i],copy); | |
strcpyUnique(FOLLOW,copy,1); | |
} | |
break; | |
} | |
else if(RHS[i][j+1]>='A' && RHS[i][j+1]<='Z'){ | |
// append(FOLLOW,'^'); | |
first(RHS[i][j+1],copy); | |
strcpyUnique(FOLLOW,copy,1); | |
if(containsE(copy)){ | |
j++; | |
}else{ | |
break; | |
} | |
} | |
else{ | |
append(FOLLOW,RHS[i][j+1]); | |
break; | |
} | |
} | |
} | |
} | |
} | |
strcpy(RESULT,FOLLOW); | |
// printf("Follow(%c)=%s\n",nterm,RESULT); | |
} | |
int main(){ | |
int i,j; | |
char FIRST[10][10]={0},FOLLOW[10][10]={0}; | |
scanf("%d",&p); | |
for(i=0;i<p;i++){ | |
scanf(" %c->%s",&LHS[i],RHS[i]); | |
} | |
int store=0,bit,n=0; | |
for(i=0;i<p;i++){ | |
bit=1<< (LHS[i]-'A'); | |
if((store&bit)!=0){ | |
continue; | |
} | |
store|=bit; | |
NTERM[n++]=LHS[i]; | |
} | |
for(i=0;i<n;i++){ | |
first(NTERM[i],FIRST[i]); | |
printf("FIRST(%c) : %s\n",NTERM[i],FIRST[i]); | |
} | |
for(i=0;i<n;i++){ | |
follow(NTERM[i],FOLLOW[i]); | |
printf("FOLLOW(%c) : %s\n",NTERM[i],FOLLOW[i]); | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment