編譯原理實(shí)驗(yàn)七：LL(1)文法的判斷

1、實(shí)驗(yàn)七：LL(1)文法的判斷 一：要求輸入：任意的上下文無(wú)關(guān)文法。輸出：判斷是否為L(zhǎng)L（1）文法二：實(shí)驗(yàn)?zāi)康?掌握LL(1)的判斷，掌握求first和follow集合的算法2熟悉運(yùn)用C/C+語(yǔ)言對(duì)求first和follow集合進(jìn)行實(shí)現(xiàn) 三：實(shí)驗(yàn)原理設(shè)x1x2xn，F(xiàn)IRST（）可按下列方法求得：令FIRST（），i1；（1）若xiVT，則xiFIRST（）；（2）若xiVN； 若 FIRST（xi），則FIRST（xi）FIRST（）； 若FIRST（xi），則FIRST（xi）FIRST（）；（3）ii+1，重復(fù)（1）、（2），直到xiVT，（i2，3，n）或xiVN且若 FIRST（xi）

2、或i>n為止。當(dāng)一個(gè)文法中存在產(chǎn)生式時(shí)，例如，存在A，只有知道哪些符號(hào)可以合法地出現(xiàn)在非終結(jié)符A之后，才能知道是否選擇A產(chǎn)生式。這些合法地出現(xiàn)在非終結(jié)符A之后的符號(hào)組成的集合被稱為FOLLOW集合。下面我們給出文法的FOLLOW集的定義。設(shè)文法GS（VN，VT，P，S），則 FOLLOW（A）a | S Aa ，aVT。若S A，#FOLLOW（A）。由定義可以看出，F(xiàn)OLLOW（A）是指在文法GS的所有句型中，緊跟在非終結(jié)符A后的終結(jié)符號(hào)的集合。FOLLOW集可按下列方法求得：（1）對(duì)于文法GS的開(kāi)始符號(hào)S，有#FOLLOW（S）；（2）若文法GS中有形如BxAy的規(guī)則，其中x，yV

3、*，則FIRST（y）FOLLOW（A）；（3）若文法GS中有形如BxA的規(guī)則，或形如BxAy的規(guī)則且FIRST（y），其中x，yV *，則FOLLOW（B）FOLLOW（A）；四：數(shù)據(jù)結(jié)構(gòu)與算法typedef struct Chomsky /定義一個(gè)產(chǎn)生式結(jié)構(gòu)體 string left; /定義產(chǎn)生式的左部 string right; /定義產(chǎn)生式的右部Chomsky;void apart(Chomsky *p,int i) /分開(kāi)產(chǎn)生式左右部，i代表產(chǎn)生式的編號(hào)string is_empty(Chomsky *p)/判斷某非終結(jié)符能否直接推出空，空用#代替string isempty(Ch

4、omsky *p)/可以間接推出空的非終結(jié)符void search(Chomsky *p,int n)/提取產(chǎn)生式中的非終結(jié)符void First(Chomsky *p,int n,char m,int mm)/求文法中非終結(jié)符的First集void Follow(Chomsky *p,int n,int m)/求文法的follow集string erase(string s)/去First集及follow集中的重復(fù)字符void select(string s1,string s2)/求產(chǎn)生式的select集,s1是產(chǎn)生式左部，s2是產(chǎn)生式右部五：出錯(cuò)分析1:select集計(jì)算不出，關(guān)鍵在于能

5、產(chǎn)生空的非終結(jié)符沒(méi)有求出來(lái)2:單個(gè)符號(hào)的first集與一串符號(hào)的first集區(qū)別3:實(shí)驗(yàn)最后沒(méi)能輸出select集，沒(méi)能判斷出來(lái)是否是LL(1)文法 六：實(shí)驗(yàn)結(jié)果與分析七：源代碼#include<iostream>#include<string>using namespace std;#define max 100typedef struct Chomsky /定義一個(gè)產(chǎn)生式結(jié)構(gòu)體 string left; /定義產(chǎn)生式的左部 string right; /定義產(chǎn)生式的右部Chomsky;int n;/產(chǎn)生式總數(shù)string strings;/存儲(chǔ)產(chǎn)生式string n

6、oend;/存放文法中的非終結(jié)符string empty;/存放可以推出空的非終結(jié)符string firstmax;/存放非終結(jié)符的first集string followmax;/存放非終結(jié)符的follow集string selectmax;/存放產(chǎn)生式的select集void apart(Chomsky *p,int i) /分開(kāi)產(chǎn)生式左右部，i代表產(chǎn)生式的編號(hào)int j; for(j=0;j<strings.length();j+)if(stringsj='-')pi.left=strings.substr(0,j);/從0開(kāi)始的j長(zhǎng)度的子串，即0j-1pi.righ

7、t=strings.substr(j+1,strings.length()-j);/從j+1開(kāi)始的后面子串/*string is_empty(Chomsky *p)/判斷某非終結(jié)符能否直接推出空，空用#代替/如果可以，返回1/不可以，返回0int i;string s;for(i=0;i<n;i+)if (pi.right0="#"&&pi.right.length()=1)/直接推出空的empty=empty+pi.left;s=empty;return s;/s存放能直接推出空的非終結(jié)符string isempty(Chomsky *p)/可以間接

8、推出空的非終結(jié)符int i,j;string s1;for(i=0;i<n;i+)if(is_empty(p).find(pi.left)>=0)/若此非終結(jié)符已經(jīng)存在直接推出空那里，在此無(wú)需重復(fù)計(jì)算elsefor(j=0;j<(int)pi.right.length();j+)if(is_empty(p).find(pi.right.j)<0)if(j=(int)pi.right.length()/如果右部所有符號(hào)都在直接推出空那里，則此左部也可以推出空s1=s1+pi.left0;*/void search(Chomsky *p,int n)/提取產(chǎn)生式中的非終結(jié)符

9、int i,j;for(i=0;i<n;i+)if(!(noend.find(pi.left0)>=0&&noend.find(pi.left0)<noend.length()noend=noend+pi.left;for(j=0;j<pi.right.length();j+)if('A'<=pi.rightj&&pi.rightj<='Z')if(noend.find(pi.rightj)>=0&&noend.find(pi.rightj)<noend.length

10、()break;elsenoend=noend+pi.right.substr(j,1);void First(Chomsky *p,int n,char m,int mm)/求文法中非終結(jié)符的First集int length=noend.length();string f;int i,j,x,y;int flag=0;for(i=0;i<n;i+)if(m=pi.left0)if('a'<=pi.right0&&'z'>=pi.right0) firstmm=firstmm+pi.right.substr(0,1);if(pi

11、.right0='#') firstmm=firstmm+pi.right.substr(0,1);if('A'<=pi.right0&&'Z'>=pi.right0)for(j=0;j<pi.right.length();j+)if('A'<=pi.rightj&&pi.rightj<='Z')flag+;if(flag=j)/產(chǎn)生式的右部均為非終結(jié)符flag=0;for(j=0;j<pi.right.length();j+)for(x=0;x&

12、lt;n;x+)if(pi.rightj=px.left0&&px.right0='#')flag+;break;if(flag=j)/產(chǎn)生式右部的全部非終結(jié)符均能推出空f(shuō)or(j=0;j<pi.right.length();j+)for(x=0;x<n;x+)if(pi.rightj=noendx)break;y=x;if(firsty="")First(p,n,pi.rightj,x); f=firsty;for(x=0;x<f.length();x+)if(fx='#')if(x=f.length()-

13、1)f=f.substr(0,x);else f=f.substr(0,x)+f.substr(x+1); firstmm=firstmm+f; firstmm=firstmm+"#"elsefor(j=0;j<pi.right.length();j+)for(x=0;x<n;x+)if(pi.rightj=noendx)break;y=x;if(firsty="")First(p,n,pi.rightj,x);f=firsty;for(x=0;x<f.length();x+)if(fx='#')if(x=f.lengt

14、h()-1)f=f.substr(0,x);else f=f.substr(0,x)+f.substr(x+1); firstmm=firstmm+f;void Follow(Chomsky *p,int n,int m)/求文法的follow集int i,j,x,y,k;string fo;for(i=0;i<n;i+)for(j=0;j<pi.right.length();j+)if(noendm=pi.rightj)if(j<pi.right.length()-1&&'a'<=pi.rightj+1&&pi.righ

15、tj+1<='z') followm=followm+pi.right.substr(j+1,1); if(j<pi.right.length()-1&&'A'<=pi.rightj+1&&pi.rightj+1<='Z')for(y=0;y<noend.length();y+)if(noendy=pi.rightj+1)break;fo=firsty;for(x=0;x<firsty.length();x+)if(0<=firsty.find('#')&a

16、mp;&firsty.find('#')<firsty.length()fo=firsty.substr(0,firstm.find('#')+firsty.substr(firsty.find('#')+1); followm=followm+fo; for(x=0;x<n;x+)if(pi.rightj+1=px.left0&&px.right0='#')break; if(x!=n)/非終結(jié)符后面的部分可以推出空f(shuō)or(y=0;y<n;y+)if(pi.left0=noendy)br

17、eak; k=y; if(followk="")Follow(p,n,y); followm=followm+followk; if(j=pi.right.length()-1) for(y=0;y<n;y+) if(pi.left0=noendy)break; k=y; if(followk="")Follow(p,n,y); followm=followm+followk; string erase(string s)/去First集及follow集中的重復(fù)字符int i,j;for(i=0;i<s.length();i+)for(j=0

18、;j<s.length();j+)if(i!=j&&si=sj)s=s.substr(0,j)+s.substr(j+1);return s;/*void select(string s1,string s2)/求產(chǎn)生式的select集,s1是產(chǎn)生式左部，s2是產(chǎn)生式右部if()/即s2可以推出空#cout<<s1<<"->"<<s2<<"="<<first(s2)<<endl;else/即s2不可以推出空#cout<<s1<<&q

19、uot;->"<<s2<<"="<<first(s2)-"#"+<<follow(s1)<<endl;*/void main()cout<<".編譯原理實(shí)驗(yàn)七：LL(1)文法的判斷."<<endl;int i,j,m;char f;/存放文法開(kāi)始符號(hào)cout<<"請(qǐng)輸入文法產(chǎn)生式個(gè)數(shù)N以及各產(chǎn)生式（空用#代替，鏈接左右部的為-）："<<endl;cin>>n;Chomsky *p=

20、new Chomskyn; / 初始化產(chǎn)生式數(shù)組 for(i=0;i<n;i+)strings.erase();/清除cin>>strings; apart(p,i); cout<<"請(qǐng)輸入該文法的開(kāi)始符號(hào)："<<endl;cin>>f;search(p,n);/提取產(chǎn)生式中的非終結(jié)符/empty=is_empty(p)+isempty(p);/可以推出空的所有非終結(jié)符for(m=0;m<noend.length();m+)if(firstm="")First(p,n,noendm,m);cout<<"