编译原理实验报告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
#include
#include
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='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;jj]=='-'&&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;i100))
{
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_i100)
{
First[Vn.find(ch)]+=ff[i_i];
}
}

}
else
{
for(int j=0;j TT=Letter_First(p,p[i].right[j]);
if(!(TT.find('*')>100)&&(j+1) TT=tt;
tt="";
for(t=0;t100)
{
First[Vn.find(ch)]+=TT[t];
}
}
}
else
{
for(t=0;t);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;ingth())
{
string gg;
gg=Letter_Follow(p,p[i].left[0]);
NONE[Vn.find(p[i].left[0])]=0;
for(int k=0;k100)
{
Follow[Vn.find(ch)]+=gg[k];
}
}
}
else
{
string FF;
for(int jj=j+1;jj100)&&(jj+1) for(int t=1;t100&&TT[t]!='*')
{
FF+=TT[t];
}
}
}
else
{
for(t=0;t100)
{
FF+=TT[t];
}
}
break;
}
}

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

}

}
}
}
}
return Follow[Vn.find(ch)];
}
void result()
{
cout<<"\n该文法不是LL(1)型文法"<>N;
cout<<"\n请输入各产生式（*代表空）:"<ndl;
STR *p=new STR[MAXS];
for(i=0;i>strings;
getlr(p,i);
}
VNVT(p);
cout<<" "<