First集和Follow集求解

#include
#include
using namespace std;

#define MAXS 50
int NONE[MAXS]={0};//求每个非终结符的Follow集时避免死循环的变量
string strings;//产生式
string Vn;//非终结符
string Vt;//终结符
string First[MAXS];//用于存放每个非终结符的First集
string Follow[MAXS];//用于存放每个非终结符的Follow集
int N;//产生式个数

//将每个产生式的左部和右部分开
struct STR
{
string left;//产生式左部
string right;//产生式右部
};

//求Vn集和Vt集
void VnVt(STR *p)
{
int i,j;
for(i=0;i{
for(j=0;j<(int)p[i].left.length();j++)//对产生式左部进行分析，求Vn集和Vt集
{
if((p[i].left[j]>='A'&&p[i].left[j]<='Z'))
{
if(Vn.find(p[i].left[j])>100)//若在Vn中找到p[i].left[j]，则find函数返回该字符串的下标；若未找到，则find函数返回一个很大的数
Vn+=p[i].left[j];
}
else
{
if(Vt.find(p[i].left[j])>100)//若在Vt中找到p[i].left[j]，则find函数返回该字符串的下标；若未找到，则find函数返回一个很大的数
Vt+=p[i].left[j];
}
}
for(j=0;j<(int)p[i].right.length();j++)//对产生式右部进行分析，求Vn集和Vt集
{
if(!(p[i].right[j]>='A'&&p[i].right[j]<='Z'))
{
if(Vt.find(p[i].right[j])>100)
Vt+=p[i].right[j];
}
else
{
if(Vn.find(p[i].right[j])>100)
Vn+=p[i].right[j];
}
}
}
}

//分别得到产生式的左部和右部
void getlr(STR *p,int i)
{
int j;
for(j=0;j{
if(strings[j]=='-'&&strings[j+1]=='>')//利用->将产生式的左部和右部分开
{
p[i].left=strings.substr(0,j);//从strings的第0个字符开始，将长为j的子字符串复制给p[i].left
p[i].right=strings.substr(j+2,strings.length()-j-2);
}
}
}

//对每个非终结符求First集
string Letter_First(STR *p,char ch)
{
int t,flag=1;//若某个产生式的右侧字符均为非终结符，且所有非终结符的First集中均含有@，则flag的值为1
for(int i=0;i{
if(p[i].left[0]==ch)//找到该非终结符
{
if(!(Vt.find(p[i].right[0])>100))//该非终结符所在的产生式的右侧第一个字符是终结符，则将此终结符加入该非终结符的First集
{
if(First[Vn.find(ch)].find(p[i].right[0])>100)
First[Vn.find(ch)]+=p[i].right[0];
}
if(p[i].right[0]=='@')//该非终结符所在的产生式的右侧是@，则将@加入该非终结符的F

irst集
{
if(First[Vn.find(ch)].find('@')>100)
First[Vn.find(ch)]+='@';
}
if(!(Vn.find(p[i].right[0])>100))//该非终结符所在的产生式的右侧第一个字符是非终结符
{
if(p[i].right.length()==1)//该非终结符所在的产生式的右侧仅有一个非终结符
{
string ff;
ff=Letter_First(p,p[i].right[0]);
for(int ii=0;ii{
if(First[Vn.find(ch)].find(ff[ii])>100)
First[Vn.find(ch)]+=ff[ii];
}
}
else//该非终结符所在的产生式的右侧字符数大于1
{
for(int j=0;j{
string TT;
if(!(Vn.find(p[i].right[j])>100))//该非终结符所在的产生式的右侧字符均为非终结符
{
TT=Letter_First(p,p[i].right[j]);
if(!(TT.find('@')>100))//非终结符p[i].right[j]的First集中含有@
{
for(t=0;t{
if(First[Vn.find(ch)].find(TT[t])>100&&TT[t]!='@')//将非终结符p[i].right[j]的First集中除@之外的元素均加入所求非终结符的First集中
First[Vn.find(ch)]+=TT[t];
}
}
else//非终结符p[i].right[j]的First集中不含@
{
flag=0;
for(t=0;t{
if(First[Vn.find(ch)].find(TT[t])>100)//将非终结符p[i].right[j]的First集中的所有元素均加入所求非终结符的First集中
First[Vn.find(ch)]+=TT[t];
}
break;
}
}
else//在该非终结符所在的产生式的右侧字符中遇到了终结符
{
flag=0;
if(First[Vn.find(ch)].find(p[i].right[j])>100)
First[Vn.find(ch)]+=p[i].right[j];
break;
}
}
if(flag==1)
First[Vn.find(ch)]+='@';//该非终结符所在的产生式的右侧字符均为非终结符，且所有非终结符的First集中均含有@，则将@加入该非终结符的First集中

}
}
}
}
return First[Vn.find(ch)];
}

//求每个非终结符的Follow集
string Letter_Follow(STR *p,char ch)
{
int t,k,flag=1;//若该非终结符的右侧字符均为非终结符，且所有非终结符的First集中均含有@，则flag的值为1
NONE[Vn.find(ch)]++;//避免死循环的变量值自增
if(NONE[Vn.find(ch)]==2)//当出现所求非终结符的Follow集需要将自身加入时，将避免死循环的变量值设为0，并跳出死循环
{
NONE[Vn.find(ch)]=0;
return Follow[Vn.find(ch)];
}
for(int i=0;i{
for(int j=0;j{
if(p[i].right[j]==ch)//找到该非终结符
{
if(j+1==p[i].right.length())//该非终结符在其所在的产生式的最右侧
{
string gg;
gg=Letter_Follow(p,p[i].left[0]);
for(k=0;k{
if(Follow[Vn.find(ch)].find(gg[k])>100)
Follow[Vn.find(ch)]+=gg[k];
}
}
else//在该非终结符所在的产生式右侧还有字符
{
string FF;
for(int jj=j+1;jj{
string TT;
if(!(Vn.find(p[i].right[jj])>100))//该非终结符右侧的字符仍是非终结符
{
TT=Letter_First(p,p[i].right[jj]);
if(!(TT.find('@')>100))//该非终结符右侧的非终结符的First集中含有@
{
for(t=0;t{
if(FF.find(TT[t])>100&&TT[t]!='@')//将非终结符p[i].right[jj]的First集中除@之外的元素均加入FF集中
FF+=TT[t];
}
}
else//该非终结符右侧的非终结符的First集中不含@
{
flag=0;
for(t=0;t{
if(FF.find(TT[t])>100)//将非终结符p[i].right[jj]的First集中的所有元素均加入FF集中
FF+=TT[t];
}
break;
}
}
else//该非终结符右侧的字符是终结符
{
flag=0;
if(FF.find(p[i].right[jj])>100)

FF+=p[i].right[jj];
break;
}
}
if(flag==1)
FF+='@';//该非终结符的右侧字符均为非终结符，且所有非终结符的First集中均含有@，则将@加入FF集中
if(FF.find('@')>100)//FF集中不含@，则将FF集中的所有元素均加入该非终结符的Follow集中
{
for(k=0;k{
if(Follow[Vn.find(ch)].find(FF[k])>100)
Follow[Vn.find(ch)]+=FF[k];
}
}
else//FF集中含有@，则将FF集中除@之外的元素均加入该非终结符的Follow集中
{
for(k=0;k{
if((Follow[Vn.find(ch)].find(FF[k])>100)&&FF[k]!='@')
Follow[Vn.find(ch)]+=FF[k];
}
string dd;
dd=Letter_Follow(p,p[i].left[0]);
for(k=0;k{
if(Follow[Vn.find(ch)].find(dd[k])>100)
Follow[Vn.find(ch)]+=dd[k];
}
}
}
}
}
}
return Follow[Vn.find(ch)];
}

int main()
{
int i,j,k;
cout<<"请输入产生式总数:"<cin>>N;
cout<<"请输入各产生式（@代表空）:"<STR *p=new STR[MAXS];
for(i=0;i{
cin>>strings;
getlr(p,i);
}
VnVt(p);
cout<<"============================================="<cout<<"非终结符"<<"\t"<<"FIRST集"<<"\t\t"<<"FOLLOW集"<for(i=0;i{
cout<<" "<string pp;
pp=Letter_First(p,Vn[i]);
for(j=0;jcout<cout<if(pp.length()>3)
cout<<"\t{";
else
cout<<"\t\t{";
Follow[0]+='$';
string ppp;
ppp=Letter_Follow(p,Vn[i]);
for(k=0;kcout<cout<}
cout<<"============================================="<return 0;
}