#include<iostream>
#include<fstream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<queue>
#include<stack>
#include<map>
using namespace std; typedef pair<char, string>PP;
typedef pair<char, pair<string, string> >PPP; //*代表弧
//~代表空
//输入：
/*
S*MH
S*a
H*LSo
H*~
K*dML
K*~
L*eHf
M*K
M*bLM
*/ class Set{ private:
multimap<char, string >Grammars;//文法
multimap<string, char >Re_Grammars; //反向映射
vector<PP >FIRST; //FIRST集
vector<PP >FOLLOW; //FOLLOW集
set<char >Ok; //能推出空的非终结符的集合
set<char >Non_terminal; //非终结符集合
vector<string >Right; //产生式右部
vector<PPP >SELECT; //SELECT集
vector<char >Sentence; //要识别的句子 public:
Set();
~Set();
bool Judge_Ok(char); //判断一个非终结符是否能推出空
void Get_Ok(); //求出那些能推出空的非终结符集合
void First_Solve(); //求解FIRST集
void Show_First(); //输出FIRST集合
void Get_First(char, set<char>&); //求解某个非终结符的FIRST集
void Follow_Solve(); //求解FOLLOW集
void Show_Follow(); //输出FOLLOW集
void Get_Follow(char, set<char>&); //求解某个非终结符的FOLLOW集
void Select_Solve(); //求解SELECT集
void Show_Select(); //输出SELECT集
void Analysis(); //预测分析程序 }; Set::Set()
{
ifstream infile;
infile.open("data.txt");
if (!infile){
cout << "can't open the file" << endl;
return;
}
string str;
while (infile >> str){
char ch = str[];
string ss = "";
for (int i = ; i < (int)str.size(); i++)ss += str[i];
Grammars.insert(make_pair(ch, ss)); //所给文法
Re_Grammars.insert(make_pair(ss, ch)); //反向映射集合
Right.push_back(ss); //得到右部产生式
for (int i = ; i < (int)str.size(); i++){
if (isupper(str[i]))Non_terminal.insert(str[i]); //求非终结符集合
}
}
infile.close();
} Set::~Set()
{
Grammars.clear();
Re_Grammars.clear();
Right.clear();
Ok.clear();
FIRST.clear();
FOLLOW.clear();
SELECT.clear();
Non_terminal.clear();
} //判断一个非终结符是否能推出空
bool Set::Judge_Ok(char ch)
{
if (Grammars.find(ch) == Grammars.end())return false;//如果找不到这个非终结符所能推出的符号，则返回false. multimap<char, string>::iterator iter = Grammars.find(ch);
int Count =(int)Grammars.count(iter->first);
for (int i = ; i < Count; i++){
bool flag = true;
for (int j = ; j < (int)iter->second.size(); j++){
//如果是大写字母，那么就继续递归
if (isupper(iter->second[j])){
//避免重复递归
if (iter->second[j] == ch){
flag = false;
break;
}
else if (!Judge_Ok(iter->second[j])){
flag = false;
break;
}
}
//如果不是大写字母，就判断是否是空，如果不是，则也是直接break;
else if (iter->second[j] != '~'){
flag = false;
break;
}
}
if (flag)return true; //在某个非终结符的多重集合中，只要有某个能产生空，那么这个非终结符就能推出空,返回true;
iter++;
}
//如果都不能推出空，那么就返回false;
return false; } //求出那些能推出空的非终结符集合
void Set::Get_Ok()
{
set<char>::iterator iter;
for (iter = Non_terminal.begin(); iter != Non_terminal.end(); iter++){
if(Judge_Ok((*iter))){
Ok.insert(*iter);
}
}
} //求某一个非终结符的FIRST集
void Set::Get_First(char ch, set<char>&st)
{
if (Grammars.find(ch) == Grammars.end())return; //如果没有找到非终结符可以转化的符号，则直接返回 multimap<char, string>::iterator iter = Grammars.find(ch);
int Count = (int)Grammars.count(iter->first);
for (int i = ; i < Count; i++){
for (int j = ; j < (int)(iter->second.size()); j++){
//此时碰到的是终结符，找到后将其插入到set集合中，并且立马跳出循环，找下一个
if (!isupper(iter->second[j])){
st.insert(iter->second[j]);
break;
}
else if (isupper(iter->second[j])){
//避免重复递归
if (iter->second[j] == ch){
break;
}
//如果不重复，那么就从这个非终结符继续找
Get_First(iter->second[j], st); //如果这个非终结符不能推出空，那么就直接break寻找下一个映射
if (Ok.find(iter->second[j]) == Ok.end()){
break;
}
}
}
iter++;
}
} //求所有非终结符的FIRST集
void Set::First_Solve()
{
set<char >First;
for (set<char >::iterator iter = Non_terminal.begin(); iter != Non_terminal.end(); iter++){
First.clear();
Get_First(*iter, First); //求某一个非终结符的FIRST集
string str = "";
for (set<char>::iterator it = First.begin(); it != First.end(); it++)str += (*it);
FIRST.push_back(make_pair(*iter, str));
}
} //输出FIRST集
void Set::Show_First()
{
cout << " " << "FIRST集" << " " << endl << endl;
for (int i = ; i <(int) FIRST.size(); i++){
cout << FIRST[i].first << " ： ";
for (int j = ; j <(int) FIRST[i].second.size(); j++){
cout << FIRST[i].second[j] << " ";
}
cout << endl;
}
cout << endl;
} //求某一个非终结符的FOLLOW集
void Set::Get_Follow(char ch, set<char>&st)
{
if (ch == 'S')st.insert('#');//如果是开始符;
for (int i = ; i < (int)Right.size(); i++){
string str = Right[i];
for (int j = ; j < (int)Right[i].size(); j++){
//如果不是当前产生式的最后一个
if (Right[i][j] == ch&&j !=(int) Right[i].size() - ){
//如果后面紧跟着的是终结符
if (!isupper(Right[i][j + ])){
if (Right[i][j + ] != '~'){
st.insert(Right[i][j + ]);
}
}
else{
//后面紧跟着是非终结符，就把这个非终极符的FIRST集（除了空）加入到当前ch的FOLLOW集中
vector<PP>::iterator iter = FIRST.begin();
while (iter != FIRST.end()){
if (iter->first == Right[i][j+]){
break;
}
iter++;
}
for (int k = ; k < (int)iter->second.size(); k++){
if (iter->second[k] != '~')st.insert(iter->second[k]);
}
//如果对形如“…UP”(P是非终结符的组合)的组合；
//如果这些非终结符都能推出空，就么就要把左部（假设是S）的Follow（S）送入到Follow（U）中
bool flag = true;
for (int pos = j + ; pos < (int)Right[i].size(); pos++){
if (isupper(Right[i][pos]) && Ok.find(Right[i][pos]) != Ok.end()){
vector<PP>::iterator ii = FIRST.begin();
while (ii != FIRST.end()){
if (ii->first == Right[i][pos]){
break;
}
ii++;
}
for (int k = ; k < (int)ii->second.size(); k++){
if (ii->second[k] != '~')st.insert(ii->second[k]);
}
continue;
}
flag = false;
break;
}
if (flag){
multimap<string, char>::iterator it = Re_Grammars.find(str);
int Count = Re_Grammars.count(it->first);
while (Count--){
if (it->second != ch){
Get_Follow(it->second, st);
}
}
}
}
}
//如果刚好是当前产生式的最后一个字符
else if (Right[i][j] == ch&&j == (int)Right[i].size() - ){
//反向映射找到推出str这个产生式的左部字符
multimap<string, char>::iterator iter = Re_Grammars.find(str);
int Count = Re_Grammars.count(iter->first);
while (Count--){
if (iter->second != ch){
Get_Follow(iter->second, st);
}
}
}
}
}
} //求所有非终结符的FOLLOW集
void Set::Follow_Solve()
{
set<char>Follow;
for (set<char>::iterator iter = Non_terminal.begin(); iter != Non_terminal.end(); iter++){
Follow.clear();
if (*iter == 'S')Follow.insert('#'); //如果是开始符
Get_Follow(*iter, Follow);
string str = "";
for (set<char>::iterator it = Follow.begin(); it != Follow.end(); it++)str += (*it);
FOLLOW.push_back(make_pair(*iter, str));
}
} //输出所有非终结符的FOLLOW集
void Set::Show_Follow()
{
cout << " " << "FOLLOW集" << " " << endl << endl;
for (int i = ; i < (int) FOLLOW.size(); i++){
cout << FOLLOW[i].first << " ： ";
for (int j = ; j <(int) FOLLOW[i].second.size(); j++){
cout << FOLLOW[i].second[j] << " ";
}
cout << endl;
}
cout << endl;
} //求解SELECT集
void Set::Select_Solve()
{
multimap<char, string>::iterator iter;
vector<PP >::iterator it;
set<char >st;
for (iter = Grammars.begin(); iter != Grammars.end(); iter++){
char ch = iter->first;
string str = iter->second;
bool flag = true;
st.clear();
for (int i = ; i < (int)str.size(); i++){
if (Ok.find(str[i]) == Ok.end()&& str[i] != '~'){
flag = false;
}
}
//求FIRST(a)
int pos = ;
while (pos < (int)str.size() && Ok.find(str[pos]) != Ok.end()){
for (it = FIRST.begin(); it != FIRST.end(); it++){
if (str[pos] == it->first)break;
}
for (int j = ; j < (int)it->second.size(); j++){
st.insert(it->second[j]);
}
pos++;
}
if (pos < (int)str.size()){
if (isupper(str[pos])){
for (it = FIRST.begin(); it != FIRST.end(); it++){
if (str[pos] == it->first)break;
}
for (int j = ; j < (int)it->second.size(); j++){
st.insert(it->second[j]);
}
}else
st.insert(str[pos]);
}
//如果产生式A->a并且a能推出空,则SELECT（A->a)=(FIRST(a)-{~})U(FOLLOW(A)
if (flag){
for (it = FOLLOW.begin(); it != FOLLOW.end(); it++){
if (ch == it->first)break;
}
for (int j = ; j < (int)it->second.size(); j++){
st.insert(it->second[j]);
}
for (set<char>::iterator ii = st.begin(); ii != st.end(); ){
if ((*ii) == '~'){
ii = st.erase(ii);
break;
}
ii++;
}
string ss = "";
for (set<char>::iterator ii = st.begin(); ii != st.end(); ii++)ss += (*ii);
SELECT.push_back(make_pair(ch, make_pair(str,ss)));
}
//否则SELECT（A->a)=(FIRST(a)
else {
string ss = "";
for (set<char>::iterator ii = st.begin(); ii != st.end(); ii++)ss += (*ii);
SELECT.push_back(make_pair(ch, make_pair(str,ss)));
}
}
} //输出SELECT集
void Set::Show_Select()
{
cout << " " << "SELECT集" << " " << endl << endl;
for (int i = ; i < (int) SELECT.size(); i++){
cout << SELECT[i].first << " ->";
cout << setw() << SELECT[i].second.first << " : ";
for (int j = ; j < (int) SELECT[i].second.second.size(); j++){
cout << SELECT[i].second.second[j] << " ";
}
cout << endl;
}
cout << endl;
} //预测分析程序
void Set::Analysis()
{
cout << "请输入要识别的串: " << endl;
string str;
cin >> str;
for (int i = ; i < (int)str.size(); i++){
Sentence.push_back(str[i]);
}
Sentence.push_back('#');
vector<char>::iterator iter = Sentence.begin(), ii;
stack<char>S;
vector<char>vet;
S.push('#');
S.push('S');
vet.push_back('#');
vet.push_back('S');
cout << "分析栈" << " " << "剩余输入串" << " " << "推倒所用的产生式或匹配" << endl;
int EMPTY = ;
while (!S.empty()){
for (int i = ; i < (int)vet.size(); i++){
cout << vet[i] << " ";
}
for (int i = (int)vet.size(); i <= EMPTY+; i++)cout << " ";
int count = ;
for (ii = iter; ii != Sentence.end(); ii++){
cout << (*ii) << " ";
count++;
}
for (; count <= EMPTY; count++)cout << " ";
char ch = S.top();
if (ch == (*iter)){
S.pop();
vet.pop_back();
iter++;
for (int i = ; i <= EMPTY; i++)cout << " ";
cout << "匹配" << endl;
}
else {
vector<PPP >::iterator it;
string ss = "";
bool flag = false;
for (it = SELECT.begin(); it != SELECT.end(); it++){
if (it->first == ch){
ss = it->second.first;
for (int i = ; i < (int)it->second.second.size(); i++){
if (it->second.second[i] == (*iter)){
flag = true;
break;
}
}
if (flag)break;
}
}
for (int i = ; i <= EMPTY; i++)cout << " ";
if (!flag){
cout << "ERROR!!!" << endl;
return;
}
cout << ch << "->" << ss << endl;
reverse(ss.begin(), ss.end()); //反转
if (ss == "~"){
S.pop();
vet.pop_back();
}
else {
S.pop();
vet.pop_back();
for (int i = ; i < (int)ss.size(); i++){
S.push(ss[i]);
vet.push_back(ss[i]);
}
}
}
}
cout << "SUCCESS" << endl;
} int main()
{
Set obj;
obj.Get_Ok();
obj.First_Solve();
obj.Show_First();
obj.Follow_Solve();
obj.Show_Follow();
obj.Select_Solve();
obj.Show_Select();
obj.Analysis();
return ;
}