编译原理C语言生成LR1分析表.rar

#include<iostream> #include<fstream> #include<vector> #include<string> #include<map> #include<set> #include<cstring> #include<unordered_map> using namespace std; vector< vector<char> > G; //文法G[S]产生式 ，~为空字 unordered_map<char, set<char> > ts; //终结符(char)terminal symbol,及它的first集合(set<char>) unordered_map<char, set<char> > nts; //非终结符(char)non-terminal symbol，及它的first集合(set<char>) map< map<string, char> , string> table; //LR分析表 struct C { //闭包CLOSURE vector< vector<char> > project; //项目集 vector< set<char> > outlook; //展望串 unordered_map<char, int> go; //GO函数 }; vector<C> c; void show_G() { cout << "原文法拓广为文法G[M]：" << endl; for (unsigned int i = 0; i < G.size(); i++) { //输出G'[S'] cout << i << "）"; for (unsigned int j = 0; j < G[i].size(); j++) { if (j == 1)cout << "->"; cout << G[i][j]; } cout << endl; } cout << endl << endl; } void show_Symbol() { for (unordered_map<char, set<char> >::iterator it = nts.begin(); it != nts.end(); it++) { //输出非终结符 cout << it->first; } cout << endl; for (unordered_map<char, set<char> >::iterator it = ts.begin(); it != ts.end(); it++) { //输出终结符 cout << it->first; } cout << endl << endl; } void show_First() { for (auto it1 : ts) { cout << it1.first << ": "; for (auto it2 : it1.second) { cout << it2 << ","; } cout << endl; } cout << endl << endl; for (auto it1 : nts) { cout << it1.first << ": "; for (auto it2 : it1.second) { cout << it2 << ","; } cout << endl; } cout << endl << endl; } void show_Closure() { fstream f("Closure.txt", ios::out); if (!f) { cout << "Closure.txt文件打开出错！" << endl; return; } f << "该文法的项目集和GO函数：" << endl; for (unsigned int i = 0; i < c.size(); i++) { f << "I" << i << ":" << endl; for (unsigned int j = 0; j < c[i].project.size(); j++) { for (unsigned int k = 0; k < c[i].project[j].size(); k++) { if (k == 1) f << "->"; if (c[i].project[j][k] == ' ') f << "·"; else f << c[i].project[j][k]; } f << "，"; for (auto it : c[i].outlook[j]) { if (it == *(c[i].outlook[j].begin())) f << it; else f << "/" << it; } f << endl; } for (auto it : c[i].go) { f <<"GO(I"<<i<<"，"<< it.first << ") = I" << it.second << endl; } f << endl; } cout << "已将项目集和GO函数生成到Closure.txt文件中。" << endl << endl; } void show_Table() { fstream f("LR_Table.txt",ios::out); if (!f) { cout << "LR_Table.txt文件打开出错！" << endl; return; } for (int i = -1; i < (int)c.size(); i++) { if(i==-1) f << " " << '\t'; else f << i << '\t'; for (auto it : ts) { if (i == -1) f << it.first << '\t'; else { map<string, char> m; m[to_string(i)] = it.first; f<<table[m]<<'\t'; } } if (i == -1) f <<"#"<< '\t'; else { map<string, char> m; m[to_string(i)] = '#'; f << table[m] << '\t'; } for (auto it : nts) { if (it.first == 'M') continue; if (i == -1)f << it.first << '\t'; else { map<string, char> m; m[to_string(i)] = it.first; f << table[m] << '\t'; } } f << endl; } f.close(); cout << "已将LR分析表生成到LR_Table.txt文件中。" << endl << endl; } void read_G() { char ch; //当前读入的字符 int i = 0; //当前行读取的第i个字符 vector<char> v; //存放输入的一行产生式 char X; //若遇到形如X->α|β|……,用于保存X以便消除| set<char> m; nts['M'] = m; while (ch = getchar()) { if (ch == '#') break; if (ch == '\n') { //换行 if (!v.empty())G.push_back(v); v.clear(); i = 0; continue; } if (ch != ' ' || ch != '\t') { //去掉空格等多余字符 if (ch == '|') { //消除元语言符号'或|' G.push_back(v); v.clear(); i = 3; v.push_back(X); continue; } i++; if (i == 1) { X = ch; nts[ch] = m; //产生式左边(第一个字符)的为非终结符 } else if (i != 2 && i != 3&&ch!='~') ts[ch] = m; //此时ts里既有非终结符又有终结符 if (i != 2 && i != 3)v.push_back(ch); //去掉产生式的-> } } if (G.empty()) exit(0); //加入新树根M v.clear(); v.push_back('M'); v.push_back(G[0][0]); G.insert(G.begin(), v); //去掉ts中的非终结符 for (unordered_map<char, set<char> >::iterator it = nts.begin(); it != nts.end(); it++) { unordered_map<char, set<char> >::iterator iter; iter = ts.find(it->first); if (iter != ts.end())ts.erase(iter); } } void get_First() { for (auto &it : ts) it.second.insert(it.first);//终结符的first集合是它自己 //求非终结符的First集合 int r = 0; int change = 1; while (change) { if (r == 20)break; r++; change = 0; for (auto &it : nts) { //对每个非终结符 for (unsigned int i = 0; i < G.size(); i++) { //遍历产生式 if (G[i][0] == it.first) { unsigned int size = it.second.size(); //操作前First(X)的大小 unordered_map<char, set<char> >::iterator iter=ts.find(G[i][1]); if (ts.find(G[i][1]) != ts.end()||G[i][1]=='~') { //形如X->a……或X->空字，把a加入First(X)中 it.second.insert(G[i][1]); if (it.second.size() > size) change = 1; } else { //形如X->Y……，把First(Y)加入First(X) unsigned int col = 1; while(1){ //若X->Y1Y2……,循环把First(Y)加入First(X) int flag = 0; //标记当前First(Y)中是否有空字 unordered_map<char, set<char> >::iterator itt= nts.find(G[i][col]); for(auto &iter:itt->second){ //遍历First(Y) if (iter == '~') flag = 1; else it.second.insert(iter); } if (flag) { col++; if (G[i].size() <= col) { it.second.insert('~'); //形如X->Y,将空字加入First(X) break; } else if (ts.find(G[i][col]) != ts.end()) { //形如X->Ya……，将a加入First(X) it.second.insert(G[i][col]); break; } else { //形如X->YZ……，将First(Z)加入First(X) } } else break; } if (it.second.size() > size) change = 1; } } } } } } void get_Closure() { int i = 0; //闭包编号 C clo; //生成第一个闭包（I0） c.push_back(clo); while(1) { if (i == c.size()) break; //没有新闭包，跳出循环（即已获得全部闭包及项目） if (i == 0) { //确定项目集I0的第一个项目 vector<char> v(G[0]); v.insert(v.begin() + 1, ' '); c[i].project.push_back(v); set<char> m; m.insert('#'); c[i].outlook.push_back(m); } for (unsigned int j = 0; j < c[i].project.size(); j++){ //遍历已有项目，生成该闭包所有项目 for (unsigned int k = 0; k < c[i].project[j].size(); k++) { //扫描单个项目，找到当前位置·（这里用空格代替） if (c[i].project[j][k] == ' ') { if (k == c[i].project[j].size() - 1) break; //形如X->β·，不会生成新的项目 for (unsigned int x = 0; x < G.size(); x++) { //形如X->α·Yβ， 遍历G'[M]，查找所有对应的产生式，以求出新的项目并加入项目集 if (G[x][0] == c[i].project[j][k + 1]) { //对应的产生式 vector<char> v(G[x]); //用于保存新项目 v.insert(v.begin() + 1, ' '); //计算新项目 int exist = 0; //标记该新项目是否已存在 for (unsigned int y = 0; y < c[i].project.size(); y++) { //遍历已有项目，判断是新项目还是已有项目 if (c[i].project[y] == v) { //已有项目，只需保存项目下标（用于添加新的展望串） exist = y; break; } } if(exist==0) c[i].project.push_back(v); //�