《編譯原理》語法分析器實(shí)驗(yàn)報(bào)告模板

1、課程設(shè)計(jì)報(bào)告課程名稱編譯原理實(shí)驗(yàn)項(xiàng)目設(shè)計(jì)與實(shí)現(xiàn)一個(gè)詞法分析器實(shí)驗(yàn)儀器PC機(jī)北京信息科技大學(xué)信息管理學(xué)院（課程上機(jī)）實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱設(shè)計(jì)與實(shí)現(xiàn)一個(gè)語法分析器實(shí)驗(yàn)地點(diǎn)信管機(jī)房204實(shí)驗(yàn)時(shí)間2011.12.201.實(shí)驗(yàn)?zāi)康模航Y(jié)合講授內(nèi)容，進(jìn)一步培養(yǎng)學(xué)生編譯器設(shè)計(jì)的思想，加深對編譯原理和應(yīng)用程序的理解，針對編譯過程的重點(diǎn)和難點(diǎn)內(nèi)容進(jìn)行編程，獨(dú)立完成有一定工作量的語法分析程序設(shè)計(jì)任務(wù)，問時(shí)強(qiáng)調(diào)好的程序設(shè)計(jì)風(fēng)格。2. 實(shí)驗(yàn)內(nèi)容：對輸入的文法判定是否為LL(1)文法，若是LL(1)文法，則構(gòu)造LL(1)分析表，輸入一個(gè)句子，依據(jù)LL(1)分析表輸出與句子對應(yīng)的語法樹。設(shè)計(jì)LL(1)文法的詞法分析器。3. 實(shí)

2、驗(yàn)要求：(1) 輸入一個(gè)文法G(如：測試數(shù)據(jù)1);(2) 編寫求FIRST集的算法；輸出文法G的First集；(3) 編寫求FOLLOW集的算法；輸出文法G的FOLLOW集；(4) 編寫求SELECT的算法，輸出文法G的SELECT集；(5) 判定是否為LL(1)文法，若是，則編寫構(gòu)造LL(1)分析表的算法，并輸出預(yù)測分析表(6) 編寫表驅(qū)動(dòng)的預(yù)測分析算法；(7) 給出輸入一個(gè)句子(如：測試數(shù)據(jù)2)的預(yù)測分析步驟；(8) 輸出依據(jù)句子構(gòu)對應(yīng)的語法樹的過程；(9) 構(gòu)造文法G的遞歸子程序；(選作)測試數(shù)據(jù)1:(若用其它測試數(shù)據(jù)，請?zhí)鎿Q下面內(nèi)容)輸入文法G:S-aHH-aMd|dM-Ab|A-aM

3、|e測試數(shù)據(jù)2:輸入句子：aaabd#4. 實(shí)驗(yàn)準(zhǔn)備:#include#include#include/*/intcount=0;intnumber;charstart;chartermin50;charnon_ter50;charv50;charleft50;charright5050;5. 實(shí)驗(yàn)過程:/*分解的產(chǎn)生式的個(gè)數(shù)*/*所有終結(jié)符和非終結(jié)符的總數(shù)*/*開始符號(hào)*/*終結(jié)符號(hào)*/*非終結(jié)符號(hào)*/*所有符號(hào)*/*左部*/charfirst5050,follow5050;charfirst15050;charselect5050;charf50,F50;charempty20;charT

4、EMP50;intvalidity=1;intll=1;intM2020;charchoose;charempt20;charfo20;/*右部*/*各產(chǎn)生式右部的FIRST和左部的FOLLOW集合*/*所有單個(gè)符號(hào)的FIRST集合*/*各單個(gè)產(chǎn)生式的SELECT集合*/*記錄各符號(hào)的FIRST和FOLLOW是否已求過*/*記錄可直接推出的符號(hào)*/*求FOLLOW時(shí)存放某一符號(hào)申的FIRST集合*/*表示輸入文法是否有效*/*表示輸入文法是否為LL(1)文法*/*分析表*/*用戶輸入時(shí)使用*/*求_emp()時(shí)使用*/*求FOLLOW集合時(shí)使用*/*判斷一個(gè)字符是否在指定字符申中*/intin

5、(charc,char*p)inti;if(strlen(p)=0)return(0);for(i=0;i+)if(pi=c)/*若在，返回1*/*若不在，返回0*/return(1);if(i=strlen(p)return(0);/*得到一個(gè)不是非終結(jié)符的符號(hào)*/charc()(charc=A;while(in(c,non_ter)=1)c+;return(c);/*分解含有左遞歸的產(chǎn)生式*/voidrecur(char*point)(/*完整的產(chǎn)生式在point中*/intj,m=0,n=3,k;chartemp20,ch;ch=c();/*得到一個(gè)非終結(jié)符*/k=strlen(non_

6、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!=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)和左部不同*/left

7、count=ch;rightcount0=;rightcount1=0;count+;for(j=n;j=strlen(point)-1;j+)(if(pointj!=|)tempm+=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;vo

8、idnon_re(char*point)intm=0,j;chartemp20;for(j=3;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;/*讀入一個(gè)文法*/chargrammer(char*t,char*n,char*left,charright5050)(cha

9、rvn50,vt50;chars;charp5050;inti,j,k;printf(-請輸入文法的非終結(jié)符號(hào)申：);scanf(%s,vn);getchar();i=strlen(vn);memcpy(n,vn,i););ni=0;printf(-請輸入文法的終結(jié)符號(hào)申：scanf(%s,vt);getchar();i=strlen(vt);memcpy(t,vt,i););ti=0;printf(請輸入文法的開始符號(hào)：scanf(%c,&s);getchar(););printf(-請輸入文法產(chǎn)生式的條數(shù)：scanf(%d,&i);getchar();for(j=0;ji;j+)(prin

10、tf(”請輸入文法的第d條(共d條)產(chǎn)生式：,j,i);scanf(%s,pj);/二維數(shù)組首地址傳遞平p,pi第i行第0列首地址，p+i表示第i行首地址if(strcmp(pj,xxx)=0)/(j=j-2;getchar();for(j=0;j)(printf(ninputerror!);validity=0;return(0);/*檢測輸入錯(cuò)誤*/for(k=0;k=i-1;k+)(/*分解輸入的各產(chǎn)生式*/if(pk3=pk0)recur(pk);elsenon_re(pk);return(s);/*將單個(gè)符號(hào)或符號(hào)申并入另一符號(hào)申*/voidmerge(char*d,char*s,i

11、nttype)(/*d是目標(biāo)符號(hào)申,s是源申,type=1,源申中的一并并入目申;type=2,源申中的不并入目申*/inti,j;for(i=0;i=strlen(s)-1;i+)(if(type=2&si=);else(for(j=0;j+)(if(jstrlen(d)&si=dj)break;if(j=strlen(d)(dj=si;dj+1=0;break;_/*求所有能直接推出的符號(hào)*/voidemp(charc)/*即求所有由推出的符號(hào)*/chartemp10;inti;for(i=0;iBB-return(1);elseif(j=1&in(righti0,termin)=1&le

12、fti+1!=c)/A-a,A-sB,S-,B-return(0);elseif(j=1&in(righti0,termin)=1&lefti+1=c)continue;elsefor(k=0;kAmark=1;if(mark=1)continue;elsefor(k=0;k=j-1;k+)result*=_emp(rightik);/太漂亮了temp0=rightik;temp1=0;merge(empt,temp,1);if(result=0&iBa,A-S,S-,B!-找下一個(gè)做不為的-Ccontinue;elseif(result=1&icount)return(1);/*判斷讀入的文

13、法是否正確*/intjudge()inti,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,nonter)=0&in(rightij,termin)=0&rightij!=)(/*若右部某一符號(hào)不在非終結(jié)符、終結(jié)符中且不為,報(bào)錯(cuò)*/printf(nerror2!);validity=0;return(0);return(1);/*求單個(gè)符號(hào)的FIRST求

14、出每個(gè)符號(hào)的first并且將其存入first1*/voidfirst2(inti)(/*i為符號(hào)在所有輸入符號(hào)中的序號(hào)*/charc,temp20;intj,k,m;c=vi;charch=;emp(ch);if(in(c,termin)=1)/*若為終結(jié)符*/(first1i0=c;first1i1=0;elseif(in(c,non_ter)=1)/*若為非終結(jié)符*/(for(j=0;j或者A-a(temp0=rightj0;temp1=0;merge(first1i,temp,1);elseif(in(rightj0,non_ter)=1)左部非終結(jié)符并且右部為非終結(jié)符(if(right

15、j0=c)/A-A.尋找下一個(gè)Acontinue;for(k=0;k+)/A-B。無限循環(huán)，找至UB的位置if(vk=rightj0)break;if(fk=0)(first2(k);/M-A.此時(shí)找出A的位置在M之后，而A的first沒有求過，所以要返回求fk=1;merge(first1i,first1k,2);/A-B則將B對應(yīng)符號(hào)表位置找出，然后將Bfirst1復(fù)制給Afor(k=0;k=strlen(rightj)-1;k+)/二位數(shù)組strlen(right。)表示第j行的長度(empt0=0;if(_emp(rightjk)=1&kABA-則找到B的位置，求B的firstbrea

16、k;if(fm=0)(first2(m);fm=1;merge(first1i,first1m,2);elseif(_emp(rightjk)=1&k=strlen(rightj)-1)(temp0=;temp1=0;merge(first1i,temp,1);elsebreak;fi=1;/*求各產(chǎn)生式右部的FIRST*/voidFIRST(inti,char*p)(intlength;intj,k,m;chartemp20;length=strlen(p);/*如果右部為單個(gè)符號(hào)*/if(length=1)(if(p0=)(if(i=0)(firsti0=;firsti1=0;else(T

17、EMP0=;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(firsti,first1j,2);elsemerge(TEMP,first1j,2);for(k=0;k=length-1;k+)

18、(empt0=0;if(_emp(pk)=1&k=0)merge(firsti,first1m,2);elsemerge(TEMP,first1m,2);elseif(_emp(pk)=1&k=length-1)(temp0=;temp1=0;if(i=0)merge(firsti,temp,1);elsemerge(TEMP,temp,1);elseif(_emp(pk)=0)break;/*求各產(chǎn)生式左部的FOLLOW*/voidFOLLOW(inti)(intj,k,m,n,result=1;charc,temp20;c=non_teri;/*c為待求的非終結(jié)符*/temp0=c;tem

19、p1=0;merge(fo,temp,1);if(c=start)/*若為開始符號(hào)*/temp0=#;temp1=0;merge(followi,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(follo

20、wi,followm,1);continue;if(Fm=0)FOLLOW(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)申能推出A*/if(in(vm,fo)=1)/*避免循環(huán)遞歸*/merge(followi,followm,1);continue;if(Fm=0)FOLLOW(m);Fm=1;merge(followi,followm,1);for(n=k+

21、1;n=strlen(rightj)-1;n+)tempn-k-1=rightjn;tempstrlen(rightj)-k-1=0;FIRST(-1,temp);merge(followi,TEMP,2);Fi=1;/*判斷讀入文法是否為一個(gè)LL(1)文法*/intll1()inti,j,p,length,result=1;chartemp50;for(j=0;j=49;j+)/*初始化*/firstj0=0;followj0=0;first1j0=0;selectj0=0;TEMPj=0;tempj=0;fj=0;Fj=0;for(j=0;j=strlen(v)-1;j+)first2(j

22、);/*求單個(gè)符號(hào)的FIRST集合*/printf(n各非終結(jié)符導(dǎo)出的first集:);for(j=0;j=strlen(v)-1;j+)printf(%c:%s,vj,first1j);printf(n能導(dǎo)空的非終結(jié)符集合：s,empty);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(nfollow集合:);for(i=0;i=strlen(non_ter)-1;i+)printf(%s,foll

23、owi);for(i=0;i=count-1;i+)for(j=0;j=strlen(firsti)-1;j+)/*求每一產(chǎn)生式的SELECT集合*/if(firstij=)merge(selecti,firsti,2);for(p=0;p+)if(vp=lefti)break;merge(selecti,followp,1);elseif(j=strlen(firsti)-1)merge(selecti,firsti,1);printf(nselect集合順序是:);for(i=0;i=count-1;i+)printf(%s,selecti);memcpy(temp,select0,str

24、len(select0);tempstrlen(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);/*構(gòu)造分析表M*/voidMM()(inti,j,k,m;for(i=

25、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)*/存儲(chǔ)序號(hào)而不存儲(chǔ)內(nèi)容，節(jié)省內(nèi)存！for(j=0;j=0;n-)Sp+=rightmn;Sq+strlen(rightm)=0;printf(S:%sstr:,S);for(p=j;p=strlen(str)-1;p+)printf(%c,strp);printf(n);/*一個(gè)用

26、戶調(diào)用函數(shù)*/voidmenu()(syntax();printf(n是否繼續(xù)？(yorn):);scanf(%c,&choose);getchar();while(choose=y)(menu();/*主函數(shù)*/voidmain()(/*讀入一個(gè)文法*/inti,j;start=grammer(termin,non_ter,left,right);printf(count=%d,count);printf(n開始符號(hào)為:%c,start);strcpy(v,non_ter);strcat(v,termin);printf(n所有符號(hào)集為:%s,v);printf(n非終結(jié)符集合:(%s,non_ter);printf();printf(n終結(jié)符集合:(%s,termin);printf();printf(n文法所有右邊表達(dá)式依次是：，for(i=0;i=count-1;i+)printf(%s,righti);printf(n文法所有左邊開始符依次是：)；for(i=0;i=count-1;i+)printf(%c,lefti);if(validity=1)validity=judge();/printf(nvalid