南郵編譯原理報(bào)告實(shí)驗(yàn)二

1、實(shí)驗(yàn)報(bào)告（ 2015 / 2016 學(xué)年 第 二 學(xué)期）課程名稱編譯原理實(shí)驗(yàn)名稱語法分析器的構(gòu)造實(shí)驗(yàn)時(shí)間2016年5月26日指導(dǎo)單位計(jì)算機(jī)軟件教學(xué)中心指導(dǎo)教師黃海平學(xué)生姓名班級(jí)學(xué)號(hào)學(xué)院 (系)計(jì)算機(jī)學(xué)院、專業(yè)計(jì)算機(jī)科學(xué)軟件學(xué)院與技術(shù)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱語法分析器的構(gòu)造指導(dǎo)教師黃海平實(shí)驗(yàn)類型驗(yàn)證實(shí)驗(yàn)學(xué)時(shí)4實(shí)驗(yàn)時(shí)間2016.5.26一、實(shí)驗(yàn)?zāi)康暮鸵髮?shí)驗(yàn)?zāi)康模涸O(shè)計(jì)、編制、調(diào)試一個(gè)LL(1) 語法分析器，利用語法分析器對(duì)符號(hào)串的識(shí)別，加深對(duì)語法分析原理的理解。實(shí)驗(yàn)要求：1、檢測(cè)左遞歸，如果有則進(jìn)行消除；2、求解 FIRST 集和 FOLLOW 集；3、構(gòu)建 LL(1) 分析表；4、構(gòu)建 LL 分析程序，

2、對(duì)于用戶輸入的句子，能夠利用所構(gòu)造的分析程序進(jìn)行分析，并顯示出分析過程。以上實(shí)驗(yàn)要求可分兩個(gè)同學(xué)完成。例如構(gòu)建分析表一個(gè)同學(xué)完成、構(gòu)建分析程序并分析符號(hào)串另一個(gè)同學(xué)完成。二、 實(shí)驗(yàn)環(huán)境 (實(shí)驗(yàn)設(shè)備 )硬件：計(jì)算機(jī)軟件： Visual C +6.0- 2 -二、實(shí)驗(yàn)原理及內(nèi)容實(shí)驗(yàn)內(nèi)容：設(shè)計(jì)并實(shí)現(xiàn)一個(gè)LL(1) 語法分析器，實(shí)現(xiàn)對(duì)算術(shù)文法GE:E-E+T|TT-T*F|FF-(E)|i所定義的符號(hào)串進(jìn)行識(shí)別，例如符號(hào)串a(chǎn)bc+age+80為文法所定義的句子，符號(hào)串 (abc-80(*s5)不是文法所定義的句子。實(shí)驗(yàn)代碼：#include#include#includeusing namespace

3、 std;void input_grammer(string *G)/ 輸入文法 G,n個(gè)非終結(jié)符int i=0;/ 計(jì)數(shù)char ch=y;while(ch=y)cinGi+;coutch;- 3 -void preprocess(string *G,string *P,string &U,string &u,int &n,int &t,int &k)/ 將文法 G預(yù)處理產(chǎn)生式集合 P，非終結(jié)符、終結(jié)符集合 U、u，int i,j,r,temp;/ 計(jì)數(shù)char C;/記錄規(guī)則中（）后的符號(hào)int flag;/ 檢測(cè)到（）n=t=k=0;for( i=0;i50;i+)Pi=;/ 字符串如果

4、不初始化，在使用Pij=a 時(shí)將不能改變，可以用 Pi.append(1,a)U=u=;/ 字符串如果不初始化，無法使用Ui=a賦值，可以用 U.append(1,a)for(n=0;!Gn.empty();n+) Un=Gn0;/ 非終結(jié)符集合， n為非終結(jié)符個(gè)數(shù)for(i=0;in;i+)for(j=4;jGi.length();j+)if(U.find(Gij)=string:npos&u.find(Gij)=string:npos)if(Gij!=|&Gij!=)/if(Gij!=(&Gij!=)&Gij!=|&Gij!=)- 4 -ut+=Gij;/ 終結(jié)符集合， t為終結(jié)符個(gè)數(shù)fo

5、r(i=0;in;i+)flag=0;r=4;for(j=4;jGi.length();j+)Pk0=Ui;Pk1=:;Pk2=:;Pk3=; /* if(Gij=()j+;flag=1; for(temp=j;Gitemp!=);temp+); C=Gitemp+1;/C記錄（）后跟的字符，將 C添加到（）中所有字符串后面if(Gij=) j+;flag=0;*/if(Gij=|)/if(flag=1) Pkr+=C;k+;j+;- 5 -Pk0=Ui;Pk1=:;Pk2=:;Pk3=;r=4;Pkr+=Gij;elsePkr+=Gij;k+;/ 獲得產(chǎn)生式集合 P，k為產(chǎn)生式個(gè)數(shù)int e

6、liminate_1(string *G,string *P,string U,string *GG)/消除文法 G1中所有直接左遞歸得到文法G2，要能夠消除含有多個(gè)左遞歸的情況）string arfa,beta;/所有形如 A:=A |中的 、連接起來形成的字符串a(chǎn)rfa、betaint i,j,temp,m=0;/ 計(jì)數(shù)int flag=0;/flag=1 表示文法有左遞歸int flagg=0;/flagg=1 表示某條規(guī)則有左遞歸char C=A;/由于消除左遞歸新增的非終結(jié)符，從A 開始增加，只要不在原來問法的非終結(jié)符中即可加入- 6 -for(i=0;i20&Ui!= ;i+)fl

7、agg=0; arfa=beta=; for(j=0;j100&Pj0!= ;j+)if(Pj0=Ui)if(Pj4=Ui)/ 產(chǎn)生式 j有左遞歸flagg=1;for(temp=5;Pjtemp!= ;temp+) arfa.append(1,Pjtemp);if(Pj+14=Ui) arfa.append(|);/ 不止一個(gè)產(chǎn)生式含有左遞歸elsefor(temp=4;Pjtemp!= ;temp+) beta.append(1,Pjtemp); if(Pj+10=Ui&Pj+14!=Ui) beta.append(|);if(flagg=0)/ 對(duì)于不含左遞歸的文法規(guī)則不重寫- 7 -G

8、Gm=Gi; m+;elseflag=1;/文法存在左遞歸GGm.append(1,Ui);GGm.append(:=);if(beta.find(|)!=string:npos) GGm.append(+beta+);else GGm.append(beta);while(U.find(C)!=string:npos)C+;GGm.append(1,C);m+;GGm.append(1,C);GGm.append(:=);if(arfa.find(|)!=string:npos) GGm.append(+arfa+);else GGm.append(arfa);GGm.append(1,C)

9、;GGm.append(|);m+;C+;/A:=A改|寫成 A:= A，A = A|， return flag;int* ifempty(string* P,string U,int k,int n)- 8 -int* empty=new int n;/ 指示非終結(jié)符能否推導(dǎo)到空串int i,j,r;for(r=0;rn;r+) emptyr=0;/ 默認(rèn)所有非終結(jié)符都不能推導(dǎo)到空int flag=1;/1 表示 empty數(shù)組有修改int step=100;/假設(shè)一條規(guī)則最大推導(dǎo)步數(shù)為步while(step-)for(i=0;ik;i+)r=U.find(Pi0);if(Pi4=) emp

10、tyr=1;/直接推導(dǎo)到空elsefor(j=4;Pij!= ;j+)if(U.find(Pij)!=string:npos)if(emptyU.find(Pij)=0) break;elsebreak;if(Pij= ) emptyr=1;/多步推導(dǎo)到空- 9 -else flag=0;return empty;string* FIRST_X(string* P,string U,string u,int* empty,int k,int n)int i,j,r,s,tmp;string* first=new stringn;char a;int step=100;/最大推導(dǎo)步數(shù)while(

11、step-)/ coutstep100-stependl; for(i=0;ik;i+)/coutPiendl;r=U.find(Pi0);if(Pi4=&firstr.find()=string:npos)firstr.append(1,);/規(guī)則右部首符號(hào)為空else-10-for(j=4;Pij!= ;j+)a=Pij;if(u.find(a)!=string:npos&firstr.find(a)=string:npos)/規(guī)則右部首符號(hào)是終結(jié)符firstr.append(1,a);break;/添加并結(jié)束if(U.find(Pij)!=string:npos)/規(guī)則右部首符號(hào)是非終結(jié)

12、符,形如 X： =Y1Y2.Yks=U.find(Pij);/coutPij:n;for(tmp=0;firststmp!=0;tmp+)a=firststmp;if(a!=&firstr.find(a)=string:npos)/將FIRSTY1 中的非空符加入firstr.append(1,a);-11-if(!emptys) break;/ 若Y1不能推導(dǎo)到空，結(jié)束if(Pij= )if(firstr.find()=string:npos)firstr.append(1,);/ 若Y1、Y2.Yk 都能推導(dǎo)到空，則加入空符號(hào)return first;string FIRST(string

13、 U,string u,string* first,string s)/ 求符號(hào)串 s=X1X2.Xn 的FIRST集int i,j,r;char a;stringfir;for(i=0;is.length();i+)if(si=) fir.append(1,);if(u.find(si)!=string:npos&fir.find(si)=string:npos)-12-fir.append(1,si);break;/X1 是終結(jié)符，添加并結(jié)束循環(huán)if(U.find(si)!=string:npos)/X1 是非終結(jié)符r=U.find(si);for(j=0;firstrj!=0;j+)a=

14、firstrj;if(a!=&fir.find(a)=string:npos)/將FIRST(X1) 中的非空符號(hào)加入fir.append(1,a);if(firstr.find()=string:npos) break;/ 若X1不可推導(dǎo)到空，循環(huán)停止if(i=s.length()/ 若X1-Xk 都可推導(dǎo)到空if(fir.find(si)=string:npos) /fir 中還未加入空符號(hào) fir.append(1,);return fir;string* create_table(string *P,string U,string u,int n,int t,int k,string*

15、 first)/ 構(gòu)造分析表， P為文法 G的產(chǎn)生式構(gòu)成的集合-13-int i,j,p,q;string arfa;/記錄規(guī)則右部string fir,follow;string FOLLOW5=)#,)#,+)#,+)#,+*)#; string *table=new string*n; for(i=0;in;i+) tablei=new stringt+1; for(i=0;in;i+)for(j=0;jt+1;j+)tableij=;/table存儲(chǔ)分析表的元素， “”表示 errorfor(i=0;ik;i+)arfa=Pi;arfa.erase(0,4);/刪除前個(gè)字符，如： E:

16、=E+T,則arfa=E+Tfir=FIRST(U,u,first,arfa);for(j=0;jt;j+)p=U.find(Pi0);if(fir.find(uj)!=string:npos)q=j;-14-tablepq=Pi;/ 對(duì)first（）中的每一終結(jié)符置相應(yīng)的規(guī)則if(fir.find()!=string:npos)follow=FOLLOWp;/ 對(duì)規(guī)則左部求 follow()for(j=0;jt;j+)if(q=follow.find(uj)!=string:npos)q=j;tablepq=Pi;/ 對(duì)follow （）中的每一終結(jié)符置相應(yīng)的規(guī)則tablept=Pi;/ 對(duì)

17、#所在元素置相應(yīng)規(guī)則return table;void analyse(string *table,string U,string u,int t,string s)/分析符號(hào)串 sstring stack;/分析棧-15-string ss=s;/記錄原符號(hào)串char x;/棧頂符號(hào)char a;/下一個(gè)要輸入的字符int flag=0;/ 匹配成功標(biāo)志int i=0,j=0,step=1;/ 符號(hào)棧計(jì)數(shù)、輸入串計(jì)數(shù)、步驟數(shù) int p,q,r;string temp;for(i=0;!si;i+)if(u.find(si)=string:npos)/ 出現(xiàn)非法的符號(hào)couts不是該文法的句

18、子 n;return;s.append(1,#);stack.append(1,#);/進(jìn)入分析#棧stack.append(1,U0);i+;/文法開始符進(jìn)入分析棧a=s0;/coutstackendl;cout步驟分析棧余留輸入串所用產(chǎn)生式n;while(!flag)-16-/ cout 步驟分析棧余留輸入串所用產(chǎn)生式 ncoutstepstacks;x=stacki;stack.erase(i,1);i-;/取棧頂符號(hào) x,并從棧頂退出/coutxendl;if(u.find(x)!=string:npos)/x 是終結(jié)符的情況if(x=a)s.erase(0,1);a=s0;/棧頂符號(hào)

19、與當(dāng)前輸入符號(hào)匹配，則輸入下一個(gè)符號(hào)coutn;/ 未使用產(chǎn)生式，輸出空elsecouterrorn;coutss不是該文法的句子 n;break;if(x=#)-17-if(a=#)flag=1;cout 成功 n;/ 棧頂和余留輸入串都為#，匹配成功elsecouterrorn;coutss不是該文法的句子 n;break;if(U.find(x)!=string:npos)/x 是非終結(jié)符的情況p=U.find(x);q=u.find(a);if(a=#) q=t;temp=tablepq;couttemp3)-18-if(tempr!=)stack.append(1,tempr);/將

20、X:=x1x2. 的規(guī)則右部各符號(hào)壓棧i+;r-;elsecouterrorn;coutss不是該文法的句子 n;break;step+;if(flag)coutendlss是該文法的句子 n;int main()-19-int i,j;string *G=new string50;/ 文法 Gstring *P=new string50;/ 產(chǎn)生式集合 Pstring U,u;/文法 G非終結(jié)符集合 U，終結(jié)符集合 uint n,t,k;/ 非終結(jié)符、終結(jié)符個(gè)數(shù) ,產(chǎn)生式數(shù)string *GG=new string50;/ 消除左遞歸后的文法 GGstring *PP=new string5

21、0;/ 文法 GG的產(chǎn)生式集合 PPstring UU,uu;/文法 GG非終結(jié)符集合 U，終結(jié)符集合 uint nn,tt,kk;/ 消除左遞歸后的非終結(jié)符、終結(jié)符個(gè)數(shù),產(chǎn)生式數(shù)string* table;/ 分析表cout歡迎使用 LL(1) 語法分析器 !nnn;cout請(qǐng)輸入文法（同一左部的規(guī)則在同一行輸入，例如：E:=E+T|T；用 表示空串） n;input_grammer(G);preprocess(G,P,U,u,n,t,k);coutn該文法有 n 個(gè)非終結(jié)符： n;for(i=0;in;i+)coutUi;coutendl;cout該文法有 t 個(gè)終結(jié)符： n;for(i=0;it;i+)coutui;coutnn左遞歸檢測(cè)與消除 nn;-20-if(eliminate_1(G,P,U,GG)preprocess(GG,PP,UU,uu,nn,tt,kk);cout該文法存在左遞歸！ nn消除左遞歸后的文法 :nn;for(i=0;inn;i+)coutGGiendl;coutendl;cout新文法有 nn 個(gè)非終結(jié)符： n;for(i=0;inn;i+)coutUUi;coutendl;cout新文法有 tt 個(gè)終結(jié)符： n;for(i=0;itt;i+)coutuui;coutendl;