求first集和follow集

编译原理实验实验名称：求first集和follow集姓名：学号：教师签字：成绩：一．实验目的：.掌握和了解first集和follow集的求解过程。二．实验原理：1.first集的求解：（1）若X∈Vt,则FIRST(X)={X};(2)若X∈Vn,且有产生式X-a……,a∈Vt，则a∈FIRST(X);(3)若X∈Vn,X-@,则@∈FIRST(X)(4)若X,Y1,Y2,Y3,Y4…………Yn都∈Vn,而产生式X-Y1,Y2……Yn.当Y1,Y2,Y3,Y4…………Yn都能=@那么FIRST(X)=并集的FIRST(Yi)-{@}(0=i=n)(5)若Yi=@(i=1,2,3……)，则FIRST(X)=并集的FIRST(Yi)-{@}并上{@}2.follow集的求解：（1）若为文法开始符号S，则FOLLOW(S)={#}(2)若为文法A-aBb是一个产生式，则把FIRST（b）的非空元素加入FOLLOW(B)中。如果b-@则把FOLLOW(A)也加入FOLLOW(B)中。三．实验代码#includeiostream#includevector#includestring#includealgorithm#includequeueusingnamespacestd;//*********************structdefine//产生式{charleft;stringright;};//***************intN,K1=0,K2=0;charB;structdefine*p=newdefine[10];//************************boolfind(charb)//查找是否有产生空的产生式{inti;for(i=0;iN;i++){if(b==p[i].left&&p[i].right[0]=='@')returntrue;}returnfalse;}//**************************boolfindfo(charb)//查找是否有产生空的产生式{inti;for(i=0;iN;i++){if(b==p[i].left&&p[i].right[0]=='@')returntrue;}returnfalse;}//************************stringfirst(charb)//求解Frist集{inti,index;queueintpos;strings,rights;for(i=0;iN;i++){if(b==p[i].left)pos.push(i);}while(!pos.empty()){if(!(p[pos.front()].right[0]='Z'&&p[pos.front()].right[0]='A')){if((int)s.find(p[pos.front()].right[0])==-1)s.append(1,p[pos.front()].right[0]);}else{rights=p[pos.front()].right;for(i=0;irights.size();i++){if(find(rights[i])){s+=first(rights[i]);index=s.find_last_of('@');s=s.erase(index,1);}else{if(rights[i]='A'&&rights[i]='Z')s+=first(rights[i]);elses.append(1,rights[i]);break;}}}pos.pop();}returns;}//***********************stringfollow(charb)//Follow集的求解{inti,index,index1;strings,right;queueintpos;if(b==B){s.append(1,'#');}else{for(i=0;iN;i++){if((int)p[i].right.find(b)!=-1){pos.push(i);}}while(!pos.empty()){index=pos.front();pos.pop();right=p[index].right;for(i=0;iright.size();i++){if(b==right[i]){index1=i;break;}}if(index1==right.size()-1){s+=follow(p[index].left);}else{for(i=index1+1;iright.size();i++){if(findfo(right[i])){s+=first(right[i]);index=s.find_last_of('@');s.erase(index,1);}else{s+=first(right[i]);}}}}}returns;}//******************************intmain(){inti;strings1,s2;charb;cout\t************求First集和Follow集**************endl;cout请输入产生式的数目：;cinN;cout请输入产生式，其中以@为空:endl;for(i=0;iN;i++){cinp[i].leftbp[i].right;}cout请输入识别符endl;cinB;for(i=0;iN;i++){if((int)s1.find(p[i].left)==-1){s1.append(1,p[i].left);}}couts1endl;cout非终结符的first集endl;for(i=0;is1.size();i++){couts1[i]first(s1[i])endl;}cout非终结符的follow集endl;for(i=0;is1.size();i++){couts1[i]follow(s1[i])endl;}return0;}四．实验截图