# CS606 Assignment 2 Solution Spring 2021 – 100% Correct and Complete Solution Guideline with Code

CS606 Assignment 2 Solution Spring 2021 – 100% Correct and Complete Solution Guideline with Code. Student is asked to Convert a Given CFG into First Set and Follow Set . Here is the complete C++ Program to calculate First and Follow sets of given CFG grammar.

Question:

Consider the following CFG.

S à AB

A à DG | ε

B à *AB | ε

D à id | ( S

G à +DG | ε

a)     Find First sets for above grammar.                        [10 Marks]

b)    Find Follow sets for above grammar.                     [10 Marks]

Question:

Consider the following CFG.

• S -> AB
• A ->DG | ε
• B ->*AB | ε
• D ->id | ( S
• G -> +DG | ε

## a)     Find First sets for above grammar.                        [10 Marks] (watch the video and implement the code

Store the grammar on a 2D character array `production``findfirst` function is for calculating the first of any non terminal. Calculation of `first` falls under two broad cases :

• If the first symbol in the R.H.S of the production is a Terminal then it can directly be included in the first set.
• If the first symbol in the R.H.S of the production is a Non-Terminal then call the findfirst function again on that Non-Terminal. To handle these cases like Recursion is the best possible solution. Here again, if the First of the new Non-Terminal contains an epsilon then we have to move to the next symbol of the original production which can again be a Terminal or a Non-Terminal.

## b)    Find Follow sets for above grammar.                     [10 Marks]

Source Article (https://www.geeksforgeeks.org/program-calculate-first-follow-sets-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;

// Stores the final result
// of the Follow Sets
char calc_follow;
int m = 0;

// Stores the production rules
char production;
char f, first;
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, "E=TR");
strcpy(production, "R=+TR");
strcpy(production, "R=#");
strcpy(production, "T=FY");
strcpy(production, "Y=*FY");
strcpy(production, "Y=#");
strcpy(production, "F=(E)");
strcpy(production, "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];
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];
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 == 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])
{
// Calculate the follow of the Non-Terminal
// in the L.H.S. of the production
follow(production[i]);
}
}
}
}
}

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] == c)
{
if(production[j] == '#')
{
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]))
{
first[n++] = production[j];
}
else
{
// Recursion to calculate First of
// New Non-Terminal we encounter
// at the beginning
findfirst(production[j], 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] == 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]);
}
else
{
// Recursion to the next symbol
// in case we encounter a "#"
followfirst(production[c1][c2], c1, c2+1);
}
}
j++;
}
}
}``````

Input 