編譯原理實驗報告《LL語法分析器構(gòu)造》

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

2、程序進行分析， 并顯示出分析過程。四、主要儀器設備硬件：微型計算機。軟件：Code blocks (也可以是其它集成開發(fā)環(huán)境)。五、實驗過程描述1、程序主要框架程序中編寫了以下函數(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預處理得到產(chǎn)生式集合P,非終結(jié)符、終結(jié)符集合U、u,int eliminate_1(string *G,stri

3、ng *P,string U,string *GG);/ 消除文法G 中所有直接左遞歸得到文法GGint* ifempty(string* P,string U,int k,int n);/ 判斷各非終結(jié)符是否能推導為空 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) ； / 求符號串s=X1X2.Xn 的 FIRST 集string* create_table(st

4、ring *P,string U,string u,int n,int t,int k,string* first) ； / 構(gòu)造分析表 void analyse(string *table,string U,string u,int t,string s)； / 分析符號串s2、編寫的源程序#include<cstdio>#include<cstring>#include<iostream> using namespace std;void input_grammer(string *G)/ 輸入文法G,n 個非終結(jié)符int i=0;/ 計數(shù) char c

5、h='y'while(ch='y')cin>>Gi+;cout<<" 繼續(xù)輸入?(y/n)n"cin>>ch; void preprocess(string *G,string *P,string &U,string &u,int &n,int &t,int &k)/ 將文法 G 預處理產(chǎn)生式集合P，非終結(jié)符、終結(jié)符集合U、 u，int i,j,r,temp;/ 計數(shù) char C;/ 記錄規(guī)則中()后的符號 int flag;/ 檢測到() n=t=k=0;for(

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

7、j!=T&&Gij!='A')/if(Gij!='('&&Gij!=')'&&Gij!=T&&Gij!=w)ut+=Gij;/ 終結(jié)符集合，t 為終結(jié)符個數(shù)for(i=0;i<n;i+)flag=0;r=4;for(j=4;j<Gi.length();j+)Pk0=Ui;Pk1=':'Pk2=':'Pk3='='/* if(Gij='(')j+;flag=1;for(temp=j;Gitemp!=')

8、'temp+);C=Gitemp+1;/C 記錄()后跟的字符，將C 添加到()中所有字符串后面if(Gij=')') j+;flag=0;*/if(Gij='|')/if(flag=1) Pkr+=C;k+;j+;Pk0=Ui;Pk1=':'Pk2=':'Pk3='='r=4;Pkr+=Gij;elsePkr+=Gij; k+;/ 獲得產(chǎn)生式集合P， k 為產(chǎn)生式個數(shù)int eliminate_1(string *G,string *P,string U,string *GG)/消除文法G1中所有直接左遞

9、歸得到文法G2,要能夠消除含有多個左遞歸的情況)string arfa,beta;所有形如 A:=A a |由的a、港接起來形成的字符串 arfa、betaint i,j,temp,m=0;/ 計數(shù)int flag=0;/flag=1 表示文法有左遞歸int flagg=0;/flagg=1 表示某條規(guī)則有左遞歸char C='A'/ 由于消除左遞歸新增的非終結(jié)符，從A 開始增加，只要不在原來問法的非終結(jié)符中即可加入for(i=0;i<20&&Ui!=' 'i+) flagg=0;arfa=beta=""for(j=0;

10、j<100&&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("|");/ 不止一個產(chǎn)生式含有左遞歸 elsefor(temp=4;Pjtemp!=' 'temp+) beta.append(1,Pjtemp); if(Pj+10=Ui&&Pj+14!=Ui) beta.append(

11、"|");if(flagg=0)/ 對于不含左遞歸的文法規(guī)則不重寫GGm=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.appe

12、nd(":=");if(arfa.find('|')!=string:npos) GGm.append("("+arfa+")");else GGm.append(arfa);GGm.append(1,C);GGm.append("F");m+;C+;/A：=A a 收箭成 A：= 3 A A =a A'| 3 ,return flag;int* ifempty(string* P,string U,int k,int n)int* empty=new int n;/ 指示非終結(jié)符能否推導到

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

14、ij=' ') emptyr=1;/ 多步推導到空 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;/ 最大推導步數(shù)while(step-)/ cout<<"step"<<100-step<<endl;for(i=0;i<k;i+)/cout<<P

15、i<<endl;r=U.find(Pi0);if(Pi4='A'&&firstr.find('A')=string:npos) firstr.append(1,'A');/ 規(guī)則右部首符號為空 else for(j=4;Pij!=' 'j+)a=Pij;if(u.find(a)!=string:npos&&firstr.find(a)=string:npos)/ 規(guī)則右部首符號是終結(jié)符 firstr.append(1,a);break;/ 添加并結(jié)束if(U.find(Pij)!=str

16、ing:npos)/ 規(guī)則右部首符號是非終結(jié)符,形如X： ： =Y1Y2.Yks=U.find(Pij);/cout<<Pij<<":n"for(tmp=0;firststmp!='0'tmp+)a=firststmp;if(a!='A'&&firstr.find(a)=string:npos)將 FIRSTY1中的非空符加入firstr.append(1,a);if(!emptys) break;/ 若 Y1 不能推導到空，結(jié)束if(Pij=' ')if(firstr.find(

17、9;A')=string:npos)firstr.append(1,'A');/ 若 Y1、 Y2.Yk 都能推導到空，則加入空符號return first;string FIRST(string U,string u,string* first,string s)/ 求符號串s=X1X2.Xn 的 FIRST 集int i,j,r;char a;string fir;for(i=0;i<s.length();i+)if(si='A')fir.append(i,'A)；if(u.find(si)!=string:npos&&

18、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!=w&&fir.find(a)=string:npos)將 FIRST(X1)中的非空符號加入fir.append(1,a);if(firstr.find('A')=string:npos) break;/ 若 X1 不可推導到空，循環(huán)停止

19、if(i=s.length()/ 若 X1-Xk 都可推導到空if(fir.find(si)=string:npos) /fir 中還未加入空符號 fir.append(1,'A'); 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=")#",&

20、quot;)#","+)#","+)#","+*)#"string *table=new string*n;for(i=0;i<n;i+) tablei=new stringt+1;for(i=0;i<n;i+)for(j=0;j<t+1;j+) tableij=""/table 存儲分析表的元素，“ ”表示 errorfor(i=0;i<k;i+)arfa=Pi;arfa.erase(0,4);刪除前 4 個字符，如：E:=E+T,貝U arfa="E+T"

21、fir=FIRST(U,u,first,arfa); for(j=0;j<t;j+) p=U.find(Pi0); if(fir.find(uj)!=string:npos) q=j;tablepq=Pi;/對first 0中的每一終結(jié)符置相應的規(guī)則if(fir.find('A')!=string:npos) follow=FOLLOWp;/ 對規(guī)則左部求follow()for(j=0;j<t;j+)if(q=follow.find(uj)!=string:npos) q=j;tablepq=Pi;/對follow ()中的每一終結(jié)符置相應的規(guī)則tablept=Pi

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

23、<<s<<" 不是該文法的句子n"return; s.append(1,'#');stack.append(1,'#');/ #進入分析棧stack.append(1,U0);i+;/ 文法開始符進入分析棧 a=s0;/cout<<stack<<endl;cout<<" 步驟分析棧余留輸入串所用產(chǎn)生式n"while(!flag)/ cout<<" 步驟分析棧余留輸入串所用產(chǎn)生式n"cout<<step<<&q

24、uot;"<<stack<<""<<s<<"x=stacki;stack.erase(i,1);i-;取棧頂符號 x,并從棧頂退出/cout<<x<<endl;if(u.find(x)!=string:npos)/x 是終結(jié)符的情況if(x=a)s.erase(0,1);a=s0;/棧頂符號與當前輸入符號匹配，則輸入下一個符號 cout<<" n"/ 未使用產(chǎn)生式，輸出空 else cout<<"errorn"cout&

25、lt;<ss<<" 不是該文法的句子n"break; if(x='#') if(a='#') flag=1;cout<<" 成功 n"/ 棧頂和余留輸入串都為#，匹配成功elsecout<<"errorn"cout<<ss<<" 不是該文法的句子n"break; if(U.find(x)!=string:npos)/x 是非終結(jié)符的情況 p=U.find(x); q=u.find(a); if(a='#'

26、;) q=t; temp=tablepq;cout<<temp<<endl;/ 輸出使用的產(chǎn)生式if(temp0!=' ')/ 分析表中對應項不為errorr=9; while(tempr=' ') r-;while(r>3) if(tempr!='A') stack.append(1,tempr);將X:=x1x2的規(guī)則右部各符號壓棧 i+;r-;elsecout<<"errorn"cout<<ss<<" 不是該文法的句子n"break;s

27、tep+; if(flag) cout<<endl<<ss<<" 是該文法的句子n"int main()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é)符個數(shù),產(chǎn)生式數(shù)string *GG=new string50;/ 消除左遞歸后的文法GGstring *PP=new string50;/ 文法 GG 的產(chǎn)生式集合PPstring UU,uu;/文法GG非終

28、結(jié)符集合 U,終結(jié)符集合 uint nn,tt,kk;/ 消除左遞歸后的非終結(jié)符、終結(jié)符個數(shù),產(chǎn)生式數(shù)string* table;/ 分析表cout<<"歡迎使用LL(1)語法分析器！nnn"n"cout<<"請輸入文法(同一左部的規(guī)則在同一行輸入，例如： E:=E+T|T ;用人表示空串) input_grammer(G);preprocess(G,P,U,u,n,t,k);cout<<"n 該文法有"<<n<<" 個非終結(jié)符：n"for(i=0;i&l

29、t;n;i+)cout<<Ui;cout<<endl;cout<<" 該文法有"<<t<<" 個終結(jié)符：n"for(i=0;i<t;i+)cout<<ui;cout<<"nnif(eliminate_1(G,P,U,GG)左遞歸檢測與消除nn"preprocess(GG,PP,UU,uu,nn,tt,kk);cout<<"該文法存在左遞歸！ nn消除左遞歸后的文法：nn"for(i=0;i<nn;i+) co

30、ut<<GGi<<endl;cout<<endl;cout<<"新文法有"<<nn<<"個非終結(jié)符：n"for(i=0;i<nn;i+) cout<<UUi;cout<<endl;cout<<"新文法有"<<tt<<"個終結(jié)符：n"for(i=0;i<tt;i+) cout<<uui;cout<<endl;/cout<<"新文法

31、有"<<kk<<"個產(chǎn)生式：n"/for(i=0;i<kk;i+) cout<<PPi<<endl;elsecout<<"該文法不存在左遞歸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(PP,UU,uu,empty,kk,nn);for(i=0;i<nn;i+)cout

32、<<"FIRST("<<UUi<<"):"<<firsti<<endl;cout<<"求解 FOLLOW 集nn"for(i=0;i<nn;i+)cout<<"FOLLOW("<<UUi<<"):"<<FOLLOWi<<endl;cout<<"nn構(gòu)造文法分析表nn"table=create_table(PP,UU,uu,nn,

33、tt,kk,first);cout<<" "for(i=0;i<tt;i+) cout<<" "<<uui<<""cout<<"#"<<endl;for( i=0;i<nn;i+)cout<<UUi<<" "for(j=0;j<t+1;j+)cout<<tableij;cout<<endl;cout<<"nn分析符號串 nn"s

34、tring s;cout<<"請輸入要分析的符號串n"cin>>s;analyse(table,UU,uu,tt,s);return 0;3、程序演示結(jié)果 (1)輸入文法就迎使用山1>語法分析器?請輸入文法(同一左部的規(guī)則在同一行輸入，例如：配EKE用人表示空串) |C - - =|E'jlT - TyT="I«FIF繼續(xù)輸入?"心豈F：=<E>!i繼續(xù)輸>>n該文法有？個非終卷將.ETF該夏法有二個終結(jié)符晝(2)消除左遞歸左遞歸檢測與消除亥文法存在左遞歸！，除左遞歸后的文法:E:i-TAH：? +TA !rt t r-rn R 二：=*FB：jF；：=<E>!i最法有*7 K結(jié)苻.EATBF前文法有"個終結(jié)符，*<>1(3)求解 FIRST和 FOLLOW求解PI-T集JI«S1<E>： <i FIBSKfi)： 產(chǎn) FIRSKT)： (i JIBSKB)： *A IBSI<P>： (i求解FULL0H集?OLLOU(E>： >tt?OLLOU