北京邮电大学形式语言第二次上机作业（c++）

#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