预测分析算法的设计与实现

预测分析算法的设计与实现程序代码:#includestdio.h#includestdlib.h#defineMaxRuleNum8#defineMaxVnNum5#defineMaxVtNum5#defineMaxStackDepth20#defineMaxPLength20#defineMaxStLength50structpRNode/*产生式右部结构*/{intrCursor;structpRNode*next;};structpNode{intlCursor;intrLength;/*右部长度*/structpRNode*rHead;/*右部结点头指针*/};charVn[MaxVnNum+1];/*非终结符集*/intvnNum;charVt[MaxVtNum+1];/*终结符集*/intvtNum;structpNodeP[MaxRuleNum];intPNum;charbuffer[MaxPLength+1];charch;charst[MaxStLength];/*要分析的符号串*/structcollectNode{intnVt;voidShowAT();/*输出分析表*/voidIdentify(char*st);voidInitStack();voidShowStack();voidPop();voidPush(intr);intmain(){chartodo,ch;Init();InputVn();InputVt();InputP();getchar();FirstFollow();printf(所得first集为：);ShowCollect(first);printf(所得follow集为：);ShowCollect(follow);CreateAT();ShowAT();todo='y';while('y'==todo){printf(\n是否继续进行句型分析？(y/n):);todo=getchar();while('y'!=todo&&'n'!=todo){printf(\n(y/n)?);todo=getchar();}if('y'==todo){inti;InitStack();printf(请输入符号串(以#结束):);ch=getchar();i=0;while('#'!=ch&&iMaxStLength){st[i]=ch;Identify(st);}elseprintf(输入出错！\n);}}getchar();}voidInit(){inti,j;vnNum=0;vtNum=0;PNum=0;for(i=0;i=MaxVnNum;i++)Vn[i]='\0';for(i=0;i=MaxVtNum;i++)Vt[i]='\0';for(i=0;iMaxRuleNum;i++){P[i].lCursor=NULL;P[i].rHead=NULL;P[i].rLength=0;}PNum=0;for(i=0;i=MaxPLength;i++)}}intIndexCh(charch){intn;n=0;/*isVn?*/while(ch!=Vn[n]&&'\0'!=Vn[n])n++;if('\0'!=Vn[n])return100+n;n=0;/*isVt?*/while(ch!=Vt[n]&&'\0'!=Vt[n])n++;if('\0'!=Vt[n])returnn;return-1;}/*输出Vn或Vt的内容*/voidShowChArray(char*collect){intk=0;while('\0'!=collect[k]){printf(%c,collect[k++]);}printf(\n);}/*输入非终结符*/voidInputVn(){{Vn[n++]='\0';}n=0;while(('#'!=ch)&&(nMaxVnNum)){if(''!=ch&&'\n'!=ch&&-1==IndexCh(ch)){Vn[n++]=ch;vnNum++;}ch=getchar();}Vn[n]='#';/*以#标志结束用于判断长度是否合法*/k=n;if('#'!=ch){if('#'!=(ch=getchar())){while('#'!=(ch=getchar()));printf(\n符号数目超过限制！\n);inErr=1;continue;}{printf(输入正确确认?(y/n):);}scanf(%c,&ch);}if('n'==ch){printf(录入错误重新输入！\n);inErr=1;}else{inErr=0;}}}/*输入终结符*/voidInputVt(){intinErr=1;intn,k;charch;while(inErr){printf(\n请输入所有的终结符，注意：);printf(以#号结束:\n);ch='';n=0;/*初始化数组*/while(nMaxVtNum){Vt[n++]='\0';}n=0;while(('#'!=ch)&&(nMaxVtNum)){if(''!=ch&&'\n'!=ch&&-1==IndexCh(ch)){Vt[n++]=ch;vtNum++;}ch=getchar();}Vt[n]='#';k=n;if('#'!=ch){if('#'!=(ch=getchar())){while('#'!=(ch=getchar()));printf(\n符号数目超过限制！\n);inErr=1;continue;}}Vt[k]='\0';ShowChArray(Vt);ch='';while('y'!=ch&&'n'!=ch){if('\n'!=ch){printf(输入正确确认?(y/n):);}scanf(%c,&ch);}if('n'==ch){printf(录入错误重新输入！\n);inErr=1;}else{inErr=0;}}}/*产生式输入*/voidInputP(){charch;inti=0,n,num;printf(请输入文法产生式的个数：);scanf(%d,&num);PNum=num;getchar();/*消除回车符*/printf(\n请输入文法的%d个产生式,并以回车分隔每个产生式：,num);printf(\n);while(inum){printf(第%d个：,i);/*初始化*/for(n=0;nMaxPLength;n++)buffer[n]='\0';/*输入产生式串*/ch='';n=0;while('\n'!=(ch=getchar())&&nMaxPLength){if(''!=ch)buffer[n++]=ch;}buffer[n]='\0';if(CheckP(buffer)){pRNode*pt,*qt;P[i].lCursor=IndexCh(buffer[0]);pt=(pRNode*)malloc(sizeof(pRNode));pt-rCursor=IndexCh(buffer[3]);pt-next=NULL;P[i].rHead=pt;n=4;while('\0'!=buffer[n]){qt=(pRNode*)malloc(sizeof(pRNode));qt-rCursor=IndexCh(buffer[n]);qt-next=NULL;pt-next=qt;pt=qt;n++;}P[i].rLength=n-3;i++;}elseprintf(输入符号含非法在成分，请重新输入！\n);}}/*判断产生式正确性*/boolCheckP(char*st){intn;if(100IndexCh(st[0]))returnfalse;if('-'!=st[1])returnfalse;if(''!=st[2])returnfalse;for(n=3;'\0'!=st[n];n++){if(-1==IndexCh(st[n]))returnfalse;}returntrue;}voidFirst(intU){inti,j;for(i=0;iPNum;i++){if(P[i].lCursor==U){structpRNode*pt;pt=P[i].rHead;j=0;while(jP[i].rLength){if(100pt-rCursor){AddFirst(U,pt-rCursor);break;}else{if(NULL==first[pt-rCursor-100]){First(pt-rCursor);}AddFirst(U,pt-rCursor);if(!HaveEmpty(pt-rCursor)){break;}else{pt=pt-next;}}j++;}if(j=P[i].rLength)/*当产生式右部都能推出空时*/AddFirst(U,-1);}}}/*加入first集*/voidAddFirst(intU,intnCh){structcollectNode*pt,*qt;intch;/*用于处理Vn*/pt=NULL;qt=NULL;if(nCh100){pt=first[U-100];while(NULL!=pt){if(pt-nVt==nCh)break;else{qt=pt;pt=pt-next;}}if(NULL==pt){pt=(structcollectNode*)malloc(sizeof(structcollectNode));pt-nVt=nCh;pt-next=NULL;if(NULL==first[U-100]){first[U-100]=pt;}else{qt-next=pt;/*qt指向first集的最后一个元素*/}pt=pt-next;}}else{pt=first[nCh-100];while(NULL!=pt){ch=pt-nVt;if(-1!=ch){AddFirst(U,ch);}pt=pt-next;}}}boolHaveEmpty(intnVn){if(nVn100)returnfalse;structcollectNode*pt;pt=first[nVn-100];while(NULL!=pt){if(-1==pt-nVt)returntrue;pt=pt-next;}returnfalse;}voidFollow(intV){inti;structpRNode*pt;if(100==V)/*当为初始符时*/AddFollow(V,-1,0);for(i=0;iPNum;i++){pt=P[i].rHead;while(NULL!=pt&&pt-rCursor!=V)pt=pt-next;if(NULL!=pt){pt=pt-next;if(NULL==pt){if(NULL==follow[P[i].lCursor-100]&&P[i].lCursor!=V){Follow(P[i].lCursor);}AddFollow(V,P[i].lCursor,0);}else{while(NULL!=pt&&HaveEmpty(pt-rCursor)){AddFollow(V,pt-rCursor,1);pt=pt-next;}if(NULL==pt){if(NULL==follow[P[i].lCursor-100]&&P[i].lCursor!=V){Follow(P[i].lCursor);}AddFollow(V,P[i].lCursor,0);}else{AddFollow(V,pt-rCursor,1);}}}}}voidAddFollow(intV,intnCh,intkind){structcollectNode*pt,*qt;intch;pt=NULL;qt=NULL;if(nCh100)/*为终结符时*/{pt=follow[V-100];while(NU