编译原理实验报告LL(1)分析法

1、课 程 编译原理 实验名称 实验二 LL(1)分析法 实验目的1掌握LL(1)分析法的基本原理； 2掌握LL(1)分析表的构造方法； 3掌握LL(1)驱动程序的构造方法。一. 实验内容及要求根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析LL（1）分析法的理解。 对下列文法，用LL（1）分析法对任意输入的符号串进行分析：（1）E-TG（2）G-+TG（3）G-（4）T-FS（5）S-*FS（6）S-（7）F-(E)（8）F-i程序输入一以#结束的符号串(包括+*（）i#)，如：i+i*i#。输出过程如下：步骤分析栈剩余输入串所用产生式1

2、Ei+i*i#E-TG.二. 实验过程及结果代码如下：#include#include edge.husing namespace std;edge:edge()cinleftright;rlen=right.length();if(NODE.find(left)NODE.length() NODE+=left;string edge:getlf()return left;string edge:getrg()return right;string edge:getfirst()return first;string edge:getfollow()return follow;string e

3、dge:getselect()return select;string edge:getro()string str;str+=right0;return str;int edge:getrlen()return right.length();void edge:newfirst(string w)int i;for(i=0;ifirst.length()first+=wi;void edge:newfollow(string w)int i;for(i=0;ifollow.length()&wi!=)follow+=wi;void edge:newselect(string w)int i;

4、for(i=0;iselect.length()&wi!=)select+=wi;void edge:delfirst()int i=first.find();first.erase(i,1);int SUM;string NODE,ENODE;/计算firstvoid first(edge ni,edge *n,int x)int i,j;for(j=0;jSUM;j+)if(ni.getlf()=nj.getlf()if(NODE.find(nj.getro()NODE.length() for(i=0;iSUM;i+) if(ni.getlf()=nj.getro() first(ni,

5、n,x);else nx.newfirst(nj.getro();/计算followvoid follow(edge ni,edge *n,int x)int i,j,k,s;string str;for(i=0;ini.getrlen();i+)s=NODE.find(ni.getrg()i);if(s-1) /是非终结符if(ini.getrlen()-1) /不在最右for(j=0;jSUM;j+)if(nj.getlf().find(ni.getrg()i)=0)if(NODE.find(ni.getrg()i+1)NODE.length()for(k=0;kSUM;k+) if(nk

6、.getlf().find(ni.getrg()i+1)=0) nj.newfollow(nk.getfirst(); if(nk.getfirst().find()nk.getfirst().length() nj.newfollow(ni.getfollow(); elsestr.erase();str+=ni.getrg()i+1;nj.newfollow(str);/计算selectvoid select(edge &ni,edge *n)int i,j;if(ENODE.find(ni.getro()ENODE.length()ni.newselect(ni.getro();if(n

7、i.getro()=)ni.newselect(ni.getfollow();elsefor(i=0;ini.getrlen();i+)for(j=0;jnj.getfirst().length()return;/输出集合void out(string p)int i;if(p.length()=0) return;cout;for(i=0;ip.length()-1;i+) coutpi,;coutpi;/连续输出符号void outfu(int a,string c)int i;for(i=0;ia;i+)coutc;/输出预测分析表void outgraph(edge *n,string

8、 (*yc)50)int i,j,k;bool flag;for(i=0;iENODE.length();i+) if(ENODEi!=) outfu(10, );coutENODEi; outfu(10, );cout#endl;int x;for(i=0;iNODE.length();i+)outfu(4, );coutNODEi;outfu(5, );for(k=0;kENODE.length();k+)flag=1;for(j=0;jSUM;j+) if(NODEi=nj.getlf()0) x=nj.getselect().find(ENODEk); if(x-1) coutnj.g

9、etrg(); ycik=nj.getrg(); outfu(9-nj.getrlen(), ); flag=0; x=nj.getselect().find(#); if(k=ENODE.length()-1&x-1) coutnj.getrg(); ycij=nj.getrg(); if(flag&ENODEk!=) outfu(11, );coutendl;/分析符号串int pipei(string &chuan,string &fenxi,string (*yc)50,int &b)char ch,a;int x,i,j,k;b+;coutendl 9) outfu(8, );els

10、e outfu(9, );coutfenxi;outfu(26-chuan.length()-fenxi.length(), );coutchuan;outfu(10, );a=chuan0;ch=fenxifenxi.length()-1;x=ENODE.find(ch);if(x-1) if(ch=a) fenxi.erase(fenxi.length()-1,1);chuan.erase(0,1);couta匹配;if(pipei(chuan,fenxi,yc,b) return 1;else return 0; elsereturn 0;else if(ch=#) if(ch=a) c

11、out分析成功endl; return 1;elsereturn 0; elseif(ch=) fenxi.erase(fenxi.length()-1,1); if(pipei(chuan,fenxi,yc,b) return 1; else return 0;else i=NODE.find(ch); if(a=#) x=ENODE.find(); if(x-1) j=ENODE.length()-1; else j=ENODE.length(); elsej=ENODE.find(a); if(ycij.length() coutNODEi-1;k-) if(ycijk!=)fenxi+

12、=ycijk; if(pipei(chuan,fenxi,yc,b) return 1; else return 0; elsereturn 0;void main()edge *n;string str,(*yc)50;int i,j,k;bool flag=0;cout请输入上下文无关文法的总规则数：SUM;cout请输入具体规则（格式：左部 右部，为空）：endl;n=new edgeSUM;for(i=0;iSUM;i+) for(j=0;jNODE.length()&ENODE.find(strj)ENODE.length()ENODE+=strj; /计算first集合for(i=

13、0;iSUM;i+) first(ni,n,i);/outfu(10,*);coutendl;for(i=0;iSUM;i+) if(ni.getfirst().find()ni.getfirst().length() if(NODE.find(ni.getro()NODE.length() for(k=1;kni.getrlen();k+) if(NODE.find(ni.getrg()k)NODE.length() for(j=0;jnj.getfirst().length() ni.delfirst();break; /计算follow集合for(k=0;kSUM;k+) for(i=0

14、;iSUM;i+) if(ni.getlf()=n0.getlf() ni.newfollow(#);follow(ni,n,i); for(i=0;iSUM;i+) for(j=0;jSUM;j+) if(nj.getrg().find(ni.getlf()=nj.getrlen()-1) ni.newfollow(nj.getfollow(); /计算select集合for(i=0;iSUM;i+) select(ni,n);for(i=0;iNODE.length();i+) str.erase(); for(j=0;jSUM;j+)if(nj.getlf()0=NODEi)if(!st

15、r.length()str=nj.getselect();elsefor(k=0;knj.getselect().length();k+)if(str.find(nj.getselect()k)str.length()flag=1;break;/输出coutendl非终结符;outfu(SUM, );coutFirst;outfu(SUM, );coutFollowendl;outfu(5+SUM,-*-);coutendl;for(i=0;iNODE.length();i+) for(j=0;jSUM;j+)if(NODEi=nj.getlf()0) outfu(3, ); coutNODE

16、i; outfu(SUM+4, ); out(nj.getfirst(); outfu(SUM+4-2*nj.getfirst().length(), ); out(nj.getfollow(); coutendl; break;outfu(5+SUM,-*-);coutendl判定结论： ;if(flag) cout该文法不是LL(1)文法!endl; return;else cout该文法是LL(1)文法!endl;/输出预测分析表coutendl预测分析表如下：endl;yc=new stringNODE.length()50;outgraph(n,yc);string chuan,fenxi,fchuan;coutendlchuan;fchuan=chuan;fenxi=#;fenxi+=NODE0;i=0;coutendl预测分析过程如