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<=c