#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <cstring>

using namespace std;

// define the grammar production rules
map<char, vector<string>> productions;

// define the FIRST sets for each non-terminal symbol
map<char, set<char>> firstSets;

// function to add a symbol to a set
void addToSet(set<char>& s, char c)
{
    if (c != ' ' && c != '\0') {
        s.insert(c);
    }
}

// function to calculate the FIRST set of a non-terminal symbol
void calculateFirst(char nonTerminal)
{
    // iterate through each production rule for the non-terminal symbol
    for (auto& rule : productions[nonTerminal]) {
        // if the first symbol is a terminal symbol, add it to the FIRST set
        if (islower(rule[0])) {
            addToSet(firstSets[nonTerminal], rule[0]);
        }
        // if the first symbol is a non-terminal symbol, add its FIRST set to the FIRST set of the current non-terminal symbol
        else {
            bool isNullable = true;
            for (int i = 0; i < rule.size(); i++) {
                calculateFirst(rule[i]);
                addToSet(firstSets[nonTerminal], *(firstSets[rule[i]].begin()));
                if (firstSets[rule[i]].find('e') == firstSets[rule[i]].end()) {
                    isNullable = false;
                    break;
                }
            }
            if (isNullable) {
                addToSet(firstSets[nonTerminal], 'e');
            }
        }
    }
}

int main()
{
    // read the grammar production rules
    cout << "Enter the grammar production rules: " << endl;
    string rule;
    while (getline(cin, rule)) {
        char nonTerminal = rule[0];
        string production = rule.substr(3);
        productions[nonTerminal].push_back(production);
    }

    // calculate the FIRST sets for each non-terminal symbol
    for (auto& p : productions) {
        char nonTerminal = p.first;
        calculateFirst(nonTerminal);
    }

    // print the FIRST sets
    cout << "FIRST sets:" << endl;
    for (auto& p : firstSets) {
        char nonTerminal = p.first;
        cout << nonTerminal << " : { ";
        for (auto& c : p.second) {
            cout << c << " ";
        }
        cout << "}" << endl;
    }

    return 0;
}