Write C program to compute the First Sets for the given Grammar
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define MAX 10
int n; // number of productions
char productions[MAX][MAX], first[MAX][MAX];
int first_done[MAX];
// Function to check if a symbol is a terminal
int is_terminal(char symbol) {
return !isupper(symbol); // Return true if it's not uppercase (i.e., terminal)
}
// Function to add a symbol to a set (if it doesn't exist)
void add_to_set(char set[MAX], char symbol) {
if (strchr(set, symbol) == NULL) {
int len = strlen(set);
set[len] = symbol;
set[len + 1] = '\0';
}
}
// Function to calculate FIRST set
void calculate_first(char symbol) {
if (first_done[symbol - 'A']) return; // Already computed
for (int i = 0; i < n; i++) {
if (productions[i][0] == symbol) { // Production matches the symbol
for (int j = 3; productions[i][j] != '\0'; j++) { // Start after '->'
char current = productions[i][j];
if (is_terminal(current)) {
add_to_set(first[symbol - 'A'], current);
break;
} else {
calculate_first(current); // Recursively compute first for non-terminal
// Add FIRST(current) to FIRST(symbol), except epsilon
for (int k = 0; first[current - 'A'][k] != '\0'; k++) {
if (first[current - 'A'][k] != 'e') // Handle epsilon as 'e'
add_to_set(first[symbol - 'A'], first[current - 'A'][k]);
}
// If current can produce epsilon, check the next symbol
if (strchr(first[current - 'A'], 'e') == NULL)
break;
}
}
}
}
first_done[symbol - 'A'] = 1;
}
int main() {
// Input grammar
printf("Enter the number of productions: ");
scanf("%d", &n);
printf("Enter the productions (format A->B):\n");
for (int i = 0; i < n; i++) {
scanf("%s", productions[i]); // Read each production rule
}
// Initialize the first sets
for (int i = 0; i < MAX; i++) {
first[i][0] = '\0';
first_done[i] = 0;
}
// Compute First sets for all non-terminals
for (int i = 0; i < n; i++) {
char symbol = productions[i][0];
if (!first_done[symbol - 'A']) {
calculate_first(symbol);
}
}
// Output First sets
printf("\nFIRST sets:\n");
for (int i = 0; i < n; i++) {
printf("FIRST(%c) = { ", productions[i][0]);
for (int j = 0; first[productions[i][0] - 'A'][j] != '\0'; j++) {
printf("%c ", first[productions[i][0] - 'A'][j]);
}
printf("}\n");
}
return 0;
}
OUTPUT
Enter the number of productions: 3
Enter the productions (format A->B):
S->AB
A->a
B->b
FIRST sets:
FIRST(S) = { a }
FIRST(A) = { a }
FIRST(B) = { b }
