LL1语法分析c++实现,first集,follow集,分析表,分析栈

...//LL（1）文法（源代码）#include"stdio.h"#include"stdlib.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;structcollectNode*next;};structcollectNode*first[MaxVnNum+1];/*first集*/structcollectNode*follow[MaxVnNum+1];/*follow集*/intanalyseTable[MaxVnNum+1][MaxVtNum+1+1];intanalyseStack[MaxStackDepth+1];/*分析栈*/inttopAnalyse;/*分析栈顶*/voidInit();/*初始化*/intIndexCh(charch);voidInputVt();/*输入终结符*/voidInputVn();/*输入非终结符*/voidShowChArray(char*collect,intnum);/*输出Vn或Vt的*/voidInputP();/*产生式输入*/boolCheckP(char*st);/*判断产生式正确性*/voidFirst(intU);voidAddFirst(intU,intnCh);/*加入first集*/boolHaveEmpty(intnVn);voidFollow(intV);/*计算follow集*/voidAddFollow(intV,intnCh,intkind);voidShowCollect(structcollectNode**collect);/*输出first或follow集*/voidFirstFollow();/*计算first和follow*/voidCreateAT();/*构造预测分析表*/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&&irCursor=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(100>IndexCh(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;ipt->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(nCh<100){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(nVn<100)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;irCursor!=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(nCh<100)/*为终结符时*/{pt=follow[V-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==follow[V-100]){follow[V-100]=pt;}else{qt->next=pt;/*qt指向follow集的最后一个元素*/}pt=pt->next;}}else{if(0==kind){pt=follow[nCh-100];while(NULL!=pt){ch=pt->nVt;AddFollow(V,ch,0);pt=pt->next;}}else{pt=first[nCh-100];while(NULL!=pt){ch=pt->nVt;if(-1!=ch){AddFollow(V,ch,1);}pt=pt->next;}}}}/*输出first或follow集*/voidShowCollect(structcollectNode**collect){inti;structcollectNode*pt;i=0;while(NULL!=collect[i]){pt=collect[i];printf("\n%c:\t",Vn[i]);while(NULL!=pt){if(-1!=pt->nVt){printf("%c",Vt[pt->nVt]);}elseprintf("#");pt=pt->next;}i++;}printf("\n");}/*计算first和follow*/voidFirstFollow(){inti;i=0;while('\0'!=Vn[i]){if(NULL==first[i])First(100+i);i++;}i=0;while('\0'!=Vn[i]){if(NULL==follow[i])Follow(100+i);i++;}}/*构造预测分析表*/voidCreateAT(){inti;structpRNode*pt;structcollectNode*ct;for(i=0;irCursor)){ct=first[pt->rCursor-100];while(NULL!=ct){if(-1!=ct->nVt)analyseTable[P[i].lCursor-100][ct->nVt]=i;ct=ct->next;}pt=pt->next;}if(NULL==pt){ct=follow[P[i].lCursor-100];while(NULL!=ct){if(-1!=ct->nVt)analyseTable[P[i].lCursor-100][ct->nVt]=i;elseanalyseTable[P[i].lCursor-100][vtNum]=i;ct=ct->next;}}else{if(100<=pt->rCursor)/*不含空的非终结符*/{ct=first[pt->rCursor-100];while(NULL!=ct){analyseTable[P[i].lCursor-100][ct->nVt]=i;ct=ct->next;}}else/*终结符或者空*/{if(-1==pt->rCursor){ct=follow[P[i].lCursor-100];while(NULL!=ct){if(-1!=ct->nVt)analyseTable[P[i].lCursor-100][ct->nVt]=i;else/*当含有#号时*/analyseTable[P[i].lCursor-100][vtNum]=i;ct=ct->next;}}else/*为终结符*/{analyseTable[P[i].lCursor-100][pt->rCursor]=i;}}}}}/*输出分析表*/voidShowAT(){inti,j;printf("构造预测分析表如下：\n");printf("\t|\t");for(i=0;ianalyseStack[topAnalyse]){if(analyseStack[topAnalyse]==IndexCh(st[current])){Pop();current++;step++;printf("%d\t",step);ShowStack();printf("\t\t%c\t\t出栈、后移\n",st[current]);}else{printf("%c-%c不匹配！",analyseStack[topAnalyse],st[current]);printf("此串不是此文法的句子！\n");return;}}else/*当为非终结符时*/{r=analyseTable[analyseStack[topAnalyse]-100][IndexCh(st[current])];if(-1!=r){Push(r);step++;printf("%d\t",step);ShowStack();printf("\t\t%c\t\t%d\n",st[current],r);}else{printf("此串不是此文法的句子！\n");return;}}}if('#'==st[current]){if(0==topAnalyse&&'#'==st[current]){step++;printf("%d\t",step);ShowStack();printf("\t\t%c\t\t分析成功！\n",st[current]);printf("%s是给定文法的句子！\n",st);}else{while(topAnalyse>0){if(100>analyseStack[topAnalyse]){printf("此串不是此文法的句子！\n");return;}else{r=analyseTable[analyseStack[topAnalyse]-100][vtNum];if(-1!=r){Push(r);/*产生式右部代替左部，指示器不移动*/step++;printf("%d\t",step);ShowStack();if(0==topAnalyse&&'#'==st[current]){printf("\t\t%c\t\t分析成功！\n",st[current]);printf("%s是给定文法的句子！\n",st);}elseprintf("\t\t%c\t\t%d\n",st[current],r);}else{printf("此串不是此文法的句子！\n");return;}}}}}}/*初始化栈及符号串*/voidInitStack(){inti;/*分析栈的初始化*/for(i=0;irCursor)return;topAnalyse+=P[r].rLength;for(i=0;irCursor;/*逆序入栈*/pt=pt->next;}}如有侵权请联系告知删除，感谢你们的配合！精品精品精品