LL1语法分析程序.docx

编译原理上机试验报告题目：1.1.（I）语法分析程序1 .设计要求（1）对输入文法，它能推断是否为1.1.（I）文法，若是，则转（2）：否则报错并终止；（2）输入已知文法，由程序自动生成它的1.1.（D分析表：（3）对于给定的输入串，应能推断识别该串是否为给定文法的句型。2 .分析该程序可分为如下几步：（1）读入文法（2）推断正误（3）若无误，推断是否为1.1.（D文法（4）若是，构造分析表；（5）由总控算法推断输入符号串是否为该文法的句型。3 .流程图ftinclude<string.h>intcount=0;/*分解的产生式的个数*/charstart：*起先符号*/chartermin50;*终结符号*/charnon_ter50;/*非终结符号*/charv50;/*全部符号*/charleft50：/*左部*/charright5050;/*右部*/intnumber;/*全部终结符和非终结符的总数*/charfirst5050,follow5050;/*各产生式右部的FIRST和左部的FO1.1.OW集合*/charfirst!5050;*全部单个符号的FIRST集合*/charselect5050;/*各单个产生式的SE1.ECT集合*/charf50,F50;/*记录各符号的FIRST和FO1.1.OW是否已求过*/charempty20;/*记录可干脆推出C的符号*/charTEMFj50;/*求FO1.1.OW时存放某一符号串的FIRST集合*/intvalidity=l;/*表示输入文法是否有效*/int11=1;/*表示输入文法是否为1.1.(I)文法*/intM2020;/*分析表*/*用户输入时运用*/charchoose;charempt20;*求_emp()时运用*/charfo20;*求FO1.1.OW集合时运用*/推断一个字符是否在指定字符串中intin(charc,char*p)/inti;size_ti;if(strlen(p)=0)return(0);for(i=0;i+)if(pi=c)return(1);*若在，返回1*/if(i=strlen(p)return(0);*若不在，返回0*/得到一个不是非终结符的符号charc()charc=',;while(in(c,non_ter)=l)c+;return(c);分解含有左递归的产生式voidrecur(char*point)/*完整的产生式在point口中*/intj,m=0,n=3,k：chartemp20,ch;ch=cO;*得到一个非终结符*/k=strlen(non_ter)：non_terk=ch;non_terk+l=,0,：for(j=0;size_t(j)<=strlen(point)-1;j+)if(pointn=point0)*假如'I'后的首符号和左部相同*/for(j=n+l;size_t(j)<=strlen(point)-1;j+)while(pointj!=,j,&&pointj!三,0,)tempm+=pointj+;leftcount=ch;memcpy(rightcount,temp,m);rightcountm=ch:rightcountm+l,0,;m=0;count+;if(pointj=I,)n=j+l;break：else*假如'I'后的首符号和左部不同*/leftcount=ch:rightcount0=，''rightcount1,0,;count+;for(j=n:size_t(j)<=strlen(point)-l;j+)if(pointj!=>)tempEm+=pointj：elseleftcount=point0;memcpy(rightcount,temp,m);rightcountm=ch:rightcountm+l='0'printf(*count=%d*,count);m=0;count+：leftcount=point0;memcpy(rightcount,temp,m)：rightcountm=ch;rightcountm+l=，0,：count+;m=0;分解不含有左递归的产生式voidnon_re(char*point)intm=0,J;chartemp20;for(j=3;size_t(j)<=strlen(point)-1;j+)if(pointj!三,)tempm+=pointj：elseleftcount=point0;memcpy(rightcount,temp,m);rightcountm=,0,;m=0:count+;leftcount=point0：memcpy(rightcount,temp,m);rightcountm=，0'count+;m=0:读入一个文法chargrammer(char*t,char*n,char*left,charright5050)charvn50,vt50;chars：charp5050;inti,j,k：printf11请输入文法的非终结符号串：”)；scanf(*%sw,vn)：getchar();i=strlen(vn);mcmcpy(n,vn,i);ni三0,;PrintfC请输入文法的终结符号串：scanf(*%s*,vt);getchar();i=strlen(vt);memcpy(t,vt,i);ti=0,;PrintfC请输入文法的起先符号：scanfC%c*,&s);getchar();Printf("请输入文法产生式的条数：”)；SCanf(",&i);getchar();for(j=l;j<=i:j+÷)Printf("请输入文法的第%d条(共%d条)产生式：”,j,i);scanfC%sa,pj-l);getchar0：for(j=0;j<=i-l;J+)if(pjl!=-pj2!=>>>)Iprintf(*ninputerror!”);Validity=O:returnC0');/*检测输入错误*/for(k=0;k<=i-l;k+)/*分解输入的各产生式*/if(pk3pk0)recur(pk);elsenon_re(pk);return(三);将单个符号或符号串并入另一符号串voidmerge(char*d,char*s,inttype)*d是目标符号串，S是源串，type=l,源串中的一'一并并入目串：type=2,源串中的八'不并入目串*/i11ti,j;for(i=O：size_t(i)<=str1en(三)-1;i+)if(type=2si=*,)elsefor(j=0;j+)if(size-t(j)<strlen(d)ftftsi=dj)break;if(size_t(j)=strlen(d)dj=si;dj+l三,0,;break;求全部能干脆推出C的符号Voidcmp(charc)/*即求全部由'C'推出的符号*/chartemp10;inti;for(i=0;i<=count-l;i+)if(righti0=c&&strlen(righti)=1)tempO=lefti;templ=*0'merge(empty,temp,1);emp(lefti)：求某一符号能否推出一int_emp(charc)/*若能推出，返回1;否则，返回O*/inti,j,k,result=1,mark=0;chartemp20;temp0=c;templ=，0,;merge(empt,temp,1)：if(in(c,empty)=1)return(l)：for(i=0;i÷+)if(i=count)return(0);if(lefti=c)*找一个左部为C的产生式*/j=strlen(righti);*j为右部的长度*/if(j=l&&in(righti0,empty)=1)return(1);elseif(j=lin(righti0,termin)=l)return(0)：elsefor(k=0;k<=j-1;k+)if(in(rightik,empt)=1)mark=l;if(mark=1)continue;elsefor(k=0;k<=j-1;k+)result*=_emp(rightik)：tempO=rightik;templ=>0,：merge(empt,temp,1);if(result=0&&i<count)continue：elseif(resu11=1&&i<count)return(1);推断读入的文法是否正确i11tjudgeOinti,j;for(i=0;i<=count-l;i+)if(in(lefti,non_ter)=0)*若左部不在非终结符中，报错*/printf(*nerrorl!*);validity=。;return(0)：for(j=0;size_t(J)<=strle11(righti)-1;j+)if(in(rightij,non_ter)=0&&in(rightij1termin)=O&&rightij!-,)*若右部某一符号不在非终结符、终结符中且不为-，报错*/printf(*nerror2!z,)：validity=O;return(0);return(1);求单个符号的FlRSTvoidfirst2(inti)*i为符号在全部输入符号中的序号*/charc,temp20;intj,k,m;c=vi;charch=，"emp(ch);if(in(c,termin)=l)*若为终结符*/firstli=c;firstl='0'*若为非终结符*/elseif(in(c,non_ter)=1)for(j=0:j<=count-l;j+)if(leftj=c)if(in(rightj0,terrain)=111rightjO=>,)tempO=rightj0;templ=t0'merge(firstli,temp,1)：elseif(in(rightj0,non_ter)=l)if(rightj0=c)continue;for(k=0;k+)if(vk=rightj0)break;if(fk=0,)first2(k);fk=t;mcrge(firstli,firsilk,2);for(k=0;size_t(k)<=strlen(rightj)-l;k+)empt0=,0,;if(_emp(rightjk)=l&&size_t(k)<strlen(rightj)-l)for(m=0;m+)if(vm=rightjk+l)break;if(fm=,0,)first2(m);fm=;merge(firstli,firstlm,2);elseif(_emp(rightjk)=l&&size_l(k)=strIen(rightj)-1)tempO=,'>tcmpi=>0*;merge(firstli,temp,1);elsebreak;fi=1,;求各产生式右部的FIRSTvoidFIRST(inti,char*p)intlength;intj,k,m;chartemp20;Icngth=Strlen(p);if(length=l)*假如右部为单个符号*/if(pO=,)if(i>=O)firstiO三,:firstil=O,;elseTEMP0J''TEMP1=0,;elsefor(j=0;j+)if(vj=p0)break;if(i>=O)memcpy(firsti,firstlj,strlen(firstlj);firstistrlen(first1Cj)=*0'：elsememcpy(TEMP,firstlj,strlen(firstlj)：TEMPstrlen(firstlj)=0,;else*假如右部为符号串*/for(j=0;：j+)if(vj=pO)break：merge(firsti,firstlj,2);elsemerge(TEMP,firstlj,2);for(k=O:k<=length-l;k+)empt0=，0'if(_emp(pk)=lk<length-l)for(m=0;m+)if(vm=rightik+l)break;if(i>=0)merge(firsti,firstlm,2);elsemerge(TEMP,firstlm,2)：elseif(-emp(pk)=l&&k=length-l)temp0='"templ-'0'if(i>=0)merge(firsti,temp,1);elsemerge(TEMP,temp,1);elseif(_cmp(pk)=0)求各产生式左部的FO1.1.OWvoidFO1.1.OW(inti)intj,k,m,n,result=l;charc,temp20;c=non_teri;*c为待求的非终结符*/temp0=c;ICmP1='0'merge(fo,temp,1)：if(c=start)*若为起先符号*/temp0='templ=*0,;merge(followi,temp,1);for(j=0;j<=count-1;j+)if(in(c,rightj)=l)*找一个右部含有c的产生式*/for(k=0;k+)if(rightjk=c)break;*k为C在该产生式右部的序号*/for(m=0:;m+)if(vm=leftj)break：*n为产生式左部非终结符在全部符号中的序号*/if(size_t(k)=strIen(rightj)-1)/*假如C在产生式右部的最终*/if(in(vm,fo)=l)merge(followi,followm,1);continue;if(Fm=tO')FO1.1.OW(m)：Fm=F;merge(followi,followm,1);else*假如C不在产生式右部的最终*/for(n=k+l：size_t(n)<=strlen(rightj)-l;n+)empt0j='0,：result*=_emp(rightjn);if(result=l)*假如右部C后面的符号串能推出一*/if(in(vm,fo)=1)/*避开循环递归*/merge(followi,followm,1);continue;if(Fm=三,O')FO1.1.OW(m);Fm=f1>merge(followi,followm,1);for(n=k+l：size_t(n)<=strlen(rightj)-l;n+)tempn-k-l=rightjn;tempstrIen(rightj)-k-l=,0,;FIRST(-1,temp);merge(followi,TEMP,2)：F=F;推断读入文法是否为一个1.1.(I)文法i11t111()inti,j,length,result=l：chartemp50;for(j=0j<=49J+)*初始化*/firstj0=0,;followj0三,0,;firstlj0=0,：selectj0-0'TEMPj三Qt;tempj=，0'fj=0'：Fj=O,;for(j=0;size_t(j)<=strlen(v)-l;j+)first2(j);*求单个符号的FIRST集合*/printf(*nfirstl:*);for(j=0;size_t(j)<=strlen(v)-1;j+)printf(*%c:%s*,vj,firstlj);printf("ncmplyempty);printf(*n:n-emp:*);for(j=0;size_t(j)<=strlen(v)-l;j+)printf(*%d*,_emp(vj);for(i=0;i<=count-l：i+)FIRST(i,righti);*求FIRST*/printfCn");for(j=0：size_t(j)<=strIen(non_ter)-1;j+)*求FO1.1.OW*/if(foj=0)fotO=10,;FO1.1.OW(j);printfCrnfirst):for(i=0:i<=count-l：i+)printf(z,%sfirsti);printf(*nfollow:*);for(i=O;size_t(i)<=strlen(non_ter)-l;i+)printf(z,%s*,followi);for(i=0;i<=count-l;i+)(*求每一产生式的SE1.ECT集合*/memcpy(selecti,firsti,strlen(firsti);selectistrlen(firsti)=,0,;for(j=0;size_t(j)<=strIen(righti)-1;j+)result*=_emp(rightij);if(strlen(righti)=l&&righti0三,)result=l：if(result=l)for(j=0:;j+)if(vj=lefti)break：merge(selecti,followj,1);printf(*nselect:*);for(i=0:i<=count-l;i+)printf(z,%s*,selecti);memcpy(temp,select0,strlen(selectO);tempstrlen(select)='0'：for(i=l:i<=count-l：i+÷)*推断输入文法是否为1.1.(I)文法*/Iength=Strlen(temp);if(lefti=lefti-l)merge(temp,selecti,1);if(strIen(temp)<length+strlen(selecti)return(O):elsetempO,O,;memcpy(temp,selecti,strlen(selecti)：tempstrlen(selecti)=，O'return(1);构造分析表MvoidMMOinti,j,k,m;for(i=0:i<=19;i+)for(j=0;j<=19;j+)Mij=-1;i=strlen(termin);termini='*将#加入终结符数组*/termini+l=,0,;for(i=0:i<=count-l;i+)for(m=0;m+)if(non_term=lefti)break;*m为产生式左部M终结符的序号*/for(j=0：size_t(j)<=strlen(selecti)-l:j+)if(in(selectij,termin)=l)for(k=0:;k+)if(termink=selectij)break:*k为产生式右部终结符的序号*/Mmk=i;总控算法voidsyntax()i11ti,j,k,m,n,p,q;charch;charS50,str50;Printf("请输入该文法的句型：”)；scanf(*%s*,str);getcharO;i=strlen(str);stri=*it,;stri+l=*0,;so=,r：Sl=start;S2=0,;j=0;ch=strj;whi1e(1)if(in(Sstrlen(三)-l,termin)=1)if(Sstrlen(三)-l!=ch)Printf("n该符号串不是文法的句型！”)；return;elseif(Sstrlen(三)-I=*)printf11该符号串是文法的句型”)；return;elseSstrlen(三)-l=,0,：J+；ch=strj：elsefor(i=0;：i+)if(non_teri=Sstrlen(三)-l)break：for(k=0;k+)if(termink=ch)break;if(size_t(k)=Strlen(termin)Printf("n词法错误!");return;if(Mik=-l)Printf("n语法错误！”)；return;elsem=Mk;if(rightm0,)Sstrlen(三)-I='O'elseP=Strlen(三)-I;q=P；for(n=strlen(rightm)-1;n>=0;n)Sp+=rightmn：Sq+strlen(rightm)=>0>printfC,11S%sstr:",S);for(p=j;size_t(p)<=strlen(str)-1;p+)Printf(飞c”,strp)：printfC");一个用户调用函数voidmenu()syntaxO：Printf("n是否接着?(yorn):");SCanf(飞c”,ftchoose);getchar();whiIe(choose=,y,)menu();主函数voidmain()inti,j：start=grammcr(tcrmin,non_ter,left,right);*读入一个文法*/Prinlf("count=,count);printfC,11start:%c/start);strcpy(v,non_ter);strcat(v,termin)：Printf("nv:%s”,v);printfC,nnon-ter%sw,non_ter);Printf("ntcrmir/s”,termin);printfC,11right)：for(i=0;i<=count-l;i+)printf(*%s*,righti);printf(*nleft:*):for(i=0:i<=count-l;i+)printf(,%c”,left)；if(validity=l)validity=judge();Printf("nvalidity=%d”,validity);if(validity=1)printf(*n文法有效”)；11=111();printf(wnll=%dw,11);if(Il=O)printfCn该文法不是一个1.1.l文法！");elseMM()；printf(*n*);for(i=0;i<=19：i+)for(j=0J<=19J+)if(M仃>=0)printfCM%d%d=%d*,i,j,Mij);printf(*n");menuO;5.执行结果(I)输入一个文法(2)输入一个符号串(3)再次输入一个符号串，然后退出程序