編譯原理實(shí)驗(yàn)報(bào)告《LL語法分析器構(gòu)造》

1、LL (1)分析器的構(gòu)造實(shí)驗(yàn)報(bào)告一、實(shí)驗(yàn)名稱LL(1)分析器的構(gòu)造二、實(shí)驗(yàn)?zāi)康脑O(shè)計(jì)、編制、調(diào)試一個(gè)LL(1)語法分析器，利用語法分析器對(duì)符號(hào)串的識(shí)別，加深對(duì) 語法分析原理的理解。三、實(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)串i+i*i為文法所定義的句子，符號(hào)串ii+*i+ 不是文法所定義的句子。實(shí)驗(yàn)要求：1、檢測左遞歸，如果有則進(jìn)行消除；2、求解 FIRST集和 FOLLOW集;3、構(gòu)建LL(1)分析表；4、構(gòu)建LL分析程序，對(duì)于用戶輸入的句子，能夠利用所構(gòu)造的分析程序進(jìn)行分析， 并顯示出

2、分析過程。四、主要儀器設(shè)備硬件：微型計(jì)算機(jī)。軟件：Code blocks (也可以是其它集成開發(fā)環(huán)境)五、實(shí)驗(yàn)過程描述1、程序主要框架程序中編寫了以下函數(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 中所有直接左遞歸得到文法 GG int* 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

4、 n,int t,int k,string* first) ； / 構(gòu)造分析表 void analyse(string *table,string U,string u,int t,string s)； / 分析符號(hào)串 s2、編寫的源程序#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

5、,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;/ 檢測到()n=t=k=0;for( i=0;i50;i+)Pi=;/ 字符串如果不初始化, 在使用 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ù)fo

6、r(i=0;in;i+)for(j=4;jGi.length();j+)if(U.find(Gij)=string:npos&u.find(Gij)=string:npos)if(Gij!=T&Gij!=A)if(Gij!=(&Gij!=)&Gij!=|&Gij!=A)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

7、 記錄()后跟的字符，將 C 添加到()中所有字符串后面 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è)左遞歸的情況)stri ng arfa,beta;所有形如 A:=A a |中的a、漣接起來形成的字符串a(chǎn)

8、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é)符中即可加 入 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 有左遞歸 flagg=1;for(temp=5;Pjtemp!= ;temp+) arfa.append(1,Pjtemp)

9、; 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ī)則不重寫GGm=Gi; m+;elseflag=1;/ 文法存在左遞歸GGm.append(1,Ui);GGm.append(:=); if(beta.find(|)!=string:npos) GGm.append(+beta+); else GGm.append(beta)

10、;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.appe nd(1,C);GGm.appe nd(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

11、;/ 指示非終結(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ù)為 100 步 while(step-)for(i=0;ik;i+)r=U.find(Pi0);if(Pi4=g) emptyr=1;直接推導(dǎo)到空elsefor(j=4;Pij!= ;j+)if(U.find(Pij)!=string:npos)if(emptyU.find(Pij)=0) break;else break;if(Pij= ) empty

12、r=1;/ 多步推導(dǎo)到空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(step-)/ coutstep100-stependl;for(i=0;ik;i+)/coutPiendl;r=U.find(Pi0);if(Pi4=A&firstr.findQ)=string:npos)firstr.append(1f

13、); 規(guī)則右部首符號(hào)為空elsefor(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.Yks=U.find(Pij);/coutPij:n;for(tmp=0;firststmp!=0;tmp+)a=firststmp;if(a!=A&firstr.find(a)=string:npos)/將 FIR

14、STY1中的非空符加入firstr.append(1,a);if(!emptys) break;/ 若 Y1 不能推導(dǎo)到空，結(jié)束if(Pij= )if(firstr.find(A)=string:npos)firstr.append(1f);若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=A) fir.

15、append(1,A);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!=A&fir.find(a)=string:npos)/將 FIRST(XI)中的非空符號(hào)加入fir.append(1,a);if(firstr.findQ)=string:npos) break;/ 若 X1 不

16、可推導(dǎo)到空，循環(huán)停止if(i=s.length()/ 若 X1-Xk 都可推導(dǎo)到空if(fir.find(si)=string:npos) /fir 中還未加入空符號(hào)fir.appe nd(1F);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=)#,)#,+)#,+)#,+*)#

17、;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);刪除前 4 個(gè)字符，如：E:=E+T,貝U 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;tablepq=Pi;/ 對(duì)

18、fi rst ()中的每一終結(jié)符置相應(yīng)的規(guī)貝if(fir.fi nd(A)!=stri ng: 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;/

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

20、ndl;cout 步驟分析棧while(!flag)/ cout 步驟分析棧余留輸入串所用產(chǎn)生式 n;余留輸入串所用產(chǎn)生式 n x=stacki;stack.erase(i,1);i-;取棧頂符號(hào) x,并從棧頂退出coutstepstackscoutxe ndl;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)生式，輸出空elsecouterrorn;coutss 不是該文法的句子 n;break;if(x=#)if(a=#) flag=1;cout成

21、功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)if(tempr!=人)stack.append(1,tempr);將X:=x1x2的規(guī)則右部各符號(hào)壓棧 i+;r-;elsecouterrorn;coutss 不是該文法的句子 n; break;step+;if(flag) coutendlss 是該文法的句子 n; int main

22、() int i,j;string *G=new string50;/ 文法 G string *P=new string50;/ 產(chǎn)生式集合 Pstring 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)語法分析器！nnn;n;cout請(qǐng)輸入文法(同一左部的規(guī)則在同一行輸入，例如：E:=E+T|T ;用A表示空串)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;coutnnif(eliminate_1(G,P,U,GG)左遞歸檢測與消除 nn;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;elsecout 該文法不存在左遞歸 n; GG=G;PP=P;UU=U;uu=u;nn=n;tt=t;kk=k;cout求解 FIRST 集nn;int *empty

25、=ifempty(PP,UU,kk,nn);string* first=FIRST_X(PP,UU,uu,empty,kk,nn);for(i=0;inn;i+)coutFIRST(UUi):firstiendl;cout求解 FOLLOW 集nn;for(i=0;inn;i+)coutFOLLOW(UUi):FOLLOWiendl;coutnn構(gòu)造文法分析表 nn;table=create_table(PP,UU,uu,nn,tt,kk,first);cout ;for(i=0;itt;i+) cout uui;cout#endl;for( i=0;inn;i+)coutUUifor(j=0

26、;jt+1;j+)couttableij;coutendl;分析符號(hào)串 nn; coutnnstring s;cout s;an alyse(table,UU,uu,tt,s);return 0;3、程序演示結(jié)果(1)輸入文法歡迎使用譏“)語法分析器t積輸入文法(同一左部的規(guī)則在同一行輸入 例如：E：-E-T：I；用表示空串)Et: -E+T IT擺續(xù)輸入? 32yT=：=T*F!F擺續(xù)輸入?3心P=：-CE11繼續(xù)輸入0川|該文法有工個(gè)日瞑結(jié)符：FT F該文祛有5個(gè)終結(jié)符：+*i(2)消除左遞歸左遞歸檢測與消除 該文法存在左遞歸！消除左遞歸后的文法：Es 二=TfiAs ? =+Tfir:=fbB言 s =FB !人Ps:= i 1新文法有5個(gè)非終結(jié)符：EATBF新文法有&個(gè)終結(jié)符：+wOt(3)求解 FIRST和 FOLLOW集求解FIHET集3IRST：?IRSTCT：i?rHST：Ci求解FOLLOW集?OLLOU：JOLLOW：FOLLOW：+FOLLOW:+ttFOLLOW(F：+tt(4)構(gòu)造分析表構(gòu)造文法分析表*i4上E：=TftftA：ft:A ：TT：=FBT：=FBBB：B ； : -*FBB：=ATh a _ 幾 Ft -B FFF：=F： ：=i(5)分析符號(hào)串 匹