编译原理-LL(1)文法源代码(实验三)

一、实验目的及要求1．掌握LL(1)分析法的基本原理；2．掌握LL(1)分析表的构造方法；3．用LL（1）分析法分析高级语言表达式。4、了解LL（1）分析器的工作过程。文法：无二义性的算术表达式的文法（1）把词法分析作为语法分析的子程序实现（5分）（2）独立的语法分析程序（4分）（3）对表达式文法消除左递归、构造LL（1）分析表（4）LL（1）分析表可以直接输入（4分），也可以用程序实现（5分）（5）给一个表达式，给出分析过程（分析栈、输入串、所用规则）（4分）（6）生成一个棵语法树（5分）用二叉树的形式表示出来二、实验内容及原理1、实验原理（1）、LL（1）文法的定义LL(1)分析法属于确定的自顶向下分析方法。LL(1)的含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第2个L表明分析过程中将使用最左推导，1表明只需向右看一个符号便可决定如何推导，即选择哪个产生式(规则)进行推导。LL(1)文法的判别需要依次计算FIRST集、FOLLOW集和SELLECT集,然后判断是否为LL(1)文法,最后再进行句子分析。需要预测分析器对所给句型进行识别。即在LL(1)分析法中，每当在符号栈的栈顶出现非终极符时，要预测用哪个产生式的右部去替换该非终极符；当出现终结符时，判断其与剩余输入串的第一个字符是否匹配，如果匹配，则继续分析，否则报错。LL(1)分析方法要求文法满足如下条件：对于任一非终极符A的两个不同产生式A,A，都要满足下面条件：SELECT(A)∩SELECT(A)=（2）、预测分析表构造LL(1)分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式进行推导。它的行对应文法的非终极符，列对应终极符，表中的值有两种：一是产生式的右部的字符串，一是null。若用M表示LL(1)分析表，则M可表示如下：M:VN×VTP∪{Error}M(A,t)=Aα，当tselect(Aα)，否则M(A,t)=Error其中P表示所有产生式的集合。（3）、语法分析程序构造LL(1)分析中X为符号栈栈顶元素，a为输入流当前字符，E为给定测试数据的开始符号，#为句子括号即输入串的括号。分析表用一个二位数组M表示，数组元素M[A，a]中的下标A表示非终结符，a为终结符或句子括号‘#’，二维数组中存放的是一条关于A的产生式，表明当非终结符A向下推导时，面临输入符a时，所采用的候选产生式，当元素内容无产生式时，则表明用A的左部向下推导时出现了不该出现的符号，因此元素内容转向出错处理的信息。LL(1)分析过程主要包括以下四个动作：替换：当XVN时选相应产生式的右部去替换X。此时X出栈，逆序入栈。匹配：当XVT时它与a进行匹配，其结果可能成功，也可能失败，如果成功则符号栈中将X退栈并将输入流指针向前移动一位，否则报错。接受：当格局为（#，空#）时报告分析成功。报错：出错后，停止分析。并给出相应的错误提示信息。2、实验内容根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析LL（1）分析法的理解。对下列文法，用LL（1）分析法对任意输入的符号串进行分析：（1）E-TG（2）G-+TG（3）G-ε（4）T-FS（5）S-*FS（6）S-ε（7）F-(E)（8）F-i程序输入一以#结束的符号串(包括+*（）i#)，如：i+i*i#。三、实验过程及步骤1.总体思路分析及流程图给定一个正规文法G，在LL(1)预测分析中，必须先求出First集和Follow集，构造预测分析表。求出预测分析表之后，再输入一个字符串，依据LL1分析表单步输出字符串的分析过程。读取正规文法求文法的First集求文法的Follow集求文法的Select集字符串分析键盘输入字符串功能模块分解图（1）主程序流程图开始输入文法构造预测分析表提示i*i+i#为可接受的字符串判断文法是否为LL(1)文法输入要分析的符号串Y出错处理N判断该符号串是否可被该文法识别出错处理结束YN（2）核心算法流程图1.计算非终结符的First集的算法及流程：First集合的构造算法：（1）若X∈VT，则First（X）={X}。（2）若X∈VN，且有产生式X→a……，则把a加入到First(X)中；若X→ε也是一条产生式，则把ε也加到First(X)中。（3）若X→Y……是一个产生式且Y∈VN，则把First(Y)中的所有非ε-元素都加到First(X)中；若X→Y1Y2…Yk是一个产生式，Y1，…，Yi-1都是非终结符，而且，对于任何j，1≤j≤i-1，First(Yj)都含有ε（即Y1…Yi-1*ε），则把First(Yj)中的所有非ε-元素都加到First(X)中；特别是，若所有的First(Yj)均含有ε，j=1,2,…，k，则把ε加到First(X)中。连续使用上面的规则，直至每个集合First不再增大为止。开始读取一个非终结符V遍历所有产生式，查找左部是V的产生式取出得到的一条产生式产生式右部第一个符号V*是终结符？V*是不是有推导规则V*-空将该终结符V*加入V的First集中空标志为真剩有非终结符？删除空，得到V的First集结束添加一个删除空的标志为true2.计算非终结符的Follow集：Follow集合的具体构造算法如下：（1）对于文法的开始符号S，置#于Follow(S)中；（2）若A→αBβ是一个产生式，则把First(β)|{ε}加至Follow(B)中；（3）若A→αB是一个产生式，或A→αBβ是一个产生式而βε（即ε∈First(β)），则把Follow(A)加至Follow(B)中。连续使用上面的规则，直至每个集合Follow不再增大为止。开始取得一个非终结符V查找产生式的右部含有V的产生式V是不是最后一个字符V后一个字符V*是否为终结符添加#到V的Follow集中添加V*到V的Follow中是否遍历完所有右部含有V的产生式是否有未求解过的非终结符将V*的First集加入到V的Follow集中完成YYYNYNYN3.预测分析控制程序的算法流程‘#’’E’进栈，当前终结符号送入a显示分析步骤A∈Vt?A=‘#’？产生式不存在？若产生式为A→A1A2…An,按逆序即[An…A2A1]入栈产生式右部为空？出错A=‘a’？读入下一符号出错NYYNNYYYN输入要分析的字符串判断字符串是否正确YN显示栈中内容显示剩余输入串显示产生式NY匹配字符串？接受NYLL（1）文法（源代码）#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;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);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){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;}}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'!=V