Skip to content

Instantly share code, notes, and snippets.

@AmalJossy
Last active November 3, 2018 18:34
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save AmalJossy/d342df2d3fda6d43b0e5cf13922eb6b2 to your computer and use it in GitHub Desktop.
Save AmalJossy/d342df2d3fda6d43b0e5cf13922eb6b2 to your computer and use it in GitHub Desktop.
Program to find first and follow of non terminals in a grammer
#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