Consider the following Grammar :
E -> TE'
E' -> +TE'/∈
T -> FT'
T' -> *FT'/∈
F -> (E)/id
To find the FIRST(E) follow the steps given below:
STEP1: Take the production E-> TE', here the first symbol is T a Non-Terminal then Find the Production of T,
STEP 2: T -> FT', here also a non- terminal occurs at the first position. then find the production of F.
STEP 3: F -> (E) and F-> id, here we can see two terminals, we conclude that :
FIRST(E) = { (,id }
Similarly
FIRST(E')={+,∈}
FIRST(T)={(,id}
FIRST(T')={*,∈}
FIRST(F)={(,id}
IMPLEMENTATION OF FIRST OF A GRAMMAR USING C
Check the sample output..Non terminal must be capital letter, epsilon is represented by # symbol
#include<stdio.h>
#include<ctype.h>
void firstof(char[], char);
void arrangearray(char[], char);
int visited(char );
int noproduction;
char production[100][100];
char visit[100];
int nTerm;
int main()
{
char option;
char ch;
char array[100];
int c,k;
printf("\nEnter Total Number of Productions:");
scanf("%d", &noproduction);
for(c = 0; c < noproduction; c++)
{
printf("\nEnter Production%d:", c + 1);
scanf("%s", production[c]);
}
k=0;
while(k<noproduction)
{
ch=production[k][0];
if(!visited(ch))
{
firstof(array, ch);
printf("\nFirst(%c):\t{ ", ch);
for(c = 0; array[c] != '\0'; c++)
{
printf("%c,", array[c]);
}
printf("}\n");
}
k++;
}
return 0;
}
void firstof(char* array, char ch)
{
int c, j, k;
char tmpresult[100];
int x;
tmpresult[0] = '\0';
array[0] = '\0';
if(!(isupper(ch)))
{
arrangearray(array, ch);
return ;
}
c=0;
while( c < noproduction)
{
if(production[c][0] == ch)
{
if(production[c][2] == '#')
{
arrangearray(array, '#');
}
else
{
j = 2;
while(production[c][j] != '\0')
{
x = 0;
firstof(tmpresult, production[c][j]);
for(k = 0; tmpresult[k] != '\0'; k++)
{
arrangearray(array,tmpresult[k]);
}
for(k = 0; tmpresult[k] != '\0'; k++)
{
if(tmpresult[k] == '#')
{
x = 1;Check the sample output..Non terminal must be capital letter, epsilon is represented by # symbol
#include<stdio.h>
#include<ctype.h>
void firstof(char[], char);
void arrangearray(char[], char);
int visited(char );
int noproduction;
char production[100][100];
char visit[100];
int nTerm;
int main()
{
char option;
char ch;
char array[100];
int c,k;
printf("\nEnter Total Number of Productions:");
scanf("%d", &noproduction);
for(c = 0; c < noproduction; c++)
{
printf("\nEnter Production%d:", c + 1);
scanf("%s", production[c]);
}
k=0;
while(k<noproduction)
{
ch=production[k][0];
if(!visited(ch))
{
firstof(array, ch);
printf("\nFirst(%c):\t{ ", ch);
for(c = 0; array[c] != '\0'; c++)
{
printf("%c,", array[c]);
}
printf("}\n");
}
k++;
}
return 0;
}
void firstof(char* array, char ch)
{
int c, j, k;
char tmpresult[100];
int x;
tmpresult[0] = '\0';
array[0] = '\0';
if(!(isupper(ch)))
{
arrangearray(array, ch);
return ;
}
c=0;
while( c < noproduction)
{
if(production[c][0] == ch)
{
if(production[c][2] == '#')
{
arrangearray(array, '#');
}Check the sample output..Non terminal must be capital letter, epsilon is represented by # symbol
#include<stdio.h>
#include<ctype.h>
void firstof(char[], char);
void arrangearray(char[], char);
int visited(char );
int noproduction;
char production[100][100];
char visit[100];
int nTerm;
int main()
{
char option;
char ch;
char array[100];
int c,k;
printf("\nEnter Total Number of Productions:");
scanf("%d", &noproduction);
for(c = 0; c < noproduction; c++)
{
printf("\nEnter Production%d:", c + 1);
scanf("%s", production[c]);
}
k=0;
while(k<noproduction)
{
ch=production[k][0];
if(!visited(ch))
{
firstof(array, ch);
printf("\nFirst(%c):\t{ ", ch);
for(c = 0; array[c] != '\0'; c++)
{
printf("%c,", array[c]);
}
printf("}\n");
}
k++;
}
return 0;
}
void firstof(char* array, char ch)
{
int c, j, k;
char tmpresult[100];
int x;
tmpresult[0] = '\0';
array[0] = '\0';
if(!(isupper(ch)))
{
arrangearray(array, ch);
return ;
}
c=0;
while( c < noproduction)
{
if(production[c][0] == ch)
{
if(production[c][2] == '#')
{
arrangearray(array, '#');
}
else
{
j = 2;
while(production[c][j] != '\0')
{
x = 0;
firstof(tmpresult, production[c][j]);
for(k = 0; tmpresult[k] != '\0'; k++)
{
arrangearray(array,tmpresult[k]);
}
for(k = 0; tmpresult[k] != '\0'; k++)
{
if(tmpresult[k] == '#')
{
x = 1;
break;
}
}
if(x==0)
{
break;
}
j++;
}
}
}
c++;
}
return;
}
void arrangearray(char array[], char value)
{
int tmp;
for(tmp = 0; array[tmp] != '\0'; tmp++)
{
if(array[tmp] == value)
{
return;
}
}
array[tmp] = value;
array[tmp + 1] = '\0';
}
int visited(char ch)
{
int i=0;
for(i=0;i<nTerm;i++)
{
if(visit[i]==ch)
{
return 1;
}
}
visit[i]=ch;
nTerm++;
return 0;
}
else
{
j = 2;
while(production[c][j] != '\0')
{
x = 0;
firstof(tmpresult, production[c][j]);
for(k = 0; tmpresult[k] != '\0'; k++)
{
arrangearray(array,tmpresult[k]);
}
for(k = 0; tmpresult[k] != '\0'; k++)
{
if(tmpresult[k] == '#')
{
x = 1;
break;
}
}
if(x==0)
{
break;
}
j++;
}
}
}
c++;
}
return;
}
void arrangearray(char array[], char value)
{
int tmp;
for(tmp = 0; array[tmp] != '\0'; tmp++)
{
if(array[tmp] == value)
{
return;
}
}
array[tmp] = value;
array[tmp + 1] = '\0';
}
int visited(char ch)
{
int i=0;
for(i=0;i<nTerm;i++)
{
if(visit[i]==ch)
{
return 1;
}
}
visit[i]=ch;
nTerm++;
return 0;
}
break;
}
}
if(x==0)
{
break;
}
j++;
}
}
}
c++;
}
return;
}
void arrangearray(char array[], char value)
{
int tmp;
for(tmp = 0; array[tmp] != '\0'; tmp++)
{
if(array[tmp] == value)
{
return;
}
}
array[tmp] = value;
array[tmp + 1] = '\0';
}
int visited(char ch)
{
int i=0;
for(i=0;i<nTerm;i++)
{
if(visit[i]==ch)
{
return 1;
}
}
visit[i]=ch;
nTerm++;
return 0;
}
