自动生成LR0分析表由刀豆文库小编整理,希望给你工作、学习、生活带来方便,猜你可能喜欢“自动生成lr0分析表”。
编译原理实验报告
实验名称
实验时间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(); 定义数据结构:
typedef struct{SElemType *base,*top;int stacksize;}SqStack;
struct grammer{char **g;char vt[127];
};
char vn[27];char s;int line;
typedef struct prjset {int id;//项目集编号,从10000开始,与
项目编号(从0开始)区别
struct prjset *next;//指向下个项目集char
prjt[PROJECT_SET_SIZE+1];//PROJECT_SET_SIZE个单元,存储项目的编号,prjt[0]项目编号的个数
char pointafter[PROJECT_SET_SIZE+1];//
圆点后的字符,pointafter[0]字符个数struct prjset *actorgo[PROJECT_SET_SIZE];char pointbefore;}prjset,*pprjset;
4.实验心得
通过这次实验我对LR(0)语法分析有了一个更熟悉的掌握,对预先定义的文法规则,并集成词法分析、符号表管理等程序来生成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)))==
{
JoinSet(root.I->prjt, JoinSet(root.I->pointafter,project.gp[i][PROJECT_ID_POS]);project.gp[i][AFCHAR_POS]);
break;}//if
}//for
Closure(root.I);int pos;
for(q=root.I;q!=NULL;q=q->next){
for(i=1;ipointafter[0];i++){
NULL)exit(1);p->id = id;
p->next = NULL;p->prjt[0] = 0;
p->pointafter[0] = 0;p->pointbefore = ' ';
for(j=0;jactorgo[j] = NULL;for(j=0;jactorgo[j] = NULL;root.I = p;root.tail = p;root.size = 1;
for(i=0;i
if(project.s==project.gp[i][GRAMMER_START_CHAR_POS]&&DOT== project.gp[i][GRAMMER_START_CHAR_POS+1])
pos = i;pos--;if((p
(pprjset)malloc(sizeof(prjset)))exit(1);
==
= NULL)
p->next = NULL;p->prjt[0] = 0;
p->pointafter[0] = 0;p->pointbefore
=
q->pointafter[i];for(j=0;j
{
p->actorgo[j] = NULL;
for(j=1;jprjt[0];j++)
if(project.gp[q->prjt[j]][AFCHAR_POS] ==q->actorgo[i-1] = ptr;
p->pointbefore)go(q->prjt[j], p);}//forClosure(p);//判断p指向的项目集是否已存在pprjset ptr;int flag;int flagsame;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;
kprjt[0];k++){
if(!IsInSet(ptr->prjt, p->prjt[k])){flag = 0;
break;
}//if
}//for
}//if
else{
flag = 0;
}//elseif(flag == 0)
flagsame = 0;
else
{
flagsame = 1;break;
}
}//for
if(flagsame)//flagsame == 1 ,有与*p相同的项目集,删除*p{
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}//CreateProjectSet
void Closure(prjset *pset)
{//rk 为项目的编号,prjset指向项目集int i;
int j;
int rk;
for(i=1;iprjt[0];i++){rk = pset->prjt[i];
if(IsInSet(g.vn,project.gp[rk][AFCHAR_POS]))//若圆点后字符为vn{for(j=0;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
}//Closure
int go(int rk, pprjset prjset)
{//rk为项目编号,将rk的去向加入prjset指向的项目集中,返回项目编号,若无返回-1
}//for
if(flag){
JoinSet(prjset->prjt,project.gp[i][PROJECT_ID_
int i;int j;int rksize;char rkS;char rkpointafter;if((rkpointafter =
project.gp[rk][AFCHAR_POS])== ' ')
{ return-1;}
int pointpos;
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;i
if(project.gp[i][GRAMMER_START_CHAR_POS]==rkS&&project.gp[i][PROJECT_LEN_POS] == rksize && project.gp[i][BFCHAR_POS] ==
rkpointafter){
int flag;
flag = 1;
for(j=pointpos+2;j
N_POS;j++)
{
if(project.gp[i][j]!=
project.gp[rk][j]){flag = 0;break;
}
POS]);//将项目加入项目集
if(project.gp[i][AFCHAR_POS]!= ' ')
{JoinSet(prjset->pointafter, project.gp[i][AFCHAR_POS]);}//将项目圆点后的字符加入
return
project.gp[i][PROJECT_ID_POS];
}//ifelsereturn-1;
}//if
}//for }//go
void main(){Init();
printf(“请输入所要分析的文法(#结束):n”);Input();
CreateProjectSet();
CreateAnalysisForm();
PrintForm();}//main
LoadRunner分析结果图功能说明Transactions(用户事务分析)用户事务分析是站在用户角度进行的基础性能分析。1、Transation Sunmmary(事务综述)对事务进行综合分析是性能分析的第......
体检报告管理软件与体检中心管理软件的区别《体检报告管理软件health-helper》(以下简称神指)与《体检中心管理软件health-finger》(以下简称妙手)同属于天方达公司《杏林七贤》......
今天刚知道原来参考文献可以自动生成……真丢脸!分享给为论文奋斗的同学 毕业论文不同于一般的小论文,特别是硕士毕业论文或者博士毕业论文。一般的小论文就四五页,而硕士论文......
方法一, 在写作或制作文件的过程中,目录是必不可少的一项,但在实际情况当中,大家不知道使用word中的目录功能,而是自己在首页手动编制,结果常常因为后面格式或者字体的调整,使得目......
毕业论文如何自动生成参考文献参考文献的自动生成 刚刚学会很好很方便~ 来源: 陈郁的日志写论文,参考文献的修改很麻烦,删除一个,添加一个,就需要改一长串数字。怎么办呢。本人推......