LL(1)语法分析程序设计

实验二LL（1）语法分析程序设计【实验目的】1．熟悉判断LL（1）文法的方法及对某一输入串的分析过程。2．学会构造表达式文法的预测分析表。【实验内容】编写一个语法分析程序，对于给定的输入串，能够判断识别该串是否为给定文法的句型。【实验步骤和要求】1．从键盘读入输入串，并判断正误；2．若无误，由程序自动构造FIRST、FOLLOW集以及SELECT集合，判断是否为LL（1）文法；3．若符合LL（1）文法，由程序自动构造LL（1）分析表；4．由算法判断输入符号串是否为该文法的句型。（可参考教材96页的例题1）【说明】语法分析主要是将从词法分析那里得来的记号构成一棵语法树。例：SHMA#adbe#S-aHH-aMdH-dM-AbM-A-aMA-e分析例句：aaabd#/*-------------------LL(1)语法分析--------------------*/#includestdio.h#includestdlib.h#defineMaxRuleNum8#defineMaxVnNum5#defineMaxVtNum5#defineMaxStackDepth20#defineMaxPLength20#defineMaxStLength50structpRNode/*产生式右部结构*/{intrCursor;/*右部序号*/structpRNode*next;};structpNode/*产生式结点结构*/{intlCursor;/*左部符号序号*/intrLength;/*右部长度*//*注当rLength=1时，rCursor=-1为空产生式*/structpRNode*rHead;/*右部结点头指针*/};charVn[MaxVnNum+1];/*非终结符集*/intvnNum;charVt[MaxVtNum+1];/*终结符集*/intvtNum;structpNodeP[MaxRuleNum];/*产生式*/intPNum;/*产生式实际个数*/charbuffer[MaxPLength+1];charch;/*符号或stringch;*/charst[MaxStLength];/*要分析的符号串*/structcollectNode/*集合元素结点结构*/{intnVt;/*在终结符集中的下标*/structcollectNode*next;};structcollectNode*first[MaxVnNum+1];/*first集*/structcollectNode*follow[MaxVnNum+1];/*follow集*/intanalyseTable[MaxVnNum+1][MaxVtNum+1+1];/*预测分析表存放为产生式的编号，+1用于存放结束符，多+1用于存放#(-1)*/intanalyseStack[MaxStackDepth+1];/*分析栈*/inttopAnalyse;/*分析栈顶*//*intreverseStack[MaxStackDepth+1];/*颠倒顺序栈*//*inttopReverse;/*倒叙栈顶*/voidInit();/*初始化*/intIndexCh(charch);/*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-1表示未找到*/voidInputVt();/*输入终结符*/voidInputVn();/*输入非终结符*/voidShowChArray(char*collect,intnum);/*输出Vn或Vt的内容*/voidInputP();/*产生式输入*/boolCheckP(char*st);/*判断产生式正确性*/voidFirst(intU);/*计算first集,U-xx...*/voidAddFirst(intU,intnCh);/*加入first集*/boolHaveEmpty(intnVn);/*判断first集中是否有空(-1)*/voidFollow(intV);/*计算follow集*/voidAddFollow(intV,intnCh,intkind);/*加入follow集，kind=0表加入follow集，kind=1加入first集*/voidShowCollect(structcollectNode**collect);/*输出first或follow集*/voidFirstFollow();/*计算first和follow*/voidCreateAT();/*构造预测分析表*/voidShowAT();/*输出分析表*/voidIdentify(char*st);/*主控程序,为操作方便*//*分析过程显示操作为本行变换所用，与教程的显示方式不同*/voidInitStack();/*初始化栈及符号串*/voidShowStack();/*显示符号栈中内容*/voidPop();/*栈顶出栈*/voidPush(intr);/*使用产生式入栈操作*/#includeLL1.hvoidmain(void){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){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++){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;}}/*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-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);}/*输入非终结符*/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;/*k用于记录n以便改Vn[n]='\0'*/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){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;/*k用于记录n以便改Vt[n]='\0'*/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';/*printf(%s,buffer);*/if(CheckP(buffer)){/*填写入产生式结构体*/pRNode*pt,*qt;P[i].lCursor=IndexCh(buffer[0]);pt