实验二-LL(1)预测分析

《编译原理》实验指导14非师第1页共24页实验二LL(1)分析的设计与实现开课实验室：A201，A207实验项目LL(1)分析的设计与实现实验类型设计实验学时4一、实验目的根据某一文法编制调试LL(1)分析程序，以便对任意输入的符号串进行分析。掌握LL(1)分析法的基本原理，LL(1)分析表的构造方法，LL(1)驱动程序的构造方法。二、设备与环境1.硬件设备：PC机一台2.软件环境：安装Windows操作系统或者Linux操作系统，并安装相关的程序开发环境，如C\C++\Java等编程语言环境。三、实验要求1.输入文法G的非终结符、终结符和产生式；（1）输出非终结符的FIRST集；（2）输出非终结符的FOLLOW集；（3）构造文法G的预测分析表；（4）对输入符号串进行分析。2、编程语言不限。四、实验原理1.程序功能（流程图参考）：开始计算FIRST集合计算FOLLOW集合输入文法构造预测分析表调用预测器进行分析结束《编译原理》实验指导13非师第2页2.计算FIRST集合：First集合最终是对产生式右部的字符串而言的，但其关键是求出非终结符的First集合，由于终结符的First集合就是它自己，所以求出非终结符的First集合后，就可很直观地得到每个字符串的First集合。直接收取：对形如U－a…的产生式（其中a是终结符），把a收入到First(U)中反复传送：对形入U－P…的产生式（其中P是非终结符），应把First(P)中的全部内容传送到First(U)中。算法描述：见教材P80①)若X∈Vt,则FIRST(X)={X};②)若X∈Vn,且有产生式X-a……,a∈Vt，则a∈FIRST(X);③)若X∈Vn,X-,则∈FIRST(X)④)若X,Y1,Y2,Y3,Y4…………Yn都∈Vn,而产生式X-Y1,Y2……Yn.当Y1,Y2,Y3,Y4…………Yn都能=，那么FIRST(X)=并集的FIRST(Yi)-{}(0=i=n)⑤)若Yi=(i=1,2,3……)，则FIRST(X)=并集的FIRST(Yi)-{}并上{}3.计算FOLLOW集合：Follow集合是针对非终结符而言的，Follow(U)所表达的是句型中非终结符U所有可能的后随终结符号的集合，特别地，“#”是识别符号的后随符。直接收取：注意产生式右部的每一个形如“…Ua…”的组合，把a直接收入到Follow(U)中；直接收取：对形如“…UP…”(P是非终结符)的组合，把First(P)直接收入到Follow(U)中；直接收取：若为文法开始符号S，则把#收入FOLLOW(S)；反复传送：对形如U－…P的产生式（其中P是非终结符），应把Follow(U)中的全部内容传送到Follow(P)中。算法描述：见教材P82①)若为文法开始符号S，则FOLLOW(S)={#}②)若为文法A-aBb是一个产生式，则把FIRST（b）的非空元素加入FOLLOW(B)中。如果b-@则把FOLLOW(A)也加入FOLLOW(B)中。4.构造预测分析表：(1)对于文法的每条产生式A，若aFIRST()，则M[A,a]=A；(2)若FIRST()，bFOLLOW()则M[A,b]=A；(3)分析表M的其他元素均为出错标志error。5.预测分析程序流图：见课本P93-P94五、程序源码#includestdio.h#includestdlib.h《编译原理》实验指导13非师第3页#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;/*分析栈顶*/《编译原理》实验指导13非师第4页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);voidmain(void){chartodo,ch;Init();InputVn();InputVt();InputP();getchar();FirstFollow();printf(所得first集为：);ShowCollect(first);printf(所得follow集为：);ShowCollect(follow);CreateAT();ShowAT();todo='y';while('y'==todo){《编译原理》实验指导13非师第5页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){if(''!=ch&&'\n'!=ch){st[i++]=ch;}ch=getchar();}if('#'==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++)《编译原理》实验指导13非师第6页{P[i].lCursor=NULL;P[i].rHead=NULL;P[i].rLength=0;}PNum=0;for(i=0;i=MaxPLength;i++)buffer[i]='\0';for(i=0;iMaxVnNum;i++){first[i]=NULL;follow[i]=NULL;}for(i=0;i=MaxVnNum;i++){for(j=0;j=MaxVnNum+1;j++)analyseTable[i][j]=-1;}}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);}/*输入非终结符*/《编译原理》实验指导13非师第7页voidInputVn(){intinErr=1;intn,k;charch;while(inErr){printf(\n请输入所有的非终结符，注意：);printf(请将开始符放在第一位，并以#号结束:\n);ch='';n=0;/*初始化数组*/while(nMaxVnNum){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;}}/*正确性确认，正确则，执行下下面，否则重新输入*/Vn[k]='\0';ShowChArray(Vn);ch='';while('y'!=ch&&'n'!=ch){if('\n'!=ch)《编译原理》实验指导13非师第8页{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)《编译原理》实验指导13非师第9页{if('#'!=(ch=getchar())){while('#'!=(ch=getchar()));printf(\n符号数目超过限制！\n);inErr=1;continue;}}Vt[k]='\0';ShowChArray(Vt);ch='';wh