編譯原理實驗七：LL(1)文法的判斷

實驗七：LL(1)文法的判斷一：要求輸入：任意的上下文無關文法。輸出：判斷是否為LL（1）文法二：實驗目的1．掌握LL(1)的判斷，掌握求first和follow集合的算法2．熟悉運用C/C++語言對求first和follow集合進行實現(xiàn)三：實驗原理設α＝x1x2…xn，F(xiàn)IRST（α）可按下列方法求得：令FIRST（α）＝Φ，i＝1；（1）若xi∈VT，則xi∈FIRST（α）；（2）若xi∈VN；①若εFIRST（xi），則FIRST（xi）∈FIRST（α）；②若ε∈FIRST（xi），則FIRST（xi）－{ε}∈FIRST（α）；（3）i＝i+1，重復（1）、（2），直到xi∈VT，（i＝2，3，…，n）或xi∈VN且若εFIRST（xi）或i>n為止。當一個文法中存在ε產(chǎn)生式時，例如，存在A→ε，只有知道哪些符號可以合法地出現(xiàn)在非終結(jié)符A之后，才能知道是否選擇A→ε產(chǎn)生式。這些合法地出現(xiàn)在非終結(jié)符A之后的符號組成的集合被稱為FOLLOW集合。下面我們給出文法的FOLLOW集的定義。設文法G[S]＝（VN，VT，P，S），則FOLLOW（A）＝{a|S…Aa…，a∈VT}。若S…A，#∈FOLLOW（A）。由定義可以看出，F(xiàn)OLLOW（A）是指在文法G[S]的所有句型中，緊跟在非終結(jié)符A后的終結(jié)符號的集合。FOLLOW集可按下列方法求得：（1）對于文法G[S]的開始符號S，有#∈FOLLOW（S）；（2）若文法G[S]中有形如B→xAy的規(guī)則，其中x，y∈V*，則FIRST（y）－{ε}∈FOLLOW（A）；（3）若文法G[S]中有形如B→xA的規(guī)則，或形如B→xAy的規(guī)則且ε∈FIRST（y），其中x，y∈V*，則FOLLOW（B）∈FOLLOW（A）；四：數(shù)據(jù)結(jié)構(gòu)與算法typedefstructChomsky//定義一個產(chǎn)生式結(jié)構(gòu)體{stringleft;//定義產(chǎn)生式的左部stringright;//定義產(chǎn)生式的右部}Chomsky;voidapart(Chomsky*p,inti)//分開產(chǎn)生式左右部，i代表產(chǎn)生式的編號stringis_empty(Chomsky*p)//判斷某非終結(jié)符能否直接推出空，空用#代替stringisempty(Chomsky*p)//可以間接推出空的非終結(jié)符voidsearch(Chomsky*p,intn)//提取產(chǎn)生式中的非終結(jié)符voidFirst(Chomsky*p,intn,charm,intmm)//求文法中非終結(jié)符的First集voidFollow(Chomsky*p,intn,intm)//求文法的follow集stringerase(strings)//去First集及follow集中的重復字符voidselect(strings1,strings2)//求產(chǎn)生式的select集,s1是產(chǎn)生式左部，s2是產(chǎn)生式右部五：出錯分析1:select集計算不出，關鍵在于能產(chǎn)生空的非終結(jié)符沒有求出來2:單個符號的first集與一串符號的first集區(qū)別3:實驗最后沒能輸出select集，沒能判斷出來是否是LL(1)文法六：實驗結(jié)果與分析七：源代碼#include<iostream>#include<string>usingnamespacestd;#definemax100typedefstructChomsky//定義一個產(chǎn)生式結(jié)構(gòu)體{stringleft;//定義產(chǎn)生式的左部stringright;//定義產(chǎn)生式的右部}Chomsky;intn;//產(chǎn)生式總數(shù)stringstrings;//存儲產(chǎn)生式stringnoend;//存放文法中的非終結(jié)符stringempty;//存放可以推出空的非終結(jié)符stringfirst[max];//存放非終結(jié)符的first集stringfollow[max];//存放非終結(jié)符的follow集stringselect[max];//存放產(chǎn)生式的select集voidapart(Chomsky*p,inti)//分開產(chǎn)生式左右部，i代表產(chǎn)生式的編號{intj;for(j=0;j<strings.length();j++)if(strings[j]=='-'){p[i].left=strings.substr(0,j);//從0開始的j長度的子串，即0~j-1p[i].right=strings.substr(j+1,strings.length()-j);//從j+1開始的后面子串}}/*stringis_empty(Chomsky*p)//判斷某非終結(jié)符能否直接推出空，空用#代替{//如果可以，返回1//不可以，返回0inti;strings;for(i=0;i<n;i++){if(p[i].right[0]="#"&&p[i].right.length()==1)//直接推出空的{empty=empty+p[i].left;}}s=empty;returns;//s存放能直接推出空的非終結(jié)符}stringisempty(Chomsky*p)//可以間接推出空的非終結(jié)符{inti,j;strings1;for(i=0;i<n;i++){if(is_empty(p).find(p[i].left)>=0)//若此非終結(jié)符已經(jīng)存在直接推出空那里，在此無需重復計算{}else{for(j=0;j<(int)p[i].right.length();j++){if(is_empty(p).find(p[i].right.[j])<0){}}if(j==(int)p[i].right.length())//如果右部所有符號都在直接推出空那里，則此左部也可以推出空{(diào)s1=s1+p[i].left[0];}}}}*/voidsearch(Chomsky*p,intn)//提取產(chǎn)生式中的非終結(jié)符{inti,j;for(i=0;i<n;i++){if(!(noend.find(p[i].left[0])>=0&&noend.find(p[i].left[0])<noend.length()))noend=noend+p[i].left;for(j=0;j<p[i].right.length();j++){if('A'<=p[i].right[j]&&p[i].right[j]<='Z'){if(noend.find(p[i].right[j])>=0&&noend.find(p[i].right[j])<noend.length())break;elsenoend=noend+p[i].right.substr(j,1);}}}}voidFirst(Chomsky*p,intn,charm,intmm)//求文法中非終結(jié)符的First集{intlength=noend.length();stringf;inti,j,x,y;intflag=0;for(i=0;i<n;i++){if(m==p[i].left[0]){if('a'<=p[i].right[0]&&'z'>=p[i].right[0])first[mm]=first[mm]+p[i].right.substr(0,1);if(p[i].right[0]=='#')first[mm]=first[mm]+p[i].right.substr(0,1);if('A'<=p[i].right[0]&&'Z'>=p[i].right[0]){for(j=0;j<p[i].right.length();j++){if('A'<=p[i].right[j]&&p[i].right[j]<='Z')flag++;}if(flag==j)//產(chǎn)生式的右部均為非終結(jié)符{flag=0;for(j=0;j<p[i].right.length();j++){for(x=0;x<n;x++)if(p[i].right[j]==p[x].left[0]&&p[x].right[0]=='#'){flag++;break;}}if(flag==j)//產(chǎn)生式右部的全部非終結(jié)符均能推出空{(diào)for(j=0;j<p[i].right.length();j++){for(x=0;x<n;x++){if(p[i].right[j]==noend[x])break;}y=x;if(first[y]=="")First(p,n,p[i].right[j],x);f=first[y];for(x=0;x<f.length();x++){if(f[x]=='#'){if(x==f.length()-1)f=f.substr(0,x);elsef=f.substr(0,x)+f.substr(x+1);}}first[mm]=first[mm]+f;}first[mm]=first[mm]+"#";}else{for(j=0;j<p[i].right.length();j++){for(x=0;x<n;x++){if(p[i].right[j]==noend[x])break;}y=x;if(first[y]=="")First(p,n,p[i].right[j],x);f=first[y];for(x=0;x<f.length();x++){if(f[x]=='#'){if(x==f.length()-1)f=f.substr(0,x);elsef=f.substr(0,x)+f.substr(x+1);}}first[mm]=first[mm]+f;}}}}}}}voidFollow(Chomsky*p,intn,intm)//求文法的follow集{inti,j,x,y,k;stringfo;for(i=0;i<n;i++){for(j=0;j<p[i].right.length();j++){if(noend[m]==p[i].right[j]){if(j<p[i].right.length()-1&&'a'<=p[i].right[j+1]&&p[i].right[j+1]<='z')follow[m]=follow[m]+p[i].right.substr(j+1,1);if(j<p[i].right.length()-1&&'A'<=p[i].right[j+1]&&p[i].right[j+1]<='Z'){for(y=0;y<noend.length();y++){if(noend[y]==p[i].right[j+1])break;}fo=first[y];for(x=0;x<first[y].length();x++){if(0<=first[y].find('#')&&first[y].find('#')<first[y].length())fo=first[y].substr(0,first[m].find('#'))+first[y].substr(first[y].find('#')+1);}follow[m]=follow[m]+fo;for(x=0;x<n;x++){if(p[i].right[j+1]==p[x].left[0]&&p[x].right[0]=='#')break;}if(x!=n)//非終結(jié)符后面的部分可以推出空{(diào)for(y=0;y<n;y++){if(p[i].left[0]==noend[y])break;}k=y;if(follow[k]=="")Follow(p,n,y);follow[m]=follow[m]+follow[k];}}if(j==p[i].right.length()-1){for(y=0;y<n;y++){if(p[i].left[0]==noend[y])break;}k=y;if(follow[k]=="")Follow(p,n,y);follow[m]=follow[m]+follow[k];}}}}}stringerase(strings)//去First集及follow集中的重復字符{inti,j;for(i=0;i<s.length();i++){for(j=0;j<s.length();j++){if(i!=j&&s[i]==s[j])s=s.substr(0,j)+s.substr(j+1);}}returns;}/*voidselect(strings1,strings2)//求產(chǎn)生式的select集,s1是產(chǎn)生式左部，s2是產(chǎn)生式右部{if()//即s2可以推出空#{cout<<s1<<"->"<<s2<<"="<<first(s2)<<endl;}else//即s2不可以推出空#{cout<<s1<<"->"<<s2<<"="<<first(s2)-"#"+<<follow(s1)<<endl;}}*/voidmain(){cout<<"....................編譯原理實驗七：LL(1)文法的判斷...................."<<endl;inti,j,m;charf;//存放文法開始符號cout<<"請輸入文法產(chǎn)生式個數(shù)N以及各產(chǎn)生式（空用#代替，鏈接左右部的為-）："<<endl;cin>>n;Chomsky*p=newChomsky[n];//初始化產(chǎn)生式數(shù)組for(i=0;i<n;i++){strings.erase();//清除cin>>strings;apart(p,i);}cout<<"請輸入該文法的開始符號："<<e