#include <sstream>
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <bitset>
using namespace std;
struct Grammar {
vector<string> productions;
bool hasN;
};
struct N {
set<char> names;
};
struct T {
set<char> names;
};
N non_terminals;
T terminals;
char start_symbol;
map<char, Grammar> grammars;
void hasN_() {
bool changes = true;
while (changes) {
changes = false;
for (auto& it : grammars) {
if (it.second.hasN)
continue;
for (string& prod : it.second.productions) {
bool onlyN = true;
for (char c : prod) {
if (grammars.count(c) == 0 || !grammars[c].hasN) {
onlyN = false;
break;
}
}
if (onlyN) {
it.second.hasN = true;
changes = true;
break;
}
}
}
}
Grammar start_grammar = grammars[start_symbol];
if (start_grammar.hasN) {
start_symbol = 'T';
vector<string> newproductions;
newproductions.push_back("S");
Grammar new_grammar;
new_grammar.hasN = 1;
new_grammar.productions = newproductions;
grammars[start_symbol] = new_grammar;
non_terminals.names.insert('T');
}
}
void cleanseN() {
hasN_();
map<char, Grammar> newGrammars;
for (auto& it : grammars) {
if (it.second.hasN)
newGrammars.insert(it);
}
for (auto& it : grammars) {
vector<string> newproductions;
for (auto& p : it.second.productions) {
int a = 0;
for (char c : p) {
if (newGrammars.count(c) > 0) {
a = (a << 1) | 1;
}
else {
a = a << 1;
}
}
for (int i = a; i ; i = (i - 1) & a) {
string transformedProduction;
for (size_t j = 0; j < p.size(); ++j) {
if ((i >> (p.size() - j - 1)) == 0) {
transformedProduction += p[j];
}
}
if (transformedProduction.size() > 0) {
newproductions.push_back(transformedProduction);
}
}
}
for (const string& newProduction : newproductions) {
it.second.productions.push_back(newProduction);
}
}
}
void removeUselessSymbols() {
set<char> generating, reachable = {start_symbol};
bool changes;
do {
changes = false;
for (const auto& it : grammars) {
for (const string& prod : it.second.productions) {
bool canGenerate = true;
for (char c : prod) {
if (grammars.count(c) > 0 && !generating.count(c)) {
canGenerate = false;
break;
}
}
if (canGenerate && generating.insert(it.first).second)
changes = true;
}
}
} while (changes);
do {
changes = false;
for (char symbol : reachable) {
if (grammars.count(symbol) > 0) {
for (const string& prod : grammars[symbol].productions) {
for (char c : prod) {
if (grammars.count(c) > 0 && reachable.insert(c).second)
changes = true;
}
}
}
}
} while (changes);
for (auto it = grammars.begin(); it != grammars.end();) {
if (!generating.count(it->first) || !reachable.count(it->first)) {
non_terminals.names.erase(it->first); // 同步删除 non_terminals 中的非终结符
it = grammars.erase(it);
}
else
++it;
}
for (auto it = terminals.names.begin(); it != terminals.names.end();) {
bool found = false;
for (const auto& grammar : grammars) {
for (const auto& prod : grammar.second.productions) {
if (prod.find(*it) != string::npos) {
found = true;
break;
}
}
if (found) break;
}
if (!found) {
it = terminals.names.erase(it);
}
else {
++it;
}
}
}
void cleanseSingleProds() {
map<char, set<char>> singleProds;
for (const auto& it : grammars) {
char nonTerminal = it.first;
for (const string& prod : it.second.productions) {
if (prod.size() == 1 && grammars.count(prod[0]) > 0) {
singleProds[nonTerminal].insert(prod[0]);
}
}
}
bool changes = true;
while (changes) {
changes = false;
for (auto& it : singleProds) {
size_t oldSize = it.second.size();
vector<char> addToSet;
for (char c : it.second) {
if (singleProds.count(c) > 0) {
for (char c2 : singleProds[c]) {
addToSet.push_back(c2);
}
}
}
it.second.insert(addToSet.begin(), addToSet.end());
if (it.second.size() > oldSize) {
changes = true;
}
}
}
for (auto& it : grammars) {
vector<string> newProds;
for (const string& prod : it.second.productions) {
if (!(prod.size() == 1 && grammars.count(prod[0]) > 0)) {
newProds.push_back(prod);
}
}
if (singleProds.count(it.first) > 0) {
for (char c : singleProds[it.first]) {
for (const string& prod : grammars[c].productions) {
if (!(prod.size() == 1 && grammars.count(prod[0]) > 0)) {
newProds.push_back(prod);
}
}
}
}
sort(newProds.begin(), newProds.end());
newProds.erase(unique(newProds.begin(), newProds.end()), newProds.end());
it.second.productions = newProds;
}
}
void readinput(){
int flag;
char c;
//read N
getchar();
getchar();
getchar();
flag = 1;
while (flag) {
char A, ch;
A = getchar();
ch = getchar();
non_terminals.names.insert(A);
if (ch == '}') {
flag = 0;
}
}
//read T
for (c = getchar(); c!='{'; c = getchar());
c = getchar();
flag = 1;
while (flag) {
char ch;
ch = getchar();
terminals.names.insert(c);
if (ch == '}') {
flag = 0;
}
else {
c = getchar();
}
}
//read P & S
string str;
cin >> str;
while (1) {
cin >> str;
//if (str.compare("S=S") == 0) {
// break;
//}
if (str[0] == 'S' && str[1] == '=') {
start_symbol = str[2];
break;
}
char S = str[0];
int length = str.length();
for (int i = 4, j = 4; i < length; i = ++j) {
while (str[j] != '|' && j < length) {
j++;
}
if (j - i == 1 && str[i] == 'N') {
grammars[S].hasN = 1;
}
else {
string str1 = str.substr(i, j - i);
grammars[S].productions.push_back(str1);
}
}
}
}
void printOutput() {
for (auto& it : grammars) {
sort(it