自动生成LR0分析表

编译原理实验报告实验名称自动生成LR（0）分析表实验时间2011年6月13日院系计算机科学与技术班级08计算机科技一班学号E10814065姓名王全鸿1.试验目的输入：任意的压缩了的上下文无关文法。输出：相应的LR（0）分析表。2.实验原理在LR分析工作过程中的任何时候，栈里的文法符号（自栈底而上）X1X2…Xm应该构成活前缀，把输入串的剩余部分配上之后即应成为规范句型（如果整个输入串确实构成一个句子）。因此，只要输入串的已扫描部分保持可归约成一个活前缀，那就意味着所扫描过的部分没有错误。构造识别文法活前缀DFA有3种方法：（1）根据形式定义求出活前缀的正则表达式，然后由此正则表达式构造NFA再确定为DFA；（2）求出文法的所有项目，按一定规则构造识别活前缀的NFA再确定化为DFA；（3）使用闭包函数（CLOSURE）和转向函数(GO(I,X))构造文法G’的LR(0)的项目集规范族，再由转换函数建立状态之间的连接关系来得到识别活前缀的DFA。对于LR（0）文法，我们可以直接从它的项目集规范族C和活前缀识别自动机的状态转换函数GO构造出LR分析表。下面是构造LR（0）分析表的算法。假定C={I0,I1,…，In}，令每个项目集Ik的下标k为分析器的一个状态，因此，G'的LR(0)分析表含有状态0，1，…，n。令那个含有项目S'→．S的Ik的下标k为初态。ACTION子表和GOTO子表可按如下方法构造：（1）若项目A→α.aβ属于Ik且GO(Ik,a)=Ij,a为终结符，则置ACTION[k,a]为“把状态j和符号a移进栈”，简记为“sj”；（2）若项目A→α．属于Ik，那么，对任何终结符a，置ACTION[k，a]为“用产生式A→α进行规约”，简记为“rj”；其中，假定A→α为文法G'的第j个产生式；（3）若项目S'→S．属于Ik,则置ACTION[k,#]为“接受”，简记为“acc”；（4）若GO(Ik,A)=Ij,A为非终结符，则置GOTO[k,A]=j；（5）分析表中凡不能用上述1至4填入信息的空白格均置上“出错标志”。按上述算法构造的含有ACTION和GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法G的一张LR(0)分析表。具有LR(0)表的文法G称为一个LR（0）文法，LR(0)文法是无二义的。3.实验内容(1)实现计算闭包closure（I）的算法；(2)实现转向函数Go（q，a）的算法；(3)构造文法项目集函数CreateProjectSet（）；定义数据结构：typedefstruct{SElemType*base,*top;intstacksize;}SqStack;structgrammer{char**g;charvt[127];charvn[27];chars;intline;};typedefstructprjset{intid;//项目集编号，从10000开始，与项目编号（从0开始）区别structprjset*next;//指向下个项目集charprjt[PROJECT_SET_SIZE+1];//PROJECT_SET_SIZE个单元,存储项目的编号,prjt[0]项目编号的个数charpointafter[PROJECT_SET_SIZE+1];//圆点后的字符,pointafter[0]字符个数structprjset*actorgo[PROJECT_SET_SIZE];charpointbefore;}prjset,*pprjset;4.实验心得通过这次实验我对LR（0）语法分析有了一个更熟悉的掌握,对预先定义的文法规则，并集成词法分析、符号表管理等程序来生成LR（0）分析表有了清醒的认识，并且对高级程序语言一般结构和主要共同特征有了全面的认识和理解.5.实验代码voidCreateProjectSet(){//构造文法的项目集inti;intj;intk;intid=ID;pprjsetp,q;root.I=root.tail=NULL;if((p=(pprjset)malloc(sizeof(prjset)))==NULL)exit(1);p-id=id;p-next=NULL;p-prjt[0]=0;p-pointafter[0]=0;p-pointbefore='\0';for(j=0;jPROJECT_SET_SIZE;j++)p-actorgo[j]=NULL;for(j=0;jPROJECT_SET_SIZE;j++)p-actorgo[j]=NULL;root.I=p;root.tail=p;root.size=1;for(i=0;iproject.line;i++){if(project.s==project.gp[i][GRAMMER_START_CHAR_POS]&&DOT==project.gp[i][GRAMMER_START_CHAR_POS+1]){JoinSet(root.I-prjt,project.gp[i][PROJECT_ID_POS]);JoinSet(root.I-pointafter,project.gp[i][AFCHAR_POS]);break;}//if}//forClosure(root.I);intpos;for(q=root.I;q!=NULL;q=q-next){for(i=1;i=q-pointafter[0];i++){pos=i;pos--;if((p=(pprjset)malloc(sizeof(prjset)))==NULL)exit(1);p-next=NULL;p-prjt[0]=0;p-pointafter[0]=0;p-pointbefore=q-pointafter[i];for(j=0;jPROJECT_SET_SIZE;j++)p-actorgo[j]=NULL;for(j=1;j=q-prjt[0];j++){if(project.gp[q-prjt[j]][AFCHAR_POS]==p-pointbefore)go(q-prjt[j],p);}//forClosure(p);//判断p指向的项目集是否已存在pprjsetptr;intflag;intflagsame;flagsame=1;flag=1;for(ptr=root.I;ptr!=NULL;ptr=ptr-next){flag=1;if(p-prjt[0]==ptr-prjt[0]){for(k=1;k=p-prjt[0];k++){if(!IsInSet(ptr-prjt,p-prjt[k])){flag=0;break;}//if}//for}//ifelse{flag=0;}//elseif(flag==0)flagsame=0;else{flagsame=1;break;}}//forif(flagsame)//flagsame==1,有与*p相同的项目集，删除*p{q-actorgo[i-1]=ptr;free(p);}else//将p挂到root.tail{q-actorgo[i-1]=p;p-id=++id;root.tail-next=p;root.tail=p;root.size++;}}//for}//for}//CreateProjectSetvoidClosure(prjset*pset){//rk为项目的编号，prjset指向项目集inti;intj;intrk;for(i=1;i=pset-prjt[0];i++){rk=pset-prjt[i];if(IsInSet(g.vn,project.gp[rk][AFCHAR_POS]))//若圆点后字符为vn{for(j=0;jproject.line;j++){if(project.gp[j][GRAMMER_START_CHAR_POS]==project.gp[rk][AFCHAR_POS]&&project.gp[j][GRAMMER_START_CHAR_POS+1]==DOT){JoinSet(pset-prjt,project.gp[j][PROJECT_ID_POS]);JoinSet(pset-pointafter,project.gp[j][AFCHAR_POS]);}//if}//for}//if}//for}//Closureintgo(intrk,pprjsetprjset){//rk为项目编号，将rk的去向加入prjset指向的项目集中,返回项目编号，若无返回-1inti;intj;intrksize;charrkS;charrkpointafter;if((rkpointafter=project.gp[rk][AFCHAR_POS])=='\0'){return-1;}intpointpos;pointpos=IsInSet(&project.gp[rk][PROJECT_LEN_POS],DOT);pointpos+=PROJECT_LEN_POS;rksize=project.gp[rk][PROJECT_LEN_POS];rkS=project.gp[rk][GRAMMER_START_CHAR_POS];for(i=0;iproject.line;i++){if(project.gp[i][GRAMMER_START_CHAR_POS]==rkS&&project.gp[i][PROJECT_LEN_POS]==rksize&&project.gp[i][BFCHAR_POS]==rkpointafter){intflag;flag=1;for(j=pointpos+2;j=project.gp[iPROJECT_LEN_POS]+PROJECT_LEN_POS;j++){if(project.gp[i][j]!=project.gp[rk][j]){flag=0;break;}}//forif(flag){JoinSet(prjset-prjt,project.gp[i][PROJECT_ID_POS]);//将项目加入项目集if(project.gp[i][AFCHAR_POS]!='\0'){JoinSet(prjset-pointafter,project.gp[i][AFCHAR_POS]);}//将项目圆点后的字符加入returnproject.gp[i][PROJECT_ID_POS];}//ifelsereturn-1;}//if}//for}//govoidmain(){Init();printf(请输入所要分析的文法(#结束):\n);Input();CreateProjectSet();CreateAnalysisForm();PrintForm();}//main