自动生成LR0分析表

1、 编译原理实验报告实验名称 自动生成LR（0）分析表 实验时间 2011年6月13日 院系 计算机科学与技术 班级 08计算机科技一班 学号 E 姓名 王全鸿 1. 试验目的输入：任意的压缩了的上下文无关文法。输出：相应的LR（0）分析表。2. 实验原理在LR分析工作过程中的任何时候，栈里的文法符号（自栈底而上）X1X2Xm应该构成活前缀，把输入串的剩余部分配上之后即应成为规范句型（如果整个输入串确实构成一个句子）。因此，只要输入串的已扫描部分保持可归约成一个活前缀，那就意味着所扫描过的部分没有错误。构造识别文法活前缀DFA有3种方法：（1）根据形式定义求出活前缀的正则表达式，然后由此正则表达

2、式构造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。令那个含有项目SS的Ik的下标k为初态。ACTION子表和GOTO子表可按如

3、下方法构造：（1）若项目A.a属于Ik且GO (Ik, a)= Ij, a为终结符，则置ACTIONk, a为“把状态j和符号a移进栈”，简记为“sj”；（2）若项目A属于Ik，那么，对任何终结符a，置ACTIONk，a为“用产生式A进行规约”，简记为“rj”；其中，假定A为文法G的第j个产生式；（3）若项目SS属于Ik, 则置ACTIONk, #为“接受”，简记为“acc”；（4）若GO (Ik, A)= Ij, A为非终结符，则置GOTOk, A=j；（5）分析表中凡不能用上述1至4填入信息的空白格均置上“出错标志”。按上述算法构造的含有ACTION和GOTO两部分的分析表，如果每个入口不

4、含多重定义，则称它为文法G的一张LR(0)分析表。具有LR(0)表的文法G称为一个LR（0）文法，LR(0)文法是无二义的。3. 实验内容(1) 实现计算闭包closure（I）的算法；(2) 实现转向函数Go（q，a）的算法；(3)构造文法项目集函数CreateProjectSet（）；定义数据结构：typedef struct SElemType *base,*top; int stacksize; SqStack;struct grammer char *g; char vt127; char vn27; char s; int line;typedef struct prjsetint

5、 id;/项目集编号，从10000开始，与项目编号（从0开始）区别struct prjset *next;/指向下个项目集char prjtPROJECT_SET_SIZE+1;/PROJECT_SET_SIZE个单元,存储项目的编号,prjt0项目编号的个数char pointafterPROJECT_SET_SIZE+1;/圆点后的字符,pointafter0字符个数struct prjset *actorgoPROJECT_SET_SIZE;char pointbefore;prjset,*pprjset;4.实验心得通过这次实验我对LR（0）语法分析有了一个更熟悉的掌握,对预先定义的文

6、法规则，并集成词法分析、符号表管理等程序来生成LR（0）分析表有了清醒的认识，并且对高级程序语言一般结构和主要共同特征有了全面的认识和理解.5.实验代码void CreateProjectSet()/构造文法的项目集int i;int j;int k;int id = ID;pprjset p,q;root.I = root.tail = NULL;if(p = (pprjset)malloc(sizeof(prjset) = NULL) exit(1);p-id = id;p-next = NULL;p-prjt0 = 0;p-pointafter0 = 0;p-pointbefore =

7、0;for(j=0; jactorgoj = NULL;for(j=0; jactorgoj = NULL;root.I = p;root.tail = p;root.size = 1;for(i=0; iprjt, project.gpiPROJECT_ID_POS);JoinSet(root.I-pointafter, project.gpiAFCHAR_POS);break;/if/forClosure(root.I);int pos;for(q=root.I; q!=NULL; q=q-next)for(i=1; ipointafter0; i+)pos = i;pos-;if(p =

8、 (pprjset)malloc(sizeof(prjset) = NULL) exit(1);p-next = NULL;p-prjt0 = 0;p-pointafter0 = 0;p-pointbefore = q-pointafteri;for(j=0; jactorgoj = NULL;for(j=1; jprjt0; j+)if(project.gpq-prjtjAFCHAR_POS = p-pointbefore)go(q-prjtj, p);/forClosure(p);/判断p指向的项目集是否已存在pprjset ptr;int flag;int flagsame;flagsa

9、me = 1;flag = 1;for(ptr=root.I; ptr!=NULL; ptr=ptr-next)flag = 1;if(p-prjt0 = ptr-prjt0)for(k=1; kprjt0; k+)if(!IsInSet(ptr-prjt, p-prjtk)flag = 0;break;/if/for/ifelseflag = 0;/elseif(flag = 0)flagsame = 0;elseflagsame = 1;break;/forif(flagsame)/flagsame = 1 , 有与*p相同的项目集，删除*pq-actorgoi-1 = ptr;free(

10、p);else/将p挂到root.tailq-actorgoi-1 = p;p-id = +id;root.tail-next = p;root.tail = p;root.size+;/for/for/CreateProjectSetvoid Closure(prjset *pset)/rk 为项目的编号，prjset指向项目集int i;int j;int rk;for(i=1; iprjt0; i+)rk = pset-prjti;if(IsInSet(g.vn, project.gprkAFCHAR_POS)/若圆点后字符为vnfor(j=0; jprjt, project.gpjPR

11、OJECT_ID_POS);JoinSet(pset-pointafter, project.gpjAFCHAR_POS);/if/for/if/for/Closureint go(int rk, pprjset prjset)/rk为项目编号，将rk的去向加入prjset指向的项目集中,返回项目编号，若无返回-1int i;int j;int rksize;char rkS;char rkpointafter;if(rkpointafter = project.gprkAFCHAR_POS) = 0)return -1;int pointpos;pointpos = IsInSet(&pro

12、ject.gprkPROJECT_LEN_POS, DOT);pointpos += PROJECT_LEN_POS;rksize = project.gprkPROJECT_LEN_POS;rkS = project.gprkGRAMMER_START_CHAR_POS;for(i=0; iproject.line; i+) if(project.gpiGRAMMER_START_CHAR_POS=rkS&project.gpiPROJECT_LEN_POS = rksize & project.gpiBFCHAR_POS = rkpointafter)int flag;flag = 1;for(j=pointpos+2;jprjt, project.gpiPROJECT_ID_POS);/将项目加入项目集if(project.gpiAFCHAR_POS != 0)JoinSet(prjset-pointafter, project.g