cd6 first

//S->Ab|B	{a,b,c}
//A->aA|e	{a,e}
//B->b|C	{b,c}
//C->c		{c}

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

#define MAX_NON_TERMINALS 10
#define MAX_PRODUCTIONS 10
#define MAX_SYMBOLS 10

typedef struct {
    char non_terminal;
    char production[MAX_PRODUCTIONS][MAX_SYMBOLS];
    int count;
} Production;

Production productions[MAX_NON_TERMINALS];
char first[MAX_NON_TERMINALS][MAX_SYMBOLS] = {0};
int production_count = 0, non_terminal_count = 0;

void addProduction(char non_terminal, char *prod) {
    for (int i = 0; i < production_count; i++) {
        if (productions[i].non_terminal == non_terminal) {
            strcpy(productions[i].production[productions[i].count++], prod);
            return;
        }
    }
    productions[production_count].non_terminal = non_terminal;
    strcpy(productions[production_count].production[productions[production_count].count++], prod);
    production_count++;
}

int findNonTerminalIndex(char non_terminal) {
    for (int i = 0; i < non_terminal_count; i++) {
        if (first[i][0] == non_terminal)
            return i;
    }
    first[non_terminal_count][0] = non_terminal;
    return non_terminal_count++;
}

int addToFirst(int index, char symbol) {
    for (int i = 1; first[index][i]; i++) {
        if (first[index][i] == symbol)
            return 0;
    }
    first[index][strlen(first[index])] = symbol;
    return 1;
}

void computeFirst() {
    int changes;
    do {
        changes = 0;
        for (int i = 0; i < production_count; i++) {
            int index = findNonTerminalIndex(productions[i].non_terminal);
            for (int j = 0; j < productions[i].count; j++) {
                char *prod = productions[i].production[j];
                for (int k = 0; prod[k]; k++) {
                    if (islower(prod[k]) || prod[k] == 'e') {
                        changes |= addToFirst(index, prod[k]);
                        break;
                    }
                    int ntIndex = findNonTerminalIndex(prod[k]);
                    int hasEpsilon = 0;
                    for (int l = 1; first[ntIndex][l]; l++) {
                        if (first[ntIndex][l] == 'e')
                            hasEpsilon = 1;
                        else
                            changes |= addToFirst(index, first[ntIndex][l]);
                    }
                    if (!hasEpsilon) break;
                }
            }
        }
    } while (changes);
}

void displayFirstSets() {
    printf("\nFIRST sets of non-terminals:\n");
    for (int i = 0; i < non_terminal_count; i++) {
        printf("FIRST(%c) = { ", first[i][0]);
        for (int j = 1; first[i][j]; j++) {
            printf("%c ", first[i][j]);
        }
        printf("}\n");
    }
}

int main() {
    printf("Enter the number of productions: ");
    int n;
    scanf("%d", &n);
    getchar();

    printf("Enter productions (e.g., A-->aB|e):\n");
    for (int i = 0; i < n; i++) {
        char line[100], *prod;
        fgets(line, sizeof(line), stdin);
        line[strcspn(line, "\n")] = '\0';

        char *non_terminal = strtok(line, "-->");
        prod = strtok(NULL, "-->");
        for (char *token = strtok(prod, "|"); token; token = strtok(NULL, "|")) {
            addProduction(non_terminal[0], token);
        }
    }

    computeFirst();
    displayFirstSets();
    return 0;
}