LL(1)文法分析

曲阜师范大学No·2009145739计算机系09级年级1班组日期2012-4-1姓名同组者姓名课程：编译原理成绩：教师签章实验名称：LL（1）文法分析一．实验目的：1．了解LL（1）文法分析是如何根据语法规则逐一分析词法分析所得到的单词，检查语法错误，即语法分析过程。2．掌握LL（1）语法分析器的设计与测试。二．实验内容：文法：ETE’,E’+TE’|ε,TFT’,T’*FT’|ε,F(E)|i针对上述文法，编写一个LL（1）语法分析程序:1.输入：诸如i+i*i的字符串，以#结束。2.处理：基于分析表进行LL（1）语法分析，判断是否符合文法。3.输出:串是否合法。三．实验要求：1.在编程前，根据上述文法建立对应的。正确的预测分析表。2.设计恰当的数据结构存储预测分析表。3.任选c/c++/java中的一种作为编程语言，要求所编程序结构清晰。四．实验环境：visualc++6.0五．实验代码：#includestdio.h#includeiostream.h#includestring.h#defineVtn8#defineVnn5#definePn10#definePmaxlen20#defineMaxStLength50#defineMaxStackDepth50charVn[Vnn]={'E','e','T','t','F'};charVt[Vtn]={'i','+','-','*','/','(',')','$'};charPstr[Pn][Pmaxlen]={E-Te,e-+Te,e--Te,e-ε,T-Ft,t-*Ft,t-/Ft,t-ε,F-(E),F-i};intPrlen[Pn]={2,3,3,1,2,3,3,1,3,1};intPint[Pn][3]={{102,101},{1,102,101},{2,102,101},{-1},{104,103},{3,104,103},{4,104,103},{-1},{5,100,6},{0}};intanalyseTable[Vnn][Vtn+1];intanalyseStack[MaxStackDepth+1];inttopAnalyse;charst[MaxStLength];//要分析的符号串/*----------------------初始化----------------------------*/voidInitanalyseTable(){/*---预测分析表存放各个产生式的编号，-1表示找不到相匹配的产生式---*/for(inti=0;iVnn;i++)for(intj=0;jVtn;j++)analyseTable[i][j]=-1;analyseTable[0][0]=0;analyseTable[0][5]=0;analyseTable[1][1]=1;analyseTable[1][2]=2;analyseTable[1][6]=3;analyseTable[1][7]=3;analyseTable[2][0]=4;analyseTable[2][5]=4;analyseTable[3][1]=7;analyseTable[3][2]=7;analyseTable[3][3]=5;analyseTable[3][4]=6;analyseTable[3][6]=7;analyseTable[3][7]=7;analyseTable[4][0]=9;analyseTable[4][5]=8;}voidInit(){//分析栈的初始化analyseStack[0]=7;//入栈analyseStack[1]=100;//初始符入栈topAnalyse=1;//初始符号串inti;for(i=0;iMaxStLength;i++)st[i]='\0';}voidPop(){topAnalyse--;}/*--------------------产生式入栈操作----------------------*/voidPush(intr){inti,len;Pop();len=Prlen[r];//为空时if((len==1)&&(Pint[r][0]==-1))return;//不为空时topAnalyse+=len;for(i=0;ilen;i++)analyseStack[topAnalyse-i]=Pint[r][i];//逆序入栈}voidShowStack(){inti;for(i=0;i=topAnalyse;i++){if(analyseStack[i]=100)printf(%c,Vn[analyseStack[i]-100]);elseprintf(%c,Vt[analyseStack[i]]);}}/*----------------------返回表中的位置，-1表示未找到----------*/intIndex(charc){inti=0;while((iVtn)&&(c!=Vt[i]))i++;if((iVtn)&&(c==Vt[i]))returni;elsereturn-1;}voidIdentify(){intcurrent,step,r;printf(\n%s：\n\n,st);step=0;current=0;printf(%d\t,step);ShowStack();printf(\t\t%s\t\t--\n,st+current);while(1){if(analyseStack[topAnalyse]100){if(Vt[analyseStack[topAnalyse]]==st[current]){Pop();current++;step++;printf(%d\t,step);ShowStack();printf(\t\t%s\t\t出栈、后移\n,st+current);}else{printf(字符%c与字符%c不匹配!,Vt[analyseStack[topAnalyse]],st[current]);printf(此串不符合此文法!\n);return;}}else{intn,m;n=analyseStack[topAnalyse]-100;m=Index(st[current]);if(m==-1){printf(%c字符输入错误!,st[current]);printf(此串不符合此文法!\n);return;}r=analyseTable[n][m];if(r!=-1){Push(r);step++;printf(%d\t,step);ShowStack();printf(\t\t%s\t\t%s\n,st+current,Pstr[r]);}else{printf(无可用产生式，此串不是此文法的句子!\n);return;}}if(topAnalyse==0&&st[current]=='$')break;}}///////////////////////////////////////////////////////////////////////////////////////////////////voidmain(){InitanalyseTable();while(1){Init();printf(请输入符号串(以$结束):);inti=0;charc;c=getchar();while(iMaxStLength){if(c=='$'){st[i]='$';break;}elseif(c!=''&&c!='\n')st[i++]=c;c=getchar();if(c=='\n'){printf(请以$结束：);c=getchar();}}if(iMaxStLength)Identify();elseprintf(输入的符号串超过规定长度);}}六.实验结果：七．实验总结：LL（1）文法是一类可以进行确定的自顶向下语法分析的文法。要求所描述的文法是无左递归无二义性的文法。优点：（1）直观,简单，可读性好（2）便于扩充。缺点：（1）递归算法的实现效率低。（2）处理能力相对有限。（3）通用性差，难以自动生成程序结构。