1、LL（1）分析器的構(gòu)造實(shí)驗(yàn)報(bào)告一、 實(shí)驗(yàn)名稱(chēng)LL(1)分析器的構(gòu)造二、實(shí)驗(yàn)?zāi)康?設(shè)計(jì)、編制、調(diào)試一個(gè)LL(1)語(yǔ)法分析器，利用語(yǔ)法分析器對(duì)符號(hào)串的識(shí)別，加深對(duì)語(yǔ)法分析原理的理解。三、實(shí)驗(yàn)內(nèi)容和要求 設(shè)計(jì)并實(shí)現(xiàn)一個(gè)LL(1)語(yǔ)法分析器，實(shí)現(xiàn)對(duì)算術(shù)文法:GE:E-E+T|T T-T*F|F F-(E)|i所定義的符號(hào)串進(jìn)行識(shí)別，例如符號(hào)串i+i*i為文法所定義的句子，符號(hào)串ii+*i+不是文法所定義的句子。 實(shí)驗(yàn)要求: 1、檢測(cè)左遞歸，如果有則進(jìn)行消除； 2、求解FIRST集和FOLLOW集； 3、構(gòu)建LL(1)分析表； 4、構(gòu)建LL分析程序，對(duì)于用戶(hù)輸入的句子，能夠利用所構(gòu)造的分析程序進(jìn)行分析，

2、并顯示出分析過(guò)程。四、主要儀器設(shè)備硬件：微型計(jì)算機(jī)。軟件： Code blocks（也可以是其它集成開(kāi)發(fā)環(huán)境）。 五、實(shí)驗(yàn)過(guò)程描述1、程序主要框架 程序中編寫(xiě)了以下函數(shù)，各個(gè)函數(shù)實(shí)現(xiàn)的作用如下：void input_grammer(string *G);/輸入文法Gvoid 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 eliminate_1(string *G,string *P,string U,string *GG);/

3、消除文法G中所有直接左遞歸得到文法GGint* ifempty(string* P,string U,int k,int n);/判斷各非終結(jié)符是否能推導(dǎo)為空string* FIRST_X(string* P,string U,string u,int* empty,int k,int n)；求所有非終結(jié)符的FIRST集string FIRST(string U,string u,string* first,string s)；/求符號(hào)串s=X1X2.Xn的FIRST集string* create_table(string *P,string U,string u,int n,int t,in

4、t k,string* first)；/構(gòu)造分析表void analyse(string *table,string U,string u,int t,string s)；/分析符號(hào)串s 2、編寫(xiě)的源程序#include#include#includeusing namespace std;void input_grammer(string *G)/輸入文法G,n個(gè)非終結(jié)符 int i=0;/計(jì)數(shù) char ch=y; while(ch=y) cinGi+; coutch; void preprocess(string *G,string *P,string &U,string &u,int

5、&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= ;/字符串如果不初始化，在使用Pij=a時(shí)將不能改變，可以用Pi.append(1,a) U=u= ;/字符串如果不初始化，無(wú)法使用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.le

6、ngth();j+) if(U.find(Gij)=string:npos&u.find(Gij)=string:npos) if(Gij!=|&Gij!=) /if(Gij!=(&Gij!=)&Gij!=|&Gij!=) ut+=Gij; /終結(jié)符集合，t為終結(jié)符個(gè)數(shù) for(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添加到（）中所有

7、字符串后面 if(Gij=) j+;flag=0; */ if(Gij=|) /if(flag=1) Pkr+=C; k+;j+; Pk0=Ui;Pk1=:;Pk2=:;Pk3=; r=4; Pkr+=Gij; else Pkr+=Gij; k+; /獲得產(chǎn)生式集合P，k為產(chǎn)生式個(gè)數(shù)int eliminate_1(string *G,string *P,string U,string *GG)/消除文法G1中所有直接左遞歸得到文法G2，要能夠消除含有多個(gè)左遞歸的情況）string arfa,beta;/所有形如A:=A|中的、連接起來(lái)形成的字符串a(chǎn)rfa、betaint i,j,temp,m=

8、0;/計(jì)數(shù)int flag=0;/flag=1表示文法有左遞歸int flagg=0;/flagg=1表示某條規(guī)則有左遞歸char C=A;/由于消除左遞歸新增的非終結(jié)符，從A開(kāi)始增加，只要不在原來(lái)問(wèn)法的非終結(jié)符中即可加入for(i=0;i20&Ui!= ;i+) flagg=0; arfa=beta=; for(j=0;j100&Pj0!= ;j+) if(Pj0=Ui) if(Pj4=Ui)/產(chǎn)生式j(luò)有左遞歸 flagg=1; for(temp=5;Pjtemp!= ;temp+) arfa.append(1,Pjtemp); if(Pj+14=Ui) arfa.append(|);/不止

9、一個(gè)產(chǎn)生式含有左遞歸 else for(temp=4;Pjtemp!= ;temp+) beta.append(1,Pjtemp); if(Pj+10=Ui&Pj+14!=Ui) beta.append(|); if(flagg=0)/對(duì)于不含左遞歸的文法規(guī)則不重寫(xiě) GGm=Gi; m+; else flag=1;/文法存在左遞歸 GGm.append(1,Ui);GGm.append(:=); if(beta.find(|)!=string:npos) GGm.append(+beta+); else GGm.append(beta); while(U.find(C)!=string:npo

10、s)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);GGm.append(|); m+; C+; /A:=A|改寫(xiě)成A:=A，A=A|，return flag;int* ifempty(string* P,string U,int k,int n) int* empty=new int n;/指示非終結(jié)符能否推導(dǎo)到空串 int i,j,r; for(r=

11、0;rn;r+) emptyr=0;/默認(rèn)所有非終結(jié)符都不能推導(dǎo)到空 int flag=1;/1表示empty數(shù)組有修改 int step=100;/假設(shè)一條規(guī)則最大推導(dǎo)步數(shù)為100步 while(step-) for(i=0;ik;i+) r=U.find(Pi0); if(Pi4=) emptyr=1;/直接推導(dǎo)到空 else for(j=4;Pij!= ;j+) if(U.find(Pij)!=string:npos) if(emptyU.find(Pij)=0) break; else break; if(Pij= ) emptyr=1;/多步推導(dǎo)到空 else flag=0; ret

12、urn 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(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

13、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é)符,形如X：=Y1Y2.Yk s=U.find(Pij); /coutPij:n; for(tmp=0;firststmp!=0;tmp+) a=firststmp; if(a!=&firstr.find(a)=string:npos)/將FIRSTY1中的非空符加入

14、firstr.append(1,a); 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 U,string u,string* first,string s)/求符號(hào)串s=X1X2.Xn的FIRST集 int i,j,r; char a; string fir; for(i=0;is.length();i+) if(si=) fir.append(1,)

15、; if(u.find(si)!=string:npos&fir.find(si)=string:npos) 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=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

16、(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* first)/構(gòu)造分析表，P為文法G的產(chǎn)生式構(gòu)成的集合 int i,j,p,q; string arfa;/記錄規(guī)則右部 string fir,follow; string FOLLOW5=)#,)#,+)#,+)#,+*)#; string *table=

17、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ǔ)分析表的元素，“ ”表示error for(i=0;ik;i+) arfa=Pi; arfa.erase(0,4);/刪除前4個(gè)字符，如：E:=E+T,則arfa=E+T fir=FIRST(U,u,first,arfa); for(j=0;jt;j+) p=U.find(Pi0); if(fir.find(uj)!=string:npos) q=j; tablepq=Pi; /對(duì)first（）

18、中的每一終結(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ì)#所在元素置相應(yīng)規(guī)則 return table; void analyse(string *table,string U,string u,int t,string s)/分析符號(hào)串s string stack;/分析棧 string ss=s;

19、/記錄原符號(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不是該文法的句子n; return; s.append(1,#); stack.append(1,#);/#進(jìn)入分析棧 stack.append(1,U0);i+;/文法開(kāi)始符進(jìn)入分析棧 a=s0; /coutstackendl; cout步驟 分析棧

20、 余留輸入串 所用產(chǎn)生式n; while(!flag) / cout步驟 分析棧 余留輸入串 所用產(chǎn)生式n coutstep stack s ; 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)與當(dāng)前輸入符號(hào)匹配，則輸入下一個(gè)符號(hào) cout n;/未使用產(chǎn)生式，輸出空 else couterrorn; coutss不是該文法的句子n; break; if(x=#) if(a=#) flag=1;co

21、ut成功n;/棧頂和余留輸入串都為#，匹配成功 else couterrorn; 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) if(tempr!=) stack.append(1,tempr);/將X:=x1x2.的規(guī)則右部各符號(hào)壓棧 i+; r-; else couterrorn; coutss不是該文法的句子n; break; step+; if(flag) coutendlss是該文法

22、的句子n; int main() int i,j; string *G=new string50;/文法G string *P=new string50;/產(chǎn)生式集合P string U,u;/文法G非終結(jié)符集合U，終結(jié)符集合u int n,t,k;/非終結(jié)符、終結(jié)符個(gè)數(shù),產(chǎn)生式數(shù) string *GG=new string50;/消除左遞歸后的文法GG string *PP=new string50;/文法GG的產(chǎn)生式集合PP string UU,uu;/文法GG非終結(jié)符集合U，終結(jié)符集合u int nn,tt,kk;/消除左遞歸后的非終結(jié)符、終結(jié)符個(gè)數(shù),產(chǎn)生式數(shù) string* table

23、;/分析表 cout 歡迎使用LL(1)語(yǔ)法分析器!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; if(eliminate_1(G,P,U,GG) preprocess(GG,PP,UU,uu,nn,tt,kk); cout該文法存在

24、左遞歸！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; /cout新文法有kk個(gè)產(chǎn)生式：n; /for(i=0;ikk;i+) coutPPiendl; else cout該文法不存在左遞歸n; GG=G;PP=P;UU=U;uu=u;nn=n;tt=t;kk=k; cout 求解FIRST集nn; int *empty=ifempty(PP,UU,kk,nn); string* first=FIRST_X