Search This Blog

Wednesday, October 9, 2013

FIRST SET of a Given Grammar using C program

The rules for finding FIRST of a given grammar is:
  1. If X is terminal, then FIRST( X ) is {X}.
  2. If X -->  ε is a production, then add  ε  to FIRST (X).
  3. If X is a nonterminal and X--> Y1Y2 . . . Yk is a production, then if Y1 doesnt derive  ε  all in Y1 will come under X else move to Y2 and so on.

#include<stdio.h>
#include<ctype.h>


void FIRST(char );
int count,n=0;
char prodn[10][10], first[10];

main()
{
int i,choice;
char c,ch;
printf("How many productions ? :");
scanf("%d",&count);
printf("Enter %d productions epsilon= $ :\n\n",count);
for(i=0;i<count;i++)
scanf("%s%c",prodn[i],&ch);
do
{
n=0;
printf("Element :");
scanf("%c",&c);
FIRST(c);
printf("\n FIRST(%c)= { ",c);
for(i=0;i<n;i++)
printf("%c ",first[i]);
printf("}\n");

printf("press 1 to continue : ");
scanf("%d%c",&choice,&ch);
}
while(choice==1);


}

void FIRST(char c)
{
int j;
if(!(isupper(c)))first[n++]=c;
for(j=0;j<count;j++)
{
if(prodn[j][0]==c)
{
if(prodn[j][2]=='$') first[n++]='$';
else if(islower(prodn[j][2]))first[n++]=prodn[j][2];
else FIRST(prodn[j][2]);
}
}
}


Output

How many productions? 8

Enter 8 productions:

E = TD
D=+TD
D=$
T=FS
S=*FS
S=$
F=(E)
F=a

FIRST (E) = FIRST (T) =FIRST (F) = { ( , a}
FIRST (D) = { + , ε }
FIRST (S)= { * ,  ε  }





5 comments:

  1. Plse can u explain this code in simple lines.....plse if u can..... I'll be very thankful to you...

    ReplyDelete
  2. S->aABc
    A->Abc/b
    B->d

    this above production is not getting desired output.

    ReplyDelete
    Replies
    1. Thats because the Grammar is left recursive, you need to convert it to right recursive grammar for the code to work

      Delete
  3. Its not working for S=a|$, please look into it

    ReplyDelete