计算first集合和follow集合--编译原理

计算first集合和follow集合姓名：彦清学号：E10914127一、实验目的输入：任意的上下文无关文法。输出：所输入的上下文无关文法一切非终结符的first集合和follow集合。二、实验原理设文法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）或in为止。当一个文法中存在ε产生式时，例如，存在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）；三、源程序#includeiostream.h#includestring.h//产生式structcss{charleft;charzhuan;//用“-”表示箭头charright[20];};//空标志structkong{intkongzuo;intkongyou;};structbiaoji//第三步扫描式子的右部标记号{intr[100];};structfirst//初步求first集合时用{charfjihe[200];};structfirst2//保存最终的first集合{charfjihe2[200];};structfollow//初步求follow集合时用{charfow[200];};structfollow2//保存最终的follow集合{charfow2[200];};voidmain(){inti,n,k;//产生式条数cssshizi[100];kongkongshi[100];cout请输入产生式的条数n(n100)：endl;cinn;cout请从开始符输入产生式(空用“#”表示，产生式由字母组成)：endl;for(i=0;in;i++){cinshizi[i].leftshizi[i].zhuanshizi[i].right;}intl,m,j,h,g,f;for(l=0;ln;l++)for(m=0;msizeof(shizi[l].right);m++){if(shizi[l].right[m]=='#'){kongshi[l].kongzuo=1;break;}elsewhile(shizi[l].right[m]='a'&&shizi[l].right[m]='z'){kongshi[l].kongyou=0;break;}}for(j=0;j=n;j++)for(h=0;hn;h++){if(j==h)break;if(shizi[j].left==shizi[h].left){if(kongshi[j].kongyou==0&&kongshi[h].kongyou==0)kongshi[j].kongzuo=kongshi[h].kongzuo=0;break;}}intd,s,a,q,w,e;charlinshi;biaojibiaoyou[100];for(d=0;dn;d++){if(!(kongshi[d].kongzuo==1||kongshi[d].kongyou==0)){for(s=0;shizi[d].right[s]!='\0';s++)for(a=0;a=n;a++){linshi=shizi[d].right[s];if(linshi==shizi[a].left&&kongshi[a].kongzuo==1){biaoyou[d].r[s]=1;}else{kongshi[d].kongyou=0;}}}}intsum,t,y;//第三部-1sum=0;for(e=0;en;e++){for(q=0;shizi[e].right[q]!='\0';q++){t=biaoyou[e].r[q];if(t==1){for(sum;shizi[e].right[q]!='\0';){sum++;y=sum-1;if(q==y)kongshi[e].kongzuo=1;break;}}elsebreak;}}inta1,a2;/*第二次扫描判断转为否的式子*/for(a1=0;a1=n;a1++)for(a2=0;a2n;a2++){if(a1==a2)break;if(shizi[a1].left==shizi[a2].left&&kongshi[a1].kongzuo!=1&&kongshi[a2].kongzuo!=1){if(kongshi[a1].kongyou==0&&kongshi[a2].kongyou==0)kongshi[a1].kongzuo=kongshi[a2].kongzuo=0;break;}}//计算first集合firstfji[100];intu,a3,a5,a6,a7,a8;//charlinshi2[2]=-;//for(u=0;un;u++){fji[u].fjihe[0]='\0';}for(a3=0;a3=n;a3++){if(shizi[a3].right[0]='a'&&shizi[a3].right[0]='z'){linshi2[0]=shizi[a3].right[0];strcat(fji[a3].fjihe,linshi2);}else{if(kongshi[a3].kongzuo==1){strcat(fji[a3].fjihe,#);}}}for(a5=0;a5=n;a5++)for(a6=0;shizi[a5].right[a6]!='\0';a6++)if(shizi[a5].right[a6]='A'&&shizi[a5].right[a6]='Z'){if(shizi[a5].right[0]='a'&&shizi[a5].right[0]='z')break;for(a7=0;a7n;a7++)if(a5!=a7&&shizi[a5].right[a6]==shizi[a7].left){{if(kongshi[a7].kongzuo!=1)strcat(fji[a5].fjihe,fji[a7].fjihe);if(a6==(strlen(shizi[a5].right)-1))for(a8=0;a8n;a8++)if(a5!=a8&&shizi[a5].right[a6]==shizi[a8].left)if(kongshi[a5].kongzuo!=1){strcat(fji[a5].fjihe,fji[a8].fjihe);}else{strcat(fji[a5].fjihe,fji[a8].fjihe);strcat(fji[a5].fjihe,#);}}}}//求follow集合followfw[100];intb1,b2,b3,b4,b5,b6,b7,b8,b9,b10;charlinshi5[2];for(b1=0;b1n;b1++){fw[b1].fow[0]='\0';}fw[0].fow[0]='#';fw[0].fow[1]='\0';for(b8=0;b8n;b8++){if(shizi[b8].left==shizi[0].left)fw[b8].fow[0]='#';fw[b8].fow[1]='\0';}inte1;for(e1=0;e12;e1++)for(b2=0;b2n;b2++)for(b3=0;b3n;b3++){if(shizi[b2].right[b3]='A'&&shizi[b2].right[b3]='Z')if(shizi[b2].right[b3+1]='a'&&shizi[b2].right[b3+1]='z'){linshi5[0]=shizi[b2].right[b3+1];linshi5[1]='\0';for(b9=0;b9n;b9++){if(shizi[b2].right[b3]==shizi[b9].left)strcat(fw[b9].fow,linshi5);}}if(shizi[b2].right[b3+1]='A'&&shizi[b2].right[b3+1]='Z'){for(b4=0;b4n;b4++){if(shizi[b2].right[b3+1]==shizi[b4].left){if(kongshi[b4].kongzuo!=1){for(b10=0;b10n;b10++){if(shizi[b2].right[b3]==shizi[b10].left)strcat(fw[b10].fow,fji[b4].fjihe);}}else{for(b5=0;b5n;b5++)if(shizi[b2].right[b3]==shizi[b5].left)strcat(fw[b5].fow,fw[b2].fow);}}}}if((b3+1)==strlen(shizi[b2].right)){for(b7=0;b7n;b7++)if(shizi[b2].right[b3]==shizi[b7].left)strcat(fw[b7].fow,fw[b2].fow);}}first2fji2[100];inta11,a12,a13;for(a11=0;a11n;a11++){fji2[a11].fjihe2[0]='\0';}for(a12=0;a12=n;a12++)for(a13=0;a13n;a13++){if(a12!=a13&&shizi[a12].left==shizi[a13].left)strcat(fji[a12].fjihe,fji[a13].fjihe);}charlinshi3[100];charlinshi4[2];inta15,a16,a17=0,a19=0,a21,a18;//for(a15=0;a15n;a15++){{for(a21=0;a2199;a21++)linshi3[a21]='\0';}{for(a16=0;a16strlen(fji[a15].fjihe);a16++){if(a16==0){linshi4[0]=fji[a15].fjihe[a16];linshi4[1]='\0';strcat(linshi3,linshi4);a16++;}for(a17=0;a17=strlen(linshi3);a17++)if(linshi3[a17]==fji[a15].fjihe[a16])break;//if(lin