編譯原理試驗報告LL語法分析器構造

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

2、分析過程。四、主要儀器設備硬件：微型計算機。軟件：Code blocks (也可以是其它集成開發(fā)環(huán)境)五、實驗過程描述1、程序主要框架程序中編寫了以下函數，各個函數實現的作用如下：void input_grammer(string *G); 輸入文法 Gvoid preprocess(string *G,string *P,string &U,string &u,int &n,int &t,int &k);/將文法G預處理得到產生式集合P,非終結符、終結符集合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);/ 判斷各非終結符是否能推導為空string* FIRST_X(string* P,string U,string u,int* empty,int k,int n) ；求所有非終結符的 FIRST 集string FIRST(string U,string u,string* first,string s) ; / 求符號串 s=X1X2.Xn 的 FIRST 集 string* create_table(string *P,string U,string u,int

4、 n,int t,int k,string* first) ； / 構造分析表 void analyse(string *table,string U,string u,int t,string s)； / 分析符號串 s2、編寫的源程序#include#include#includeusing namespace std;void input_grammer(string *G)/ 輸入文法 G,n 個非終結符int i=0;/ 計數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 預處理產生式集合 P, 非終結符、終結符集合 U、 u,int i,j,r,temp;/ 計數char C;/ 記錄規(guī)則中()后的符號int flag;/ 檢測到()n=t=k=0;for( i=0;i50;i+)Pi=;/ 字符串如果不初始化, 在使用 Pij=a 時將不能改變, 可以用 Pi.append(1,a)U=u=;/ 字符串如果不初始化, 無法使用 Ui=a 賦值,可以用 U.append(1,a)for(n=0;!Gn.empty();n+) Un=Gn0;/ 非終結符集合, n 為非終結符個數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;/ 終結符集合， t 為終結符個數 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;elsePkr+=Gij; k+;/ 獲得產生式集合 P，k 為產生式個數int eliminate_1(string *G,string *P,string U,string *GG)/消除文法G1中所有直接左遞歸得到文法G2，要能夠消除含有多個左遞歸的情況)stri ng arfa,beta;所有形如 A:=A a |中的a、漣接起來形成的字符串a

8、rfa、betaint i,j,temp,m=0;/ 計數int flag=0;/flag=1 表示文法有左遞歸int flagg=0;/flagg=1 表示某條規(guī)則有左遞歸char C=A;/ 由于消除左遞歸新增的非終結符，從 A 開始增加，只要不在原來問法的非終結符中即可加 入 for(i=0;i20&Ui!= ;i+) flagg=0;arfa=beta=;for(j=0;j100&Pj0!= ;j+)if(Pj0=Ui)if(Pj4=Ui)/ 產生式 j 有左遞歸flagg=1;for(temp=5;Pjtemp!= ;temp+) arfa.append(1,Pjtemp); if(

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

10、e(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、非終結符能否推導到空串int i,j,r;for(r=0;rn;r+) emptyr=0;/ 默認所有非終結符都不能推導到空int flag=1;/1 表示 empty 數組有修改int step=100;/ 假設一條規(guī)則最大推導步數為 100 步 while(step-)for(i=0;ik;i+)r=U.find(Pi0);if(Pi4=g) emptyr=1;直接推導到空elsefor(j=4;Pij!= ;j+)if(U.find(Pij)!=string:npos)if(emptyU.find(Pij)=0) break;else break;if(Pij= ) emptyr=1;/

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

13、右部首符號為空else for(j=4;Pij!= ;j+)a=Pij;if(u.find(a)!=string:npos&firstr.find(a)=string:npos)/ 規(guī)則右部首符號是終結符 firstr.append(1,a);break;/ 添加并結束if(U.find(Pij)!=string:npos)/ 規(guī)則右部首符號是非終結符 ,形如 X：=Y1Y2.Yk s=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 不能推導到空，結束if(Pij= )if(firstr.find(A)=string:npos)firstr.append(1f);若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;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 是終結符， 添 加并結束循環(huán)if(U.find(si)!=string:npos)/X1 是非終結符r=U.find(si);for(j=0;firstrj!=0;j+) a=firstrj;if(a!=A&fir.find(a)=string:npos)/將 FIRST(XI)中的非空符號加入fir.append(1,a);if(firstr.findQ)=string:npos) break;/ 若 X1 不

16、可推導到空，循環(huán)停止if(i=s.length()/ 若 X1-Xk 都可推導到空if(fir.find(si)=string:npos) /fir 中還未加入空符號fir.appe nd(1F);return fir;string* create_table(string *P,string U,string u,int n,int t,int k,string* first)/ 構造分析表，P 為文法 G 的產生式 構成的集合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 存儲分析表的元素，“”表示 errorfor(i=0;ik;i+)arfa=Pi;arfa.erase(0,4);刪除前 4 個字符，如：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;/ 對

18、fi rst ()中的每一終結符置相應的規(guī)貝if(fir.fi nd(A)!=stri ng: npos) follow=FOLLOWp;/ 對規(guī)則左部求 follow() for(j=0;jt;j+)if(q=follow.find(uj)!=string:npos)q=j; tablepq=Pi;/ 對 follow ()中的每一終結符置相應的規(guī)則 tablept=Pi;/ 對# 所在元素置相應規(guī)則return table;void analyse(string *table,string U,string u,int t,string s)/ 分析符號串 s string stack;/

19、 分析棧string ss=s;/ 記錄原符號串char x;/ 棧頂符號char a;/ 下一個要輸入的字符int flag=0;/ 匹配成功標志int i=0,j=0,step=1;/ 符號棧計數、輸入串計數、步驟數int p,q,r;string temp;for(i=0;!si;i+)if(u.find(si)=string:npos)/ 出現非法的符號 couts 不是該文法的句子 n;return;s.append(1,#);stack.append(1,#);/ #進入分析棧/coutstackendl;cout 步驟分析棧while(!flag)/ cout 步驟分析棧stac

20、k.append(1,U0);i+;/ 文法開始符進入分析棧 a=s0;余留輸入串所用產生式 n;余留輸入串所用產生式 n x=stacki;stack.erase(i,1);i-;取棧頂符號 x,并從棧頂退出coutstepstackscoutxe ndl;if(u.find(x)!=string:npos)/x 是終結符的情況if(x=a)s.erase(0,1);a=s0;棧頂符號與當前輸入符號匹配，則輸入下一個符號cout n;/ 未使用產生式，輸出空elsecouterrorn;coutss 不是該文法的句子 n;break;if(x=#)if(a=#) flag=1;cout成功n

21、; 棧頂和余留輸入串都為#，匹配成功elsecouterrorn;coutss 不是該文法的句子 n;break;if(U.find(x)!=string:npos)/x 是非終結符的情況p=U.find(x);q=u.find(a);if(a=#) q=t;temp=tablepq;couttemp3)if(tempr!=人)stack.append(1,tempr);將X:=x1x2的規(guī)則右部各符號壓棧 i+;r-;elsecouterrorn;coutss 不是該文法的句子 n; break;step+;if(flag) coutendlss 是該文法的句子 n;int main()in

22、t i,j;string *G=new string50;/ 文法 Gstring *P=new string50;/ 產生式集合 Pstring U,u;文法G非終結符集合U，終結符集合uint n,t,k;/ 非終結符、終結符個數,產生式數string *GG=new string50;/ 消除左遞歸后的文法 GGstring *PP=new string50;/ 文法 GG 的產生式集合 PPstring UU,uu;文法GG非終結符集合 U，終結符集合 uint nn,tt,kk;/ 消除左遞歸后的非終結符、終結符個數,產生式數string* table;/ 分析表cout歡迎使用LL

23、(1)語法分析器！nnn;n;cout請輸入文法(同一左部的規(guī)則在同一行輸入，例如：E:=E+T|T ;用A表示空串)input_grammer(G);preprocess(G,P,U,u,n,t,k);coutn 該文法有 n 個非終結符： n; for(i=0;in;i+) coutUi;coutendl;cout 該文法有 t 個終結符： n; for(i=0;it;i+) coutui;coutnnif(eliminate_1(G,P,U,GG) 左遞歸檢測與消除 nn;preprocess(GG,PP,UU,uu,nn,tt,kk);cout 該文法存在左遞歸！ nn 消除左遞歸后的

24、文法 :nn;for(i=0;inn;i+) coutGGiendl;coutendl;cout 新文法有 nn 個非終結符： n;for(i=0;inn;i+) coutUUi;coutendl;cout 新文法有 tt 個終結符： n;for(i=0;itt;i+) coutuui;coutendl;/cout 新文法有 kk 個產生式： 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=ifempty(PP,

25、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;構造文法分析表 nn;分析符號串 nn;coutnntable=create_table(PP,UU,uu,nn,tt,kk,first);cout ;for(i=0;itt;i+) cout uui cout#endl;for( i=0;inn;i+)coutUUi ;for(j=0;

26、jt+1;j+)couttableij;coutendl; coutnnstring s;cout s;an alyse(table,UU,uu,tt,s);return 0;3、程序演示結果(1) 輸入文法歡迎使用S語法分析器?諳輸人文法(辰一左部的艦則在同一行輸入，例如 s占用”表亍空串) |C - - =|EjlT T 廳制&沖oyT=-IFIF綁續(xù)輸入閉F：=!i繼續(xù)輸入?n該文法右護卜非縉埒ETF該丈法有石個終結符(2) 消除左遞歸左遽歸檢測與湄除”文法存在左遞歸！”除左遞歸后的文法：E:;-TAH：? +TA !rtt:；-roR;：=*FB：*F；:=!i 冷文法有討TK給苻.EATBF新文法決個終給符.*1(3) 求解 FIRST和 FOLLOW集耶:解FI RET集JIBSKE)：FIBSKA)：+*HRSKT)：(i?IR8T :?IRST：?OLLOU :FOLLOW :+ Jit7OLLOU：*#FOLLOU：+ *H(4) 構造分析表構造文袪分析表+*Ci1EE=：-TfiE=-TfiA觸：fT白Ai = =AA “Tr:=FBT；=FBHT1 . Tti . -B-rTTTiTTi _ A-