試驗(yàn)3預(yù)測(cè)分析法

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

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

3、a , 3 e V*若 a =*= ，則規(guī)定 s 6 FIRST( a ).當(dāng)一個(gè)文法中相同左部非終結(jié)符的右部存在能=*= 的情況則必須知道該非終結(jié)符的后跟符號(hào)的集合中是否含有其它右部開始符號(hào)集合的元素。為此，我們定義一個(gè)文法非終結(jié)符的后跟符號(hào)的集合如下：定義2.設(shè)G=(VT , VN , S, P)是上下文無關(guān) 文法，A C VN , S是開始符號(hào)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é)束符，或稱為句子括號(hào)，如：#輸入串#。定義 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 元素。更進(jìn)一步可以看出能夠使用自頂向下分析技術(shù)必須使文法滿足如下條件，我們稱滿足條件的文法為L(zhǎng)L(1)文法，其定義為：定義4. 一個(gè)上下文無關(guān)文法是 LL(1)文法的充分

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

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

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

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

9、非終結(jié)符的符號(hào)； 4分解含有左遞歸的產(chǎn)生式；5分解不含有左遞歸的產(chǎn)生式；6讀入一個(gè)文法；7將單個(gè)符號(hào)或符號(hào)串并入另一符號(hào)串； 8求所有能直接推出 人的符號(hào)； 9求某一符號(hào)能否推出 人；10判斷讀入的文法是否正確；11求單個(gè)符號(hào)的 FIRST ;12求各產(chǎn)生式右部的 FIRST;13求各產(chǎn)生式左部的 FOLLOW ; 14判斷讀入文法是否為一個(gè) LL(1)文法；15構(gòu)造分析表M;16總控算法；17 一個(gè)用戶調(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)生式的個(gè)數(shù)*/*所有終結(jié)符和非名結(jié)符的總數(shù)*/*開始符號(hào)*/*終結(jié)符號(hào)*/*非終結(jié)符號(hào)*/*所有符號(hào)*/*左部*/*右部*/char first5050,follow5050;/*各產(chǎn)生式右部的 FIRST和左部的FOLLOW 集合*/char first15050;/*所有單個(gè)符號(hào)的FIRST集合*/char select5050;/*各單個(gè)產(chǎn)生式的 SELECT集合*/char f50,F50;char empty20;/*記錄可直接推出人的符號(hào)*/*記錄各符號(hào)的 FIRST和FOLLOW

11、是否已求過*/char TEMP50;int validity=1;/*求FOLLOW時(shí)存放某一符號(hào)串的 FIRST集合*/*表示輸入文法是否有效*/int ll=1;/*表示輸入文法是否為L(zhǎng)L(1)文法*/編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)三int M2020;char choose;/*分析表*/*用戶輸入時(shí)使用*/char empt20;/*求_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(pi=c)r

12、eturn(1); /*若在，返回 1*/if(i=strlen(p)return(0); /* 若不在，返回 0*/)/*得到一個(gè)不是非終結(jié)符的符號(hào)*/ 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();/*得到一個(gè)非終結(jié)符*/k=strlen(non_ter);non_terk=ch;non_terk+1=0;for(j=0;j=strlen(p

13、oint)-1;j+)編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)三if(pointn=point0)/*如果|后的首符號(hào)和左部相同*/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/*如果|后的首符號(hào)和左部不同*/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;編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)三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;)/*讀入一個(gè)文法*/char grammer(char *t,char *n,char *left,char right5050)

16、(char vn50,vt50;char s;char p5050;int i,j,k;printf(n請(qǐng)輸入文法的非終結(jié)符號(hào)串：);scanf(%s,vn);getchar();i=strlen(vn);編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)三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;printf(請(qǐng)輸入文法的開始符號(hào)：);scanf(%c,&s);getchar();printf(請(qǐng)輸入文法產(chǎn)生式的條數(shù)：);scanf(%d,&i);getchar();fo

17、r(j=1;j=i;j+)printf(請(qǐng)輸入文法的第 %d條(共%d條)產(chǎn)生式：,j,i);scanf(%s,pj-1);getchar();for(j=0;j) printf(ninput error!);validity=0;return(0);/*檢測(cè)輸入錯(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)串*/void merge(char *d,char *s,int type)/*d是目標(biāo)符號(hào)串，s是源串，type=1,源串中的人一并并入目

18、串;type=2,源串中的人不并入目串*/int i,j;for(i=0;i=strlen(s)-1;i+)編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)三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;/*求所有能直接推出人的符號(hào)*/ void emp(char c)/*即求所有由人推出的符號(hào)*/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);/*求某一符號(hào)能否推出人*/ int _emp(char c)/*若能推出，返回1;否則，返回0*/int i,j,k,result=1,mark=0;char temp20;temp0=c;編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)三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(righti); /*j 為右部的長(zhǎng)度 */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編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)三(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,non_ter)=0&in(rightij,termin)=0&rightij!=A)/*若右部某一符號(hào)不在非終結(jié)符、終結(jié)符中且不為printf(nerror2!);validity=0;return(0);)return(1);)*/*求單個(gè)符號(hào)

22、的 FIRST*void first2(int i)/*i為符號(hào)在所有輸入符號(hào)中的序號(hào)*/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，)人，報(bào)錯(cuò)*/11編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)三(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編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)三)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+)(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編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)三char c,temp20;c=non_teri;/*c為待求的非終結(jié)符*/temp0=c;temp1=0;merge(fo,temp,1)

26、;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(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后面的符號(hào)串能推出人*/15編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)三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;)/*判斷讀入文法是否為一個(gè)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:);/*初始化*/*求單個(gè)符號(hào)的 FIRST集合*/編譯原理實(shí)驗(yàn)報(bào)告16實(shí)驗(yàn)三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編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)三for(i=1;i=count-1;i+)/*判斷輸入文法是否為L(zhǎng)L(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é)符的序號(hào)*/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編譯原理實(shí)驗(yàn)報(bào)告/*讀入一個(gè)文法*/21實(shí)驗(yàn)三一個(gè)用戶調(diào)用函數(shù)*void menu()(syntax();printf(n 是否繼續(xù)？ (y or n):);scanf(%c,&choose);getchar()