Experiment 3

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

#define MAX_RULES 20   // Maximum number of grammar rules
#define MAX_LEN 100    // Maximum length for production strings

// Structure representing a grammar rule with its left-hand side (non-terminal)
// and an array of right-hand side production strings.
typedef struct {
    char lhs;                          // Non-terminal on the left-hand side
    char rhs[MAX_RULES][MAX_LEN];        // Array of production strings (right-hand sides)
    int rhs_count;                     // Count of productions for this non-terminal
} GrammarRule;

// Global array to hold the grammar rules and the total count of rules.
GrammarRule rules[MAX_RULES];
int num_rules = 0;

// Function prototypes
void append_unique(char *set, char symbol);
void get_first_set(char symbol, char *first_set);
void get_follow_set(char symbol, char *follow_set);

//-------------------------------------------------------------------
// Append a symbol to a set (string) if it's not already present.
// A space is added after the symbol for better readability.
void append_unique(char *set, char symbol) {
    if (!strchr(set, symbol)) {
        int len = strlen(set);
        if (len < MAX_LEN - 2) {
            set[len] = symbol;
            set[len + 1] = ' ';  // Insert a space after the symbol
            set[len + 2] = '\0';
        }
    }
}

//-------------------------------------------------------------------
// Recursively computes the FIRST set for a given symbol.
// If the symbol is a terminal, its FIRST set is just itself.
// For non-terminals, the function examines each production to determine the FIRST set.
void get_first_set(char symbol, char *first_set) {
    // Base case: if symbol is a terminal, add it to FIRST set.
    if (!isupper(symbol)) {
        append_unique(first_set, symbol);
        return;
    }

    // Iterate through all grammar rules looking for a rule with this non-terminal.
    for (int i = 0; i < num_rules; i++) {
        if (rules[i].lhs == symbol) {
            // Process each production (right-hand side) of the rule.
            for (int j = 0; j < rules[i].rhs_count; j++) {
                char *production = rules[i].rhs[j];
                int is_nullable = 1;  // Flag to check if production can derive epsilon

                // Examine symbols in the production from left to right.
                for (int k = 0; production[k] != '\0' && is_nullable; k++) {
                    char current_symbol = production[k];
                    char temp_set[MAX_LEN] = "";

                    // If current symbol is a terminal, add it and break out.
                    if (!isupper(current_symbol)) {
                        append_unique(first_set, current_symbol);
                        is_nullable = 0;
                    } else {
                        // Recursively compute FIRST set for the non-terminal.
                        get_first_set(current_symbol, temp_set);
                        // Add symbols (except epsilon, represented by '#') from temp_set.
                        for (int m = 0; temp_set[m] != '\0'; m += 2) {
                            if (temp_set[m] != '#')
                                append_unique(first_set, temp_set[m]);
                        }
                        // If epsilon is not present, this production is not nullable.
                        if (!strchr(temp_set, '#'))
                            is_nullable = 0;
                    }
                }
                // If the entire production can derive epsilon, add epsilon to FIRST set.
                if (is_nullable)
                    append_unique(first_set, '#');
            }
        }
    }
}

//-------------------------------------------------------------------
// Recursively computes the FOLLOW set for a given non-terminal symbol.
// FOLLOW set contains terminals that can immediately appear after the symbol in a derivation.
void get_follow_set(char symbol, char *follow_set) {
    // If the symbol is the start symbol, add the end marker '$'.
    // printf("Computing FOLLOW(%c)\n", symbol);
    if (symbol == rules[0].lhs) {
        append_unique(follow_set, '$');
    }

    // Traverse each rule to locate occurrences of the symbol.
    for (int i = 0; i < num_rules; i++) {
        for (int j = 0; j < rules[i].rhs_count; j++) {
            char *production = rules[i].rhs[j];
            int prod_len = strlen(production);

            // Look for the symbol in the production.
            for (int k = 0; k < prod_len; k++) {
                if (production[k] == symbol) {
                    int is_nullable = 1;  // Assume subsequent symbols can derive epsilon
                    // Process symbols following the found symbol.
                    for (int l = k + 1; l < prod_len && is_nullable; l++) {
                        char next_symbol = production[l];
                        char temp_set[MAX_LEN] = "";

                        // If next symbol is a terminal, add it to FOLLOW set.
                        if (!isupper(next_symbol)) {
                            append_unique(follow_set, next_symbol);
                            is_nullable = 0;
                        } else {
                            // Otherwise, compute FIRST set for the non-terminal.
                            get_first_set(next_symbol, temp_set);
                            // Add all terminal symbols from FIRST (excluding epsilon) to FOLLOW.
                            for (int m = 0; temp_set[m] != '\0'; m += 2) {
                                if (temp_set[m] != '#')
                                    append_unique(follow_set, temp_set[m]);
                            }
                            // If epsilon is not in FIRST, then no further symbols are nullable.
                            if (!strchr(temp_set, '#'))
                                is_nullable = 0;
                        }
                    }
                    // If the following part is nullable, add FOLLOW of the current rule's LHS.
                    if (is_nullable && rules[i].lhs != symbol) {
                        // printf("Adding FOLLOW(%c) to FOLLOW(%c)\n", rules[i].lhs, symbol);
                        char temp_follow[MAX_LEN] = "";
                        get_follow_set(rules[i].lhs, temp_follow);
                        for (int m = 0; temp_follow[m] != '\0'; m += 2) {
                            append_unique(follow_set, temp_follow[m]);
                        }
                    }
                }
            }
        }
    }
    // printf("FOLLOW(%c) = { %s }\n", symbol, follow_set);
}

//-------------------------------------------------------------------
// Main function: Reads grammar rules, computes FIRST and FOLLOW sets,
// and prints the results in a formatted manner.
int main() {
    char input_line[MAX_LEN];

    // Read the number of grammar rules.
    printf("Enter number of rules: ");
    scanf("%d", &num_rules);
    getchar(); // Consume newline

    // Input each grammar rule.
    for (int i = 0; i < num_rules; i++) {
        printf("Enter rule : ");
        fgets(input_line, sizeof(input_line), stdin);
        input_line[strcspn(input_line, "\n")] = '\0'; // Remove newline character

        // Set the left-hand side (non-terminal) of the rule.
        rules[i].lhs = input_line[0];
        rules[i].rhs_count = 0;

        // Tokenize the right-hand side productions separated by '|'.
        char *token = strtok(&input_line[3], "|");
        while (token && rules[i].rhs_count < MAX_RULES) {
            strcpy(rules[i].rhs[rules[i].rhs_count++], token);
            token = strtok(NULL, "|");
        }
    }

    // Compute and print FIRST sets for each rule.
    printf("\n--- FIRST SETS ---\n");
    for (int i = 0; i < num_rules; i++) {
        char first_output[MAX_LEN] = "";
        get_first_set(rules[i].lhs, first_output);
        printf("FIRST(%c) = { %s}\n", rules[i].lhs, first_output);
    }

    // Compute and print FOLLOW sets for each rule.
    printf("\n--- FOLLOW SETS ---\n");
    for (int i = 0; i < num_rules; i++) {
        char follow_output[MAX_LEN] = "";
        // printf("hi");
        get_follow_set(rules[i].lhs, follow_output);
        printf("FOLLOW(%c) = { %s}\n", rules[i].lhs, follow_output);
    }

    return 0;
}