Notes

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;

// Production rule structure
struct Production {
char lhs;
string rhs;
};

// Function to compute FIRST set for a given non-terminal
set<char> computeFirst(char nonTerminal, vector<Production>& productions, map<char, set<char>>& first) {
// Check if FIRST set for this non-terminal has already been computed
if (first.find(nonTerminal) != first.end()) {
return first[nonTerminal];
}

set<char> firstSet;

// Iterate over all productions for this non-terminal
for (auto& production : productions) {
if (production.lhs == nonTerminal) {
// If the first symbol in the RHS is a terminal, add it to the FIRST set
if (islower(production.rhs[0])) {
firstSet.insert(production.rhs[0]);
}
// If the first symbol in the RHS is a non-terminal, compute its FIRST set and add it to the FIRST set
else if (isupper(production.rhs[0])) {
set<char> firstSetForSymbol = computeFirst(production.rhs[0], productions, first);
firstSet.insert(firstSetForSymbol.begin(), firstSetForSymbol.end());
}
// If the first symbol in the RHS is epsilon, add it to the FIRST set
else if (production.rhs[0] == '#') {
firstSet.insert('#');
}
}
}

// Cache the computed FIRST set for this non-terminal
first[nonTerminal] = firstSet;

return firstSet;
}

// Function to compute FOLLOW set for a given non-terminal
set<char> computeFollow(char nonTerminal, vector<Production>& productions, map<char, set<char>>& first, map<char, set<char>>& follow) {
// Check if FOLLOW set for this non-terminal has already been computed
if (follow.find(nonTerminal) != follow.end()) {
return follow[nonTerminal];
}

set<char> followSet;

// Add $ to the FOLLOW set of the starting symbol
if (nonTerminal == 'S') {
followSet.insert('$');
}

// Iterate over all productions
for (auto& production : productions) {
// Iterate over all symbols in the RHS of the production
for (int i = 0; i < production.rhs.size(); i++) {
// If the current symbol is the non-terminal we are computing the FOLLOW set for
if (production.rhs[i] == nonTerminal) {
// If the current symbol is the last symbol in the RHS, add the FOLLOW set of the LHS to the FOLLOW set of the current non-terminal
if (i == production.rhs.size() - 1) {
if (production.lhs != nonTerminal) {
set<char> followSetForSymbol = computeFollow(production.lhs, productions, first, follow);
followSet.insert(followSetForSymbol.begin(), followSetForSymbol.end());
}
}
// If the next symbol is a terminal, add it to the FOLLOW set of the current non-terminal
else if (islower(production.rhs[i + 1])) {
followSet.insert(production.rhs[i + 1]);
}
// If the next symbol is a non-terminal, add its FIRST set to the FOLLOW set of the current non-terminal
else if (isupper(production.rhs[i + 1])) {
set<char> firstSetForSymbol = computeFirst(production.rhs[i + 1], productions, first);
if (firstSetForSymbol.find('#') != firstSetForSymbol.end()) {
firstSetForSymbol.erase('#');
set<char> followSetForSymbol = computeFollow(production.lhs, productions, first, follow);
followSet.insert(followSetForSymbol.begin(), followSetForSymbol.end());
}
followSet.insert(firstSetForSymbol.begin(), firstSetForSymbol.end());
}
}
}
}

// Cache the computed FOLLOW set for this non-terminal
follow[nonTerminal] = followSet;

return followSet;
}

int main() {
// Example grammar
vector<Production> productions = {
{'S', "aABc"},
{'A', "bA"},
{'A', "#"},
{'B', "dB"},
{'B', "e"}
};

// Compute FIRST and FOLLOW sets for each non-terminal
map<char, set<char>> first;
map<char, set<char>> follow;
for (auto& production : productions) {
computeFirst(production.lhs, productions, first);
computeFollow(production.lhs, productions, first, follow);
}

// Print FIRST and FOLLOW sets for each non-terminal
for (auto& production : productions) {
cout << "FIRST(" << production.lhs << ") = { ";
for (auto& symbol : first[production.lhs]) {
cout << symbol << " ";
}
cout << "}" << endl;

cout << "FOLLOW(" << production.lhs << ") = { ";
for (auto& symbol : follow[production.lhs]) {
cout << symbol << " ";
}
cout << "}" << endl;
}

return 0;
}