FIRST of a Given Grammar using C program

Hello Friend,

In this post we will discuss how to find FIRST of a grammar using C.


The rules for finding FIRST of a given grammar is:

1. If X is terminal, FIRST(X) = {X}.
2. If X → ε is a production, then add ε to FIRST(X).
3. If X is a non-terminal, and X → Y₁ Y₂ … Y_k is a production, and ε is in all of FIRST(Y₁), …, FIRST(Y_k), then add ε to FIRST(X).
4. If X is a non-terminal, and X → Y₁ Y₂ … Y_k is a production, then add a to FIRST(X) if for some i, a is in FIRST(Y_i), and ε is in all of FIRST(Y₁), …, FIRST(Y_i-1).

Assumptions:

1. Each Non terminal character is represented by one Uppercase letter.
2. Each Terminal character is represented by one lowercase letter.
3. LHS and RHS of each production will be separated by a "=" symbol.
4. There will be no Blank space within a production string. 
5. Assumed that Left recursion is avoided in all input productions. 

/* Author : Vipin
* mail:   vipinnarayantvm@gmail.com

 *Modified on : 23/03/2105

 */

#include<stdio.h>

#include<ctype.h>

void FIRST(char[],char );

void addToResultSet(char[],char);

int numOfProductions;

char productionSet[10][10];

main()

{

    int i;

    char choice; 

    char c;

    char result[20];

    printf("How many number of productions ? :");

    scanf(" %d",&numOfProductions);

    for(i=0;i<numOfProductions;i++)//read production string eg: E=E+T

    {

        printf("Enter productions Number %d : ",i+1);

        scanf(" %s",productionSet[i]);

    }

    do

    {

        printf("\n Find the FIRST of  :");

        scanf(" %c",&c);

        FIRST(result,c); //Compute FIRST; Get Answer in 'result' array

        printf("\n FIRST(%c)= { ",c);

        for(i=0;result[i]!='\0';i++)

        printf(" %c ",result[i]);       //Display result

        printf("}\n");

         printf("press 'y' to continue : ");
        scanf(" %c",&choice);

    }

    while(choice=='y'||choice =='Y');

}

/*

 *Function FIRST:

 *Compute the elements in FIRST(c) and write them

 *in Result Array.

 */

void FIRST(char* Result,char c)

{

    int i,j,k;

    char subResult[20];

    int foundEpsilon;

    subResult[0]='\0';

    Result[0]='\0';

    //If X is terminal, FIRST(X) = {X}.

    if(!(isupper(c)))

    {

        addToResultSet(Result,c);

               return ;

    }

    //If X is non terminal

    //Read each production

    for(i=0;i<numOfProductions;i++)

    {

//Find production with X as LHS

        if(productionSet[i][0]==c)

        {

//If X → ε is a production, then add ε to FIRST(X).

 if(productionSet[i][2]=='$') addToResultSet(Result,'$');

            //If X is a non-terminal, and X → Y1 Y2 … Yk

            //is a production, then add a to FIRST(X)

            //if for some i, a is in FIRST(Yi),

            //and ε is in all of FIRST(Y1), …, FIRST(Yi-1).

      else

            {

                j=2;

                while(productionSet[i][j]!='\0')

                {

                foundEpsilon=0;

                FIRST(subResult,productionSet[i][j]);

                for(k=0;subResult[k]!='\0';k++)

                    addToResultSet(Result,subResult[k]);

                 for(k=0;subResult[k]!='\0';k++)

                     if(subResult[k]=='$')

                     {

                         foundEpsilon=1;

                         break;

                     }

                 //No ε found, no need to check next element

                 if(!foundEpsilon)

                     break;

                 j++;

                }

            }

    }

}

    return ;

}

/* addToResultSet adds the computed

 *element to result set. 

 *This code avoids multiple inclusion of elements

  */

void addToResultSet(char Result[],char val)

{

    int k;

    for(k=0 ;Result[k]!='\0';k++)

        if(Result[k]==val)

            return;

    Result[k]=val;

    Result[k+1]='\0';

}

Output