LL(1)进阶 7-1 求SELECT集及LL(1)文法判别
题目详情(题目中ε
用@
表示):
题目链接:https://pintia.cn/problem-sets/1635285818107949056/exam/problems/1635286021019992064
提示:这个题是基于上三个文章的基础之上来做的,上三篇文章分别是:
LL(1) 基础 7-3 求FOLLOW集
LL(1) 基础 7-2 求FIRST集
LL(1) 基础 7-1 求可推导出空的非终结符
输入样例1:
4
S->aA
S->d
A->bAS
A->c
输出样例1:
SELECT(S->aA)={ a }
SELECT(S->d)={ d }
SELECT(A->bAS)={ b }
SELECT(A->c)={ c }
Yes
输入样例2:
10
S->AB
S->b C
A->@
A-> b
B->@
B->aD
C- >A D
C->b
D->aS
D->c
输出样例2:
SELECT(S->AB)={ # a b }
SELECT(S->bC)={ b }
SELECT(A->@)={ # a c }
SELECT(A->b)={ b }
SELECT(B->@)={ # }
SELECT(B->aD)={ a }
SELECT(C->AD)={ a b c }
SELECT(C->b)={ b }
SELECT(D->aS)={ a }
SELECT(D->c)={ c }
No
SELECT
集的定义和性质:
-
定义:大概就是对于产生式
A->α
,SELECT(A->α)
就是A
通过这个产生式可以直接匹配的非终极符集合 -
SELECT
集肯定是不存在ε
SELECT
集的求法:
-
若
α
无法推导出ε
,则A
能通过这个产生式能够匹配到的终结符就是FIRST(α)
,即SELECT(A->α)=FIRST(α)
-
若
α
可以推导出ε
,则A
能通过这个产生式能够匹配到的终结符FIRST(α)
中的终结符,或者(当α
为ε
时)A
能够匹配的终结符就是A
后面跟的,即FOLLOW(A)
,故有SELECT(A->α)=(FIRST(α)-{ε})∪FOLLOW(A)
LL(1)
文法:
-
一个容易理解的概念就是,
LL(1)
文法匹配一个语言的路径一定是唯一的 -
所以对于同一个非终结符,能够匹配非终结符的产生式也一定是唯一的
-
所以判断
LL(1)
文法的充要条件就是:对每个非终结符A
的两个不同产生式A→α
,A→β
,满足SELECT(A→α) ∩ SELECT(A→β)=φ
算法(select_operation和check_ll1
):
-
由于求
SELECT
集只需要求得对应的非终结符的FOLLOW
集,和FIRST
集,前面已经实现过了:
所以我们只需要遍历所有的产生式,调用相应的函数和数组就好了 -
而对于
LL(1)文法
的判断,就是遍历所有的产生式的左部非终结符(第一层循环),然后再遍历所有的产生式(第二层循环)找到所有以这个为非终结符为左部的非终究符,然后对每个产生式的SELECT
集作交集,如果不为空,则说明不是LL(1)
文法,break
,返回false
即可 -
而对于求交集的操作,无非就是看有没有相同的元素,如果有相同的元素,两个集合加起来的size和两个集合作并集的size应该是不对的,所以看交集是不是空集可以转化成求并集的size的情况,代码如下:
int size_i=Select[i].size(),size_j=Select[j].size();
if(Select[i].size()&&Select[j].size())//交集为空,如果有一个是空集,则交集一定是空集
{
string res = Select[i]+Select[j];
sort(res.begin(),res.end());
res.erase(unique(res.begin(),res.end()),res.end());
if(res.size()<size_i+size_j)//并起来的大小小于加起来的大小,说明有重的,即交集不是空集
return false;
}
具体的代码如下:
#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;//所有的右部
string Select[N];//select集合
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;
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;
}
}
void select_operation()
{
// 遍历所有的产生式
for(int i=0;i<p_mirror.size();i++)
{
string left=p_mirror[i].x;
string right=p_mirror[i].y;//右部
string right_first=first_for_right(right);//右部对应的first集
string res;//得到的select集结果
if(check_blank(right_first))//存在空串
{
// 若α->ε,select(A->α)={first(α)-{ε}}∪FOLLOW(A)
res = delete_blank(right_first)+follow[left[0]];
}
else //若α无法推出空串,那么select(A->α)=first(α)
{
res = right_first;
}
sort(res.begin(),res.end());
res.erase(unique(res.begin(),res.end()),res.end());
Select[i]=res;
cout<<"SELECT("<<left<<"->"<<right<<")={ ";
for(int j=0;j<res.size();j++)
cout<<res[j]<<" ";
cout<<"}"<<endl;
}
}
bool check_ll1()
{
for(int i=0;i<p_mirror.size();i++)
{
for(int j=i+1;j<p_mirror.size();j++)
{
string left_i=p_mirror[i].x;
string left_j=p_mirror[j].x;
if(left_i==left_j)//比较左部相同的产生式的select集
{
int size_i=Select[i].size(),size_j=Select[j].size();
if(Select[i].size()&&Select[j].size())//交集为空,如果有一个是空集,则交集一定是空集
{
string res = Select[i]+Select[j];
sort(res.begin(),res.end());
res.erase(unique(res.begin(),res.end()),res.end());
if(res.size()<size_i+size_j)//并起来的大小小于加起来的大小,说明有重的,即交集不是空集
return false;
}
}
}
}
return true;
}
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集
select_operation();//求select集
if(check_ll1())cout<<"Yes";
else cout<<"No";
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;
}