編譯原理實驗報告LL語法解析總結(jié)器構(gòu)造

1、 ll（1）分析器的構(gòu)造實驗報告一、實驗名稱ll(1) 分析器的構(gòu)造二、實驗?zāi)康脑O(shè)計、編制、調(diào)試一個 ll(1) 語法分析器，利用語法分析器對符號串的識別，加深對語法分析原理的理解。三、實驗內(nèi)容和要求設(shè)計并實現(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 分析程序，對于用戶輸入的句子，能夠利

2、用所構(gòu)造的分析程序進行分析，并顯示出分析過程。四、主要儀器設(shè)備硬件：微型計算機。軟件： 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 預(yù)處理得到產(chǎn)生式集合p，非終結(jié)符、終結(jié)符集合u、 u，int eliminate_1(string *g,string *p,str

3、ing u,string *gg);/ 消除文法 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) ； / 求符號串 s=x1x2.xn 的 first 集 string* create_table(strin

4、g *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#include#includeusing namespace std;void input_grammer(string *g)/輸入文法g,n 個非終結(jié)符int i=0;/ 計數(shù)char ch=y;while(ch=y)cingi+;coutch;void preprocess(string *

5、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;/ 計數(shù)char c;/ 記錄規(guī)則中（）后的符號int flag;/ 檢測到（）n=t=k=0;for( i=0;i50;i+)pi=用 pi.append(1,a)u=u=;/;/ 字符串如果不初始化，在使用 pij=a 時將不能改變， 可以字符串如果不初始化，無法使用ui=a 賦值，可以用 u.append(1,a)for(n=0;!gn.empty();n+) un=gn0;/ 非終結(jié)符集合，n

6、 為非終結(jié)符個數(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!=)ut+=gij;/ 終結(jié)符集合， t 為終結(jié)符個數(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=gitem

7、p+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 中所有直接左遞歸得到文法g2，要能夠消除含有多個左遞歸的情況）string arfa,beta;/ 所有形如 a:=a |中的 、連接起來形成的字符串

8、arfa、 betaint i,j,temp,m=0;/計數(shù)int flag=0;/flag=1表示文法有左遞歸int flagg=0;/flagg=1表示某條規(guī)則有左遞歸由于消除左遞歸新增的非終結(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); if(pj+14=ui) arfa.

9、append(|);/ 不止一個產(chǎn)生式含有左遞歸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);while(u.find(c)!=string

10、: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);ggm.append(|);m+;c+;/a:=a 改|寫成 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=0

11、;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)到空elsefor(j=4;pij!= ;j+)if(u.find(pij)!=string:npos)if(emptyu.find(pij)=0) break;elsebreak;if(pij= ) emptyr=1;/多步推導(dǎo)到空else flag=0;return empty;str

12、ing* 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ī)則右部首符號為空elsefor(j=4;pij!= ;j+)a=pij;

13、if(u.find(a)!=string:npos&firstr.find(a)=string:npos)/規(guī)則右部首符號是終結(jié)符firstr.append(1,a);break;/ 添加并結(jié)束if(u.find(pij)!=string:npos)/規(guī)則右部首符號是非終結(jié)符,形如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);if(!emptys)

14、break;/ 若 y1 不能推導(dǎo)到空，結(jié)束if(pij= )if(firstr.find()=string:npos)firstr.append(1,);/ 若 y1、 y2.yk 都能推導(dǎo)到空，則加入空符號return first;string first(string u,string u,string* first,string s)/求符號串s=x1x2.xn的 first集int i,j,r;char a;stringfir;for(i=0;is.length();i+)if(si=) fir.append(1,);是終結(jié)符， 添加并結(jié)束循環(huán)if(u.find(si)!=strin

15、g:npos)/x1 是非終結(jié)符r=u.find(si);for(j=0;firstrj!=0;j+)a=firstrj;if(a!=&fir.find(a)=string:npos)/將 first(x1) 中的非空符號加入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中還未加入空符號fir.append(1,);return fir;string* create_table(str

16、ing *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=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;

17、ik;i+)arfa=pi;arfa.erase(0,4);/刪除前 4 個字符，如： e:=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;tablepq=pi;/對 first （）中的每一終結(jié)符置相應(yīng)的規(guī)則if(fir.find()!=string:npos)follow=followp;/對規(guī)則左部求follow()for(j=0;jt;j+)if(q=follow.find(uj)!=string:npos)q=j;tablepq

18、=pi;/對 follow （）中的每一終結(jié)符置相應(yīng)的規(guī)則tablept=pi;/對 # 所在元素置相應(yīng)規(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;/ 匹配成功標(biāo)志int i=0,j=0,step=1;/符號棧計數(shù)、輸入串計數(shù)、步驟數(shù)int p,q,r;string temp;for(i=0;!si;i+)if(u.

19、find(si)=string:npos)/出現(xiàn)非法的符號couts 不是該文法的句子n;return;s.append(1,#);stack.append(1,#);/ #進入分析棧stack.append(1,u0);i+;/ 文法開始符進入分析棧a=s0;/coutstackendl;cout 步驟分析棧余留輸入串所用產(chǎn)生式 n;while(!flag)/ cout步驟分析棧余留輸入串所用產(chǎn)生式nx=stacki;stack.erase(i,1);i-;/ 取棧頂符號x,并從棧頂退出/coutxendl;if(u.find(x)!=string:npos)/x是終結(jié)符的情況if(x=a)

20、s.erase(0,1);a=s0;/棧頂符號與當(dāng)前輸入符號匹配，則輸入下一個符號coutn;/未使用產(chǎn)生式，輸出空elsecouterrorn;coutss 不是該文法的句子n;break;if(x=#)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)if(tempr!=)stack.append(

21、1,tempr);/ 將 x:=x1x2. 的規(guī)則右部各符號壓棧 i+;r-;elsecouterrorn;coutss 不是該文法的句子n;break;step+;if(flag)coutendlss是該文法的句子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 str

22、ing50;/ 文法 gg 的產(chǎn)生式集合ppstring uu,uu;/ 文法 gg 非終結(jié)符集合u，終結(jié)符集合uint nn,tt,kk;/ 消除左遞歸后的非終結(jié)符、終結(jié)符個數(shù),產(chǎn)生式數(shù)string* table;/ 分析表cout歡迎使用ll(1)語法分析器!nnn;cout 請輸入文法（同一左部的規(guī)則在同一行輸入，例如：e:=e+t|t；用 表示空串）n;input_grammer(g);preprocess(g,p,u,u,n,t,k);coutn該文法有 n個非終結(jié)符： n;for(i=0;in;i+)coutui;coutendl;cout 該文法有 t個終結(jié)符： n;for(i=

23、0;it;i+)coutui;coutnn左遞歸檢測與消除nn;preprocess(gg,pp,uu,uu,nn,tt,kk);cout 該文法存在左遞歸！nn消除左遞歸后的文法:nn;for(i=0;inn;i+)coutggiendl;coutendl;cout 新文法有 nn個非終結(jié)符：n;for(i=0;inn;i+)coutuui;coutendl;cout 新文法有 tt個終結(jié)符： n;for(i=0;itt;i+)coutuui;coutendl;/cout新文法有 kk個產(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=ifempty(pp,uu,kk,nn);string* first=first_x(pp,uu,uu,empt