安徽大學(xué)編譯原理實(shí)驗(yàn)

1、編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：實(shí)驗(yàn)4 ll(1)文法分析院系：計(jì)算機(jī)學(xué)院專業(yè)：科技專業(yè)年級:1級姓名：xxx學(xué)號：e01114xxx實(shí)驗(yàn)4 ll(1)文法判別實(shí)驗(yàn)名稱：ll(1)文法的判別實(shí)驗(yàn)要求：輸入一個文法gs,判別其是否為ll(1)文法。輸入任意文法消除左遞歸消除左因子測試任意輸入語句是否合法數(shù)據(jù)結(jié)構(gòu)描述算法說明 輸出first集合輸出follow集合輸出1x(1)表實(shí)驗(yàn)?zāi)康模涸O(shè)計(jì)、編制、調(diào)試一個具體的ll (1)語法分析程序，加深對語法分析原理的理解。1. 掌握ll(1)分析法的基本原理2. 掌握ll(1)分析表的構(gòu)造方法3. 掌握ll(1)驅(qū)動程序的構(gòu)造方法4. 加深對預(yù)測分析ll (1

2、)分析法的理解。實(shí)驗(yàn)原理：1. ll(1)文法定義一個上下文無關(guān)文法g是ll(1)文法，當(dāng)且僅當(dāng)對g中每個菲終結(jié)符a的 任何兩個不同的規(guī)則a-a |b,滿足select (a- a ) n select (a- p )= 其屮a、 b屮至多只有一個能推出£串。含義：第一個l表示從左到右掃描輸入串>第二個l表示自上而下進(jìn)行最左推導(dǎo)> 1表明只需向前看一個符號便可以決定選哪條產(chǎn)生式進(jìn)行推導(dǎo)，類似地 ll(k)文法需要向前看k個符號才可以確定選用哪個產(chǎn)生式。2ll(1)文法的判別五步判別法/求能推出£的非終結(jié)符集/計(jì)算每個產(chǎn)生式右部a的flrst(a)集/計(jì)算每個非終

3、結(jié)符a的follow (a)集/計(jì)算每個產(chǎn)生式a-> a的select (a-> a )集“按i丄(1)文法的定義判別歹 假定所給文法是經(jīng)過壓縮的(不包含多余規(guī)則)3.算法初始化置數(shù)組x中對應(yīng)每一非終結(jié)符的標(biāo)記為初值“未定”；掃描文法中的產(chǎn)生式 刪除右部含有終結(jié)符的產(chǎn)生式，假使以某一非終結(jié)符為左部的所有產(chǎn) 生式都被刪除，并將數(shù)組中對應(yīng)該非終結(jié)符的標(biāo)記值改為“否”，說明該非 終結(jié)符不能推出£ ; 刪除右部僅為£的產(chǎn)生式，則將數(shù)組中對應(yīng)該非終結(jié)符的標(biāo)志置為 “是”，說明該非終結(jié)符能推出£ ;捋本次掃描后僅剩下產(chǎn)生式左右均為非終結(jié)符的產(chǎn)生式掃描產(chǎn)生式右部的每

4、-符號 若所掃描到的非終結(jié)符號在數(shù)組中對應(yīng)的標(biāo)志為“是”，則刪去該非終 結(jié)符，若這使產(chǎn)生式右部為空，則對產(chǎn)生式左部的非終結(jié)符在數(shù)組中對應(yīng)的 標(biāo)志改“是”，并刪除該非終結(jié)符為左部的所有產(chǎn)生式 若所掃描到的非終結(jié)符號在數(shù)組屮對應(yīng)的標(biāo)志為“否”，則刪去該產(chǎn)生 式，若這使產(chǎn)生式左部非終結(jié)符的有關(guān)產(chǎn)生式都被刪去，則把在數(shù)組中該非終結(jié)符對應(yīng)的標(biāo)志改成“否”重復(fù)(3)直到掃描完畢數(shù)組屮非終結(jié)符對應(yīng)的特征再沒有改變?yōu)橹埂?. 計(jì)算每個產(chǎn)生式右部a的first(a)集定義法i、首先對每一文法符號x (xg vtuvn),求first (a)的算法：1. 對每個 awvt, first (a) = a 2對每個

5、agvn,若 a e ,則 first (a) = e 3. 對每個 agvn,若有產(chǎn)生式 a->a-,aevt,則 first (a)二a4. 對每個產(chǎn)生式a-xlxjxn做：first (a) =first (a) uscctionfirst (xlxjxn)其中:sectionfirst (xi xj xn)=(first(xl)- e ) o(first(x2)- e )uu(first(xj)- £ ) ufirst(xj+1)xj+1是產(chǎn)生式右部中第一個不能推出e的符號a 若 xi e則 sectionfirst(xixjxn)二first (xi)> 若xl

6、xn全可推出£則 sectionfirst (xl-xn)=flrst(xi) u - ufirst(xn) u e 5. 重復(fù)4直到每個符號的first集合都不再增大為止。ii、利用求出每個文法符號的first集求箭號爭的first集 設(shè)a二xlx2xn1當(dāng) xi e,則 first ( a )二first (xi)2. 若對任何j (lwjvn)都有£ gfirst(xj),且xj+1不能導(dǎo)出空串,則first(a) = (first(xl)- e ) uu (first(xj)- e ) ufirst(xj+1)3. 若對所有 i (lwiwn),都有 £

7、g first (xi),則 first (a ) =first (xi) u - u first (xn) u e 關(guān)系圖法 每個文法符號對應(yīng)圖中一個結(jié)點(diǎn)，對應(yīng)vt的結(jié)點(diǎn)時用符號本身標(biāo)記，對應(yīng)vn的結(jié)點(diǎn)用first (a)標(biāo)記。這里a表示vn 如果文法中有產(chǎn)生式a->vt,則從結(jié)點(diǎn)first (a)到結(jié)點(diǎn)vt連一條箭弧 如果文法中有產(chǎn)生式a-> a vnp , ka £，則從結(jié)點(diǎn)first(a)到結(jié)點(diǎn) first (vn)連一條箭弧 凡是從first (a)結(jié)點(diǎn)有路徑可到達(dá)的vt結(jié)點(diǎn)所標(biāo)記的vt都為first (a)的 成員由判別步驟1確定e是否為某vn的first集的

8、成員，若是則將£加入該vn的first集中5. 計(jì)算每個非終結(jié)符a的follow (a)集定義法1. 對所有 awvn 令 follow二 ;對開始符 s,令 follow(s)二#2. 對每條產(chǎn)牛式a->xby,考察產(chǎn)牛式右部的每一非終結(jié)符b, x,ywv*, 如果y不能推出£foilow(b) =fo 11 ow(b) ufirst (y) 否則follow(b)=follow(b) u (first(y)- e ) u follow (a)分 若ae follow (a),則表明s=>*aa,由于axby,且y二* e ,則有 s=>*aa二xbya

9、二xba，即s=>*xba,所以aefollow(b)3重復(fù)2,直至對所有agvn, fol low (a)不再擴(kuò)大為止。孑follow集合屮不能有£關(guān)系圖法 文法g中的每個符號和對應(yīng)圖中的一個結(jié)點(diǎn)，對應(yīng)vt和的結(jié) 點(diǎn)用符號本身標(biāo)記。對應(yīng)vn的結(jié)點(diǎn)，則用follow(vn)或first(vn)標(biāo)記 從結(jié)點(diǎn)follow(s)到號結(jié)點(diǎn)連一條箭弧 如果文法中有產(chǎn)生式a-> a b 3 vn,且b e,則從結(jié)點(diǎn)follow (b)到結(jié)點(diǎn) first (vn)連一條箭弧 如果文法中有產(chǎn)生式a-> abbvt,且b £ ,則從結(jié)follow(b)到結(jié)點(diǎn)vt連一條箭弧

10、如果文法中有產(chǎn)生式a->abp,且b £ ,則從 結(jié)點(diǎn)follow(b)到結(jié)點(diǎn)follow(a)連一條箭弧 對每一 first (a)結(jié)點(diǎn)如果有產(chǎn)生式a->ax0, k a j則從結(jié)點(diǎn)first(a)到結(jié)點(diǎn)first(x)連一條箭弧 凡是從結(jié)點(diǎn)follow(a)有路徑可以到達(dá)的終結(jié)符或號結(jié)點(diǎn)，其所標(biāo)記 的終結(jié)符或號即為follow(a)的成員6. 計(jì)算每個產(chǎn)生式a-> a的select (a-> a )集按定義計(jì)算select (a-> a)：若 a a4 £，則 select (a- a ) =f1rst (a )若 a 斗 e,貝 v se

11、lect (a- a ) = (first ( a ) - e ) u follow (a)附錄：#include<stdio. h> #include<string h> int count=0;int number;char start;char termin50;char non_ter 50;char v50;char left50; char right50 50;/*分解的產(chǎn)生式的個數(shù)*/*所有終結(jié)符和非終結(jié)符的總數(shù)*/*開始符號*/*終結(jié)符號*/*非終結(jié)符號*/*所有符號*/*左部*/*右部*/char first5050, follow5050;/*各產(chǎn)

12、生式右部的first和左部的follow集合*/ char firstl50 50; char select5050;char f50,f50;/*所有單個符號的first集合*/*各單個產(chǎn)生式的select集合*/*記錄各符號的first和follow是否已求過*/char empty20;char temp 50;/*記錄可直接推出八的符號*/*求follow時存放某一符號吊的first集合*/int validity=l;/*表示輸入文法是否有效*/int 11=1;/*表示輸入文法是否為i丄(1)文法*/int m2020;/*分析表*/char choose;/*用戶輸入時使用*/c

13、har cmpt20;char fo20;/*求_emp()時使用*/*求follow集合時使用*/int in (char c, char *p) int i;if (strlen(p)=o)return (0);for(i=0;i+)if (pi=c)return (1) ;/*若在，返回 1*/if (i=strlen( p)return (0) ;/*若不在，返回 0*/)/判斷一個字符是否在指定字符串屮char c ()char c二'a'whi 1 e(in(c, non_ter)=l)c+;return (c);/得到一個不是非終結(jié)符的符號void recur (

14、char *point)/分解含有左遞歸的產(chǎn)牛式/*完整的產(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+l=，0'for(j=0;j<=strlen(point)-1;j+)if (pointn二二point0)/*如果丨后的首符號和左部相同*/for(j=n+l;j<=strlen (point)t;j+)while(pointjf&&pointj- 0')tempm+二point

15、j+;leftcount=ch;memcpy(rightcount, temp, m);rightcountm二ch;rightcountm+l=, 0"hl二 0；count+;if(pointj二二'i')break;else/*如果'丨'后的首符號和左部不同*/leftcount二ch;rightcount0二'八；right count 1=，0,;count+;for(j=n;j<=strlen(point)-1;j+)if (pointj !二'i') tempm+=point j;elseleftcount二

16、point0;memcpy (rightcount, temp, m);right countm二ch;right count m+l=, 0'/ printf (z，count=%d /z, count);m=0;count+;jleftcount二point0;memcpy (rightcount, temp, m);rightcountm二ch;right count m+10，;count+；void non_re(char *point)/分解不含有左遞歸的產(chǎn)牛式iint m=0, j;char temp20;for (j=3;j<=strlen(point)-1;j+

17、)if (pointtj !二|')tempm+=pointj;elseleftcount二point0;memcpy (rightcount, temp, m);rightcount m=，0，;m=0;count+;jjleftcount=point0;memcpy (rightcount, temp, m);right count m0，;count+；m=0; char grammer (char *t, char *n, char *1 eft, char right50 50)/讀入一 個文法char vn50, vt50;char s;char p5050;int i,

18、j, k;printff請輸入文法的非終結(jié)符號串:)；scanf ("%s", vn);getchar ();i=strlen(vn);memcpy (n, vn, i);ni= 0,;printfc請輸入文法的終結(jié)符號串:)；seanf (s, vt);get char ();i=sttlen( vt);mcmcpy (t, vt, i);ti二'0'printff請輸入文法的開始符號：)；getchar ();printfc請輸入文法產(chǎn)生式的條數(shù)：)；scanf (%d, &i); getchar ();for(j=l;je;j+)printfc

19、請輸入文法的第%d條(共%d條)產(chǎn)生式：",j, i); scanf ("%s： p j-1);getchar ();for(j=0;j<=i-l;j+)if (pjl!=''l|pj！二'') printf (z，ninput error!z，);vali di ty=o;return(，0');/*檢測輸入錯誤*/for(k=0;k<=i-l;k+)/*分解輸入的各產(chǎn)生式*/if(pk3=pk0)recur (pk);elsenon_re(pk);return(s);void merge (char *d, char

20、*s, int type)/將單個符號或符號串并入另一符 號串/*d是目標(biāo)符號串，s是源串，type=l,源串中的''一并并入目串；type = 2,源串中的'八'不并入目串*/int i, j;for(i=0;i<=strlen(s)l;i+)if (type二二2&&si二二'八')elsefor(j=0;j+)if(j<strlcn(d)&&si=djl) break;if (j 二二 sttlen(d)dj=si;dj+l= 0,;break;void emp(char c)/求所有能直接推出八

21、的符號/*即求所有由'八推出的符號*/char temp10;int i;for(i=0;i<=count-1;i+)if (righti0=c&&strlcn(righti)=l)temp0=lefti;tempt 1=' 0'merge (empty, temp, 1);cmp(lefti); int _emp(char c)/求某一符號能否推出''/*若能推出，返回1；否則，返回0*/int i, j, k, result=l, mark=0;char temp20;temp0二c;templ=，0'merge (cm

22、pt, tcmp, 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=l&&in(righti0, empty)=1)return (1);else if (j=l&&in(righti0, termin)=1)teturn (0);elseifor (k=0;k<=j-l;k+)if (in(rightik, empt)二二1)mark=l;if (

23、mark=l)continue;el sefor(k=0;k<=j-l;k+)result*=_emp(rightik);temp0=rightik;temp 1二'0'merge (empt, temp, 1);if (resuit二二0&&icount) continue;else if (result=l&&i<count) return (1); int judge()/判斷讀入的文法是否正確int i, j；for (i=0; i<=countt ; i+)if(in(lefti, non_ter)=0)/*若左部不在

24、非終結(jié)符中，報(bào)錯*/printf("nerrorl!);validity=0;return (0);for(j=0;j<=strlen(right i)-l; j+)if(in(rightij,non tcr)=0&&in(rightij, tcrmin)=0&&rightij!八)/*若右部某一符號不在非終結(jié)符、終結(jié)符中且不為報(bào)錯*/printf(nerror2!)；validity=0;return(0);)rcturn(l); void first2(int i)/求單個符號的 first/*i為符號在所有輸入符號中的序號*/char c,

25、temp20;int j, k, m;char ch二''；c=vi;emp(ch);if (in(c, termin) =1)/*若為終結(jié)符*/firstli0=c;firstli1二'0,;else if (in (c, non ter) =1)/*若為非終結(jié)符*/ifor (j=0;j<=count-1;j+)if (leftj=c)if (in(rightj 0, termin) =11 | rightj 0二二'")temp0二rightj0;tempt 1二'0'merge(firstli, temp, 1);!els

26、e if (in(rightj0, non_ter)=l)if (rightj0=c)continue;for (k=0;k+)if (vk=rightj 0)break;if(fk二二'o')first2 (k);merge(firstli,firstl k,2);for (k=0;k<=strlen(rightj)t;k+)empt0二'0,;if (_emp(right j k) =l&&k<strlen(rightj)-1)for(m=0;m+)if (vm=rightjk+1)break;if (f m二二'o')f

27、irst2(m);f：m= r;merge(firstli, firstlm, 2);)else if( cmp(rightj k)=l&&k=strlcn(rightj)t)temp0二'"；tempt 1二'0'merge (firstli, temp, 1);!elsebreak;void first(int i, char *p) /求各產(chǎn)生式右部的 firstini length;int j, k, m;char temp20;lcngth=strlcn(p);/*如果右部為單個符號*/if (length=l)if(p0二八)辻(i

28、>=0)firsti0二' firsti 1=' 0,;)elsetemp 0二'“；temp1二'0')el sefor(j=0;j+)if (vj=p0) break;if(i>=0)memcpy(firsti, firstlj, strlen(firstlj); firsti strlen(firstlj)二'0'el sememcpy(temp, firstlj, strlen(firstl j);temp str len (f irst 1 j) =, 0,;else/*如果右部為符號串*/ifor(j=0;j+)i

29、f (vj二二p0)break;if(i>=0)merge (firs t i, firs tl j, 2);elsemerge(temp, fi rstlj,2);for(k=0;k<=lengthl;k+)empt0二'0'if(_emp(pkj)=l&&k<1ength-1)for (m二0;m+)if (vm=rightik+1)break;if(i> 二 0)merge(firsti, firstlm, 2);elsemerge (temp, first 1m, 2);else i f(_emp(pk)=l&&k

30、=length-1)tcmpo=，c ;templ二'0'if(i> 二 0)merge(firsti, temp,1);elsemerge (temp, temp, 1);else if(_emp(pk)=0)break;)! void follow(int i) /求各產(chǎn)生式左部的followint j, k, m, n, result=l;char c, tcmp20;c=non_te譏i ;/*c為待求的非終結(jié)符*/temp0=c;tempt 1二'0'merge (fo, temp, 1);if(c=start)/*若為開始符號*/temp0=,

31、 #'tempt 1=' 0'merge(followi, temp, 1);!for (j=0;j<=count-1;j+)if (in(c, rightj) = l)/*找一個右部含有c的產(chǎn)牛式*/for(k=0;k+)if(rightjk=c)break;/*k為c在該產(chǎn)生式右部的序號*/for(m=0;m+)if(vm=leftj)break;/*ni為產(chǎn)生式左部非終結(jié)符在所有符號中的序號*/if (k=strlen (right j)t)/*如果c在產(chǎn)生式右部的最后*/if (in(vm, fo)二二 1)merge(followi, followm,1

32、);conti nue;if (fm=，o')follow(m);fni二t'merge(followi, followm, 1);else/*如果c不在產(chǎn)生式右部的最后*/for(n二k+1;n<=strlen(rightj)t;n+)empt 0=，0'result*=_emp (rightjn);if(resuit二二1)/*如果右部c后面的符號串能推出"*/if (in(vm, fo) =1)/*避免循環(huán)遞歸*/merge(followi, followm,1);continue;j辻(fm =，0,)follow (m);fni二i ;jmer

33、ge(followi, followm,1);for(n二k+1;n<=strlen(rightj)t;n+)tempn-k-l=rightjn;tempstrlcn(rightj)-kt二'0'first(t, temp);merge(followi, temp,2);fi二t'int 111() /判斷讀入文法是否為一個ll(1)文法int i, j, length, resuit二 1;char temp50;for(j=0;j<=49;j+)/*初始化*/firstj 0- 0,;followj0二'0'firstltj 0= 0&#

34、39;selectj 0=，0'tempj二'0'tempj二'0,;fj二'o'fj二'o'for(j=0;j<=strlen(v)-l;j+)first2 (j) ;/*求單個符號的first集合*/printf cn單個符號的first集合為:);for(j=0;j<=strlcn(v)-1;j+)printf (z，%c:%s，vj, firstl j);printf (z，n能推出八的非終結(jié)符:s，empty);/printf(n_emp:);/for(j=0;j<=strlen(v)-l;j+)/ p

35、rintf(d z，, _emp(vj);for (i=0; i<=countt ; i+)ftrst(i,righti) ;/*求 first*/for(j二0;j<=strlen(non_ter)-l;j+)/*求 follow*/if (foj=0)fo0二'0,;follow (j);)!printf (n每個產(chǎn)生式右部符號串的first集合為:)；for (i=0;i<=countl;i+)printf(s “,firsti);printf (z，n每個非終結(jié)符的follow集合為：)；for(i=0;i<=strlcn(non ter)-l;i+)

36、printf (z，%s ，z, followi);for (i=0;i<=countl;i+)/*求每一產(chǎn)牛式的select集合*/memcpy(selecti, firsti, strlen(firsti); selectistrlen(firsti)=, 0'for (j=0;j<=strlen(righti)-l;j+)resuit*=_emp(rightij);if (strlen(righti)=l&&righti0=，八')result=l;if (result=l)for(j=0;j+)if (vj=lefti)break;merge

37、 (select i, fol low j, 1);printf(z，n每個產(chǎn)生式的select集合為：)；for (i=0; i<=countt ; i+)printf (z，%s ，z, selecti);memepy(temp,select0, strlen(select0);tempstrlen(select0) =, 0,;for (i=l;i<=count-l;i+)/*判斷輸入文法是否為ll(1)文法*/length=strlen(temp);if (left i二二 left it)merge(temp, selecti, 1);if(strlcn(tcmp)<

38、;lcngth+strlcn (select i)return (0);elsetemp0二'0'memepy(temp, selecti,strlen(selecti);tempstrlen(selecti)二'0')!return (1);vo i d mm () /構(gòu)造分析表mint i, j, k, m;for(i=0;i<=19;i+)for(j=0;j<=19;j+)mij二-1;i二sttlen(termin);termini=，w ;/*將#加入終結(jié)符數(shù)組*/termini+l=，0'for (i=0; i<=count

39、t ; i+)for(m=0;m+)if(non_term=left i)break;am為產(chǎn)生式左部非終結(jié)符的序號*/for(j=0;j<=strlen(selecti)-1;j+)if (in(selecti j, termin)=l)for (k=0;k+)if (termink二二selecti j)break;/*k為產(chǎn)牛式右部終結(jié)符的序號*/mm k=i;void syntax() /總控算法int i, j, k, m, n, p, q;char ch;char s50,st譏50;printf(z，請輸入該文法的句型：”)；scanf(s，str);getchar ();i=strlcn(str);stri=，#'str i+1二'0,;s0='#'sl=start;s2= 0'j=0；ch=strj;while(l)if (in(sstrlen(s)-l, termin) =1)if (sstrlen(s)-l !=ch)printfc該符號串不是文法的句型！ )；return;els