语法分析程序实验报告.pdf

1.设计规定(1)对输入文法，它能判断与否为LL(1)文法，若是，则转(2)；否则报错并终止；(2)输入已知文法，由程序自动生成它日勺LL(1)分析表；(3)对于给定时输入串，应能判断识别该串与否为给定文法日勺句型。2.分析该程序可分为如下几步：(1)读入文法(2)判断正误(3)若无误，判断与否为LL(1)文法(4)若是，构造分析表；(5)由总控算法判断输入符号串与否为该文法日勺句型。3.流程图是4.源程序语法分析程序作者：龚勋刘栋罗晓波学号：31500342 31500350 31500351计科系13班#include#include#includeint count=0;/*分解时产生式的个数*/int number;/*所有终止符和非终止符的总数*/char start;/*开始符号*/char termin50;/*终止符号*/char non_ter50;/*非终止符号*/char v50;/*所有符号*/*左部*/char left50;char right50 50;/*右部*/charfirst5050,follow5050;/*各产生式右部的 FIRST 和左部的 FOLLOW 集合*/char firstl5050;/*所有单个符号的FIRST集合*/char select5050;/*各单个产生式的SELECT集合*/char f50,F50;/*记录各符号的FIRST和FOLLOW与否已求过*/char empty 20;/*记录可直接推出八时符号*/char TEMP50;/*求FOLLOW时寄存某一符号串的FIRST集合*/int validity=l;/*表达输入文法与否有效*/int 11=1;/*表达输入文法与否为LL(1)文法*/intM2020;/*分析表*/char choose;/*顾客输入时使用*/char empt20;/*求_emp()时使用*/char fo20;/*求FOLLOW 集合时使用*/判断一种字符与否在指定字符串中int in(char c,char*p)(int i;if(strlen(p)=O)return(O);for(i=0;i+)if(pi=c)return(l);/*若在，返回1*/if(i=strlen(p)return(O);/*若不在，返回 0*/)得到一种不是非终止符日勺符号char c()|char c-A;while(in(c,non_ter)=1)C+；return(c);)分解具有左递归日勺产生式void recur(char*point)/*完整时产生式在point口中*/int j,m=0,n=3,k;char temp20,ch;ch=c();/*得到一种非终止符*/k=strlen(non_ter);non_terk=ch;non_terk+l=0;for(j=0;j=strlen(point)-l;j+)(if(pointn=point0)/*假如I后的首符号和左部相似*/for(j=n+l;j=strlen(point)-1;j+)|while(pointj!=T&pointj!=0)temp m+=point+;leftcount=ch;memcpy(rightcount,temp,m);rightcount m=ch;right count m+1-0;m=0;count+;if(point|j=T)(n=j+1;break;)else/*假如T后的首符号和左部不一样*/leftcount=ch;rightcount 0=A，;rightcount 1=0;count+;for(j=n;j=strlen(point)-1;j+)(if(pointj!=T)tempm+=pointj;else(leftcount=point0;memcpy(rightcount,temp,m);rightcount m=ch;rightcount m+l=O;printf(count=%d,count);m=0;count+;)leftcount=point0;memcpy(rightcount,temp,m);rightcount m=ch;right count m+1=0;count+;m=0;分解不具有左递归日勺产生式void non_re(char*point)|int m=0,j;char temp 20;for(j=3;j=strlen(point)-1;j+)(if(pointU!=T)tempm+=pointj;else|leftcount=point0;memcpy(right count,temp,m);rightcount m=0;m=0;count+;)leftcount=point0;memcpy(rightcount,temp,m);rightcountm=0;count+;m=0;)读入一种文法char grammer(char*t,char*n,char*left,char right5050)(char vn50,vt50;char s;charp5050;int i,j,k;printf(”n请输入文法的非终止符号串：);scanf(%sn,vn);getchar();i=strlen(vn);memcpy(n,vn,i);ni=0;printf(”请输入文法的终止符号串：);scanf(%s,vt);getchar();i=strlen(vt);memcpy(t,vt,i);ti=0;printf（请输入文法时开始符号:）;scanf(%c,&s);getchar();printf(请输入文法产生式的条数:)；scanf(%d,&i);getchar();for(j=l;j=i;j+)(printf(请输入文法的第d条(共d条)产生式:scanf(%s,pj-l);getchar();)for(j=0;j=i-l;j+)if(P 皿 皿 2!=少)printf(ninput error!1);validity=O;return(0);/*检测输入错误*/for(k=0;k=i-l;k+)/*分解输入时各产生式*/if(pk3=pkO)recur(pk);elsenon_re(pk);retum(s);将单个符号或符号串并入另一符号串void merge(char*d,char*s,int type)/*d是目日勺符号串，s是源串,type=l,源串中日勺八一并并入目串;type=2,源串中的八不并入目串*/int i,j;for(i=0;i=strlen(s)-1;i+)(if(type=2&si=A)else|for(j=0;j+)(if(jstrlen(d)&si=dj)break;if(j=strlen(d)|dj=si;dj+l=O;break;求所有能直接推出八时符号void emp(char c)/*即求所有由八推出的符号*/char temp 10;int i;for(i=0;i=count-1;i+)if(righti 0=c&strlen(righti)=1)temp0=lefti;templ-0;merge(empty,temp,1);emp(lefti);求某一符号能否推出八int _emp(char c)/*若能推出，返回I；否则，返回0*/int i,j,k,result=l,mark=0;char temp 20;temp0=c;tempfl-0;merge(empt,temp,1);if(in(c,empty)=1)return(l);for(i=0;i+)(if(i=count)return(O);if(lefti=c)/*找一种左部为c的产生式*/(j=strlen(righti);/*j 为右部的长度*/if(j=1&in(righti 0,empty)=1)retum(l);else if(j=1&in(rightiO,termin)=1)return(O);else(for(k=0;k=j-l;k+)if(in(rightik,empt)=1)mark=l;if(mark=l)continue;else|for(k=0;k=j-1;k+)|result*=_emp(righti k);temp0=righti k;templ=0;merge(empt,temp,1);)if(result=0&icount)continue;else if(result=1&icount)return(l);判断读入的文法与否对时int judge()int i,j;for(i=0;i=count-1;i+)if(in(lefti,non_ter)=0)/*若左部不在非终止符中，报错*/printf(nerrorl!);validity=0;return(O);for(j=0;j 0;)else if(in(c,non_ter)=1)/*若为非终止符*/(for(j=0;j=count-1;j+)(if(leftj=c)(if(in(rightj 0,termin)=1|rightj0=A，)(temp0=rightj0;templ-0;merge(first li,temp,l);)else if(in(rightj 0,non_ter)=1)if(rightj0=c)continue;for(k=0;k+)if(vk=right 皿 0)break;if(fk=O)(first2(k);fk=T;merge(firstli,firstlk,2);for(k=0;k=strlen(rightj)-l;k+)|empt0=0;if(_emp(rightj k)=1&k=0)(firstiO=，A，;firstil=O;)else(TEMPO=，A，;TEMPl=fO;)else(for(j=0;j+)if(vj=pO)break;if(i=0)(memcpy(first i,first 1 j,strlen(firstl j);firstistrlen(firstl j)=,0,;elsememcpy(TEMP,fir st 1 j,strlen(firstl j);TEMPstrlen(firstl j)=0;else/*假如右部为符号串*/(for(j=0;j+)if(vj=p)break;if(i=0)merge(firsti,firstl j,2);elsemerge(TEMP,fir st 1 j,2);for(k=0;k=length-1;k+)|emptO=O;if(_emp(pk)=1&k=0)merge(firsti,first 1 m,2);elsemerge(TEMP,first 1 m,2);else if(_emp(pk)=l&k=length-1)temp0-A，;templ=O;if(i=0)merge(firsti,temp,1);elsemerge(TEMP,temp,1);else if(_emp(p k)=0)break;求各产生式左部的FOLLOWvoid FOLLOW(int i)int j,k,m,n,result=1;char c,temp 20;c=non_teri;/*c为待求时非终止符*/tempO=c;templ-O;merge(fo,temp,l);if(c=start)/*若为开始符号*/tempO=#;templ=O;merge(follow i,temp,l);)for(j=0;j=count-l;j+)if(in(c,right用)=1)/*找一种右部具有c的产生式*/(for(k=0;k+)if(rightjk=c)break;/*k为c在该产生式右部的序号*/for(m=0;m+)if(vm=leftj)break;/*m为产生式左部非终止符在所有符号中的序号*/if(k=strlen(rightj)-1)/*假如c在产生式右部的最终*/if(in(vm,fo)1)merge(follow i,follow m,l);continue;if(Fm=O)|FOLLOW(m);)merge(follow i,follow)else/*假如c不在产生式右部的最终*/for(n=k+l;n=strlen(right(j)-1;n+)|empt0=0;result*=_emp(rightj n);)if(result=l)/*假如右部c背面日勺符号串能推出八*/if(in(vm,fo)-1)/*防止循环递归*/merge(follow i,follow continue;)if(Fm=O)FOLLOW(m);merge(follow i,follow m,1);for(n=k+l;n=strlen(rightj)-l;n+)temp n-k-1=right。n;tempstrlen(rightj)-k-l=O;FIRST(-l,temp);merge(followi,TEMP,2);)判断读入文法与否为一种LL(1)文法int 111()|int i,j,length,result=l;char temp 50;for(j=0;j=49;j+)/*初始化*/firstjO=O;follow j0=0;firstljO=O;selectjO=O;TEMP|j=0;tempj=O;FJ=O;)for(j=0;j=strlen(v)-1;j+)first2(j);/*求单个符号的FIRST集合*/printf(nfirstl:);for(j=0;j=strlen(v)-l;j+)printf(%c:%s n,vj,firstly);printf(nempty:%s,empty);printf(n:n_emp:);for(j=0;j=strlen(v)-1;j+)printf(%d,_emp(vj);for(i=0;i=count-1;i+)FIRST(i,righti);/*求 FIRST*/printf(n);for(j=0;j=strlen(non_ter)-1;j+)/*求 FOLLOW*/if(fo-=0)fo0=0;FOLLOW(j)；printf(nfirst:);for(i=0;i=count-1;i+)printf(n%s,firsti);printf(nfollow:);fbr(i=0;i=strlen(non_ter)-1;i+)printf(n%s followi);for(i=0;i=count-1;i+)/*求每一产生式的SELECT集合*/memcpy(selecti,firsti,strlen(firsti);selectistrlen(firsti)=O;for(j=0;j=strlen(righti)-l;j+)result*=_emp(righti j);if(strlen(righti)=1&righti 0=A，)result=l;if(result=l)|for(j=0;j+)if(vj=lefti)break;merge(select i,folio wj,l);)printf(nselect:);for(i=0;i=count-1;i+)printf(%s,selecti);memcpy(temp,selectO,strlen(selectO);tempstrlen(select 0)=0;for(i=1;i=count-l;i+)/*判断输入文法与否为LL文法*/length=strlen(temp);if(lefti=lefti-l)|merge(temp,selecti,l);if(strlen(temp)length+strlen(selecti)return(O);)elsetemp0=0;memcpy(temp,selecti,strlen(selecti);tempstrlen(selecti)=O;)return(l);)构造分析表Mvoid MM()(intfor(i=0;i=19;i+)for(j=0;j=19;j+)i=strlen(termin);termini=#;/*将#加入终止符数组*/termini+l=O;for(i=0;i=count-1;i+)(for(m=0;m+)if(non_term lefti)break;/*m为产生式左部非终止符的序号*/for(j=0;j=O;n-)Sp+=rightmn;S q+strlen(rightm)=0;printf(nS:%s str:,S);for(p=j;p=strlen(str)-l;p+)printf(%c,strp);printf();一种顾客调用函数void menu()syntax();printf(n 与否继续？(y or n):);scanf(%c,&choose);getchar();while(choose=y)menu();主函数void main()|int i,j;start=grammer(termin,non_ter,left,right);printf(count=%d,count);printf(nstart:%c,start);strcpy(v,non_ter);strcat(v,termin);printf(nv:%s,v);printf(nnon_ter:%s,non_ter);printf(ntermin:%s,termin);printf(nright:);for(i=0;i=count-1;i+)printf(%s,righti);printf(nleft:);for(i=0;i=count-1;i+)printf(%c,lefti);if(validity=l)validity 二judge。；printf(nvalidity=%d,validity);if(validity=l)/*读入一种文法*/printf n文法有效）IMHO；printf(nll=%d,ll);if(ll=O)printf(n该文法不是一种LL1文法！);else|MM();printf(n);for(i=0;i=19;i+)for(j=0;j=0)printf(M%d%d=%d,i,j,Mi|j);printf(n);menu();5.执行成果(i)输入一种文法（2）输入一种符号串I C、D:Turboc2Debugsyirtax.exe，陶晶莹-太委屈EOT 回 x|请输入该文法的句型：S：ttAT str：i*#S：ttABF str：i*tt S：ttABi str：i*#S：ttAB str：*tt S：#ABF*str：*tt S：ttABF str：tt S：1tABE str：#S：ttABE str：i+itt S：ttABAT str：i+i#S：ttABABF str：i+i#str：i+ittS：ttABAB str：+i#S：ttABA str：+i#S：ttABAT*str：+i#S：ttABAT str：i#S：ttABABF str：itt str：ittS：ttABAB str：tt S：ttABA str：tt S：ttAB str：#S：ttAB str：#S：ttA str：tt S：tt str：#该符号串是文法的句型.是否继续？。or n：3J（3）再次输入一种符号串，然后退出程序