LL(1)预测分析法

#includeiostream#includefstream#includecstring#includeiomanipusingnamespacestd;charold[20][20],table[20][20][10],n[20],s[20];//old存放文法(一个非终结符各产生式以|相隔`代表空-不存储)//table存放预测分析表数组n存放非终结符数组s存放终结符intnnum,gnum;//gnum为文法的行数；nnum为终结符的个数intinsert(charch[20],charc)//将字符c插入数组ch中{inti,flag=0;afor(i=0;i20;i++)if(ch[i]=='\0')break;elseif(ch[i]==c)return1;ch[i]=c;return1;}inttestn(charch){//如果是终结符就返回1intflag=0,i;for(i=0;i20&&s[i]!='\0';i++)if(s[i]==ch){flag=1;break;}returnflag;}intfirst(charch,charc[]);intcheck(charch){//判断非终结符能不能导出空能则返回1charc[20]={'\0'};first(ch,c);inti=0,flag=0;for(i=0;i20&&c[i]!='\0';i++)if(c[i]=='`'){flag=1;break;}returnflag;}intstringcat(charc1[20],charc2[20]){//把c2中除空以外的不与c1中一样的字符插到c1中inti=0,j=0,k,t;while(c1[i]!='\0')i++;t=i;while(c2[j]!='\0'){if(c2[j]=='`')j++;else{intflag=1;for(k=0;ki;k++)if(c2[j]==c1[k]){flag=0;break;}if(flag==1){c1[i]=c2[j];i++;}j++;}}if(j==0||t==i)return0;return1;}intconvert(charch,chararr[20][20])//找形如ch-的产生式，并将其放入arr数组中并返回ch-产生式个数{inti;for(i=0;i20;i++)if(ch==old[i][0])break;inti1=1,i2=0,i3=0;while(old[i][i1]!='\0'&&old[i][i1]!='\n'){/////////////////////////////////求出ch所有的产生式放在arr中共i2-1个charcht=old[i][i1];if(cht!='|')arr[i2][i3++]=cht;else{i2++;i3=0;}i1++;}///////////////////////////returni2+1;//返回ch-产生式个数}intfirst(charch,charc[20])//求ch的first集数组c存放ch的first集{if(testn(ch))insert(c,ch);//如果是终结符就插入else{inti2=0;chararr[20][20]={'\0'};//初始化i2=convert(ch,arr);//找到ch-的产生式将其放入arr中intflag=1,length=0;while(flag){//求firstintj;for(j=0;ji2;j++){//对ch的每个产生式intk=0,go_on=1;while(go_on&&arr[j][k]!='\0'){charc1[20]={'\0'};first(arr[j][k],c1);//递归求first集stringcat(c,c1);////把c1中除空以外的不与c中一样的字符插到c1中if(check(arr[j][k])==0)//不能导出空go_on=0;k++;//往后继续走}if(go_on==1)insert(c,'`');}//对ch的每个产生式if(strlen(c)==length)flag=0;else{flag=1;length=strlen(c);}}//求first}return1;}intfirst(charc[20],chararr[20]){//重载first来求产生式c的首符集放在arr中for(intk=0;c[k]!='\0'&&k20;k++){if(testn(c[k])==1){insert(arr,c[k]);break;}//coutnum=num,j=j,k=kendl;chartemp[20]={'\0'};first(c[k],temp);stringcat(arr,temp);if(check(c[k])==0)break;//判断非终结符能不能导出空能则返回1}if(c[k]=='\0'&&check(c[k-1]))insert(arr,'`');//非终结符能导出空return1;}intfollow(intn,charc[20][20]){//把含有n个规则的文法old[][]求其follow集，放在c中intflag=1,i,j;c[0][0]='#';//for(i=0;i20;i++)c[i]='\0';while(flag){for(i=0;in;i++){//对n个非终结符规则分别求followchararr[20][20]={'\0'};intnum=convert(old[i][0],arr);////找形如old[i][0]-的产生式，并将其放入arr数组中，num为产生式个数for(j=0;jnum;j++){//对第i行的非终结符的num行分别求其中的followintk,l;for(k=0;arr[j][k]!='\0';k++){if(testn(arr[j][k])==1)continue;//coutnum=num,j=j,k=kendl;for(l=0;ln;l++)if(old[l][0]==arr[j][k])break;if(arr[j][k+1]=='\0')//如果是最后一个就把followi加入{flag=stringcat(c[l],c[i]);}else{intflag1=1,q=k+1;for(;flag1&&arr[j][q]!='\0';q++){chartemp[20]={'\0'};first(arr[j][q],temp);//求arr[j][q]的first集,并将其放入temp数组中intm=stringcat(c[l],temp);//coutc[l],m=mendl;if(flag==0)flag=m;if(check(arr[j][q])==0)flag1=0;elseif(arr[j][q+1]=='\0'){m=stringcat(c[l],c[i]);if(flag==0)flag=m;}}}}}//对第i行的非终结符的num行分别求其中的follow}//对n个非终结符规则分别求follow}//while(flag)return1;}intlocate(charch)//返回字符ch在数组s[]中的位置{inti;if(ch=='#')returnnnum;for(i=0;innum;i++)if(s[i]==ch)returni;return-1;}intconstruct(charc[20][20]){//c是follow集inti,j;for(i=0;ignum;i++){//couti=iendl;chararr[20][20]={'\0'};intnum=convert(old[i][0],arr);//找到形如old[i][0]的产生式并将其放入arr中，num为产生式个数//coutnum=numendl;for(j=0;jnum;j++){chartemp[20]={'\0'};first(arr[j],temp);//求产生式arr[j]的首符集放在temp中intk=0;while(temp[k]!='\0'){if(temp[k]=='`'){for(intl=0;c[i][l]!='\0';l++){strcpy(table[i][locate(c[i][l])],arr[j]);//比较table表中第i行第c[i][l]列与arr[j]}}elsestrcpy(table[i][locate(temp[k])],arr[j]);//couttable[i][locate(temp[k])]table[i][locate(temp[k])]endl;k++;}}}return1;}intcontrol(chartable[][20][10])//总控程序{charstack[40]={'#',old[0][0]},ch;//将#E(开始符号)传入stack//coutstack;intpointer=1,flag=1;cinch;while(flag&&ch!='\n'){charx=stack[pointer];stack[pointer--]='\0';if(testn(x)){if(x==ch)cinch;else{return0;}}//保证输入的均为终结符elseif(x=='#'){if(x==ch){flag=0;}else{return0;}}else{inti;for(i=0;ignum;i++)if(old[i][0]==x)break;chararr[20]={'\0'};strcpy(arr,table[i][locate(ch)]);if(arr[0]!='\0'){if(arr[0]!='`'){for(i=0;arr[i]!='\0';i++);for(i-=1;i=0;i--)stack[++pointer]=arr[i];}}else{return0;}}}cout匹配成功!endl;return1;}intmain(){ifstreamin(input.txt,ios_base::in);//从文件读入相关信息inti;charc[20]={'\0'};ingnumnnum;//printf(gnum=%d,nnum=%d\n,gnum,nnum);gnum为文法的行数；nnum为终结符的个数inn;ins;//puts(n);puts(s);将非终结符传入n将终结符传入sfor(i=0;i=gnum;i++)inold[i];//将文法传入数组old[][]//cout文法如下：endl;//for(i=0;ignum;i++)//coutold[i]endl;coutfirst集：\n;for(i=0;ignum;i++){intk;for(k=0;k20;k++)c[k]='\0';first(old[i][0],c);coutold[i][0]::cendl;}//对第0列每行字符求first集chararr[20][20]={'\0'};arr[0][0]='#';follow(gnum,arr);coutfollow集：\n;for(i=0;ignum;i++)coutold[i][0]--arr[i]endl;//对第0列每行字符求follow集construct(arr);//构造预测分析表cout预测分析表：endlsetw(5)table;for(intj=0;jnnum;j++)coutsetw(5)s[j];coutsetw(5)'#'endl;//打印终结