LL(1)分析法

编译原理实验报告日期：班级：题目：LL(1)分析法组员：LL(1)语法分析程序1.实验目的：1.根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。2.本次实验的目的主要是加深对预测分析LL（1）分析法的理解。2.实验平台Windows+VC+Win32Console范例程序:“3-LL1.c”3.实验内容1.在范例程序的基础上完善功能对下列文法，用LL(1)分析法对任意输入的符号串进行分析：（1）E→TG（2）G→+TG|—TG（3）G→ε（4）T→FS（5）S→*FS|/FS（6）S→ε（7）F→(E)（8）F→i程序输入/输出示例：程序现有功能:输入:一个以#结束的符号串(包括+*（）i#)：例如：i+i*i#输出:只能输出步骤1,格式如下:程序目前还不能对所有输入串进行正确的分析.需要完善的功能:(1)请输出完整的分析过程。即详细输出每一步骤分析栈和剩余串的变化情况,及每一步所用的产生式.(2)请输出最终的分析结果,即输入串“合法”或“非法”.(3)示例程序只能完成+、*、（、）的语法分析,请加入-和/的语法分析(4)可将测试用的表达式事先放在文本文件中，一行存放一个表达式，以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照；备注：1.在“所用产生式”一列中，步骤分析栈剩余输入串所用产生式1#Ei+i*i#E→TG如果对应有推导，则写出所用产生式；如果为匹配终结符，则写明匹配的终结符；如分析异常出错则，写为“分析出错”；如成功结束则写为“分析成功”。2.对一个新的文法实现LL(1)分析。4.程序代码第一种文法#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[7];/*产生式右边字符*/intlength;/*字符个数*/}type;typee,t,g,g0,g1,s,s0,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);e.length=2;t.origin='T';strcpy(t.array,FS);t.length=2;g.origin='G';strcpy(g.array,+TG);g.length=3;g0.origin='G';strcpy(g0.array,-TG);g0.length=3;g1.origin='G';g1.array[0]='^';g1.length=1;s.origin='S';strcpy(s.array,*FS);s.length=3;s0.origin='S';strcpy(s0.array,/FS);s0.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][5]=e;C[1][1]=g;C[1][2]=g0;C[1][6]=g1;C[1][7]=g1;C[2][0]=t;C[2][5]=t;C[3][1]=s1;C[3][2]=s1;C[3][3]=s;C[3][4]=s0;C[3][6]=s1;C[3][7]=s1;C[4][0]=f1;C[4][5]=f;printf(提示:本程序只能对由'i','+','-','*','/','(',')'构成的以'#'结束的字符串进行分析,\n);printf(请输入要分析的字符串:\n);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*/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/*非终结符处理*/{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--;}/*if*/else/*出错处理*/{print();print1();printf(%c出错\n,x);/*输出出错非终结符*/exit(1);}/*else*/}/*else*/}while(finish==0);}/*main*/测试一（1）测试i+i#（2）测试i-i（3）测试i*i#（4）测试i/i#（5）测试i+i*i#（6）测试输入非法字符i+i*#第二中文发#includestdlib.h#includestdio.h#includestring.h/*******************************************/intcount=0;/*分解的产生式的个数*/intnumber;/*所有终结符和非终结符的总数*/charstart;/*开始符号*/chartermin[50];/*终结符号*/charnon_ter[50];/*非终结符号*/charv[50];/*所有符号*/charleft[50];/*左部*/charright[50][50];/*右部*/charfirst[50][50],follow[50][50];/*各产生式右部的FIRST和左部的FOLLOW集合*/charfirst1[50][50];/*所有单个符号的FIRST集合*/charselect[50][50];/*各单个产生式的SELECT集合*/charf[50],F[50];/*记录各符号的FIRST和FOLLOW是否已求过*/charempty[20];/*记录可直接推出^的符号*/charTEMP[50];/*求FOLLOW时存放某一符号串的FIRST集合*/intvalidity=1;/*表示输入文法是否有效*/intll=1;/*表示输入文法是否为LL(1)文法*/intM[20][20];/*分析表*/charchoose;/*用户输入时使用*/charempt[20];/*求_emp()时使用*/charfo[20];/*求FOLLOW集合时使用*//*******************************************判断一个字符是否在指定字符串中********************************************/intin(charc,char*p){inti;if(strlen(p)==0)return(0);for(i=0;;i++){if(p[i]==c)return(1);/*若在，返回1*/if(i==strlen(p))return(0);/*若不在，返回0*/}}/*******************************************得到一个不是非终结符的符号********************************************/charc(){charc='A';while(in(c,non_ter)==1)c++;return(c);}/*******************************************分解含有左递归的产生式********************************************/voidrecur(char*point){/*完整的产生式在point[]中*/intj,m=0,n=3,k;chartemp[20],ch;ch=c();/*得到一个非终结符*/k=strlen(non_ter);non_ter[k]=ch;non_ter[k+1]='\0';for(j=0;j=strlen(point)-1;j++){if(point[n]==point[0]){/*如果'|'后的首符号和左部相同*/for(j=n+1;j=strlen(point)-1;j++){while(point[j]!='|'&&point[j]!='\0')temp[m++]=point[j++];left[count]=ch;memcpy(right[count],temp,m);right[count][m]=ch;right[count][m+1]='\0';m=0;count++;if(point[j]=='|'){n=j+1;break;}}}else{/*如果'|'后的首符号和左部不同*/left[count]=c