编译原理实验报告FIRST集和FOLLOW集.doc

编译原理实验报告

实验名称 计算first集合和follow集合

实验时间

院系 计算机科学与技术

班级 软件工程1班

学号

姓名
1. 实验目的
输入：任意的上下文无关文法。
输出：所输入的上下文无关文法一切非终结符的first集合和follow集合。

2. 实验原理
设文法G[S]＝（VN，VT，P，S），则首字符集为：
FIRST（α）＝{a | αaβ，a∈VT，α,β∈V *}。
若αε，ε∈FIRST（α）。
由定义可以看出，FIRST（α）是指符号串α能够推导出的所有符号串中处于串首的终结符号组成的集合。所以FIRST集也称为首符号集。
设α＝x1x2…xn，FIRST（α）可按下列方法求得：
令FIRST（α）＝Φ，i＝1；
（1） 若xi∈VT，则xi∈FIRST（α）；
（2） 若xi∈VN；
① 若εFIRST（xi），则FIRST（xi）∈FIRST（α）；
② 若ε∈FIRST（xi），则FIRST（xi）－{ε}∈FIRST（α）；
（3） i＝i+1，重复（1）、（2），直到xi∈VT，（i＝2，3，…，n）或xi∈VN且若εFIRST（xi）或i>n为止。
当一个文法中存在ε产生式时，例如，存在A→ε，只有知道哪些符号可以合法地出现在非终结符A之后，才能知道是否选择A→ε产生式。这些合法地出现在非终结符A之后的符号组成的集合被称为FOLLOW集合。下面我们给出文法的FOLLOW集的定义。
设文法G[S]＝（VN，VT，P，S），则
FOLLOW（A）＝{a | S… Aa …，a∈VT}。
若S…A，#∈FOLLOW（A）。
由定义可以看出，FOLLOW（A）是指在文法G[S]的所有句型中，紧跟在非终结符A后的终结符号的集合。
FOLLOW集可按下列方法求得：
（1） 对于文法G[S]的开始符号S，有#∈FOLLOW（S）；
（2） 若文法G[S]中有形如B→xAy的规则，其中x，y∈V *，则FIRST（y）－{ε}∈FOLLOW（A）；
（3） 若文法G[S]中有形如B→xA的规则，或形如B→xAy的规则且ε∈FIRST（y），其中x，y∈V *，则FOLLOW（B）∈FOLLOW（A）；
3.实验内容
计算first集合和follow集合

4.实验心得
通过上机实验我对文法符号的FIRST集和FOLLOW集有了更深刻的理解，已经熟练的掌握了求解的思想和方法，同时也锻炼了自己的动手解决问题的能力，对编程能力也有所提高。

5.实验代码与结果
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define MAXS 50
int NONE[MAXS]={0};
string strings;//产生式
string Vn;//非终结符
string Vt;//终结符
string first[MAXS];// 用于存放每个终结符的first集
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<N;i++)
{
for(j=0;j<(int)p[i].left.length();j++)
{
if((p[i].left[j]>='A'&&p[i].left[j]<='Z'))
{
if(Vn.find(p[i].left[j])>100)
Vn+=p[i].left[j];
}
else
{
if(Vt.find(p[i].left[j])>100)
Vt +=p[i].left[j];
}
}
for(j=0;j<(int)p[i].right.length();j++)
{
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<strings.length();j++)
{
if(strings[j]=='-'&&strings[j+1]=='>')
{
p[i].left=strings.substr(0,j);
p[i].right=strings.substr(j+2,strings.length()-j);
}
}
}

//对每个文法符号求first集
string Letter_First(STR *p,char ch)
{
int t;
if(!(Vt.find(ch)>100))
{
first[Vt.find(ch)]="ch";
return first[Vt.find(ch)-1];
}
if(!(Vn.find(ch)>100))
{
for(int i=0;i<N;i++)
{
if(p[i].left[0]==ch)
{
if(!(Vt.find(p[i].right[0])>100))
{
if(First[Vn.find(ch)].find(p[i].right[0])>100)
{
First[Vn.find(ch)]+=p[i].right[0];
}
}
if(p[i].right[0]=='*')
{
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 i_i=0;i_i<ff.length();i_i++)
{
if( First[Vn.find(ch)].find(ff[i_i])>100)
{
First[Vn.find(ch)]+=ff[i_i];
}
}

}
else
{
for(int j=0;j<p[i].right.length();j++)
{
string TT;
TT=Letter_First(p,p[i].right[j]);
if(!(TT.find('*')>100)&&(j+1)<p[i].right.length())
{
sort(TT.begin(),TT.end());
string tt;
for(int t=1;t<TT.length();t++)
{
tt+=TT[t];
}
TT=tt;
tt="";
for(t=0;t<TT.length();t++)
{
if( First[Vn.find(ch)].find(TT[t])>100)
{
First[Vn.find(ch)]+=TT[t];
}
}
}
else
{
for(t=0;t<TT.length();t++)
{
if( First[Vn.find(ch)].find(TT[t])>100)
{
First[Vn.find(ch)]+=TT[t];
}
}
break;
}
}
}

}
}
}
return First[Vn.find(ch)];
}
}
// 求每个非终结符的Follow集
string Letter_Follow(STR *p,char ch)
{
int t,k;
NONE[Vn.find(ch)]++;
if(NONE[Vn.find(ch)]==2)
{
NONE[Vn.find(ch)]=0;
return Follow[Vn.find(ch)];
}
for(int i=0;i<N;i++)
{
for(int j=0;j<p[i].right.length();j++)
{
if(p[i].right[j]==ch)
{
if(j+1==p[i].right.length())
{
string gg;
gg=Letter_Follow(p,p[i].left[0]);
NONE[Vn.find(p[i].left[0])]=0;
for(int k=0;k<gg.length();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<p[i].right.length();jj++)
{
string TT;
TT=Letter_First(p,p[i].right[jj]);
if(!(TT.find('*')>100)&&(jj+1)<p[i].right.length())
{
sort(TT.begin(),TT.end());
string tt;
for(int t=1;t<TT.length();t++)
{
tt+=TT[t];
}
TT=tt;
tt="";
for(t=0;t<TT.length();t++)
{
if( FF.find(TT[t])>100&&TT[t]!='*')
{
FF+=TT[t];
}
}
}
else
{
for(t=0;t<TT.length();t++)
{
if( FF.find(TT[t])>100)
{
FF+=TT[t];
}
}
break;
}
}

if(FF.find('*')>100)
{
for(k=0;k<FF.length();k++)
{
if(Follow[Vn.find(ch)].find(FF[k])>100)
{
Follow[Vn.find(ch)]+=FF[k];
}
}
}
else
{
for(k=0;k<FF.length();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]);
NONE[Vn.find(p[i].left[0])]=0;
for(k=0;k<dd.length();k++)
{
if(Follow[Vn.find(ch)].find(dd[k])>100)
{
Follow[Vn.find(ch)]+=dd[k];
}
}

}

}
}
}
}
return Follow[Vn.find(ch)];
}
void result()
{
cout<<"\n该文法不是LL(1)型文法"<<endl;
}

//主函数
int main()
{
int i,j,k;
cout<<"请输入产生式总数:";
cin>>N;
cout<<"\n请输入各产生式（*代表空）:"<<endl;
STR *p=new STR[MAXS];
for(i=0;i<N;i++)
{
cin>>strings;
getlr(p,i);
}
VNVT(p);
cout<<endl;
cout<<"\n========================================="<<endl;
cout<<"非终结符"<<"\t"<<"FIRST"<<"\t\t"<<"FOLLOW"<<endl;
for(i=0;i<Vn.length();i++)
{
cout<<" "<<Vn[i]<<"\t\t{";
string pp;
pp=Letter_First(p,Vn[i]);
for(j=0;j+1<pp.length();j++)
{
cout<<pp[j]<<",";
}
cout<<pp[pp.length()-1]<<"} ";
Follow[0]+='#';
cout<<" {";
string ppp;
ppp=Letter_Follow(p,Vn[i]);
for(k=0;k+1<ppp.length();k++)
{
cout<<ppp[k]<<",";
}
cout<<ppp[ppp.length()-1]<<"}"<<endl;
}
result();
cout<<"\n========================================="<<endl;
return 0;
}