LL1文法的判別

1、實(shí)驗(yàn)四：LL（1）文法的判別一、 實(shí)驗(yàn)名稱LL（1）文法的判別二、 實(shí)驗(yàn)?zāi)康模?）能導(dǎo)出空串的非終結(jié)符算法（2）實(shí)現(xiàn)首符集，后跟符集和可選集算法（3）輸出要指出是否為L(zhǎng)L（1）文法， 三、 實(shí)驗(yàn)原理 將數(shù)組X 中對(duì)應(yīng)每一非終結(jié)符的標(biāo)記置初值為"未定"。 掃描文法中的產(chǎn)生式。(a) 刪除所有右部含有終結(jié)符的產(chǎn)生式，若這使得以某一非終結(jié)符為左部的所有產(chǎn)生式都被刪除，則將數(shù)組中對(duì)應(yīng)該非終結(jié)符的標(biāo)記值改為"否"，說(shuō)明該非終結(jié)符不能推出。(b) 若某一非終結(jié)符的某一產(chǎn)生式右部為，則將數(shù)組中對(duì)應(yīng)該非終結(jié)符的標(biāo)志置為"是"，并從文法中刪除該非終結(jié)符

2、的所有產(chǎn)生式。例中對(duì)應(yīng)非終結(jié)符A、B的標(biāo)志改為"是"。 掃描產(chǎn)生式右部的每一符號(hào)。(a) 若所掃描到的非終結(jié)符號(hào)在數(shù)組中對(duì)應(yīng)的標(biāo)志是"是"，則刪去該非終結(jié)符，若這使產(chǎn)生式右部為空，則對(duì)產(chǎn)生式左部的非終結(jié)符在數(shù)組中對(duì)應(yīng)的標(biāo)志改"是"，并刪除該非終結(jié)符為左部的所有產(chǎn)生式。(b) 若所掃描到的非終結(jié)符號(hào)在數(shù)組中對(duì)應(yīng)的標(biāo)志是"否"，則刪去該產(chǎn)生式，若這使產(chǎn)生式左部非終結(jié)符的有關(guān)產(chǎn)生式都被刪去，則把在數(shù)組中該非終結(jié)符對(duì)應(yīng)的標(biāo)志改成"否"。 重復(fù)，直到掃描完一遍文法的產(chǎn)生式，數(shù)組中非終結(jié)符對(duì)應(yīng)的特征再?zèng)]有改

3、變?yōu)橹?。由?a) 、(b)得知例中對(duì)應(yīng)非終結(jié)符D的標(biāo)志改為"否"，對(duì)應(yīng)非終結(jié)符A、B的標(biāo)志改為"是"。經(jīng)過(guò)上述中(a)、(b)兩步后文法中的產(chǎn)生式只剩下：SAB和CAD ，也就是只剩下右部全是非終結(jié)符串的產(chǎn)生式。再由中的(a)步掃描到產(chǎn)生式SAB時(shí)，在數(shù)組中A、B對(duì)應(yīng)的標(biāo)志都為"是"，刪去后S的右部變?yōu)榭?，所以S對(duì)應(yīng)標(biāo)志置為"是"。最后由中的(b)掃描到產(chǎn)生式CAD時(shí)，其中，A對(duì)應(yīng)的標(biāo)志為"是"，D對(duì)應(yīng)的標(biāo)志是"否"，刪去該產(chǎn)生式后，再無(wú)左部為C的產(chǎn)生式，所以C的對(duì)應(yīng)標(biāo)志改

4、為"否"四、 實(shí)驗(yàn)小結(jié)通過(guò)本次實(shí)驗(yàn)，熟悉了LL（1）文法，掌握了LL（1）文法的判定方法，具體實(shí)踐了FIRST集、FOLLOW集、SELECT集的計(jì)算，加深了對(duì)LL（1）文法的理解。此外，將理論用于實(shí)踐，親身體會(huì)到了怎樣求FIRST集等。如何理解轉(zhuǎn)化的過(guò)程是相當(dāng)重要，以及如何去創(chuàng)建程序去實(shí)現(xiàn)這一轉(zhuǎn)化過(guò)程。這樣的編程對(duì)于我來(lái)說(shuō)是相當(dāng)困難的，這次的程序并非自己編寫(xiě)的。但是我會(huì)一步步去理解該程序的每步含義，爭(zhēng)取就算自己不會(huì)編寫(xiě)代碼，但至少做到實(shí)現(xiàn)過(guò)程、步驟。通過(guò)實(shí)驗(yàn)進(jìn)一步理解編譯原理這門(mén)課程，知道這么可是多么難學(xué)，知道和理解了該理論在計(jì)算機(jī)中是怎樣執(zhí)行的，對(duì)該理論在實(shí)踐中的應(yīng)用有

5、深刻的理解。在這次課程設(shè)計(jì)中，我們組就是按照實(shí)驗(yàn)指導(dǎo)的思想來(lái)完成，加強(qiáng)培養(yǎng)實(shí)踐動(dòng)手能力和程序開(kāi)發(fā)能力。五、 附錄#include<stdio.h>#include<string.h>int count=0; /*分解的產(chǎn)生式的個(gè)數(shù)*/int number; /*所有終結(jié)符和非終結(jié)符的總數(shù)*/char start; /*開(kāi)始符號(hào)*/char termin50; /*終結(jié)符號(hào)*/char non_ter50; /*非終結(jié)符號(hào)*/char v50; /*所有符號(hào)*/char left50; /*左部*/char right5050; /*右部*/char first5050,

6、follow5050; /*各產(chǎn)生式右部的FIRST和左部的FOLLOW集合*/char first15050; /*所有單個(gè)符號(hào)的FIRST集合*/char select5050; /*各單個(gè)產(chǎn)生式的SELECT集合*/char f50,F50; /*記錄各符號(hào)的FIRST和FOLLOW是否已求過(guò)*/char empty20; /*記錄可直接推出的符號(hào)*/char TEMP50; /*求FOLLOW時(shí)存放某一符號(hào)串的FIRST集合*/int validity=1; /*表示輸入文法是否有效*/int ll=1; /*表示輸入文法是否為L(zhǎng)L(1)文法*/int M2020; /*分析表*/ch

7、ar choose; /*用戶輸入時(shí)使用*/char empt20; /*求_emp()時(shí)使用*/char fo20; /*求FOLLOW集合時(shí)使用*/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*/判斷一個(gè)字符是否在指定字符串中char c()char c='A' while(in(c,non_ter)=1)c+;return(c);/得到一個(gè)不是非終結(jié)符的符號(hào)voi

8、d recur(char *point)/ 分解含有左遞歸的產(chǎn)生式 /*完整的產(chǎn)生式在point中*/ int j,m=0,n=3,k;char temp20,ch;ch=c(); /*得到一個(gè)非終結(jié)符*/k=strlen(non_ter);non_terk=ch;non_terk+1='0'for(j=0;j<=strlen(point)-1;j+) if(pointn=point0) /*如果|后的首符號(hào)和左部相同*/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 /*如果|后的首符號(hào)和左部不同*/ 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)/ 分解不含有左遞歸的產(chǎn)生式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)/讀入一個(gè)文法char vn50,vt50; char s; char p5050; int i,j,k; printf("請(qǐng)輸入文法的非終結(jié)符號(hào)串："); scanf("%s",vn); getchar(); i=strlen(vn); memcpy(n,vn,i); ni='0' printf("請(qǐng)輸入文法的終結(jié)符號(hào)串："); scanf("%s",vt); getchar(); i=strlen(vt); memcpy(t,vt,i); ti='0&#

13、39; printf("請(qǐng)輸入文法的開(kāi)始符號(hào)："); scanf("%c",&s); getchar(); printf("請(qǐng)輸入文法產(chǎn)生式的條數(shù)："); scanf("%d",&i); getchar(); for(j=1;j<=i;j+) printf("請(qǐng)輸入文法的第%d條（共%d條）產(chǎn)生式：",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'); /*檢測(cè)輸入錯(cuò)誤*/ for(k=0;k<=i-1;k+) /*分解輸入的各產(chǎn)生式*/ if(pk3=pk0) recur(pk); else non_re(pk); return(s);void merge(char *d,char *s,int type)/將單個(gè)符號(hào)或符號(hào)串并入另一符號(hào)串/*d是目標(biāo)符號(hào)串，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)/求所有能直接推出的符號(hào)/*即求所有由 推出的符號(hào)*/ 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)/ 求某一符號(hào)能否推出 /*若能推出，返回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) /*找一個(gè)左部為c的產(chǎn)生式*/ j=strlen(r

17、ighti); /*j為右部的長(zhǎng)度*/ 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) /*若左部不在非終結(jié)符中，報(bào)錯(cuò)*/ 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!='') /*若右部某一符號(hào)不在非終結(jié)符、終結(jié)符中且不為，報(bào)錯(cuò)*/ printf("nerror2!");validity=0;return(0); return(1); void first2(int i)/求單個(gè)符號(hào)的FIRST/*i為符號(hào)在所有輸入符號(hào)中的序號(hào)*/ char c,temp20; int j,k,m; char ch='' c=vi; emp(ch); if(in(c,termin)=1) /*若為終結(jié)符*/

20、first1i0=c; first1i1='0' else if(in(c,non_ter)=1) /*若為非終結(jié)符*/ 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) /求各產(chǎn)生式右部的FIRST int length; int j,k,m; char temp20; length=strlen(p); if(length=1) /*如果右部為單個(gè)符號(hào)*/ 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 /*如果右部為符號(hào)串*/ 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) /求各產(chǎn)生式左部的FOLLOW int j,k,m,n,result=1; char c,temp20; c=non_teri; /*c為待求的非終結(jié)符*/ temp0=c; temp1='0' merge(fo,temp,1); if(c=start) /*若為開(kāi)始符號(hào)*/ temp0='#' temp1='0' merge(fo

26、llowi,temp,1); for(j=0;j<=count-1;j+) if(in(c,rightj)=1) /*找一個(gè)右部含有c的產(chǎn)生式*/ for(k=0;k+) if(rightjk=c) break; /*k為c在該產(chǎn)生式右部的序號(hào)*/ for(m=0;m+) if(vm=leftj) break; /*m為產(chǎn)生式左部非終結(jié)符在所有符號(hào)中的序號(hào)*/ if(k=strlen(rightj)-1) /*如果c在產(chǎn)生式右部的最后*/ 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不在產(chǎn)生式右部的最后*/ for(n=k+1;n<=strlen(rightj)-1;n+) empt0='0' result*=_emp(rightjn); if(result=1) /*如果右部c后面的符號(hào)串能推出*/ if(in(vm,fo)=1) /*避免循環(huán)遞歸*/ 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() /判斷讀入文法是否為一個(gè)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); /*求單個(gè)符號(hào)的FIRST集合*/ printf("n單個(gè)符號(hào)的FIRST集合為:"); for(j=0;j<=strlen(v)-1;j+) printf("%c:%s ",vj,first1j); printf("n能推出的非終結(jié)符:%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每個(gè)產(chǎn)生式右部符號(hào)串的FIRST集合為:"); for(i=0;i<

31、=count-1;i+) printf("%s ",firsti); printf("n每個(gè)非終結(jié)符的FOLLOW集合為:"); for(i=0;i<=strlen(non_ter)-1;i+) printf("%s ",followi); for(i=0;i<=count-1;i+) /*求每一產(chǎn)生式的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每個(gè)產(chǎ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+) /*判斷輸入文法是否為L(zhǎng)L(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、構(gòu)造分析表M int i,j,k,m; for(i=0;i<=19;i+) for(j=0;j<=19;j+) Mij=-1; i=strlen(termin); termini='#' /*將#加入終結(jié)符數(shù)組*/ termini+1='0' for(i=0;i<=count-1;i+) for(m=0;m+) if(non_term=lefti) break; /*m為產(chǎn)生式左部非終結(jié)符的序號(hào)*/ for(j=0;j<=strlen(selecti)-1;j+) if(in(selectij,termin)=1) for(k=0;k+)

35、 if(termink=selectij) break; /*k為產(chǎn)生式右部終結(jié)符的序號(hào)*/ Mmk=i; void syntax() /總控算法 int i,j,k,m,n,p,q; char ch; char S50,str50; printf("請(qǐng)輸入該文法的句型："); 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("該符號(hào)串不是文法的句型！"); return; else if(Sstrlen(S)-1='#') printf("該符號(hào)串是文法的句型."); 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("詞法錯(cuò)誤！"); return; if(Mik=-1) printf("語(yǔ)法錯(cuò)誤！"); return; else m=Mik; if(rightm0='') Sstrlen