試驗3預(yù)測分析法

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

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

3、a , 3 e V*若 a =*= ，則規(guī)定 s 6 FIRST( a ).當一個文法中相同左部非終結(jié)符的右部存在能=*= 的情況則必須知道該非終結(jié)符的后跟符號的集合中是否含有其它右部開始符號集合的元素。為此，我們定義一個文法非終結(jié)符的后跟符號的集合如下：定義2.設(shè)G=(VT , VN , S, P)是上下文無關(guān) 文法，A C VN , S是開始符號FOLLOW(A)= a|S=*= 科 A 3 ,且 a VT , aC FIRST( 3 ),科 C VT* , 3 V+ 若 S=*= w A3 ,且 3 ,則#C FOLLOW(A)。也可定義為：FOLLOW(A)=a|S=*= Aa，a C

4、VT若有 S=*= - A,則規(guī)定 #C FOLLOW(A)這里我們用#作為輸入串的結(jié)束符，或稱為句子括號，如：#輸入串#。定義 3.給定上下文無關(guān)文法的產(chǎn)生式A一 a , AC VN, a V*,若a = e，則SELECT(A - a )=FIRST( a )如果 a =*= s ,貝U SELECT(A 一 a )=FIRST( a )U FOLLOW(A) 。 FIRST( a e )表示 FIRST( a)的非 s 元素。更進一步可以看出能夠使用自頂向下分析技術(shù)必須使文法滿足如下條件，我們稱滿足條件的文法為LL(1)文法，其定義為：定義4. 一個上下文無關(guān)文法是 LL(1)文法的充分

5、必要條件是：對每個非終結(jié)符A的兩個不同產(chǎn)生式，A - a , A 一 3，滿足 SELECT(A - a ) ASELECT(A - 3尸空淇中a , 3不同時能e .定義5. LL (1)文法也可定義為：一個文法G是LL (1)的，當且僅當對于 G的每一個非終結(jié)符 A的任何兩個不同產(chǎn)生 式A-a |3 ,下面的條件成立：(1)FIRST ( a ) A FIRST( 3 )=空,也就是a和3推導不出以某個相同的終結(jié)符a為首的編譯原理實驗報告實驗三符號串；它們不應(yīng)該都能推出空字.(2)假若3=e那么，F(xiàn)IRST(a)n FOLLOW (A)=空也就是，若3 = e則a所能 推出的串的首符號不應(yīng)

6、在FOLLOW(A)中。二、算法該程序可分為如下幾步：(1)讀入文法(2)判斷正誤(3)若無誤，判斷是否為LL(1)文法(4)若是，構(gòu)造分析表；根據(jù)下面LL(1)文法，對輸入串 w: (i+i)*(i+i)+i*i 進行1、先手工建立LL(1)分析表；2、分析輸入串，判斷是否是語法上正確的句子，并輸出整個分析過程。LL(1)文法G為：E - TEE 一+TE | T - FTT 一*FT | F 一 (E)|id分析算法：輸入：串w和文法G的分析表M。輸出：如果 W屬于L (G),則輸出 W的最左推導，否則報告錯誤。方法：開始時，#S在分析棧中，其中 S是文法的開始符號，在棧頂；令指針 ip指

7、向W#的第一個符號；repeat讓X等于棧頂符號，a為ip所指向的符號；if X 是終結(jié)符號或 # thenIf X=a then把X從棧頂彈出并使ip指向下一個輸入符號else error()else /*X是非終結(jié)符號*/if Mx,a=X dy1y2 yk then begin從棧中彈出X;把yk,yk-1,y1壓入棧，y1在棧頂；輸出產(chǎn)生式 X 41y2yk; endelse error()until X=#/* ?？?/編譯原理實驗報告實驗三語法分析的流程算法三、設(shè)計目的：(1)理解和掌握LL(1)語法分析方法的基本原理；根據(jù)給出的 LL(1)文法，掌握LL(1)分析 表的構(gòu)造及分析

8、過程的實現(xiàn)。(2)掌握預(yù)測分析程序如何使用分析表和棧聯(lián)合控制實現(xiàn)LL(1)分析。四、實現(xiàn)環(huán)境和要求選擇實習環(huán)境為 486以上CPU,4M內(nèi)存,TURBO C2.0語言.實現(xiàn)程序見附錄 具體的實現(xiàn)要求：(1)對輸入文法，它能判斷是否為LL(1)文法，若是，則轉(zhuǎn)(2);否則報錯并終止;(2)輸入已知文法，由程序自動生成它的LL(1)分析表;編譯原理實驗報告實驗三(3)對于給定的輸入串，應(yīng)能判斷識別該串是否為給定文法的句型。附錄/*預(yù)測分析程序(語法分析程序)，分析對象為C語言源程序文件。該分析程序有18部分組成：1首先定義各種需要用到的常量和變量； 2判斷一個字符是否在指定字符串中；3得到一個不是

9、非終結(jié)符的符號； 4分解含有左遞歸的產(chǎn)生式；5分解不含有左遞歸的產(chǎn)生式；6讀入一個文法；7將單個符號或符號串并入另一符號串； 8求所有能直接推出 人的符號； 9求某一符號能否推出 人；10判斷讀入的文法是否正確；11求單個符號的 FIRST ;12求各產(chǎn)生式右部的 FIRST;13求各產(chǎn)生式左部的 FOLLOW ; 14判斷讀入文法是否為一個 LL(1)文法；15構(gòu)造分析表M;16總控算法；17 一個用戶調(diào)用函數(shù)； 18主函數(shù)；程序如下：#include#includeint count=0;int number;char start;char termin50;char non_ter50;

10、char v50;char left50;char right5050;#include/*分解的產(chǎn)生式的個數(shù)*/*所有終結(jié)符和非名結(jié)符的總數(shù)*/*開始符號*/*終結(jié)符號*/*非終結(jié)符號*/*所有符號*/*左部*/*右部*/char first5050,follow5050;/*各產(chǎn)生式右部的 FIRST和左部的FOLLOW 集合*/char first15050;/*所有單個符號的FIRST集合*/char select5050;/*各單個產(chǎn)生式的 SELECT集合*/char f50,F50;char empty20;/*記錄可直接推出人的符號*/*記錄各符號的 FIRST和FOLLOW

11、是否已求過*/char TEMP50;int validity=1;/*求FOLLOW時存放某一符號串的 FIRST集合*/*表示輸入文法是否有效*/int ll=1;/*表示輸入文法是否為LL(1)文法*/編譯原理實驗報告實驗三int M2020;char 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)r

12、eturn(1); /*若在，返回 1*/if(i=strlen(p)return(0); /* 若不在，返回 0*/)/*得到一個不是非終結(jié)符的符號*/ char c()(char c=A;while(in(c,non_ter)=1)c+;return(c);) /*分解含有左遞歸的產(chǎn)生式*/void recur(char *point)/*完整的產(chǎn)生式在 point中*/int j,m=0,n=3,k;char temp20,ch;ch=c();/*得到一個非終結(jié)符*/k=strlen(non_ter);non_terk=ch;non_terk+1=0;for(j=0;j=strlen(p

13、oint)-1;j+)編譯原理實驗報告實驗三if(pointn=point0)/*如果|后的首符號和左部相同*/for(j=n+1;j=strlen(point)-1;j+)while(pointj!=T&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/*如果|后的首符號和左部不同*/leftcount=ch;rightcount0=A;rightcount1=0;count

14、+;for(j=n;j=strlen(point)-1;j+)if(pointj!=|)tempm+=pointj;elseleftcount=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;) /*分解不含有左遞歸的產(chǎn)生式*/ void non_re(c

15、har *point)(int m=0,j;char temp20;for(j=3;j=strlen(point)-1;j+)(if(pointj!=T)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 *left,char right5050)

16、(char vn50,vt50;char s;char p5050;int i,j,k;printf(n請輸入文法的非終結(jié)符號串：);scanf(%s,vn);getchar();i=strlen(vn);編譯原理實驗報告實驗三memcpy(n,vn,i);ni=0;printf(請輸入文法的終結(jié)符號串：);scanf(%s,vt);getchar();i=strlen(vt);memcpy(t,vt,i);ti=0;printf(請輸入文法的開始符號：);scanf(%c,&s);getchar();printf(請輸入文法產(chǎn)生式的條數(shù)：);scanf(%d,&i);getchar();fo

17、r(j=1;j=i;j+)printf(請輸入文法的第 %d條(共%d條)產(chǎn)生式：,j,i);scanf(%s,pj-1);getchar();for(j=0;j) printf(ninput error!);validity=0;return(0);/*檢測輸入錯誤*/for(k=0;k=i-1;k+)/*分解輸入的各產(chǎn)生式*/if(pk3=pk0)recur(pk);elsenon_re(pk);return(s);/*將單個符號或符號串并入另一符號串*/void merge(char *d,char *s,int type)/*d是目標符號串，s是源串，type=1,源串中的人一并并入目

18、串;type=2,源串中的人不并入目串*/int i,j;for(i=0;i=strlen(s)-1;i+)編譯原理實驗報告實驗三if(type=2&si=A)1else (for(j=0;j+)(if(jstrlen(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)temp0=lefti;temp1=0;mer

19、ge(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的產(chǎn)生式*/( j=strlen(righti); /*j 為右部的長度 */if(j=1&in(righti0,e

20、mpty)=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,1); if(result=0&icount)continue;else if(result=1&icount)return(1);/*判斷讀入的文法是否正確*/int

21、 judge()10編譯原理實驗報告實驗三(int i,j;for(i=0;i=count-1;i+)(if(in(lefti,non_ter)=0)/*若左部不在非終結(jié)符中，報錯 */printf(nerror1!);validity=0;return(0);)for(j=0;j=strlen(righti)-1;j+)if(in(rightij,non_ter)=0&in(rightij,termin)=0&rightij!=A)/*若右部某一符號不在非終結(jié)符、終結(jié)符中且不為printf(nerror2!);validity=0;return(0);)return(1);)*/*求單個符號

22、的 FIRST*void first2(int i)/*i為符號在所有輸入符號中的序號*/char c,temp20;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=count-1;j+)if(leftj=c)if(in(rightj0,termin)=1|rightj0=A，)人，報錯*/11編譯原理實驗報告實驗三(temp0=rightj0;temp1=0;merge(first1

23、i,temp,1);)else if(in(rightj0,non_ter)=1)(if(rightj0=c)continue;for(k=0;k+)if(vk=rightj0)break;if(fk=0)(first2(k);fk=1;)merge(first1i,first1k,2);for(k=0;k=strlen(rightj)-1;k+)(empt0=0;if(_emp(rightjk)=1&k=0)(firsti0=A;firsti1=0;)else(TEMP0=A;TEMP1=0;)else(for(j=0;j+)if(vj=p0)break;if(i=0)(memcpy(fir

24、sti,first1j,strlen(first1j);firstistrlen(first1j)=0;)else(memcpy(TEMP,first1j,strlen(first1j);TEMPstrlen(first1j)=0;)13編譯原理實驗報告實驗三)else/*如果右部為符號串*/(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+)(empt0=0;if(_emp(pk)=1&k=0)merge(firsti,first1m

25、,2);elsemerge(TEMP,first1m,2);)else if(_emp(pk)=1&k=length-1)(temp0=A;temp1=0;if(i=0)merge(firsti,temp,1);elsemerge(TEMP,temp,1); )else if(_emp(pk)=0) break;)/*求各產(chǎn)生式左部的FOLLOW*/ void FOLLOW(int i)(int j,k,m,n,result=1;14編譯原理實驗報告實驗三char c,temp20;c=non_teri;/*c為待求的非終結(jié)符*/temp0=c;temp1=0;merge(fo,temp,1)

26、;if(c=start)/*若為開始符號*/temp0=#;temp1=0;merge(followi,temp,1);for(j=0;j=count-1;j+) if(in(c,rightj)=1)/*找一個右部含有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,followm,

27、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后面的符號串能推出人*/15編譯原理實驗報告實驗三if(in(vm,fo)=1)/*避免循環(huán)遞歸*/merge(followi,followm,1); continue;) if(Fm=0) FOLLOW(m);Fm=1;)merge(followi,foll

28、owm,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;)/*判斷讀入文法是否為一個LL(1)文法*/int ll1()int i,j,length,result=1;char temp50;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)

29、-1;j+) first2(j);printf(nfirst1:);/*初始化*/*求單個符號的 FIRST集合*/編譯原理實驗報告16實驗三for(j=0;j=strlen(v)-1;j+)printf(%c:%s ,vj,first1j);printf(nempty:%s,empty);printf(n: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*/printf(n);for(j=0;j=strlen(non_ter)-1;j+)/*

30、 求 FOLLOW*/if(foj=0)fo0=0;FOLLOW(j);printf(nfirst:);for(i=0;i=count-1;i+)printf(%s ,firsti);printf(nfollow:);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)-1;j+)result*=_

31、emp(rightij);if(strlen(righti)=1&righti0=A)result=1;if(result=1) for(j=0;j+)if(vj=lefti)break;merge(selecti,followj,1);printf(nselect:);for(i=0;i=count-1;i+)printf(%s ,selecti);memcpy(temp,select0,strlen(select0);tempstrlen(select0)=0;17編譯原理實驗報告實驗三for(i=1;i=count-1;i+)/*判斷輸入文法是否為LL(1)文法*/length=strl

32、en(temp);if(lefti=lefti-1)merge(temp,selecti,1);if(strlen(temp)length+strlen(selecti) return(0);elsetemp0=0;memcpy(temp,selecti,strlen(selecti);tempstrlen(selecti)=0;return(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é)符數(shù)組*/termini+1=0;fo

33、r(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;)printf(nS:%s str:,S);for(p=j;p=strlen(str)-1;p+) printf(%c,strp);printf();)/*20編譯原理實驗報告/*讀入一個文法*/21實驗三一個用戶調(diào)用函數(shù)*void menu()(syntax();printf(n 是否繼續(xù)？ (y or n):);scanf(%c,&choose);getchar()