编译原理课程设计LL1文法

LL(1)文法分析及程序设计1.设计目的通过设计、编制、调试LL(1)语法分析程序，加深对LL(1)语法分析原理的理解。2.设计要求（1）写出符合LL(1)分析方法要求的文法，给出分析的算法思想、步骤、程序结构以及最终完成语法分析程序设计。（2）编制完成分析程序后，选取几个例子，上机测试并通过所设计的分析程序。3.设计方案用LL(1)分析法判别给定文法是否为LL(1)文法，提供其分析过程与结果，最终根据结果设计算法分析程序，对输入的符号串进行分析。4.设计内容4.1设计基本思想设计一个LL(1)文法分析器，构造出预测分析表，通过预测分析表，判别用户输入的字符串是否符合LL(1)文法。并给出分析过程与结果。4.2LL(1)文法的基本原理与算法一个上下无关的文法是LL(1)文法的充要条件时，对每个非终结符A的两个不同产生式，A-α,A-β满足SELECT（A-α）∩SELECT（A-β）=φ，其中α和β不同时推出ξ。如果某个文法满足上述条件，称该文法为LL(1)文法。LL(1)分析法是一种采用确定的自顶向下的语法分析技术，其含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第二个L表明分析过程中将用最左推导，1表明只需向右看一个符号便可以决定如何推导，即便选择哪个产生式规则进行推导。4.3LL(1)判别分析步骤4.3.1求出能推出ξ的非终结符(1)将数组X[]中对应的每一个非终结符的标记为“未定”。(2)扫描文法中的产生式。1.删除所有右部含有终结符的产生式。若使得以某一非终结符为左部的所有产生式都被删除，则将数组中对应的非终结符的标记值改为“否”，说明该终结符不能推出ξ。2.若某一非终结符的某一个产生式右部为ξ，则将数组中对应该非终结符的标志置为“是”，并从文法中删除该非终结符的所有产生式。（3）扫描产生式右部的每一个符号。1.若所扫描到的非终结符号在数组中对应的标志是“是”，则删去该非终结符，若使得产生式右部为空，则对产生式右部的非终结符在数组中对应的标志改为“是”，并删除该非终结符为左部的所有的产生式。2.若所扫描到的非终结符号在数组中对应的标志是“是”，则删除该产生式。若这使得产生式左部非终结符的有关产生式都被删除，则把在数组中该非终结符对应的标志改为“否”。（4）重复（3），直到扫描完一遍文法的产生式，数组中的非终结符对应的特征再没有改变为止。4.3.2求FIRST集合1）A-aα则a∈first（A）2）A-Bα则first（B）∈first（A）3）A-^则^∈first（A）4.3.3计算FOLLOW集合1）A-αBaβ则a∈follow（B）2）A-αBCβ则first（C）∈follow（B）3）A-αB则follow（A）∈follow（B）3）由产生式形成（1）（2）（3）A-αBDaβ，D-^，则a∈follow（B），a∈follow（D）4.3.4计算SELECT集4.4数据结构数组A实现分析栈，数组B存储剩余分析串；一维数组V1存放文法终结符，一维数组V2存放文法非终结符。将产生式类型定义为结构体变量。4.5算法描述1.首先将#压入堆栈中,将开始符号S也压入堆栈中，读取第一个输入符号到a。循环执行2～4:2.栈顶符号弹出放入X中,如果X为终结符号:当X==a!=#时,表明成功匹配a符号,然后读取下一个符号到a,否则出错；当X==a=#时,分析结束,接受句子,跳出循环.3.如果X!=a,进行出错处理.4.如果X为非终结符号,则查分析表M:如果M[X,a]为空,进行出错处理；如果M[X,a]=X1X2X3...Xn,则将右部Xn...X2X1反序压入堆栈中.4.6对给定文法进行LL(1)分析的过程给定文法：E-TGG-+TG|^T-FSS-*FS|^F-i|(E)对上述文法进行分析判断：4.6.1求各非终结符的FIRST集FIRST（E）=FIRST（T）=FIRST（F）={(,i}FIRST（G）={+,^}FIRST（T）={(,i}FIRST（S）={*,^}FIRST（F）={(,i}4.6.2求各非终结符的FOLLOW集FOLLOW（E）={),#}FOLLOW（G）=FOLLOW（E）={),#}FOLLOW（T）=FIRST（G）∪FOLLOW（E）={+,),#}FOLLOW（S）=FOLLOW（T）={+,),#}FOLLOW（F）=FIRST（S）∪FOLLOW（E）∪FOLLOW（T）={*,+,),#}4.6.3求各个产生式的SELECT集SELECT（E-TG）={(,i}SELECT（G-+TG）={+}SELECT（G-^）={#,)}SELECT（T-FS）={(,i}SELECT（S-*FS）={*}SELECT（S-^）={+,},#}SELECT（F-(E)）={(}SELECT（F-i）={i}4.6.4构造预测分析表由以上步骤可知，该文法是LL(1)文法。对其建立预测分析表。对于每个终结符或#，用a表示。若a∈SELECT（A-α）,则把A-α放入M[A,a]中。把所有无定义的M[A,a]标上出错标记。预测分析表如下：i+*()#E-TG-TGG-+TG-^-^T-FS-FSS-^-*FS-^-^F-i-(E)4.7程序函数流程图输出分析栈：输出剩余串：主函数：4.8程序测试结果4.8.1当输入的字符串错误时：4.8.2对输入字符串进行分析：1）输入i+i*i#得到分析结果如下2）如果不适合LL(1)文法，则显示输入错误。例如输入i++i*i#，分析结果如下：4.9源代码#includestdio.h#includestdlib.h#includestring.h#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);}voidprint1()/*输出剩余串*/{intj;for(j=0;jb;j++)/*输出对齐符*/printf();for(j=b;j=l;j++)printf(%c,B[j]);printf(\t\t\t);}voidmain(){intm,n,k=0,flag=0,finish=0;charch,x;typecha;/*用来接受C[m][n]*/e.origin='E';/*把文法产生式赋值结构体*/strcpy(e.array,TG);e.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=7;n++)C[m][n].origin='N';/*全部赋为空*/C[0][0]=e;C[0][3]=e;/*填充分析表*/C[1][1]=g;C[1][4]=g1;C[1][7]=g1;C[2][0]=t;C[2][3]=t;C[3][1]=s1;C[3][2]=s;C[3][4]=C[3][5]=C[3][7]=s1;C[4][0]=f1;C[4][3]=f;printf(请输入要分析的字符串:);do/*读入分析串*/{scanf(%c,&ch);if((ch!='i')&&(ch!='+')&&(ch!='*')&&(ch!='(')&&(ch!=')')&&(ch!='#')&&(ch!='-')&&(ch!='/')){printf(输入串中有非法字符\n);exit(1);}B[j]=ch;j++;}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=7;j++)/*判断是否为终结符*/if(x==v1[j]){flag=1;break;}if(flag==1)/*如果是终结符*/{if(x=='#'){finish=1;/*结束标记*/printf(接受!\n);getchar();getchar();exit(1);}if(x==ch){print();print1();printf(%c匹配\n,ch);ch=B[++b];/*下一个输入字符*/flag=0;/*恢复标记*/}else/*出错处理*/{print();print1();printf(%c出错\n,ch);/*输出出错终结符*/exit(1);}}else/*非终结符处理*/{for(j=0;j=4;j++)if(x==v2[j]){m=j;break;}for(j=0;j=7;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--;}else/*出错处理*/{print();print1();printf(%c出错\n,x);/*输出出错非终结符*/exit(1);}}}while(finish==0);}5.总结通过这次的课程设计，我比原来更加了解了LL(1)文法的分析过程及实现方法，学会设计、编制、调试语法及语义分析程序，加深了对语法及语义分析原理的理解。在课程设计前，我想过很多种实现LL(1)文法的办法，最完美的一种就是通过输入表达式，进行判定分析是否属于LL(1)文法，从而要进行First集、Follow集和SELECT集的计算分析，由于时间和水平的有限，最终只能选取最终一步，就是对输入符号串的分析，前提是必须事先人工分析完成LL(1)文法，我觉得这是一个不完美的地方。对这次课程设计给我的感觉是，进行文法分析的过程还是很有趣的，不过也觉得蛮深奥的，不容易弄明白的地方也有很多。有机会的话还是希望自己能在以后的学习中不断学习了解，争取有更好的进步。6.参考文献[1]杨德芳等.编译原