Write a program to find out the FIRST of the Non‐terminals in a grammar.

 #include <iostream>

#include <unordered_map>

#include <unordered_set>

#include <vector>

using namespace std;

// Data structure to represent a production rule

struct Production

{

    string nonTerminal;

    string expression;

};

// Function to calculate the FIRST set for a non-terminal

unordered_set<char> calculateFirst(const string &nonTerminal, const vector<Production> &productions, unordered_map<string, unordered_set<char>> &firstCache)

{

    // If FIRST set for the non-terminal is already calculated, return it

    if (firstCache.find(nonTerminal) != firstCache.end())

    {

        return firstCache[nonTerminal];

    }

    unordered_set<char> firstSet;

    for (const Production &production : productions)

    {

        if (production.nonTerminal == nonTerminal)

        {

            char firstSymbol = production.expression[0];

            if (isalpha(firstSymbol) && islower(firstSymbol))

            {

                firstSet.insert(firstSymbol);

            }

            else if (isalpha(firstSymbol) && isupper(firstSymbol))

            {

                const auto &firstSetOfSymbol = calculateFirst(string(1, firstSymbol), productions, firstCache);

                firstSet.insert(firstSetOfSymbol.begin(), firstSetOfSymbol.end());

            }

            else if (firstSymbol == '\0')

            {

                firstSet.insert('\0');

            }

        }

    }

    // Cache the calculated FIRST set for future use

    firstCache[nonTerminal] = firstSet;

    return firstSet;

}

// Function to display a set

void displaySet(const string &setName, const unordered_set<char> &set)

{

    cout << "FIRST(" << setName << "): { ";

    for (char symbol : set)

    {

        cout << symbol << ' ';

    }

    cout << '}' << endl;

}

int main()

{

    // Define the grammar with production rules

    vector<Production> productions = {

        {"S", "aAB"},

        {"A", "b"},

        {"A", ""},

        {"B", "cC"},

        {"C", "d"},

        {"C", ""}};

    // Cache for storing calculated FIRST sets

    unordered_map<string, unordered_set<char>> firstCache;

    // Calculate and display FIRST sets for each non-terminal

    unordered_set<string> displayedNonTerminals;

    for (const Production &production : productions)

    {

        const string &nonTerminal = production.nonTerminal;

        // Display FIRST set only if not displayed before

        if (displayedNonTerminals.find(nonTerminal) == displayedNonTerminals.end()) {

            const unordered_set<char> &firstSet = calculateFirst(nonTerminal, productions, firstCache);

            displaySet(nonTerminal, firstSet);

            displayedNonTerminals.insert(nonTerminal);

        }

    }

    return 0;

}

Ignore [ . ]