實(shí)驗(yàn)3預(yù)測分析法模板

1、實(shí)驗(yàn)三一、分析語法分析部分我們我們采用 LL ( 1)方法實(shí)現(xiàn)，采用 LL ( 1)方法實(shí)現(xiàn)語法發(fā)分析要 求文法滿足以下要求：一個(gè)文法能否用確定的自頂向下分析與文法中相同左部的每個(gè)產(chǎn)生式右部的開始符號 集合有關(guān)，當(dāng)有右部能=*= 時(shí)則與其左部非終結(jié)符的后跟符號集合也有關(guān)，此外在產(chǎn)生 式中不存在左遞歸， 無回溯。它的基本思想是從左到右掃描源程序，同時(shí)從識別符號開始生成句子的最左推導(dǎo)，并只向前查看一個(gè)輸入符號，便能唯一確定應(yīng)選擇的規(guī)則。下面將確切地定義滿足確定的自頂向下分析條件的文法即LL(1)文法及LL(1)文法的判別并介紹如何對非LL(1)文法進(jìn)行等價(jià)變換問題，也就是消除一個(gè)文法中的左遞歸和左

2、公共 因子。注意：一個(gè)文法中含有左遞歸和左公共因子絕對不是LL(1)文法，所以也就不可能用確定的自頂向下分析法，對此結(jié)論可以證明。 然而，某些含有左遞歸和左公共因子的文法在通過等價(jià) 變換把它們消除以后可能變?yōu)長L(1)文法，但需要用LL(1)文法的定義判別，也就是說文法中不含左遞歸和左公共因子，只是 LL(1)文法的必要條件。LL(1)文法的定義(5種定義)：一個(gè)文法符號串的開始符號集合定義如下：定義1.設(shè)G=(VT , VN , S, P)是上下文無關(guān)文法，a是任意的文法符號串,FIRST( a )是從a推導(dǎo)出的串的開始符號的終結(jié)符集合。= ，則規(guī)定 FIRST( a ).的情況則必須知道該

3、非終結(jié)符的 為此，我們定義一個(gè)文法非終結(jié)FIRST( a )=a| a =*=a 3 ,a VT , a ,3 V*若 a當(dāng)一個(gè)文法中相同左部非終結(jié)符的右部存在能=后跟符號的集合中是否含有其它右部開始符號集合的元素。 符的后跟符號的集合如下：定義2.設(shè)G=(VT , VN , S, P)是上下文無關(guān) 文法，A VN , S是開始符號FOLLOW(A)= a|S=*= 卩 A 3 且 a VT , a FIRST( 3 ),卩 若S=*=卩A 3，且3 ,則# FOLLOW(A) o也可定義為：Aa ,a VT若有S=*=A，則規(guī)定# FOLLOW(A)這里我們用#作為輸入串的結(jié)束符，或稱為句子

4、括號，如：定義3.給定上下文無關(guān)文法的產(chǎn)生式A T aSELECT(A T a )=FIRST( a )如果 a =*= ，貝U SELECT(A t a )=FIRST( a ) U FOLLOW(A) FIRST( a )的非 元素。更進(jìn)一步可以看出能夠使用自頂向下分析技術(shù)必須使文法滿足如下條件， 件的文法為LL(1)文法，其定義為：定義4. 一個(gè)上下文無關(guān)文法是 LL(1)文法的充分必要條件是： 對每個(gè)非終結(jié)符A的兩個(gè)不同產(chǎn)生式，SELECT(A T 3 )=空，其中a , 3不同時(shí)能 .定義5. LL (1)文法也可定義為：一個(gè)文法G是LL (1)的，當(dāng)且僅當(dāng)對于式AT a |3，下面

5、的條件成立：(1)FIRST ( a)n FIRST( 3 )=空,也就是= VT* , 3 V+ FOLLOW(A)=a|S=*=#輸入串#O,A VN, a V*,若 a= ,則O FIRST( a )表示我們稱滿足條SELECT(A Ta ) AG的每一個(gè)非終結(jié)符 A的任何兩個(gè)不同產(chǎn)生a和3推導(dǎo)不出以某個(gè)相同的終結(jié)符a為首的符號串；它們不應(yīng)該都能推出空字 .假若B = 那么，F(xiàn)IRST ( a )n FOLLOW (A)=空也就是，若3 = 則a所能 推出的串的首符號不應(yīng)在 FOLLOW(A)中。二、算法該程序可分為如下幾步：(1) 讀入文法(2) 判斷正誤(3) 若無誤，判斷是否為LL

6、(1)文法(4) 若是，構(gòu)造分析表；根據(jù)下面1、先手工建立LL(1)分析表；2、分析輸入串，判斷是否是語法上正確的句子，并輸出整個(gè)分析過程。LL(1)文法G為：EETTFLL(1)文法，對輸入串W： (i+i)*(i+i)+i*i 進(jìn)行LL(1)分析，要求如下F判斷句型1F是LL(1)文法?結(jié)束報(bào)錯(cuò)7 TE7+TE |7 FT7 *FT |7 (E)|id編譯原理實(shí)驗(yàn)報(bào)告3分析算法： 輸入：串W和文法G的分析表M。輸出：如果 W屬于L ( G),則輸出W的最左推導(dǎo)，否則報(bào)告錯(cuò)誤。方法：開始時(shí)，#S在分析棧中，其中S是文法的開始符號，在棧頂；令指針 ip指向W#的第一個(gè)符號；rep eat讓X等

7、于棧頂符號，a為ip所指向的符號；if X 是終結(jié)符號或# thenIf X=a then把X從棧頂彈出并使ip指向下一個(gè)輸入符號else error()else /*X是非終結(jié)符號*/cy1y2 yk the n beginX ;把yk,yk-1,y1壓入棧，y1在棧頂;X cy1y2 yk ； endif Mx,a=X從棧中彈出輸出產(chǎn)生式else error() un til X=#/*棧空*/三、設(shè)計(jì)目的：(1) 理解和掌握LL(1)語法分析方法的基本原理；根據(jù)給出的LL(1)文法，掌握LL(1)分析 表的構(gòu)造及分析過程的實(shí)現(xiàn)。LL(1)分析。(2) 掌握預(yù)測分析程序如何使用分析表和棧聯(lián)

8、合控制實(shí)現(xiàn)四、實(shí)現(xiàn)環(huán)境和要求選擇實(shí)習(xí)環(huán)境為 486以上CPU,4M內(nèi)存,TURBO C2.0語言.實(shí)現(xiàn)程序見附錄. 具體的實(shí)現(xiàn)要求：(1) 對輸入文法，它能判斷是否為LL(1)文法，若是，則轉(zhuǎn)(2);否則報(bào)錯(cuò)并終止;(2) 輸入已知文法，由程序自動(dòng)生成它的LL(1)分析表；實(shí)驗(yàn)三for(j=0;j#includevstdio.h#includeint count=0;int number;/*分解的產(chǎn)生式的個(gè)數(shù)*/*所有終結(jié)符和非終結(jié)符的總數(shù)*/char start;/*開始符號*/char termin50;char non_ter50;/*終結(jié)符號*/*非終結(jié)符號*/char v50;/*

9、所有符號*/char left50;char right5050;/*左部*/*右部*/char first5050,follow5050;/*所有單個(gè)符號的FIRST集合*/*各產(chǎn)生式右部的 FIRST和左部的FOLLOW 集合*/char first15050;char select5050;/*各單個(gè)產(chǎn)生式的 SELECT集合*/char f50,F50;/*記錄各符號的 FIRST和FOLLOW 是否已求過*/char emp ty20;/*記錄可直接推出A的符號*/char TEMP 50;int validity=1;/*求FOLLOW時(shí)存放某一符號串的 FIRST集合*/*表示輸

10、入文法是否有效*/int ll=1;/*表示輸入文法是否為LL(1)文法*/int M2020;/*分析表*/char choose;/*用戶輸入時(shí)使用*/char emp t20;/*求_emp()時(shí)使用*/char fo20;/*求FOLLOW集合時(shí)使用*/*判斷一個(gè)字符是否在指定字符串中*/ int in(char c,char *p)int i;if(strlen (p)=0)return(0);for(i=0;i+)if(p i=c)return(1);/*若在，返回1*/if(i=strlen( p)return(0);/*若不在，返回0*/*得到一個(gè)不是非終結(jié)符的符號*/ cha

11、r c()char c=A;while(in(c,non_ter)=1)c+;return(c);/*分解含有左遞歸的產(chǎn)生式*/ void recur(char *po int)/*完整的產(chǎn)生式在point中*/int j,m=0,n=3,k;char temp 20,ch;ch=c();/*得到一個(gè)非終結(jié)符*/k=strlen(non_ter);non_terk=ch;non_terk+1=0;if(po intn=po intO)/*如果 I后的首符號和左部相同*/for(j=n+1;jv=strlen (po int)-1;j+)while( pointj!=T&p ointj!=、O)

12、temp m+=po intj+;leftcount=ch;meme py (nghtcount,te mp, m);rightcountm=ch;rightcountm+1=0;m=0;count+;if(p ointj=T)n=j+1;break;else/*如果 r后的首符號和左部不同*/leftcount=ch;rightcountO=A;rightcount1=O;count+;for(j=n;jv=strlen (po int)-1;j+)if(po intj!=T)temp m+=p ointj;elseleftcount=p ointO;memc py (nghtcount,t

13、e mp, m);rightcountm=ch;rightcountm+1=0;p rintf( count=%d ,count);m=0;count+;leftcount=pointO;memc py (nghtcount,te mp, m); rightcountm=ch;rightcountm+1=0;實(shí)驗(yàn)三count+;m=0;/*分解不含有左遞歸的產(chǎn)生式*/ void non_re(char *po int)int m=0,j;char temp 20;for(j=3;jv=strlen (po int)-1;j+)if(p ointj!=T)temp m+=p ointj;else

14、leftcount=point0;memc py (nghtcount,te mp, m);rightcountm=0;m=0;count+;leftcount=point0;memc py (nghtcount,te mp, m);rightcountm=0;count+;m=0;/*讀入一個(gè)文法*/ char grammer(char *t,char *n,char *left,char right5050)char vn50,vt50;char s;char p5050;int i,j,k;printf（n請輸入文法的非終結(jié)符號串：）;scanf(%s,vn);getchar();i=s

15、trlen(vn);編譯原理實(shí)驗(yàn)報(bào)告9實(shí)驗(yàn)三for(i=0;iv=strlen(s)-1;i+)編譯原理實(shí)驗(yàn)報(bào)告11meme py( n,vn,i);ni=0;printf(請輸入文法的終結(jié)符號串:)；scanf(%s,vt);getchar();i=strlen(vt);meme py(t,vt,i);ti=0;printf(請輸入文法的開始符號:)；seanf(%e, &s);getchar();printf(請輸入文法產(chǎn)生式的條數(shù):)；scanf(%d,&i);getcharO;for(j=1;jv=i;j+)printf(請輸入文法的第 %d條(共%d條)產(chǎn)生式:,j,i);scanf

16、(%s, pj-1);getcharO;for(j=0;jv=i-1;j+)if(p j1!=-ll Pj【2!=)p rintf(n input error!);validity=0;return(0);/*檢測輸入錯(cuò)誤*/for(k=0;kv=i-1;k+)/*分解輸入的各產(chǎn)生式*/if(P k3=pk0)recur( pk);elsenon_re( pk);return(s);/*將單個(gè)符號或符號串并入另一符號串*/void merge(char *d,char *s,int type)/*d是目標(biāo)符號串，s是源串，type= 1, type=2,源串中的A 不并入目串源串中的A 并并入

17、目串;*/int i,j;實(shí)驗(yàn)三if(typ e=2&si=A)elsefor(j=0;j+)if(jstrlen(d)&si=dj)break;if(j=strlen(d)dj=si;dj+1=0;break;/*求所有能直接推出A的符號*/ void emp( char c)/*即求所有由A 推出的符號*/char temp 10;int i;for(i=0;i=count-1;i+)if(righti0=c&strlen(righti)=1)tem p 0=lefti;te mp 1=、0;merge(e mp ty,te mp ,1);emp (lefti);/*求某一符號能否推出*/

18、 int _emp( char c)/*若能推出，返回1;否則，返回0*/int i,j,k,result=1,mark=0;char temp 20;tem p 0=c;編譯原理實(shí)驗(yàn)報(bào)告15tem p1=、0;merge(e mp t,te mp ,1);if(in(c,em pty)=1)retum(1);for(i=0;i+)if(i=count)retum(0);if(lefti=c)/*找一個(gè)左部為c的產(chǎn)生式*/j=strlen(righti);/*j為右部的長度*/if(j=1 &in(righti0,e mp ty)=1)retum(1);else if(j=1 &i n(rig

19、hti0,termin)=1)retum(0);elsefor(k=0;kv=j-1;k+)if(in(righ tik,em pt)=1)mark=1;if(mark=1)continue;elsefor(k=0;k=j-1;k+)result*=_em p(rightik);tem p 0=rightik;te mp 1=、0;merge(e mp t,te mp ,1);if(result=0&ivcount)continue;else if(result=1 &i vcount)return(1);/*判斷讀入的文法是否正確*/ int judge()int i,j;for(i=0;i

20、v=count-1;i+)if(in(lefti,non_ter)=0)/*若左部不在非終結(jié)符中，報(bào)錯(cuò)*/p rintf(nerror1!);validity=0;retum(0);for(j=0；jv=strlen(righti)-1;j+)retum(1);if(in(rightij,non_ter)=0&in(righ tij,termin)=0&righ ti j!=A)/*若右部某一符號不在非終結(jié)符、終結(jié)符中且不為A ,報(bào)錯(cuò)*/p rintf(nerror2!);validity=0;retum(0);/*求單個(gè)符號的 FIRST*/void first2(int i)/*i為符號在

21、所有輸入符號中的序號*/char c,te mp 20;int j,k,m;c=vi;char ch=A;emp (ch);if(in(c,termin)=1)/*若為終結(jié)符*/first1i0=c;first1i1=0;else if(in(c,non_ter)=1)/*若為非終結(jié)符*/for(j=0;j|eaiqX L-dLue 二二 l4sEe6eLUvp-2d專宀命一亙 I4S一二二 l4sEe6g二-言壬)剁S匸(D+蘭-=莖6出巨)一(+uroMLU)OJ言盒(+K L 丄-mwEueESHVKO 艾)0命 2I4S一二二 l4sEe6g(Ogg-|eaiq(-0=莖6匸丄蘭壬(+

22、圭0艾)0-enuRUOO(。“出0=莖6呂一(LMM(euouo=mug)uw as忑X L-dLue 二二 l4sEe6eLUJo=m 呂斤實(shí)驗(yàn)三fi=1;/*求各產(chǎn)生式右部的 FIRST */ void FIRST(int i,char *p)int length;int j,k,m;char temp 20;length=strlen (p);編譯原理實(shí)驗(yàn)報(bào)告21if(length=1)/*如果右部為單個(gè)符號*/if(p 0=)if(i=0)firsti0=A;firsti1=0;elseTEM P 0=A;TEMP 1=、0;elsefor(j=0;j+)if(vj=P0)break

23、;if(i=0)memc py(firs ti ,first1j,strlen(first1j);firstistrlen(first1j)=0;elsememc py(TEMP ,first1j,strlen(first1j);TEMP strlen(first1j)=、0;else/*如果右部為符號串*/for(j=0;j+)if(vj=P 0)break;merge(firsti,first1j,2);elsemerge (TEMP ,first1j,2);for(k=0;kv=length-1;k+)emp t0=0;if(_emp(p k)=1 &k=0)merge(firsti,f

24、irst1m,2);elsemerge (TEMP ,first1m,2);else if(_emp(p k)=1 &k=length-1)tem p 0=A;temp 1=、0;if(i=0)merge(firsti,tem p,1);elsemerge (TEMP ,tem p,1);else if(_e mp(p k)=0)break;/*求各產(chǎn)生式左部的 FOLLOW */ void FOLLOW(int i)int j,k,m,n,result=1;char c,te mp 20;c=non_teri;/*c為待求的非終結(jié)符*/tem p 0=c;temp1=0; merge(fo,

25、te mp ,1);if(c=start)/*若為開始符號*/tem p 0=#;temp 1=、0;merge(followi,te mp ,1);for(j=0;jv=count-1;j+)if(in(c,rightj)=1)/*找一個(gè)右部含有c的產(chǎn)生式*/for(k=0;k+)if(rightjk=c)break;/*k為c在該產(chǎn)生式右部的序號*/for(m=0;m+)if(vm=leftj)break;/*m為產(chǎn)生式左部非終結(jié)符在所有符號中的序號*/if(k=strlen(rightj)-1)c在產(chǎn)生式右部的最后*/*如果if(in(vm,fo)=1)merge(followi,fol

26、lowm,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+)emp t0=0;result*=_emp(rightj n);if(result=1)/*如果右部c后面的符號串能推出A*/實(shí)驗(yàn)三if(in(vm,fo)=1)/*避免循環(huán)遞歸*/ merge(followi,followm,1);continue;if(Fm=O)FOLLOW(m);Fm=1;merge(followi,followm,1);for(n=k

27、+1;nv=strlen(nghtj)-1;n+)tem p n-k-1=rightjn;te mp strlen(rightj)-k-1=、0;FIRST(-1,tem p);merge(followi,TE MP,2);Fi=1;/*判斷讀入文法是否為一個(gè)LL(1)文法*/ int ll1()int i,j,length,result=1;char temp 50;/*初始化*/*求單個(gè)符號的 FIRST集合*/for(j=0;j=49;j+)firstj0=0;followj0=0;first1j0=0;selectj0=0;TEM Pj=、0;tem pj=、0;fj=0;Fj=0;f

28、or(j=0;j=strlen(v)-1;j+)first2(j);p rintf(nfirst1:);編譯原理實(shí)驗(yàn)報(bào)告25for(j=0;jv=strlen(v)-1;j+)p rintf(%c:%s ,vj,first1j);printf(ne mp ty:%s,e mp ty);p rintf(n:n_e mp:);for(j=0;j=strlen(v)-1;j+)printf(%d ,_em p(vj);for(i=0;i=count-1;i+)FIRST(i,righti);/* 求 FIRST*/p rintf(n);for(j=0;j=strlen(non_ter)-1;j+)/

29、* 求 FOLLOW*/if(foj=0)fo0=0;FOLLOW(j); p rintf(nfirst:);for(i=0;i=count-1;i+)printf(%s ,firsti);p rintf(nfollow:);for(i=0;i=strlen(non_ter)-1;i+)p rintf(%s ,followi);for(i=0;i=count-1;i+)/*求每一產(chǎn)生式的 SELECT集合*/memc py (selecti,firsti,strlen(firsti);selectistrlen(firsti)=0;for(j=0;j=strlen(righti)-1;j+)r

30、esult*=_e mp (rightij);if(strlen(righ ti)=1 &righti0=)result=1;if(result=1)for(j=0;j+)if(vj=lefti)break;merge(selecti,followj,1);p rintf(nselect:);for(i=0;i=count-1;i+)p rintf(%s ,selecti);memc py(te mp ,select0,strlen(select0);te mp strlen(select0)=0;for(i=1;i=count-1;i+)/*判斷輸入文法是否為LL(1)文法*/length=

31、strlen(te mp);if(lefti=lefti-1)merge(te mp ,selecti,1);if(strlen(tem p) vlength+strlen(selecti)retum(O);elsetem p 0=、0;memc py (te mp ,selecti,strlen(selecti);te mp strlen(selecti)=、0;retum(1);/*構(gòu)造分析表M*/ void MM()int i,j,k,m;for(i=0;i=19;i+)for(j=0;j=19;j+)Mij=-1;i=strlen(termin);termini=#;/*將#加入終結(jié)符

32、數(shù)組*/termini+1=0;for(i=0;i=count-1;i+)for(m=0;m+)if(non_term=lefti)break;/*m為產(chǎn)生式左部非終結(jié)符的序號*/for(j=0;j=0;n-)Sp+=rightmn;Sq+strlen(rightm)=0;p rintf(nS:%s str:,S);for(p=j;pv=strlen(str)-1; p+)p rintf(%c,str p);prin tf();/*一個(gè)用戶調(diào)用函數(shù)*/ void menu()syntax();printf(n 是否繼續(xù)？ (y or n):);scanf(%c, &choose);getcha

33、rO;while(choose=y)menu();/*主函數(shù)*/ void main()/*讀入一個(gè)文法*/int i,j;start=grammer(termin,non_ter,left,right);p rintf(count=%d,count);p rintf(nstart:%c,start);strc py (v,non_ter); strcat(v,termin);p rintf(nv:%s,v);p nntf(nnon_ter:%s,non_ter);printf(ntermin:%s,termin);p rintf(nright:);for(i=0;i=count-1;i+)p rintf(%s ,righti);p rintf(nleft:);for(i=0;i=0)p rintf(n);menu();5.執(zhí)行結(jié)果（1）輸入一個(gè)文法p rintf(M%d%d=%d ,i,j,Mij);:廠 *D:Turboc2DebuesTnt ai. exe晶瑩-丸委屈miro BBS終開生ww 的盼盼產(chǎn)紛紛紛 文文文文文文文 請請請請請請請串:號串3) =s