SLR(1)分析1 7-1 SLR(1)项目集规范族的构造
题目详情：
在本实验中，您需要使用C++进行编程，实现如下功能。
SLR(1)项目集规范族的构造过程主要包括“CLOSURE闭包构造”和“转换函数GO(I,X)求解”两个操作。
综上可以使用闭包函数和转换函数构造文法G的SLR(1)项目集规范族，其步骤如下：
(1) 拓广文法，为文法增加一个新产生式G→.S （S表示开始符号）。
(2) 置项目G→.S为初态集的核，然后对核求闭包，CLOSURE({S’→.S}）得到初态的项目集。
(3) 依次对初态集和其它新构造的项目集应用转换函数GO(I，X)=CLOSURE(J)，求出新状态J的项目集。
(4) 重复3直到不出现新的项目为止。
输入格式：
第1行为文法产生式的数量n，
第2行之后n行是文法产生式（文法中的ε用@表示）。
输出格式：
第一部分依次输出拓广后的文法，
第二部分依次输出项目集规范族，
第三部分依次输出根据项目集规范族构造的DFA状态转换，
第四部分依次输出句柄识别态编号。
注意：
① 忽略产生式里的空格，样例输入产生式的终结符不包括“.”；
② 本题中拓广产生式的左部均为G；
③ 每个产生式前加上编号，编号从0开始，编号后的点为英文字符；
④ 项目集规范族的编号依次是I0、I1、I2...，编号后的冒号为英文字符；
⑤ 项目集内部，按照闭包的求解顺序输出，左部相同的项目按照产生式的顺序输出；
⑥ 按照项目集内项目的出现顺序计算转换函数，构造新的项目集；
⑦ 第一、二、三部分输出后均空一行，第四部分输出后没有空行；
⑧ DFA转换函数按照项目集的构造顺序依次输出。
题目链接：https://pintia.cn/problem-sets/1640317334583414784/exam/problems/1640317518918873088
输入样例1：
3
A-> c D
A-> d
D ->a
输出样例1：
0.G->A
1.A->cD
2.A->d
3.D->a
I0:
G->.A
A->.cD
A->.d
I1:
G->A.
I2:
A->c.D
D->.a
I3:
A->d.
I4:
A->cD.
I5:
D->a.
I0 A I1
I0 c I2
I0 d I3
I2 D I4
I2 a I5
I3 I4 I5
输入样例2：
8
E->E+T
E->T
T->T*F
T->F
F->P^F
F->P
P->(E)
P->i
输出样例2：
0.G->E
1.E->E+T
2.E->T
3.T->T*F
4.T->F
5.F->P^F
6.F->P
7.P->(E)
8.P->i
I0:
G->.E
E->.E+T
E->.T
T->.T*F
T->.F
F->.P^F
F->.P
P->.(E)
P->.i
I1:
G->E.
E->E.+T
I2:
E->T.
T->T.*F
I3:
T->F.
I4:
F->P.^F
F->P.
I5:
P->(.E)
E->.E+T
E->.T
T->.T*F
T->.F
F->.P^F
F->.P
P->.(E)
P->.i
I6:
P->i.
I7:
E->E+.T
T->.T*F
T->.F
F->.P^F
F->.P
P->.(E)
P->.i
I8:
T->T*.F
F->.P^F
F->.P
P->.(E)
P->.i
I9:
F->P^.F
F->.P^F
F->.P
P->.(E)
P->.i
I10:
P->(E.)
E->E.+T
I11:
E->E+T.
T->T.*F
I12:
T->T*F.
I13:
F->P^F.
I14:
P->(E).
I0 E I1
I0 T I2
I0 F I3
I0 P I4
I0 ( I5
I0 i I6
I1 + I7
I2 * I8
I4 ^ I9
I5 E I10
I5 T I2
I5 F I3
I5 P I4
I5 ( I5
I5 i I6
I7 T I11
I7 F I3
I7 P I4
I7 ( I5
I7 i I6
I8 F I12
I8 P I4
I8 ( I5
I8 i I6
I9 F I13
I9 P I4
I9 ( I5
I9 i I6
I10 ) I14
I10 + I7
I11 * I8
I2 I3 I4 I6 I11 I12 I13 I14
对处理输入的一点点小的改进：
之前输入我都是用fgets函数输出到一个char数组中，遍历去空格换行等，然后再赋给一个string变量
现在有了更好更简洁的方法：
string temp;
getline(cin,temp);
//去掉空格、'\t'和换行
temp.erase(remove(temp.begin(),temp.end(),' '),temp.end());
temp.erase(remove(temp.begin(),temp.end(),'\t'),temp.end());
temp.erase(remove(temp.begin(),temp.end(),'\n'),temp.end());
其中remove函数在algorithm这个库中。
思考：
首先，我们需要知道，“核”的定义是什么，就是一个状态通过一条弧得到的初始的集合（初态的核就只有G→.S或类似的）
例如样例1当中由I0经过c这条弧可以得到I2的核：A->c.D，而通过对这个核求闭包（CLOSURE），就可以得到完整的状态，由此可知，我们只需要得到一个状态的核，就相当于得到了这个状态。
对于求闭包（CLOSURE），我们先看看闭包的定义：
-
I的任何项目都属于
CLOSURE(I)； -
若
A→α•Bβ属于CLOSURE(I)，对任何产生式B→γ，B→•γ也属于CLOSURE(I)； -
重复执行上述两步骤直至
CLOSURE(I)不再增大为止。
也就是说，我们要求闭包，就必须得到所有的.后面的非终结符（不仅仅是核当中的，还有通过求CLOSURE）的过程中得到的，我们对于每个这样的非终结符都需要遍历一次所有的产生式。
那么问题就来了，对于每个非终结符都需要遍历来求闭包，会不会导致重复，比如原来核当中已经有A的产生式了，在求闭包的过程中有要更新A的产生式，会不会导致重复呢？
答案是不会，除了初态以外，所有状态的核中的产生式中的.一定不会出现在右部的开头，而在求闭包的时候更新的产生式，.一定在右部的开头，所以是不会导致重复的。
知道了定义和相关的问题之后，我们来看一下求CLOSURE集合的具体思路：
-
我们用一个队列来存所有的
.后面的非终结符，先遍历所有的核得到这样的非终结符，然后对队列中的非终结符进行处理，循环条件为队列是否为空，每次遍历到一个队列中的元素，就要遍历所有的产生式，然后再来更新这个状态中的产生式。 -
如果更新出来的产生式又产生了新的
.后面的非终结符，那么就继续把这个非终结符压入进队列即可，同时，我们还需要用一个数据结构来标记哪些非终结符是已经被存入过队列中的，可以用unordered_set也可以用一个bool数组
下面我们具体讲一下项目集规范族的构造：
相当于就是基于初态然后根据可以走的边不断更新出整个项目集规范族，对于样例，I0可以走A、c、d这条边，来更新出I1、I2、I3，我们再由更新出来的I1、I2、I3，又可以更新出I4、I5，直到不能再更新为止。
其实上面所说的过程就相当于广度优先遍历了（BFS），我们将需要更新的状态放入队列中，每次取队头的元素，根据队头来更新新的状态，也就是说，每取一次队头，就需要遍历这个状态当中的所有产生式，来得到所有的出边，再通过go函数来得到新的状态，同时我们还需要记录出边，因为一个状态中可以有多个产生式走一条边，但是一个状态到另一个状态只能走一条边，所以记录.后面的符号的时候也需要用一个数据结构来判断这个符号是不是以及走过了（代码中用的是unordered_set<char> weight;）。
最后就是go函数了，其实我们实现了CLOSURE闭包之后，go函数就不难了，int go(int t,char c)意思是从t这个状态走c这个边得到的状态，我们遍历t这个状态所有的产生式，然后对.后面是c的产生式进行处理即可，遍历处理完之后，我们得到的是这个新状态的核，所以我们还需要做一次闭包，然后再判断，这个状态是不是以及存在了，如果存在了，就直接加边即可，图我们这里用邻接表来存，如果不存在，我们就需要更新项目集规范族，更新一个新的状态。
check_handle：最后就是关于句柄识别态了，这里老师其实讲的不够清楚，对于一个状态是不是句柄识别态，我们首先需要除掉句子识别态的情况，然后再判断，这个状态中有没有以.结尾的产生式，如果有，那就说明这个状态就是句柄识别态。
一个误区：
- 认为句子识别态只有一个产生式：
G->(非终结符).但其实只要I0有别的产生式也走同样的边就好了。
所以最简单的判断方法就是，如果这个状态编号为1（句子识别态），就不管，如果不是，就需要判断
下面是具体的实现代码：
#include<iostream>
#include<string.h>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#include<unordered_set>
using namespace std;
/*
题目：SLR(1)分析1 7-1 SLR(1)项目集规范族的构造
*/
#define x first
#define y second
typedef pair<string,string> PSS;//可以用这样的数据结构来存产生式
vector<PSS> p;
vector<vector<PSS>> I;//存储所有的状态
vector<int> handle_state;//存储所有的句柄识别态
const int N =110;
//定义邻接表
int h[N],e[N],ne[N],idx;
char w[N];
void add(int a,int b,char c);
int vector_find(vector<PSS> c);
int go(int t,char c);
void cin_init();
void generating_LR0();
void CLOSURE(vector<PSS>& t);
void print();
int main()
{
cin_init();
generating_LR0();
print();
return 0;
}
void print()
{
cout<<endl;
for(int i=0;i<I.size();i++)
{
cout<<"I"<<i<<":"<<endl;
for(int j=0;j<I[i].size();j++)cout<<I[i][j].x<<"->"<<I[i][j].y<<endl;
}
cout<<endl;
for(int i=0;i<I.size();i++)
{
string temp;
for(int j=h[i];j!=-1;j=ne[j])
{
temp="I"+to_string(i)+" "+w[j]+" I"+to_string(e[j])+"\n"+temp;
}
cout<<temp;
}
cout<<endl;
for(int i=0;i<handle_state.size();i++)
{
cout<<"I"<<handle_state[i];if(i!=handle_state.size()-1)cout<<" ";
}
}
bool check_handle(int t)
{
if(t==1)return false;
for(int i=0;i<I[t].size();i++)
{
string right = I[t][i].y;
if(right.find('.')==right.size()-1)return true;
}
return false;
}
void add(int a,int b,char c)
{
e[idx]=b;
ne[idx]=h[a];
w[idx]=c;
h[a]=idx++;
}
int vector_find(vector<PSS> c)
{
for(int i=0;i<I.size();i++)
{
if(I[i]==c)return i;
}
return -1;
}
int go(int t,char c)
{
/*
go函数实现的过程是将t状态走c这条边到达另一状态
*/
vector<PSS> source = I[t];
vector<PSS> temp;
for(int i=0;i<source.size();i++)//遍历source所有的产生式
{
string right = source[i].y;
int index = right.find('.');
if(index<right.size()-1&&right[index+1]==c)
{
swap(right[index],right[index+1]);
temp.push_back({source[i].x,right});
}
}//得到对应所有的核
// 得到这个核对应的状态
CLOSURE(temp);
//如果有原来的状态,说明要go的状态是存在的,只需要找到这个状态然后加边即可
//如果没有的话就需要新建一个状态，再加边
int location = vector_find(temp);
int target;
int flag;
if(location == -1)
{
I.push_back(temp);
target=I.size()-1;flag=target;
if(check_handle(target))//判断是不是句柄识别态
handle_state.push_back(target);
}
else {target = location;flag=-1;}
add(t,target,c);
return flag;
}
void generating_LR0()
{
// 初始化初态的状态集,即I0
vector<PSS> I0;
I0.push_back({p[0].x,"."+p[0].y});
I.push_back(I0);//I0的核
CLOSURE(I[0]);
if(check_handle(0))handle_state.push_back(0);
queue<int> q;
//由初态更新
q.push(0);
memset(h,-1,sizeof(h));//初始化
while(q.size())
{
int t = q.front();//取出队头状态
q.pop();
vector<PSS> state=I[t];
unordered_set<char> weight;
for(int i=0;i<state.size();i++)//遍历这个状态中的所有产生式
{
string right = state[i].y;
int index = right.find('.');
if(right.size()-1==index)continue;//'.'在最后,不会产生出边
if(!weight.count(right[index+1]))//由于每次go都会把所有的有关的边都记录上，所以只需要走一次
{
int flag = go(t,right[index+1]);
weight.insert(right[index+1]);
if(flag!=-1)q.push(flag);
}
}
}
}
void CLOSURE(vector<PSS>& t)//对这个核求闭包
{
unordered_set<char> behind;
queue<char> q;
for(int i=0;i<t.size();i++)//=t.y[t.y.find('.')+1];//找到'.'的后面非终结符
{
string right = t[i].y;
int index = right.find('.')+1;
if(index<right.size())
{
char c = right[index];
if(!behind.count(c)&&(c>='A'||c<='Z'))
{
behind.insert(c);q.push(c);
}
}
}
while(q.size())
{
char s=q.front();q.pop();
for(int i=0;i<p.size();i++)
{
char left=p[i].x[0];//左部
if(left==s)
{
//需要注意的是对于空产生式,只有一个项目,即A->.
if(p[i].y=="@")t.push_back({p[i].x,"."});
else
{
if(!behind.count(p[i].y[0])&&(p[i].y[0]>='A'||p[i].y[0]<='Z'))
{
behind.insert(p[i].y[0]);q.push(p[i].y[0]);
}
t.push_back({p[i].x,"."+p[i].y});
}
}
}
}
}
void cin_init()
{
int n;cin>>n;getchar();
for(int i=0;i<n;i++)
{
string temp;
getline(cin,temp);//可以用这个函数
//去掉空格、'\t'和换行
temp.erase(remove(temp.begin(),temp.end(),' '),temp.end());
temp.erase(remove(temp.begin(),temp.end(),'\t'),temp.end());
temp.erase(remove(temp.begin(),temp.end(),'\n'),temp.end());
string a=temp.substr(0,1);
string b=temp.substr(3,temp.size()-2);
if(i==0)p.push_back({"G",a});//拓广文法
p.push_back({a,b});
}
//先输出拓广文法
for(int i=0;i<p.size();i++)
cout<<i<<"."<<p[i].x<<"->"<<p[i].y<<endl;
}
