LL(1) 基础 7-3 求FOLLOW集
题目详情(题目中ε用@表示):
题目链接:https://pintia.cn/problem-sets/1635283457335554048/exam/problems/1635283976988848130
提示:这个题是基于上两个文章的基础之上来做的,求FOLLOW集合算是三道里面最简单的了,上两篇分别是:
LL(1)基础 7-2 求FIRST集
LL(1) 基础 7-1 求可推导出空的非终结符
输入样例1:
4
S->aA
S->d
A->bAS
A->@
输出样例1:
FOLLOW(A)={ a d # }
FOLLOW(S)={ a d # }
输入样例2:
10
S->AB
S->* C
A->@
A-> *
B->@
B->(D
C- >A D
C->*
D->(S
D->c
输出样例:
FOLLOW(A)={ ( c # }
FOLLOW(B)={ # }
FOLLOW(C)={ # }
FOLLOW(D)={ # }
FOLLOW(S)={ # }
FOLLOW集合的定义和性质:
FOLLOW集顾名思义就是文法符号后面可能跟随的终结符的集合（不包括ε）
对于A ->αBβ，首先判断β是不是可以推出ε
-
如果不可以推出
ε,FOLLOW(B)=FOLLOW(B)∪first(β),无论遇到的是非终结符还是终结符,只要不能推出空串,他的FOLLOW集合一定包含了后面串的first集。 -
如果可以推出
ε,那除了后面的first集除去空串的部分,FOLLOW(B)应该还包含有FOLLOW(A),因为B后面如果是空,那么A后面遇到的字符就是B后面遇到的字符了。用公式来表示就是FOLLOW(B)={FIRST(β)-ε}∪FOLLOW(A)∪FOLLOW(B)
思考:
算法核心(follow_operation):
先将开始符号的FOLLOW集初始化为{#}
外层放一个循环,直到没有FOLLOW集合更新为止
循环遍历所有的非终结符N,找到右部有N的产生式,得到N右边的串r,即string r = right.substr(idx+1,right.size()-idx-1);
-
如果r为空或者r能推出空串,即first(r)中存在
ε,FOLLOW(N)={FIRST(r)-ε}∪FOLLOW(A)∪FOLLOW(N) -
如果r不能推出空,
FOLLOW(N)=FOLLOW(N)∪first(r) -
对于循环的中止条件,我们在最开始设置一个标志位
sign，一开始为0，最开始res为对应的左部的FOLLOW集合,最后res求得新的了之后跟旧的比较,如果不相同,则还需要迭代更新,sign=1,如果相同,则说明循环可以停止,sign=0。在最后:if(sign==0)break;
下面式具体的代码实现:
#include<iostream>
#include<vector>
#include<unordered_set>
#include<cstring>
#include<algorithm>
#include<string.h>
using namespace std;
#define x first
#define y second
typedef pair<string,string> PSS;//可以用这样的数据结构来存产生式
const int N = 1010;
vector<PSS> p;
vector<PSS> p_mirror;
int st[N];//状态数组,为0表示未定,为1表示是,即能推出ε,否则则为2
int cnt[N];//用来记录以这个非终结符为左部的产生式有多少,这样用来判断一个以某个非终结符为左部的产生式是不是多被删掉了就很方便
char start;
vector<char> Vn;//非终结符
unordered_set<char> Vn_set;
vector<char> result;//可以直接推导出ε的非终结符
unordered_set<char> result_set;
string first[N];//first集合
string follow[N];//follow集合
vector<string> right_s;//所有的右部
void init()
{
for(int i=0;i<p.size();i++)//遍历所有的产生式,收集所有的非终结符
{
string a=p[i].x,b=p[i].y;
cnt[a[0]]++;//记录以这个非终结符为左部的产生式的个数
for(int j=0;j<a.size();j++)
if(a[j]>='A'&&a[j]<='Z'&&!Vn_set.count(a[j]))
{Vn.push_back(a[j]);Vn_set.insert(a[j]);}
for(int j=0;j<b.size();j++)
if(b[j]>='A'&&b[j]<='Z'&&!Vn_set.count(b[j]))
{Vn.push_back(b[j]);Vn_set.insert(b[j]);}
}
sort(Vn.begin(),Vn.end());
}
void delete_terminal()//删除所有右部含终结符的产生式
{
for(int i=0;i<p.size();i++)
{
string right=p[i].y;
string left = p[i].x;
bool sign=false;
for(int j=0;j<right.size();j++)
{
// if(right[j]>='a'&&right[j]<='z')
if((right[j]<'A'||right[j]>'Z')&&right[j]!='@')
{
sign=true;break;
}
}
if(sign)//说明含终结符,需要删掉这一个
{
cnt[left[0]]--;
p.erase(p.begin()+i,p.begin()+i+1);
i--;continue;
}
}
for(int i=0;i<Vn.size();i++)
{
if(!cnt[Vn[i]])//这个终结符为左部的所有产生式都被删除
st[Vn[i]]=2;//标记为否
}
}
void sign_not_terminal()
{
unordered_set<string> temp;
for(int i=0;i<p.size();i++)
{
if(p[i].y=="@")//右部为ε
{
string a=p[i].x;
st[a[0]]=1;//标记为是
cnt[a[0]]=0;//直接全部删掉
result.push_back(p[i].x[0]);
result_set.insert(p[i].x[0]);
if(!temp.count(a))
temp.insert(a);
}
}
//根据temp里的统一做删除
for(int i=0;i<p.size();i++)
{
if(temp.count(p[i].x))
{
p.erase(p.begin()+i,p.begin()+i+1);
i--;
continue;
}
}
}
void dealing_right()
{
//这个时候,所有产生式的右部不可能含终结符,也不可能含有ε,只可能是各种非终结符
while(1)
{
int sign=0;
char d;//需要删除的有关产生式的左部的非终结符
for(int i=0;i<p.size();i++)
{
string right=p[i].y,left=p[i].x;
for(int j=0;j<right.size();j++)
{
if(st[right[j]]==1)//对应标志是“是”,则删去该符号
{
if(right.size()==1)//删完这个之后就为空了
{
d=left[0];
st[left[0]]=1;//将这个产生式左部的非终结符对应的标志改为“是”
result.push_back(d);
result_set.insert(d);
sign=1;
break;
}
else
{
right=right.substr(0,j)+right.substr(j+1,right.size()-j-1);//去掉中间那个字符
p[i].y=right;//再写回去
j--;continue;
}
}
else if(st[right[j]]==2)//对应标志是“否”,则直接把这个产生式删掉
{
if(cnt[left[0]]==1)//一删就都删掉了
{
st[left[0]]=2;
}
p.erase(p.begin()+i,p.begin()+i+1);
cnt[left[0]]--;
sign=2;//标记需要删掉下标为i的产生式
break;
}
}
if(sign)break;
}
if(sign==1)
{
for(int i=0;i<p.size();i++)
{
string left = p[i].x;
if(left[0]==d)
{
p.erase(p.begin()+i,p.begin()+i+1);
cnt[d]--;
}
}
}
else if(sign==0)break;//没有改变,说明已经收敛,循环停止
}
sort(result.begin(),result.end());
}
string check(string s)
{
for(int i=0;i<s.size();i++)
{
if(s[i]=='@')
return s.substr(0,i)+s.substr(i+1,s.size()-i-1)+"@";
}
return s;
}
string first_operation(char t)
{
if(first[t].size()!=0)return first[t];
// 对所有的非终结符都求first集合
string res;
for(int i=0;i<p_mirror.size();i++)//遍历所有有关t的产生式
{
string left=p_mirror[i].x,right=p_mirror[i].y;
if(left[0]==t)
{
int sign=1;//用来标志t的first集存不存在ε
for(int j=0;j<right.size();j++)
{
//遇到终结符就可以结束
//遇到非终结符就并ε
if(right[j]!='@'&&(right[j]<'A'||right[j]>'Z'))//遇到的是终结符,包括ε
{
res+=right[j];sign=0;
break;
}
else//遇到非终结符
{
if(right[j]=='@')continue;
string temp = first_operation(right[j]);
if(result_set.count(right[j]))//如果可以直接推导出ε,则要继续往下并
{
temp = check(temp);//把“@”放到最后面
temp = temp.substr(0,temp.size()-1);
res += temp;
}
else
{
res += temp;
sign=0;break;//绝对不存在ε
}
}
}
if(sign==1)res+="@";
}
}
sort(res.begin(),res.end());
res.erase(unique(res.begin(),res.end()),res.end());
first[t]=res;
return res;
}
void first_for_each()
{
for(int i=0;i<Vn.size();i++)
{
char t=Vn[i];
string res = first_operation(t);
res=check(res);
}
}
string first_for_right(string t)
{
string res;
if(t.size()==1&&t[0]>='A'&&t[0]<='Z'&&first[t[0]].size()!=0)
{
res = first[t[0]];
}
else
{
if(t=="@")
res="@";
else
{
int sign=1;
// cout<<"t:"<<t<<endl;
for(int j=0;j<t.size();j++)
{
if(t[j]!='@'&&(t[j]<'A'||t[j]>'Z'))//遇到的是终结符,包括ε
{
res+=t[j];sign=0;
break;
}
else//遇到非终结符
{
if(t[j]=='@')continue;
string temp = first_operation(t[j]);
if(result_set.count(t[j]))//如果可以直接推导出ε,则要继续往下并
{
temp = check(temp);//把“@”放到最后面
temp = temp.substr(0,temp.size()-1);
res += temp;
}
else
{
res += temp;
sign=0;break;//绝对不存在ε
}
}
}
if(sign==1)res+="@";
}
}
sort(res.begin(),res.end());
res.erase(unique(res.begin(),res.end()),res.end());
return res;
}
int check_exist(string s,char t)
{
for(int i=0;i<s.size();i++)
if(s[i]==t)return i;
return -1;
}
bool check_blank(string s)
{
for(int i=0;i<s.size();i++)
if(s[i]=='@')return true;
return false;
}
string delete_blank(string s)
{
string res;
for(int i=0;i<s.size();i++)
if(s[i]!='@')res+=s[i];
return res;
}
string check_over(string s)
{
for(int i=0;i<s.size();i++)
{
if(s[i]=='#')
return s.substr(0,i)+s.substr(i+1,s.size()-i-1)+"#";
}
return s;
}
void follow_operation()
{
//这里需要对开始符号的follow集初始化“#”
follow[start]+="#";
while(1)
{
int sign=0;
for(int i=0;i<Vn.size();i++)
{
//对于这个非终结符,找到在右部有这个终结符的产生式
string res=follow[Vn[i]];//res表示这一次循环的到的follow集
for(int j=0;j<p_mirror.size();j++)
{
string right=p_mirror[j].y ,left = p_mirror[j].x;
if(check_exist(right,Vn[i])==-1)
continue;//没有可以直接跳过
else//如果有
{
int idx=check_exist(right,Vn[i]);
string r = right.substr(idx+1,right.size()-idx-1);//即β
if(r.size()==0||check_blank(first_for_right(r)))//为空,则按β能推出ε处理
{
//{FIRST(β)-ε}∪FOLLOW(A)
string t = first_for_right(r);
res+=follow[left[0]];
if(r.size())//对于A ->αB，将FOLLOW(A)结果加入FOLLOW(B),不需要{FIRST(β)-ε}
res+=delete_blank(first_for_right(r));
}
else //不为空
{
// 将FIRST(β)加入FOLLOW(B)
res+=first_for_right(r);
}
}
}
sort(res.begin(),res.end());
res.erase(unique(res.begin(),res.end()),res.end());
if(follow[Vn[i]]!=res)
{
sign=1;follow[Vn[i]]=res;
}
}
if(sign==0)break;
}
for(int i=0;i<Vn.size();i++)
{
cout<<"FOLLOW("<<Vn[i]<<")={ ";
string res=follow[Vn[i]];
res = check_over(res);
for(int j=0;j<res.size();j++)
cout<<res[j]<<" ";
cout<<"}"<<endl;
}
}
void cin_init();
int main()
{
cin_init();
init();
delete_terminal();
sign_not_terminal();
dealing_right();
first_for_each();
for(int i=0;i<right_s.size();i++)
first_for_right(right_s[i]);
follow_operation();//求follow集
return 0;
}
void cin_init()
{
int n;cin>>n;getchar();
for(int i=0;i<n;i++)
{
char in[99];
string temp;
fgets(in,99,stdin);
for(int i=0;i<strlen(in);i++)//需要忽略空格
{
if(in[i]!=' '&&in[i]!='\t'&&in[i]!='\n')
temp+=in[i];
}
// cout<<temp<<endl;
int t=0;
for(int j=0;j<temp.size();j++)
{
if(temp[j]=='-')
{t=j;break;}
}
string a=temp.substr(0,t);//从下标为0开始,长度位t的子串
string b=temp.substr(t+2,temp.size()-t-1);//'-'的下标是t,'>'的下标是t+1
right_s.push_back(b);
p.push_back({a,b});
start=p[0].x[0];
}
p_mirror=p;
}
好家伙，直接是个实验了