Question

Answer 1

/ C program to calculate the First and

// Follow sets of a given grammar

#include<stdio.h>

#include<ctype.h>

#include<string.h>

// Functions to calculate Follow

void followfirst(char, int, int);

void follow(char c);

// Function to calculate First

void findfirst(char, int, int);

int count, n = 0;

// Stores the final result  

// of the First Sets

char calc_first[10][100];

// Stores the final result

// of the Follow Sets

char calc_follow[10][100];

int m = 0;

// Stores the production rules

char production[10][10];

char f[10], first[10];

int k;

char ck;

int e;

int main(int argc, char **argv)

{

  

  int jm = 0;

  

  int km = 0;

  

  int i, choice;

  

  char c, ch;

  

  count = 8;

  

  

  

  // The Input grammar

  

  strcpy(production[0], "E=TR");

  

  strcpy(production[1], "R=+TR");

  

  strcpy(production[2], "R=#");

  

  strcpy(production[3], "T=FY");

  

  strcpy(production[4], "Y=*FY");

  

  strcpy(production[5], "Y=#");

  

  strcpy(production[6], "F=(E)");

  

  strcpy(production[7], "F=i");

  

  

  

  int kay;

  

  char done[count];

  

  int ptr = -1;

  

  

  

  // Initializing the calc_first array

  

  for(k = 0; k < count; k++) {

    

    for(kay = 0; kay < 100; kay++) {

      

      calc_first[k][kay] = '!';

      

    }

    

  }

  

  int point1 = 0, point2, xxx;

  

  

  

  for(k = 0; k < count; k++)

    

    {

      

      c = production[k][0];

      

      point2 = 0;

      

      xxx = 0;

      

      

      

      // Checking if First of c has

      

      // already been calculated

      

      for(kay = 0; kay <= ptr; kay++)

        

        if(c == done[kay])

          

        xxx = 1;

      

      

      

      if (xxx == 1)

        

        continue;

      

      

      

      // Function call

      

      findfirst(c, 0, 0);

      

      ptr += 1;

      

      

      

      // Adding c to the calculated list

      

      done[ptr] = c;

      

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

      

      calc_first[point1][point2++] = c;

      

      

      

      // Printing the First Sets of the grammar

      

      for(i = 0 + jm; i < n; i++) {

        

        int lark = 0, chk = 0;

        

        

        

        for(lark = 0; lark < point2; lark++) {

          

          

          

          if (first[i] == calc_first[point1][lark])

            

            {

              

              chk = 1;

              

              break;

              

            }

          

        }

        

        if(chk == 0)

          

          {

            

            printf("%c, ", first[i]);

            

            calc_first[point1][point2++] = first[i];

            

          }

        

      }

      

      printf("}\n");

      

      jm = n;

      

      point1++;

      

    }

  

  printf("\n");

  

  printf("-----------------------------------------------\n\n");

  

  char donee[count];

  

  ptr = -1;

  

  

  

  // Initializing the calc_follow array

  

  for(k = 0; k < count; k++) {

    

    for(kay = 0; kay < 100; kay++) {

      

      calc_follow[k][kay] = '!';

      

    }

    

  }

  

  point1 = 0;

  

  int land = 0;

  

  for(e = 0; e < count; e++)

    

    {

      

      ck = production[e][0];

      

      point2 = 0;

      

      xxx = 0;

      

      

      

      // Checking if Follow of ck

      

      // has alredy been calculated

      

      for(kay = 0; kay <= ptr; kay++)

        

        if(ck == donee[kay])

          

        xxx = 1;

      

      

      

      if (xxx == 1)

        

        continue;

      

      land += 1;

      

      

      

      // Function call

      

      follow(ck);

      

      ptr += 1;

      

      

      

      // Adding ck to the calculated list

      

      donee[ptr] = ck;

      

      printf(" Follow(%c) = { ", ck);

      

      calc_follow[point1][point2++] = ck;

      

      

      

      // Printing the Follow Sets of the grammar

      

      for(i = 0 + km; i < m; i++) {

        

        int lark = 0, chk = 0;

        

        for(lark = 0; lark < point2; lark++)  

          

          {

            

            if (f[i] == calc_follow[point1][lark])

              

              {

                

                chk = 1;

                

                break;

                

              }

            

          }

        

        if(chk == 0)

          

          {

            

            printf("%c, ", f[i]);

            

            calc_follow[point1][point2++] = f[i];

            

          }

        

      }

      

      printf(" }\n\n");

      

      km = m;

      

      point1++;  

      

    }

}

void follow(char c)

{

  

  int i, j;

  

  

  

  // Adding "$" to the follow

  

  // set of the start symbol

  

  if(production[0][0] == c) {

    

    f[m++] = '$';

    

  }

  

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

    

    {

      

      for(j = 2;j < 10; j++)

        

        {

          

          if(production[i][j] == c)

            

            {

              

              if(production[i][j+1] != '\0')

                

                {

                  

                  // Calculate the first of the next

                  

                  // Non-Terminal in the production

                  

                  followfirst(production[i][j+1], i, (j+2));

                  

                }

              

              

              

              if(production[i][j+1]=='\0' && c!=production[i][0])

                

                {

                  

                  // Calculate the follow of the Non-Terminal

                  

                  // in the L.H.S. of the production

                  

                  follow(production[i][0]);

                  

                }

              

            }  

          

        }

      

    }

}

void findfirst(char c, int q1, int q2)

{

  

  int j;

  

  

  

  // The case where we  

  

  // encounter a Terminal

  

  if(!(isupper(c))) {

    

    first[n++] = c;

    

  }

  

  for(j = 0; j < count; j++)

    

    {

      

      if(production[j][0] == c)

        

        {

          

          if(production[j][2] == '#')

            

            {

              

              if(production[q1][q2] == '\0')

                

                first[n++] = '#';

              

              else if(production[q1][q2] != '\0'

                

                && (q1 != 0 || q2 != 0))

                

                {

                  

                  // Recursion to calculate First of New

                  

                  // Non-Terminal we encounter after epsilon

                  

                  findfirst(production[q1][q2], q1, (q2+1));

                  

                }

              

              else

                

                first[n++] = '#';

              

            }

          

          else if(!isupper(production[j][2]))

            

            {

              

              first[n++] = production[j][2];

              

            }

          

          else

            

            {

              

              // Recursion to calculate First of

              

              // New Non-Terminal we encounter  

              

              // at the beginning

              

              findfirst(production[j][2], j, 3);

              

            }

          

        }

      

    }  

}

void followfirst(char c, int c1, int c2)

{

  

  int k;

  

  

  

  // The case where we encounter

  

  // a Terminal

  

  if(!(isupper(c)))

    

    f[m++] = c;

  

  else

    

    {

      

      int i = 0, j = 1;

      

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

        

        {

          

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

            

            break;

          

        }

      

      

      

      //Including the First set of the

      

      // Non-Terminal in the Follow of

      

      // the original query

      

      while(calc_first[i][j] != '!')

        

        {

          

          if(calc_first[i][j] != '#')  

            

            {

              

              f[m++] = calc_first[i][j];

              

            }

          

          else

            

            {

              

              if(production[c1][c2] == '\0')

                

                {

                  

                  // Case where we reach the

                  

                  // end of a production

                  

                  follow(production[c1][0]);

                  

                }

              

              else

                

                {

                  

                  // Recursion to the next symbol

                  

                  // in case we encounter a "#"

                  

                  followfirst(production[c1][c2], c1, c2+1);

                  

                }

              

            }

          

          j++;

          

        }

      

    }

}