编译原理LL(1)分析器(C语言)

数学与软件科学学院实验报告学期：2015至2016第2学期2016年4月15日课程名称：编译原理专业：信息与计算科学2013级5班实验编号：3实验名称：LL(1)分析器指导教师：王开端学生姓名：李丹学号：2013060510实验成绩：实验三LL(1)分析器实验目的：根据书本知识和查阅相关资料，设计一个LL(1)语法分析器。实验内容：利用所设计的LL(1)语法分析器判断输入串i+i*i是否为文法G[E]的句子。文法G[E]如下：G[E]：iEFFTTFTTTEETEE|)(|'*''|'''实验步骤：1LL(1)分析法LL(1)分析法又称预测分析法，是一种不带回溯的非递归自顶向下分析法。LL(1)的含义是：第一个L表明自顶向下分析是从左至右扫描输入串的；第二个L表明分析过程中将用最左推导；“1”表明只需向右查看一个符号就可以决定如何推导（即可知用哪一个产生式进行推导）。LL(1)分析器结构如图1：图1LL(1)分析器使用LL(1)分析法将会涉及到LL(1)分析表，而分析表又会涉及到FIRST集和FOLLOW集。2FIRST集构造对文法中的每一个非终结符X构造FIRST(X)，其方法是连续使用以下规则，直到每个集合的FIRST不再增大为止。若有产生式...aX，且TVa，则把a加入到FIRST(X)中；若存在X，则将ε也加入到FIRST(X)中。若有...YX且NVY，则将FIRST(Y)中的所有非ε元素（记为“\{ε}”）都加入到FIRST(X)中；若有KYYYX...21，且iYY~1都是非终结符，而iYY~1的候选式都有ε存在，则把FIRST(jY)(j=1,2,...i)的所有非ε元素都加入到FIRST(X)中；特别是当kYY~1均含有ε产生式时，应把ε也加入到FIRST(X)中。文法G[E]的FIRST集如下：（1）FIRST(E’)={+,ε}；FIRST(T’)={*,ε}；FIRST(F)={(,i}；（2）由......TEFT和知)()()(EFIRSTTFIRSTFFIRST，即有FIRST(T)=FIRST(E)=FIRST(F)={(,i}；3FOLLOW集构造对文法G[S]的每一个非终结符A构造FOLLOW(A)，其方法是连续使用以下规则，直到每个集合的FOLLOW不再增大为止。对文法开始符号S，置#于FOLLOW(S)中（由语句括号“#S#”中的S#得到）。若有BA（可为空），则将FIRST()\{ε}加入到FOLLOW(B)中。若有BA或BA，且*（即)(FIRST），则把FOLLOW(A)加到FOLLOW(B)中（此处也可为空）。文法G[E]的FOLLOW集如下：（1）FOLLOW(E)={#}；（2）由'TEE知)(\)'(TFOLLOWEFIRST，即FOLLOW(T)={+}；由'FTT知)(\)'(FFOLLOWTFIRST，即FOLLOW(F)={*}；由)(EF知)())'('EFOLLOWFIRST,即FOLLOW(E)={),#}；（3）由'TEE知)'()(EFIRSTEFIRST，即FOLLOW(E’)={),#}；由'TEE且'E知)()(TFIRSTEFIRST，即FOLLOW(T)={+,),#}；由}#),,{)'(),'()('TFOLLOWTFOLLOWTFOLLOWFTT即知；由''TFTT且知)()(FFOLLOWTFOLLOW,即FOLLOW(F)={*,+,),#}。4LL(1)分析表知道了FIRST集和FOLLOW集，我们就可以构造出LL(1)分析表。文法G[E]的分析表如表1：表1文法G[E]的分析表i+*（）#E'TEE'TEEE’''TEE'E'ET'FTT'FTTT’'T'*'FTT'T'TFiF)(EF5输入串i+i*i分析根据分析表，结合栈，对输入串进行分析，分析过程如表2：表2输入串i+i*i分析过程表步骤符号栈(逆序)读入符号剩余符号串栈顶元素与读入字符使用规则1#Ei+i*i#(E,i)'TEE2#E’Ti+i*i#(T,i)'TEE3#E’T’Fi+i*i#(F,i)iF4#E’T’ii+i*i#匹配i5#E’T’+i*i#(T’,+)'T6#E’+i*i#(E’,+)''TEE7#E’T++i*i#匹配+8#E’Ti*i#(T,i)'FTT9#E’T’Fi*i#(F,i)iF10#E’T’ii*i#匹配i11#E’T’*i#(T’,*)'*'FTT12#E’T’F**i#匹配*13#E’T’Fi#(F,i)iF14#E’T’ii#匹配i15#E’T’#(T’,#)'T16#E’#(E’,#)'E17##匹配#，成功6流程图图2LL(1)分析器流程图7程序设计在程序设计方面，做出了如下定义：二维数组ll1[5][6]：表示LL(1)分析表内容一位数组ch[10]：用于存放符号栈内容一位数组str[10]：存放输入串一维数组str1[10]：用于存放最初输入的字符串cha：分析字符l：符号栈大小k：分析输入串的第几个字符j：终结符所代表数字m：非终结符所代表数字how：利用那个产生式n：产生式右部大小代码：#includestring.h#includestdio.hintll1[5][6]={{1,0,0,1,0,0},{0,2,0,0,3,3},{4,0,0,4,0,0},{0,6,5,0,6,6},{8,0,0,7,0,0}};/*1:E-TE'2:E'-+TE'3:E'-e4:T-FT'5:T'-*FT'6:T'-e7:F-(E)8:F-i*/voidmain(){charch[10]={'#','E'};charstr[10];charstr1[10];charcha;inti,j,m,n;intl=1;intk=1;inthow;intstep=1;intlength=0;clrscr();printf(Pleaseinputastring(endwith'#'):);do{scanf(%c,&cha);str[length]=cha;str1[length]=cha;length++;}while(cha!='#');printf(-------------------------------------------------------------------------------\n);printf(Step\tCharacter\tchar\tString\tAction\n);printf(-------------------------------------------------------------------------------\n);do{cha=str1[k-1];printf(%d\t,step);for(i=0;i=l;i++)printf(%c,ch[i]);printf(\t\t);printf(%c\t,cha);for(i=0;ik;i++){str[i]='';printf(%c,str[i]);}for(i=k;ilength;i++)printf(%c,str[i]);printf(\t);switch(cha){case'i':j=0;break;case'+':j=1;break;case'*':j=2;break;case'(':j=3;break;case')':j=4;break;case'#':j=5;break;defult:j=-1;break;}/*switch(cha)*/if(j!=-1){if(ch[l]!=cha){if(ch[l]!=39){switch(ch[l]){case'E':m=0;break;case'T':m=2;break;case'F':m=4;break;default:m=-1;break;}}/*if(ch[l]!=''')*/else{switch(ch[l-1]){case'E':m=1;break;case'T':m=3;break;default:m=-1;break;}}/*if(ch[l])=='''*/}/*ifch[l]!=cha*/if(m!=-1){if(ch[l]!=cha){how=ll1[m][j];if(how==1){printf(Pop%c,pushE-TE'byreversing!\n,ch[l]);n=3;l=l+n-1;ch[l]='T';ch[l-1]=39;ch[l-2]='E';step=step+1;}/*ifhow==1*/elseif(how==2){printf(Pop%c%c,pushE'-+TE'byreversing!\n,ch[l-1],ch[l]);n=4;l=l+n-2;ch[l]='+';ch[l-1]='T';ch[l-2]=39;ch[l-3]='E';step=step+1;}/*ifhow==2*/elseif(how==3){printf(Pop%c%c,usingE'-e!\n,ch[l-1],ch[l]);l=l-2;step=step+1;}/*ifhow==3*/elseif(how==4){printf(Pop%c,pushT-FT'byreversing!\n,ch[l]);n=3;l=l+n-1;ch[l]='F';ch[l-1]=39;ch[l-2]='T';step=step+1;}/*ifhow==4*/elseif(how==5){printf(Pop%c%c,pushT'-*FT'byreversing!\n,ch[l-1],ch[l]);n=4;l=l+n-2;ch[l]='*';ch[l-1]='F';ch[l-2]=39;ch[l-3]='T';step=step+1;}/*ifhow==5*/elseif(how==6){printf(Pop%c%c,usingT'-e!\n,ch[l-1],ch[l]);l=l-2;step=step+1;}/*ifhow==6*/elseif(how==7){printf(Pop%c,pushF-(E)byreversing!\n,ch[l]);n=3;l=l+n-1;ch[l]='(';ch[l-1]='E';ch[l-2]=')';step=step+1;}/*ifhow==7*/elseif(how==8){printf(Pop%c,pushF-ibyreversing!\n,ch[l]);n=1;l=l+n-1;ch[l]='i';step=step+1;}/*ifhow==8*/else{printf(ERROR!\n);exit(0);}/*ifhow==0*/}/*ifcha[l]!=cha*/else{if(cha=='#'&&ch[l]=='#'){printf(Match,success!\n);exit(0);}else{printf(Match%c!\n,cha);l=l-1;k=k+1;step=step+1;}}/*ifch[l]==cha*/}/*ifm!=-1*/else{printf(ERROR!);exit(0);}/*ifm==-1*/}/*ifj!=-1*/else{printf(Wrongcharacter!);exit(0);}/*ifj==-1*/}while(l=0);/*do...while*/}/*main*/实验结果：实验心得：本实验加深了我对LL(1)分析法的算法和思想的理解，刚开始并不知道用程序怎么写出这么一个比较难的设计，但是通过资料的查阅和一步步的分析，画出LL(1)分析法思路的流程图之后，发现程序代码设计的方向比较明确，虽然中间出现很多错误，经历时间也比