1、實(shí)驗(yàn)三一、分析語法分析部分我們我們采用LL（）方法實(shí)現(xiàn)，采用LL（）方法實(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)長(zhǎng)L(1)文法，但需要用LL(1)文法的定義判別，也就是說文法中不含左遞歸和左公共因子，只是LL(1)文法的必要條件。 LL(1) 文法的定義（5種定義）： 一個(gè)文法符號(hào)串的開始符號(hào)集合定義如下： 定義1. 設(shè)G=(VT，VN，S，P)是上下文無關(guān)文法,是任意的文法符號(hào)串 ,FIRST()是從推導(dǎo)出的串的開始符號(hào)的終結(jié)符集合。 FIRST()=a|=*=>a,aVT，,V*若=*=>,則規(guī)定FIRS

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

4、子括號(hào)，如：#輸入串#。 定義3. 給定上下文無關(guān)文法的產(chǎn)生式A, AVN,V*, 若=>,則SELECT(A)=FIRST() 如果=*=>，則SELECT(A)=FIRST()FOLLOW(A)。FIRST()表示FIRST()的非元素。 更進(jìn)一步可以看出能夠使用自頂向下分析技術(shù)必須使文法滿足如下條件，我們稱滿足條件的文法為L(zhǎng)L(1)文法，其定義為： 定義4. 一個(gè)上下文無關(guān)文法是LL(1)文法的充分必要條件是：  對(duì)每個(gè)非終結(jié)符A的兩個(gè)不同產(chǎn)生式，A, A,滿足SELECT(A)SELECT(A)=空,其中，不同時(shí)能. 定義5. LL（1）文法也可定義為: 一個(gè)文法

5、G是LL（1）的，當(dāng)且僅當(dāng)對(duì)于G的每一個(gè)非終結(jié)符A的任何兩個(gè)不同產(chǎn)生式 A|，下面的條件成立： (1)FIRST（）FIRST()= 空,也就是和推導(dǎo)不出以某個(gè)相同的終結(jié)符a為首的符號(hào)串；它們不應(yīng)該都能推出空字 (2)假若=>那么，F(xiàn)IRST（) FOLLOW（A） 空也就是，若=>則所能推出的串的首符號(hào)不應(yīng)在FOLLOW(A)中。23編譯原理實(shí)驗(yàn)報(bào)告二、算法該程序可分為如下幾步：（1）讀入文法 （2）判斷正誤 （3）若無誤，判斷是否為L(zhǎng)L(1)文法 （4）若是，構(gòu)造分析表；是LL(1)文法？結(jié)束報(bào)錯(cuò)判斷句型根據(jù)下面LL(1)文法，對(duì)輸入串w: (i+i)*(i+i)+i*i進(jìn)行L

6、L(1)分析,要求如下：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指向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 err

7、or()else   /*X 是非終結(jié)符號(hào)*/ if Mx,a=Xày1y2yk  then begin從棧中彈出X；把yk,yk-1,y1壓入棧，y1在棧頂；輸出產(chǎn)生式Xày1y2yk；endelse error()until X=#          /*棧空*/語法分析的流程算法三、設(shè)計(jì)目的： （1）理解和掌握LL(1)語法分析方法的基本原理；根據(jù)給出的LL(1)文法，掌握LL(1)分析表的構(gòu)造及分析過程的實(shí)現(xiàn)。（2）掌握預(yù)測(cè)分析程序如何使

8、用分析表和棧聯(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)分析表；（3）對(duì)于給定的輸入串，應(yīng)能判斷識(shí)別該串是否為給定文法的句型。附錄/*預(yù)測(cè)分析程序（語法分析程序），分析對(duì)象為C語言源程序文件。 該分析程序有18部分組成：1首先定義各種需要用到的常量和變量；2判斷一個(gè)字符是否在指定字符串中；3得到一個(gè)不是非終結(jié)符的符號(hào)；4分解含有左遞歸的產(chǎn)生式；5分解不含有左遞歸的

9、產(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<stdlib.h>#include<stdio.h>#include<string.h>int count=0; /*分解的產(chǎn)生式的個(gè)數(shù)*/int number; /*所有終結(jié)符和非終結(jié)符的總數(shù)*

10、/char start; /*開始符號(hào)*/char termin50; /*終結(jié)符號(hào)*/char non_ter50; /*非終結(jié)符號(hào)*/char v50; /*所有符號(hào)*/char left50; /*左部*/char right5050; /*右部*/char first5050,follow5050; /*各產(chǎn)生式右部的FIRST和左部的FOLLOW集合*/char first15050; /*所有單個(gè)符號(hào)的FIRST集合*/char select5050; /*各單個(gè)產(chǎn)生式的SELECT集合*/char f50,F50; /*記錄各符號(hào)的FIRST和FOLLOW是否已求過*/char

11、empty20; /*記錄可直接推出的符號(hào)*/char TEMP50; /*求FOLLOW時(shí)存放某一符號(hào)串的FIRST集合*/int validity=1; /*表示輸入文法是否有效*/int ll=1; /*表示輸入文法是否為L(zhǎng)L(1)文法*/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

12、+)if(pi=c)return(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=

13、9;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

14、;break;else /*如果|后的首符號(hào)和左部不同*/leftcount=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;

15、count+; leftcount=point0; memcpy(rightcount,temp,m); rightcountm=ch; rightcountm+1='0'count+; m=0;/* 分解不含有左遞歸的產(chǎn)生式*/void non_re(char *point) int m=0,j;char temp20;for(j=3;j<=strlen(point)-1;j+) if(pointj!='|') tempm+=pointj;else leftcount=point0; memcpy(rightcount,temp,m); rightcou

16、ntm='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)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)

17、; 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(); for(j=1;j&

18、lt;=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!='-'|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_r

19、e(pk);return(s);/* 將單個(gè)符號(hào)或符號(hào)串并入另一符號(hào)串*/void merge(char *d,char *s,int type) /*d是目標(biāo)符號(hào)串，s是源串，type1，源串中的 一并并入目串； type2，源串中的 不并入目串*/ int i,j;for(i=0;i<=strlen(s)-1;i+) if(type=2&&si='');elsefor(j=0;j+) if(j<strlen(d)&&si=dj) break; if(j=strlen(d) dj=si; dj+1='0' break

20、;/* 求所有能直接推出的符號(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'merge(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;temp1='0

21、'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,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(m

22、ark=1)continue;else for(k=0;k<=j-1;k+)result*=_emp(rightik);temp0=rightik;temp1='0'merge(empt,temp,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é)

23、符中，報(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!='') /*若右部某一符號(hào)不在非終結(jié)符、終結(jié)符中且不為 ，報(bào)錯(cuò)*/printf("nerror2!");validity=0;return(0);return(1);/* 求單個(gè)符號(hào)的FIRST*/void first2(int i)

24、/*i為符號(hào)在所有輸入符號(hào)中的序號(hào)*/ char c,temp20;int j,k,m;c=vi;char ch=''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='') temp0=rightj0; temp1='0'merge(first1i,

25、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<strlen(rightj)-1) for(m=0;m+)if(vm=rightjk+1)break;if(f

26、m='0')first2(m);fm='1'merge(first1i,first1m,2);else if(_emp(rightjk)=1&&k=strlen(rightj)-1)temp0=''temp1='0'merge(first1i,temp,1);else break;fi='1'/* 求各產(chǎn)生式右部的FIRST*/void FIRST(int i,char *p)int length;int j,k,m;char temp20;length=strlen(p);if(length=1)

27、 /*如果右部為單個(gè)符號(hào)*/if(p0='') if(i>=0) firsti0='' firsti1='0'elseTEMP0=''TEMP1='0'elsefor(j=0;j+)if(vj=p0)break;if(i>=0) memcpy(firsti,first1j,strlen(first1j); firstistrlen(first1j)='0'elsememcpy(TEMP,first1j,strlen(first1j);TEMPstrlen(first1j)='0&

28、#39; 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<length-1) for(m=0;m+)if(vm=rightik+1)break; if(i>=0) merge(firsti,first1m,2);elsemerge(TEMP,first1m,2); else if(_emp

29、(pk)=1&&k=length-1) temp0=''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;char c,temp20;c=non_teri; /*c為待求的非終結(jié)符*/temp0=c;temp1='0'merge(fo,temp,1);if(c=start) /*若為開始

30、符號(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,

31、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)串能推出*/ if(in(vm,fo)=1) /*避免循環(huán)遞歸*/merge(followi,followm,1);continue;if(Fm='0') FOLLOW(m); F

32、m='1' merge(followi,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'/* 判斷讀入文法是否為一個(gè)LL(1)文法*/int ll1() int i,j,length,result=1;char temp50;for(j=0;j<=49;j+) /*初始化*/firstj0='0' fol

33、lowj0='0'first1j0='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("nfirst1:");for(j=0;j<=strlen(v)-1;j+)printf("%c:%s ",vj,first1j); printf("nempty:%s&quo

34、t;,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+) /*求FOLLOW*/if(foj=0)fo0='0' FOLLOW(j); printf("nfirst:");for(i=0;i<

35、=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*

36、=_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("nselect:");for(i=0;i<=count-1;i+) printf("%s ",selecti);memcpy(temp,select0,strlen(select0);tempstrlen(select0)='0'for(i=1;

37、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);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+

38、)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+)if(termink=selectij)break; /*k為產(chǎn)生式右部終結(jié)符的序號(hào)*/ Mm

39、k=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)if(in(Sstrlen(S)-1,termin)=1) if(Sstrlen(S)-1!=ch)printf("n該符號(hào)串不是文法的句型！"); return;else if(Sstrlen(S)-1='#') printf("n該符號(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("n詞法錯(cuò)誤！");retu