1、LL(1) 文法的判斷一：要求輸入：任意的上下文無(wú)關(guān)文法。輸出：判斷是否為L(zhǎng)L( 1)文法二：實(shí)驗(yàn)?zāi)康?1) 握LL(1)B勺判斷，掌握求first和follow集合的算法 2,熟悉運(yùn)用C/C+語(yǔ)言又求first和follow集合進(jìn)行實(shí)現(xiàn)三：實(shí)驗(yàn)原理設(shè)a = x1x2rn, FIRST( a)可按下列方法求得：令 FIRST( a )=，i=1 ;(1)若 xiC VT,則 xiC FIRST( a);(2) 若 xiCVN; 若 e FIRSTxi), M FIRST(xi) FIRST( a );若 e e FIRST(xi),貝U FIRST(xi) - FIRST( a );(3) i

2、=i+1,重復(fù)(1)、(2),直到 xiCVT, (i = 2, 3,，n)或 xi C VN 且若 FIRST(xi)或 in 為止。當(dāng)一個(gè)文法中存在e產(chǎn)生式時(shí)，例如，存在只有知道哪些符號(hào)可以合法地出現(xiàn)在非終結(jié)符A之后，才能知道是否選擇A-e產(chǎn)生式。這些合法地出現(xiàn)在 非終結(jié)符A之后的符號(hào)組成的集合被稱為 FOLLOW集合。下面我們給出文法的 FOLLOW的定義。設(shè)文法 GS= (VN, VT, P, S),則FOLLOW (A) =a | S Aa ，aCVT。若 S A, #C FOLLOW (A)。由定義可以看出，F(xiàn)OLLOW A)是指在文法GSR勺所有句型中，緊跟在非終結(jié)符A 后的終結(jié)

3、符號(hào)的集合。FOLLOW褰可按下列方法求得：(1) 對(duì)于文法GS的開(kāi)始符號(hào)S,有# FOLLOW(S);(2) 若文法GS中有形如B-xAy的規(guī)則，其中x, yC V *,則FIRSTy) - 6 FOLLOW (A);(3) 若文法GS中有形如B-xA的規(guī)則，或形如 B-xAy的規(guī)則且e FIRST (y),其中 x, y V *,貝 tj FOLLOW (B) FOLLOW (A);四：數(shù)據(jù)結(jié)構(gòu)與算法typedefstructChomskyeft=(0J);ight=(j+1,()-j);ight0=#&pi.()=1)eft; s=empty;return s;ind(pi.left)=

4、0);j+)if(is_empty(p).find(pi.right.j)=0&(pi.left0)() noend=noend+pi.left;for(j=0;jpi.();j+)if(A=pi.rightj&pi.rightj=0&(pi.rightj)() break;elsenoend=noend+pi.(j,1); void First(Chomsky *p,int n,char m,int mm)eft0)if(a=pi.right0)firstmm=firstmm+pi.(0,1);if(pi.right0=#)firstmm=firstmm+pi.(0,1);if(A=pi.r

5、ight0)for(j=0;jpi.();j+)if(A=pi.rightj&pi.rightj=Z)flag+;if(flag=j);j+)for(x=0;xn;x+)if(pi.rightj=px.left0&px.right0=#)flag+;break;if(flag=j);j+)for(x=0;xn;x+)if(pi.rightj=noendx)break;y=x;if(firsty=)First(p,n,pi.rightj,x);f=firsty;for(x=0;x();x+)if(fx=#)if(x=()-1)f=(0,x);else f=(0,x)+(x+1);firstmm=

6、firstmm+f;firstmm=firstmm+#;elsefor(j=0;jpi.();j+)for(x=0;xn;x+)if(pi.rightj=noendx)break;y=x;if(firsty=)First(p,n,pi.rightj,x);f=firsty;for(x=0;x();x+)if(fx=#)if(x=()-1)f=(0,x);else f=(0,x)+(x+1);firstmm=firstmm+f;void Follow(Chomsky *p,int n,int m);j+)if(noendm=pi.rightj)if(jpi.()-1&a=pi.rightj+1&

7、pi.rightj+1=z)followm=followm+pi.(j+1,1);if(jpi.()-1&A=pi.rightj+1&pi.rightj+1=Z)for(y=0;y();y+)if(noendy=pi.rightj+1)break;fo=firsty;for(x=0;xfirsty.length();x+)if(0=firsty.find(#)&firsty.find(#)firsty.length()fo=firsty.substr(0,firstm.find(#)+firsty.substr(firsty.find(#)+1);followm=followm+fo;for(x=0;xn;x+)if(pi.rightj+1=px.left0&px.right0=#)break;if(x!=n)eft0=noendy)break;k=y;if(followk=)Follow(p,n,y);followm=followm+followk;if(j=pi.()-1)for(y=0;yn;y+)if(pi.left0=noendy)break;k=y;if(followk=)Follow(p,n,y);fol