Write a program to find out the leading of the non-terminals in a grammar.
#include <iostream>
#include <vector>
#include <unordered_map>
#include <set>
#include <sstream>
using namespace std;
void findLeading(const vector<string>& productions, unordered_map<char, set<char>>& leading) {
bool changed = true;
for (const string& production : productions) {
char head = production[0];
leading[head] = set<char>();
}
while (changed) {
changed = false;
for (const string& production : productions) {
char head = production[0];
const string& body = production.substr(3);
if (body == "$") {
if (leading[head].find('$') == leading[head].end()) {
leading[head].insert('$');
changed = true;
}
} else if (islower(body[0])) {
if (leading[head].find(body[0]) == leading[head].end()) {
leading[head].insert(body[0]);
changed = true;
}
} else {
char nextSymbol = body[0];
size_t i = 0;
while (i < body.size() && !isupper(body[i])) {
++i;
}
char nonTerminal = body[i];
for (char symbol : leading[nonTerminal]) {
if (symbol != '$' && leading[head].find(symbol) == leading[head].end()) {
leading[head].insert(symbol);
changed = true;
}
}
bool canDeriveEpsilon = true;
for (size_t j = i; j < body.size(); ++j) {
if (leading[body[j]].find('$') == leading[body[j]].end()) {
canDeriveEpsilon = false;
break;
}
}
if (canDeriveEpsilon && leading[head].find(nextSymbol) == leading[head].end()) {
leading[head].insert(nextSymbol);
changed = true;
}
}
}
}
}
int main() {
vector<string> productions = {
"S -> AC",
"A -> aAb | bA | $",
"C -> cC | dC | $"
};
unordered_map<char, set<char>> leading;
findLeading(productions, leading);
cout << "Leading Sets:" << endl;
for (const auto& entry : leading) {
cout << "Leading(" << entry.first << ") = { ";
for (char symbol : entry.second) {
cout << symbol << " ";
}
cout << "}" << endl;
}
return 0;
}
Comments
Post a Comment