LL1预测分析法实验报告

编译原理实验报告一、实验目的及要求1.通过本次实验，加深对LL(1)预测分析法原理的认识和理解。2.构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子。3.了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。二、运行环境：硬件：windowsxp软件：visualc++6.0三、实验内容1、分析使用LR(1)的优点：(1)LR分析器能够构造来识别所有能用上下文无关文法写的程序设计语言的结构。(2)LR分析方法是已知的最一般的无回溯移进-归约方法，它能够和其他移进-归约方法一样有效地实现。(3)LR方法能分析的文法类是预测分析法能分析的文法类的真超集。(4)LR分析器能及时察觉语法错误,快到自左向右扫描输入的最大可能。为了使一个文法是LR的，只要保证当句柄出现在栈顶时，自左向右扫描的移进-归约分析器能够及时识别它便足够了。当句柄出现在栈顶时，LR分析器必须要扫描整个栈就可以知道这一点，栈顶的状态符号包含了所需要的一切信息。如果仅知道栈内的文法符号就能确定栈顶是什么句柄。LR分析表的转移函数本质上就是这样的有限自动机。不过，这个有限自动机不需要根据每步动作读栈，因为，如果这个识别句柄的有限自动机自底向上读栈中的文法符号的话，它达到的状态正是这时栈顶的状态符号所表示的状态，所以，LR分析器可以从栈顶的状态确定它需要从栈中了解的一切。2、LR分析器由三个部分组成：(1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。(2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。四、程序源代码：//edge.h#ifndefHEAD_EDGE#defineHEAD_EDGE#includestringusingnamespacestd;externintSUM;externstringNODE,ENODE;classedge{public:edge();stringgetlf();stringgetrg();stringgetfirst();stringgetfollow();stringgetselect();stringgetro();intgetrlen();voidnewfirst(stringw);voidnewfollow(stringw);voidnewselect(stringw);voiddelfirst();private:stringleft,right,first,follow,select;intrlen;};#endif///////////////////////////////////////////////////////////////////////////////edge.cpp#includeiostream#includeedge.husingnamespacestd;edge::edge(){cinleftright;rlen=right.length();if(NODE.find(left)NODE.length())NODE+=left;}stringedge::getlf(){returnleft;}stringedge::getrg(){returnright;}stringedge::getfirst(){returnfirst;}stringedge::getfollow(){returnfollow;}stringedge::getselect(){returnselect;}stringedge::getro(){stringstr;str+=right[0];returnstr;}intedge::getrlen(){returnright.length();}voidedge::newfirst(stringw){inti;for(i=0;iw.length();i++)if(first.find(w[i])first.length())first+=w[i];}voidedge::newfollow(stringw){inti;for(i=0;iw.length();i++)if(follow.find(w[i])follow.length()&&w[i]!='*')follow+=w[i];}voidedge::newselect(stringw){inti;for(i=0;iw.length();i++)if(select.find(w[i])select.length()&&w[i]!='*')select+=w[i];}voidedge::delfirst(){inti=first.find('*');first.erase(i,1);}//LL1.cpp#includeiostream#includestring#includeedge.husingnamespacestd;intSUM;stringNODE,ENODE;//计算firstvoidfirst(edgeni,edge*n,intx){inti,j;for(j=0;jSUM;j++){if(ni.getlf()==n[j].getlf()){if(NODE.find(n[j].getro())NODE.length()){for(i=0;iSUM;i++)if(n[i].getlf()==n[j].getro())first(n[i],n,x);}elsen[x].newfirst(n[j].getro());}}}//计算followvoidfollow(edgeni,edge*n,intx){inti,j,k,s;stringstr;for(i=0;ini.getrlen();i++){s=NODE.find(ni.getrg()[i]);if(sNODE.length()&&s-1)//是非终结符if(ini.getrlen()-1)//不在最右for(j=0;jSUM;j++)if(n[j].getlf().find(ni.getrg()[i])==0){if(NODE.find(ni.getrg()[i+1])NODE.length()){for(k=0;kSUM;k++)if(n[k].getlf().find(ni.getrg()[i+1])==0){n[j].newfollow(n[k].getfirst());if(n[k].getfirst().find(*)n[k].getfirst().length())n[j].newfollow(ni.getfollow());}}else{str.erase();str+=ni.getrg()[i+1];n[j].newfollow(str);}}}}//计算selectvoidselect(edge&ni,edge*n){inti,j;if(ENODE.find(ni.getro())ENODE.length()){ni.newselect(ni.getro());if(ni.getro()==*)ni.newselect(ni.getfollow());}elsefor(i=0;ini.getrlen();i++)for(j=0;jSUM;j++)if(ni.getrg()[i]==n[j].getlf()[0]){ni.newselect(n[j].getfirst());if(n[j].getfirst().find('*')n[j].getfirst().length())return;}}//输出集合voidout(stringp){inti;if(p.length()==0)return;cout{;for(i=0;ip.length()-1;i++){coutp[i],;}coutp[i]};}//连续输出符号voidoutfu(inta,stringc){inti;for(i=0;ia;i++)coutc;}//输出预测分析表voidoutgraph(edge*n,string(*yc)[50]){inti,j,k;boolflag;for(i=0;iENODE.length();i++){if(ENODE[i]!='*'){outfu(10,);coutENODE[i];}}outfu(10,);cout#endl;intx;for(i=0;iNODE.length();i++){outfu(4,);coutNODE[i];outfu(5,);for(k=0;kENODE.length();k++){flag=1;for(j=0;jSUM;j++){if(NODE[i]==n[j].getlf()[0]){x=n[j].getselect().find(ENODE[k]);if(xn[j].getselect().length()&&x-1){cout-n[j].getrg();yc[i][k]=n[j].getrg();outfu(9-n[j].getrlen(),);flag=0;}x=n[j].getselect().find('#');if(k==ENODE.length()-1&&xn[j].getselect().length()&&x-1){cout-n[j].getrg();yc[i][j]=n[j].getrg();}}}if(flag&&ENODE[k]!='*')outfu(11,);}coutendl;}}//分析符号串intpipei(string&chuan,string&fenxi,string(*yc)[50],int&b){charch,a;intx,i,j,k;b++;coutendlb;if(b9)outfu(8,);elseoutfu(9,);coutfenxi;outfu(26-chuan.length()-fenxi.length(),);coutchuan;outfu(10,);a=chuan[0];ch=fenxi[fenxi.length()-1];x=ENODE.find(ch);if(xENODE.length()&&x-1){if(ch==a){fenxi.erase(fenxi.length()-1,1);chuan.erase(0,1);cout'a'匹配;if(pipei(chuan,fenxi,yc,b))return1;elsereturn0;}elsereturn0;}else{if(ch=='#'){if(ch==a){cout分析成功endl;return1;}elsereturn0;}elseif(ch=='*'){fenxi.erase(fenxi.length()-1,1);if(pipei(chuan,fenxi,yc,b))return1;elsereturn0;}else{i=NODE.find(ch);if(a=='#'){x=ENODE.find('*');if(xENODE.length()&&x-1)j=ENODE.length()-1;elsej=ENODE.length();}elsej=ENODE.find(a);if(yc[i][j].length()){coutNODE[i]-yc[i][j];fenxi.erase(fenxi.length()-1,1);for(k=yc[i][j].length()-1;k-1;k--)if(yc[i][j][k]!='*')fenxi+=