《编译原理》实验指导书2016new

武汉科技大学计算机科学与技术学院编译原理实验指导书实验一词法分析器设计【实验目的】1．熟悉词法分析的基本原理，词法分析的过程以及词法分析中要注意的问题。2．复习高级语言，进一步加强用高级语言来解决实际问题的能力。3．通过完成词法分析程序，了解词法分析的过程。【实验内容】用C语言编写一个PL/0词法分析器，为语法语义分析提供单词，使之能把输入的字符串形式的源程序分割成一个个单词符号传递给语法语义分析，并把分析结果（基本字，运算符，标识符，常数以及界符）输出。【实验要求】1．要求绘出词法分析过程的流程图。2．根据词法分析的目的以及内容，确定完成分析过程所需模块。3．写出每个模块的源代码，并给出注释。4．整理程序清单及所得结果。【参考说明】PL/0的词法分析程序GETSYM是一个独立的过程，其功能是为语法语义分析提供单词，把输入的字符串形式的源程序分割成一个个单词符号传递给语法语义分析。其主要任务为：1、滤空格；2、识别基本字；3、识别标识符；4、拼数；5、拼复合词；6、输出源程序。PL/0编译程序一般设置3个全程变量：SYM：存放每个单词的类别，用内部编码形式表示；ID：存放用户所定义的标识别符的值；NUM：存放用户定义的数。单词的种类分成5种：基本字（亦称保留字）、运算符、标识符、常数、界符。例：consta=10;const基本字a标识符=运算符10常数运行成功以后，检查程序，并将运行结果截图打印粘贴到实验报告上。实验二LL（1）语法分析程序设计【实验目的】1．熟悉判断LL（1）文法的方法及对某一输入串的分析过程。2．学会构造表达式文法的预测分析表。【实验内容】编写一个语法分析程序，对于给定的输入串，能够判断识别该串是否为给定文法的句型。【实验要求】1．输入一个LL（1）文法，构造相应的LL（1）预测分析表。2．从键盘读入输入串，由算法判断该输入串是否为该文法的句子，若正确，就通过，若错误就报错。【参考说明】语法分析主要是将从词法分析那里得来的记号构成一棵语法树。例：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'