LL1文法的判别

1、实验四：LL（1）文法的判别一、 实验名称LL（1）文法的判别二、 实验目的（1）能导出空串的非终结符算法（2）实现首符集，后跟符集和可选集算法（3）输出要指出是否为LL（1）文法， 三、 实验原理 将数组X 中对应每一非终结符的标记置初值为"未定"。 扫描文法中的产生式。(a) 删除所有右部含有终结符的产生式，若这使得以某一非终结符为左部的所有产生式都被删除，则将数组中对应该非终结符的标记值改为"否"，说明该非终结符不能推出。(b) 若某一非终结符的某一产生式右部为，则将数组中对应该非终结符的标志置为"是"，并从文法中删除该非终结符

2、的所有产生式。例中对应非终结符A、B的标志改为"是"。 扫描产生式右部的每一符号。(a) 若所扫描到的非终结符号在数组中对应的标志是"是"，则删去该非终结符，若这使产生式右部为空，则对产生式左部的非终结符在数组中对应的标志改"是"，并删除该非终结符为左部的所有产生式。(b) 若所扫描到的非终结符号在数组中对应的标志是"否"，则删去该产生式，若这使产生式左部非终结符的有关产生式都被删去，则把在数组中该非终结符对应的标志改成"否"。 重复，直到扫描完一遍文法的产生式，数组中非终结符对应的特征再没有改

3、变为止。由中(a) 、(b)得知例中对应非终结符D的标志改为"否"，对应非终结符A、B的标志改为"是"。经过上述中(a)、(b)两步后文法中的产生式只剩下：SAB和CAD ，也就是只剩下右部全是非终结符串的产生式。再由中的(a)步扫描到产生式SAB时，在数组中A、B对应的标志都为"是"，删去后S的右部变为空，所以S对应标志置为"是"。最后由中的(b)扫描到产生式CAD时，其中，A对应的标志为"是"，D对应的标志是"否"，删去该产生式后，再无左部为C的产生式，所以C的对应标志改

4、为"否"四、 实验小结通过本次实验，熟悉了LL（1）文法，掌握了LL（1）文法的判定方法，具体实践了FIRST集、FOLLOW集、SELECT集的计算，加深了对LL（1）文法的理解。此外，将理论用于实践，亲身体会到了怎样求FIRST集等。如何理解转化的过程是相当重要，以及如何去创建程序去实现这一转化过程。这样的编程对于我来说是相当困难的，这次的程序并非自己编写的。但是我会一步步去理解该程序的每步含义，争取就算自己不会编写代码，但至少做到实现过程、步骤。通过实验进一步理解编译原理这门课程，知道这么可是多么难学，知道和理解了该理论在计算机中是怎样执行的，对该理论在实践中的应用有

5、深刻的理解。在这次课程设计中，我们组就是按照实验指导的思想来完成，加强培养实践动手能力和程序开发能力。五、 附录#include<stdio.h>#include<string.h>int count=0; /*分解的产生式的个数*/int number; /*所有终结符和非终结符的总数*/char start; /*开始符号*/char termin50; /*终结符号*/char non_ter50; /*非终结符号*/char v50; /*所有符号*/char left50; /*左部*/char right5050; /*右部*/char first5050,

6、follow5050; /*各产生式右部的FIRST和左部的FOLLOW集合*/char first15050; /*所有单个符号的FIRST集合*/char select5050; /*各单个产生式的SELECT集合*/char f50,F50; /*记录各符号的FIRST和FOLLOW是否已求过*/char empty20; /*记录可直接推出的符号*/char TEMP50; /*求FOLLOW时存放某一符号串的FIRST集合*/int validity=1; /*表示输入文法是否有效*/int ll=1; /*表示输入文法是否为LL(1)文法*/int M2020; /*分析表*/ch

7、ar choose; /*用户输入时使用*/char empt20; /*求_emp()时使用*/char fo20; /*求FOLLOW集合时使用*/int in(char c,char *p)int i;if(strlen(p)=0)return(0);for(i=0;i+) if(pi=c)return(1); /*若在，返回1*/if(i=strlen(p)return(0); /*若不在，返回0*/判断一个字符是否在指定字符串中char c()char c='A' while(in(c,non_ter)=1)c+;return(c);/得到一个不是非终结符的符号voi

8、d 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+1='0'for(j=0;j<=strlen(point)-1;j+) if(pointn=point0) /*如果|后的首符号和左部相同*/for(j=n+1;j<=strlen(point)-1;j+)while(pointj!='|'&&pointj

9、!='0)tempm+=pointj+;leftcount=ch;memcpy(rightcount,temp,m);rightcountm=ch;rightcountm+1='0'm=0;count+;if(pointj='|')n=j+1;break; else /*如果|后的首符号和左部不同*/ leftcount=ch; rightcount0='' rightcount1='0' count+; for(j=n;j<=strlen(point)-1;j+) if(pointj!='|') t

10、empm+=pointj; else leftcount=point0; memcpy(rightcount,temp,m); rightcountm=ch; rightcountm+1='0'/ printf(" count=%d ",count); m=0; count+; leftcount=point0; memcpy(rightcount,temp,m); rightcountm=ch; rightcountm+1='0' count+; m=0; void non_re(char *point)/ 分解不含有左递归的产生式int

11、m=0,j; char temp20; for(j=3;j<=strlen(point)-1;j+) if(pointj!='|') tempm+=pointj; else leftcount=point0; memcpy(rightcount,temp,m); rightcountm='0' m=0; count+; leftcount=point0; memcpy(rightcount,temp,m); rightcountm='0' count+; m=0; char grammer(char *t,char *n,char *lef

12、t,char right5050)/读入一个文法char vn50,vt50; char s; char p5050; int i,j,k; printf("请输入文法的非终结符号串："); scanf("%s",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&#

13、39; printf("请输入文法的开始符号："); scanf("%c",&s); getchar(); printf("请输入文法产生式的条数："); scanf("%d",&i); getchar(); for(j=1;j<=i;j+) printf("请输入文法的第%d条（共%d条）产生式：",j,i); scanf("%s",pj-1); getchar(); for(j=0;j<=i-1;j+) if(pj1!='-'|

14、pj2!='>') printf("ninput error!"); validity=0; return('0'); /*检测输入错误*/ for(k=0;k<=i-1;k+) /*分解输入的各产生式*/ if(pk3=pk0) recur(pk); else non_re(pk); return(s);void merge(char *d,char *s,int type)/将单个符号或符号串并入另一符号串/*d是目标符号串，s是源串，type1，源串中的 一并并入目串；type2，源串中的 不并入目串*/ int i,j;

15、for(i=0;i<=strlen(s)-1;i+) if(type=2&&si='') ; else for(j=0;j+) if(j<strlen(d)&&si=dj) break; if(j=strlen(d) dj=si; dj+1='0' break; void emp(char c)/求所有能直接推出的符号/*即求所有由 推出的符号*/ char temp10; int i; for(i=0;i<=count-1;i+)if(righti0=c&&strlen(righti)=1) t

16、emp0=lefti; temp1='0' merge(empty,temp,1); emp(lefti); int _emp(char c)/ 求某一符号能否推出 /*若能推出，返回1；否则，返回0*/ int i,j,k,result=1,mark=0; char temp20; temp0=c; temp1='0' merge(empt,temp,1); if(in(c,empty)=1) return(1); for(i=0;i+) if(i=count) return(0); if(lefti=c) /*找一个左部为c的产生式*/ j=strlen(r

17、ighti); /*j为右部的长度*/ if(j=1&&in(righti0,empty)=1) return(1); else if(j=1&&in(righti0,termin)=1) return(0); else for(k=0;k<=j-1;k+) if(in(rightik,empt)=1) mark=1; if(mark=1) continue; else for(k=0;k<=j-1;k+) result*=_emp(rightik); temp0=rightik; temp1='0' merge(empt,temp,

18、1); if(result=0&&i<count) continue; else if(result=1&&i<count) return(1); int judge()/判断读入的文法是否正确 int i,j; for(i=0;i<=count-1;i+) if(in(lefti,non_ter)=0) /*若左部不在非终结符中，报错*/ printf("nerror1!"); validity=0; return(0); for(j=0;j<=strlen(righti)-1;j+) if(in(rightij,n

19、on_ter)=0&&in(rightij,termin)=0&&rightij!='') /*若右部某一符号不在非终结符、终结符中且不为，报错*/ printf("nerror2!");validity=0;return(0); return(1); void first2(int i)/求单个符号的FIRST/*i为符号在所有输入符号中的序号*/ char c,temp20; int j,k,m; char ch='' c=vi; emp(ch); if(in(c,termin)=1) /*若为终结符*/

20、first1i0=c; first1i1='0' else if(in(c,non_ter)=1) /*若为非终结符*/ for(j=0;j<=count-1;j+) if(leftj=c) if(in(rightj0,termin)=1|rightj0='') temp0=rightj0; temp1='0' merge(first1i,temp,1); else if(in(rightj0,non_ter)=1) if(rightj0=c) continue; for(k=0;k+) if(vk=rightj0) break; if(f

21、k='0') first2(k); fk='1' merge(first1i,first1k,2); for(k=0;k<=strlen(rightj)-1;k+) empt0='0' if(_emp(rightjk)=1&&k<strlen(rightj)-1) for(m=0;m+)if(vm=rightjk+1)break;if(fm='0')first2(m);fm='1'merge(first1i,first1m,2); else if(_emp(rightjk)=1&

22、&k=strlen(rightj)-1) temp0='' temp1='0' merge(first1i,temp,1); else break; fi='1'void FIRST(int i,char *p) /求各产生式右部的FIRST int length; int j,k,m; char temp20; length=strlen(p); if(length=1) /*如果右部为单个符号*/ if(p0='') if(i>=0) firsti0='' firsti1='0'

23、else TEMP0='' TEMP1='0' else for(j=0;j+) if(vj=p0) break; if(i>=0) memcpy(firsti,first1j,strlen(first1j); firstistrlen(first1j)='0' else memcpy(TEMP,first1j,strlen(first1j); TEMPstrlen(first1j)='0' else /*如果右部为符号串*/ for(j=0;j+) if(vj=p0) break; if(i>=0) merge(fi

24、rsti,first1j,2); else merge(TEMP,first1j,2); for(k=0;k<=length-1;k+) empt0='0' if(_emp(pk)=1&&k<length-1) for(m=0;m+) if(vm=rightik+1) break; if(i>=0) merge(firsti,first1m,2); else merge(TEMP,first1m,2); else if(_emp(pk)=1&&k=length-1) temp0='' temp1='0&#

25、39; if(i>=0) merge(firsti,temp,1); else merge(TEMP,temp,1); else if(_emp(pk)=0) break; void FOLLOW(int i) /求各产生式左部的FOLLOW int j,k,m,n,result=1; char c,temp20; c=non_teri; /*c为待求的非终结符*/ temp0=c; temp1='0' merge(fo,temp,1); if(c=start) /*若为开始符号*/ temp0='#' temp1='0' merge(fo

26、llowi,temp,1); for(j=0;j<=count-1;j+) if(in(c,rightj)=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(followi,followm,1); continue; if(Fm='0') FOLL

27、OW(m); Fm='1' merge(followi,followm,1); else /*如果c不在产生式右部的最后*/ for(n=k+1;n<=strlen(rightj)-1;n+) empt0='0' result*=_emp(rightjn); if(result=1) /*如果右部c后面的符号串能推出*/ if(in(vm,fo)=1) /*避免循环递归*/ merge(followi,followm,1); continue; if(Fm='0') FOLLOW(m); Fm='1' merge(follo

28、wi,followm,1); for(n=k+1;n<=strlen(rightj)-1;n+) tempn-k-1=rightjn; tempstrlen(rightj)-k-1='0' FIRST(-1,temp); merge(followi,TEMP,2); Fi='1'int ll1() /判断读入文法是否为一个LL(1)文法 int i,j,length,result=1; char temp50; for(j=0;j<=49;j+) /*初始化*/ firstj0='0' followj0='0' fir

29、st1j0='0' selectj0='0' TEMPj='0' tempj='0' fj='0' Fj='0' for(j=0;j<=strlen(v)-1;j+) first2(j); /*求单个符号的FIRST集合*/ printf("n单个符号的FIRST集合为:"); for(j=0;j<=strlen(v)-1;j+) printf("%c:%s ",vj,first1j); printf("n能推出的非终结符:%s"

30、;,empty); /printf("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*/ for(j=0;j<=strlen(non_ter)-1;j+) /*求FOLLOW*/ if(foj=0) fo0='0' FOLLOW(j); printf("n每个产生式右部符号串的FIRST集合为:"); for(i=0;i<

31、=count-1;i+) printf("%s ",firsti); printf("n每个非终结符的FOLLOW集合为:"); for(i=0;i<=strlen(non_ter)-1;i+) printf("%s ",followi); for(i=0;i<=count-1;i+) /*求每一产生式的SELECT集合*/ memcpy(selecti,firsti,strlen(firsti); selectistrlen(firsti)='0' for(j=0;j<=strlen(righti)

32、-1;j+) result*=_emp(rightij); if(strlen(righti)=1&&righti0='') result=1; if(result=1) for(j=0;j+) if(vj=lefti) break; merge(selecti,followj,1); printf("n每个产生式的SELECT集合为:"); for(i=0;i<=count-1;i+) printf("%s ",selecti);memcpy(temp,select0,strlen(select0); tempst

33、rlen(select0)='0' for(i=1;i<=count-1;i+) /*判断输入文法是否为LL(1)文法*/ length=strlen(temp); if(lefti=lefti-1) merge(temp,selecti,1);if(strlen(temp)<length+strlen(selecti) return(0); else temp0='0' memcpy(temp,selecti,strlen(selecti); tempstrlen(selecti)='0' return(1);void MM() /

34、构造分析表M int i,j,k,m; for(i=0;i<=19;i+) for(j=0;j<=19;j+) Mij=-1; i=strlen(termin); termini='#' /*将#加入终结符数组*/ termini+1='0' for(i=0;i<=count-1;i+) for(m=0;m+) if(non_term=lefti) break; /*m为产生式左部非终结符的序号*/ for(j=0;j<=strlen(selecti)-1;j+) if(in(selectij,termin)=1) for(k=0;k+)

35、 if(termink=selectij) break; /*k为产生式右部终结符的序号*/ Mmk=i; void syntax() /总控算法 int i,j,k,m,n,p,q; char ch; char S50,str50; printf("请输入该文法的句型："); scanf("%s",str); getchar(); i=strlen(str); stri='#' stri+1='0' S0='#' S1=start; S2='0' j=0; ch=strj; while(1

36、) if(in(Sstrlen(S)-1,termin)=1) if(Sstrlen(S)-1!=ch) printf("该符号串不是文法的句型！"); return; else if(Sstrlen(S)-1='#') printf("该符号串是文法的句型."); return; else Sstrlen(S)-1='0' j+; ch=strj; else for(i=0;i+) if(non_teri=Sstrlen(S)-1) break; for(k=0;k+) if(termink=ch) break; if(k=strlen(termin) printf("词法错误！"); return; if(Mik=-1) printf("语法错误！"); return; else m=Mik; if(rightm0='') Sstrlen