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

编译原理实验报告

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

实验时间

院系计算机科学与技术

班级软件工程1班

1.实验目的

输入：任意的上下文无关文法。

输出：所输入的上下文无关文法一切非终结符的first集合和follow集合。

2.实验原理

设文法G[S]＝（VN，VT，P，S），则首字符集为：

FIRST（α）＝{a|αaβ，a∈VT，α,β∈V}。

若αε，ε∈FIRST（α）。

由定义可以看出，FIRST（α）是指符号串α能够推导出的所有符号串中处于串首的终结符号组成的集合。所以FIRST集也称为首符号集。

设α＝_1_2…_n，FIRST（α）可按下列方法求得：

令FIRST（α）＝Φ，i＝1；

（1）若_i∈VT，则_i∈FIRST（α）；

（2）若_i∈VN；

①若εFIRST（_i），则FIRST（_i）∈FIRST（α）；

②若ε∈FIRST（_i），则FIRST（_i）－{ε}∈FIRST（α）；

（3）i＝i+1，重复（1）、（2），直到_i∈VT，（i＝2，3，…，n）或_i

∈VN且若εFIRST（_i）或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→_Ay的规则，其中_，y∈V，则FIRST

（y）－{ε}∈FOLLOW（A）；

（3）若文法G[S]中有形如B→_A的规则，或形如B→_Ay的规则且ε

∈FIRST（y），其中_，y∈V，则FOLLOW（B）∈FOLLOW（A）；

3.实验内容

计算first集合和follow集合

4.实验心得

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

5.实验代码与结果

include

include

include

usingnamespacestd;

defineMA_S50

intNONE[MA_S]={0};

stringstrings;/产生式

stringVn;/非终结符

stringVt;/终结符

stringfirst[MA_S];/用于存放每个终结符的first集

stringFirst[MA_S];/用于存放每个非终结符的first集

stringFollow[MA_S];/用于存放每个非终结符的follow集

intN;/产生式个数

structSTR

stringleft;

stringright;

/求VN和VT

voidVNVT(STRp)

inti,j;

for(i=0;i

for(j=0;j<(int)p[i]XXX();j++)

if((p[i].left[j]>='A'p[i].left[j]<='Z'))

if(XXX(p[i].left[j])>100)

Vn+=p[i].left[j];

else

if(XXX(p[i].left[j])>100)

Vt+=p[i].left[j];

for(j=0;j<(int)p[i]XXX();j++)

if(!(p[i].right[j]>='A'p[i].right[j]<='Z')){

if(XXX(p[i].right[j])>100)

Vt+=p[i].right[j];

else

if(XXX(p[i].right[j])>100)

Vn+=p[i].right[j];

voidgetlr(STRp,inti)

intj;

for(j=0;j

if(strings[j]=='-'strings[j+1]=='>')

p[i].left=XXX(0,j);

p[i].right=XXX(j+2,XXX()-j);}

/对每个文法符号求first集

stringLetter_First(STRp,charch)

intt;

if(!(XXX(ch)>100))

first[XXX(ch)]="ch";returnfirst[XXX(ch)-1];}if(!(XXX(ch)>100)){for(inti=0;i100)){if(First[XXX(ch)].find(p[i].right[0])>100){First[XXX(ch)]+=p[i].right[0];}}if(p[i].right[0]==''){if(First[XXX(ch)].find('')>100){First[XXX(ch)]+='';}}if(!(XXX(p[i].right[0])>100)){if(p[i]XXX()==1){stringff;ff=Letter_First(p,p[i].right[0]);for(inti_i=0;i_i100){First[XXX(ch)]+=ff[i_i];}}}else{for(intj=0;j

if(!(XXX('')>100)(j+1)

sort(XXX(),XXX());

stringtt;

for(intt=1;t

tt+=TT[t];

TT=tt;

tt="";

for(t=0;t

if(First[XXX(ch)].find(TT[t])>100){

First[XXX(ch)]+=TT[t];}

else

for(t=0;t

if(First[XXX(ch)].find(TT[t])>100){

First[XXX(ch)]+=TT[t];}

break;

returnFirst[XXX(ch)];

/求每个非终结符的Follow集

stringLetter_Follow(STRp,charch)

intt,k;

NONE[XXX(ch)]++;

if(NONE[XXX(ch)]==2)

{NONE[XXX(ch)]=0;returnFollow[XXX(ch)];}for(inti=0;i100){Follow[XXX(ch)]+=gg[k];}}}else{stringFF;for(intjj=j+1;jj100)(jj+1)100TT[t]!=''){

FF+=TT[t];}}}else{for(t=0;t100){FF+=TT[t];}}break;}}if(XXX('')>100){for(k=0;k100){Follow[XXX(ch)]+=FF[k];}}}else{for(k=0;k100)FF[k]!=''){Follow[XXX(ch)]+=FF[k];}}stringdd;dd=Letter_Follow(p,p[i].left[0]);NONE[XXX(p[i].left[0])]=0;for(k=0;k100){Follow[XXX(ch)]+=dd[k];

returnFollow[XXX(ch)];

voidresult()

cout<<" 该文法不是LL(1)型文法"<

/主函数

intmain()

inti,j,k;

cout<<"请输入产生式总数:";

cin>N;

cout<<" 请输入各产生式（代表空）:"<

STRp=newSTR[MA_S];

for(i=0;i

cin>strings;

getlr(p,i);

VNVT(p);

cout<

cout<<" ========================================="<

cout<<""<

stringpp;

pp=Letter_First(p,Vn[i]);

for(j=0;j+1

cout<

cout<

Follow[0]+='';

}cout<<"{";stringppp;ppp=Letter_Follow(p,Vn[i]);for(k=0;k+1