编译原理LL(1)语法分析实验报告要点

学号20102798专业软件工程姓名薛建东实验日期2013.04.08教师签字成绩实验报告【实验名称】LL（1）语法分析【实验目的】通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练掌握开发应用程序的基本方法。【实验内容】根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分析程序。分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号以及LL（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可表示如下：1M: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退栈并将输入流指针向前移动一位，否则报错。接受：当格局为（#，空#）时报告分析成功。报错：出错后，停止分析。并给出相应的错误提示信息。【实验要求】1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。2、如果遇到错误的表达式，应输出错误提示信息。【流程图】1.总体思路分析及流程图给定一个正规文法G，在LL(1)预测分析中，必须先求出First集和Follow集，然后求出Select集，通过Select集判断是否是LL1文法，如果是的话，构造预测分析表。求出预测分析表之后，再输入一个字符串，依据LL1分析表单步输出字符串的分析过程。2读取正规文法求文法的First集求文法的Follow集求文法的Select集字符串分析键盘输入字符串功能模块分解图（1）主程序流程图3开始输入文法构造预测分析表提示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不再增大为止。4开始读取一个非终结符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不再增大为止。5开始取得一个非终结符V查找产生式的右部含有V的产生式V是不是最后一个字符V后一个字符V*是否为终结符添加#到V的Follow集中添加V*到V的Follow中是否遍历完所有右部含有V的产生式是否有未求解过的非终结符将V*的First集加入到V的Follow集中完成YYYNYNYN3.预测分析控制程序的算法流程6‘#’’E’进栈，当前终结符号送入a显示分析步骤A∈Vt?A=‘#’？产生式不存在？若产生式为A→A1A2…An,按逆序即[An…A2A1]入栈产生式右部为空？出错A=‘a’？读入下一符号出错NYYNNYYYN输入要分析的字符串判断字符串是否正确YN显示栈中内容显示剩余输入串显示产生式NY匹配字符串？接受NY【源代码】#includestdio.h#includestdlib.h#includestring.h7#includedos.hcharA[20];/*分析栈*/charB[20];/*剩余串*/charv1[20]={'i','+','*','(',')','#'};/*终结符*/charv2[20]={'E','G','T','S','F'};/*非终结符*/intj=0,b=0,top=0,l;/*L为输入串长度*/typedefstructtype/*产生式类型定义*/{charorigin;/*大写字符*/chararray[5];/*产生式右边字符*/intlength;/*字符个数*/}type;typee,t,g,g1,s,s1,f,f1;/*结构体变量*/typeC[10][10];/*预测分析表*/voidprint()/*输出分析栈*/{inta;/*指针*/for(a=0;a=top+1;a++)printf(%c,A[a]);printf(\t\t);}/*print*/voidprint1()/*输出剩余串*/{intj;for(j=0;jb;j++)/*输出对齐符*/printf();for(j=b;j=l;j++)printf(%c,B[j]);printf(\t\t\t);}/*print1*/voidmain(){intm,n,k=0,flag=0,finish=0;charch,x;typecha;/*用来接受C[m][n]*//*把文法产生式赋值结构体*/e.origin='E';strcpy(e.array,TG);8e.length=2;t.origin='T';strcpy(t.array,FS);t.length=2;g.origin='G';strcpy(g.array,+TG);g.length=3;g1.origin='G';g1.array[0]='^';g1.length=1;s.origin='S';strcpy(s.array,*FS);s.length=3;s1.origin='S';s1.array[0]='^';s1.length=1;f.origin='F';strcpy(f.array,(E));f.length=3;f1.origin='F';f1.array[0]='i';f1.length=1;for(m=0;m=4;m++)/*初始化分析表*/for(n=0;n=5;n++)C[m][n].origin='N';/*全部赋为空*//*填充分析表*/C[0][0]=e;C[0][3]=e;C[1][1]=g;C[1][4]=g1;C[1][5]=g1;C[2][0]=t;C[2][3]=t;C[3][1]=s1;C[3][2]=s;C[3][4]=C[3][5]=s1;C[4][0]=f1;C[4][3]=f;printf(提示:本程序只能对由'i','+','*','(',')'构成的以'#'结束的字符串进行分析,\n);printf(请输入要分析的字符串:);do/*读入分析串*/{scanf(%c,&ch);if((ch!='i')&&(ch!='+')&&(ch!='*')&&(ch!='(')&&(ch!=')')&&(ch!='#')){printf(输入串中有非法字符\n);exit(1);}B[j]=ch;9j++;}while(ch!='#');l=j;/*分析串长度*/ch=B[0];/*当前分析字符*/A[top]='#';A[++top]='E';/*'#','E'进栈*/printf(步骤\t\t分析栈\t\t剩余字符\t\t所用产生式\n);do{x=A[top--];/*x为当前栈顶字符*/printf(%d,k++);printf(\t\t);for(j=0;j=5;j++)/*判断是否为终结符*/if(x==v1[j]){flag=1;break;}if(flag==1)/*如果是终结符*/{if(x=='#'){finish=1;/*结束标记*/printf(acc!\n);/*接受*/getchar();getchar();exit(1);}/*if*/if(x==ch){print();print1();printf(%c匹配\n,ch);ch=B[++b];/*下一个输入字符*/flag=0;/*恢复标记*/}/*if*/else/*出错处理*/{print();print1();printf(%c出错\n,ch);/*输出出错终结符*/exit(1);}/*else*/}/*if*/else/*非终结符处理*/10{for(j=0;j=4;j++)if(x==v2[j]){m=j;/*行号*/break;}for(j=0;j=5;j++)if(ch==v1[j]){n=j;/*列号*/break;}cha=C[m][n];if(cha.origin!='N')/*判断是否为空*/{print();print1();printf(%c-,cha.origin);/*输出产生式*/for(j=0;jcha.length;j++)printf(%c,cha.array[j]);printf(\n);for(j=(cha.length-1);j=0;j--)/*产生式逆序入栈*/A[++top]=cha.array[j];if(A[top]=='^')/*为空则不进栈*/top--;}/*if*/else/*出错处理*/{print();print1();printf(%c出错\n,x);/*输出出错非终