LL(1)进阶 7-2 预测分析表构造
题目详情:
题目链接:https://pintia.cn/problem-sets/1635285818107949056/exam/problems/1635286021024186368
提示:这个题是基于上四篇文章的基础之上来做的,上四篇文章分别是:
LL(1)进阶 7-1 求SELECT集及LL(1)文法判别
LL(1) 基础 7-3 求FOLLOW集
LL(1) 基础 7-2 求FIRST集
LL(1) 基础 7-1 求可推导出空的非终结符
输入样例:
4
S->aA
S->d
A->bAS
A->@
输出样例:
# a b d
A @ @ bAS @
S aA d
预测分析表:
预测分析表就是根据当前的非终结符和需要匹配的终结符来查表匹配需要使用哪一个产生式
这个前面的基础都做好了,做这个表就很简单了
算法(generate_table
):
-
先按照格式按照顺序输出所有的非终结符包括(
#
) -
再收集所有的非终结符,并排序,遍历所有非终结符(第一层循环),先输出这个非终结符,再遍历第一步所有的终结符(第二层循环),根据当前的终结符找到,左部为对应非终究符和对应
SELECT
集中有这个终结符的产生式(第三层循环),输出这个产生式的右部即可 -
需要注意的是
setw
函数在<iomanip>
这个库中
下面是具体的代码:
#include<iostream>
#include<vector>
#include<unordered_set>
#include<cstring>
#include<algorithm>
#include<string.h>
#include<iomanip>//setw
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> Vt;//终结符
unordered_set<char> Vt_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集合
unordered_set<char> select_set[N];
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;
}
}
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;
for(int j=0;j<res.size();j++)//由于生成分析表的时候需要匹配左部和对应的非终结符,所以这里就用unordered_set来实现
select_set[i].insert(res[j]);
}
}
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())//交集为空,如果有一个是空集,则交集一定是空集
{
// cout<<left_i<<" "<<left_j<<endl;
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 generate_table()
{
Vt.push_back('#');
sort(Vt.begin(),Vt.end());
// 先输出所有的终结符
cout<<" ";
for(int i=0;i<Vt.size();i++)
cout<<setw(10)<<Vt[i];
string res;
for(int i=0;i<p_mirror.size();i++)
res+=p_mirror[i].x;
cout<<endl;
sort(res.begin(),res.end());
res.erase(unique(res.begin(),res.end()),res.end());
for(int i=0;i<res.size();i++)
{
cout<<res[i];
for(int k=0;k<Vt.size();k++)//匹配每一个终结符
{
char terminal = Vt[k];
string ans;
for(int j=0;j<p_mirror.size();j++)//找到左部为res[i]的产生式的下标
{
if(p_mirror[j].x[0]==res[i])
{
if(select_set[j].count(terminal))
{
ans=p_mirror[j].y;break;
}
}
}
cout<<setw(10)<<ans;
}
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集
select_operation();//求select集
if(!check_ll1())
{
cout<<"This is not a LL(1) grammar!";
}
else
{
generate_table();
}
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);
//记录终结符
for(int j=0;j<b.size();j++)
{
if((b[j]<'A'||b[j]>'Z')&&b[j]!='@')
{
if(!Vt_set.count(b[j]))
{
Vt_set.insert(b[j]);Vt.push_back(b[j]);
}
}
}
p.push_back({a,b});
start=p[0].x[0];
}
p_mirror=p;
}