编译原理实验报告
自动生成LR（0）分析表
计算机科学与技术
08计算机科技一班
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,*
}SqS struct grammer{
char vt[127];
char vn[27]; typedef struct prjset {//项目集编号，从10000开始，与 项目编号（从0开始）区别
struct prjset *//指向下个项目集
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]; }prjset,* 4.实验心得 通过这次实验我对LR（0）语法分析有了一个更熟悉的掌握,对预先定义的文法规则，并集成词法分析、符号表管理等程序来生成LR（0）分析表有了清醒的认识，并且对高级程序语言一般结构和主要共同特征有了全面的认识和理解. 5.实验代码
void CreateProjectSet() {//构造文法的项目集
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]);
}//if }//for Closure(root.I); for(q=root.I; q!=NULL; q=q->next) {
for(i=1; ipointafter[0]; i++) { NULL) exit(1);
p->next = NULL; p->prjt[0] = 0; p->pointafter[0] = 0; p->pointbefore = '\\0'; for(j=0; jactorgo[j] = NULL; for(j=0; jactorgo[j] = NULL; root.I = root.tail = root.size = 1;
for(i=0; i 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] = p->pointbefore)
go(q->prjt[j], p);
Closure(p);
//判断p指向的项目集是否已存在
flagsame = 1;
for(ptr=root.I; ptr!=NULL; ptr=ptr->next)
if(p->prjt[0] == ptr->prjt[0])
for(k=1; kprjt[0]; k++)
if(!IsInSet(ptr->prjt, p->prjt[k]))
if(flag == 0)
flagsame = 0;
flagsame = 1;
if(flagsame)//flagsame == 1 , 有与*p相同的项目集，删除*p
else//将p挂到root.tail
q->actorgo[i-1] =
p->id = ++
root.tail->next =
root.tail =
root.size++;
}//for }//for}//CreateProjectSet void Closure(prjset *pset) {//rk 为项目的编号，prjset指向项目集
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]);
}//Closure
int go(int rk, pprjset prjset) {//rk为项目编号，将rk的去向加入prjset指向的项目集中,返回项目编号，若无返回-1
}//for if(flag) { JoinSet(prjset->prjt, project.gp[i][PROJECT_ID_
if((rkpointafter = project.gp[rk][AFCHAR_POS]) == '\\0')
{ return -1; }
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)
flag = 1; for(j=pointpos+2;j<=project.gp[i PROJECT_LEN_POS]+PROJECT_LEN_POS; j++)
if(project.gp[i][j] != project.gp[rk][j])
} POS]);//将项目加入项目集
if(project.gp[i][AFCHAR_POS] != '\\0')
{JoinSet(prjset->pointafter, project.gp[i][AFCHAR_POS]);}//将项目圆点后的字符加入
return project.gp[i][PROJECT_ID_POS];
return -1;
}//for }//go
void main() {
printf(\请输入所要分析的文法(#结束):\\n\ Input();
CreateProjectSet();
CreateAnalysisForm();
PrintForm(); }//main您现在的位置： &
编译原理：LR(0)分析
　　7.2 LR(0)分析
　　LR(0)分析表构造的思想和方法是构造其它LR分析表的基础。我们回顾在第6章中曾给出例6.1文法G[S]为：
　　(1) S→aAcBe
　　(2) A→b
　　(3) A→Ab
　　(4) B→d
　　对输入串abbcde#用自底向上归约的方法进行分析，当归约到第5步时栈中符号串为#aAb，我们采用了产生式(3)进行归约而不是用产生式(2)归约，而在第3步归约时栈中符号串为#ab时却用产生式(2)归约，虽然在第2步和第5步归约前栈顶符号都为b，但归约所用产生式却不同，其原因在于已分析过的部分在栈中的前缀不同，也就是我们在LR分析中引进的状态栈的栈顶状态不同，为了说明这个问题我们先在表7.1中给出例6.1文法G[S]的LR(0)分析表，在表7.2给出对输入串abbcde#的分析过程，并引进一些概念和术语。
　　对表7.1的构造原理和表7.2分析过程的实现思想将在下面详细介绍。
　　表 7.1 例6.1文法的LR(0)分析表
　　表 7.1符号说明：
　　Si：移进，将状态i和输入符进栈
　　ri：归约，用第i个产生式归约，同时状态栈与符号栈退出相应个符号，并把GOTO表相应状态和第i个产生式的左部非终结符入栈。
　　表 7.2 对输入串abbcde#的分析过程
　　总结上面LR分析算法为：
　　置ip指向输入串w的第一个符号
　　令Si为栈顶状态
　　a是ip指向的符号（当前输入符号）
　　begin (重复开始)
　　if ACTION[Si,a]=Sj
　　then begin PUSH j,a (进栈)
　　ip 前进(指向下一输入符号)
　　if ACTION[Si,a]=rj(若第j条产生式 为A→β)
　　then begin
　　pop |β| 项
　　若当前栈顶状态为Sk
　　push GOTO[Sk,A] 和A(进栈)
　　else if ACTION[Si,a]=acc
　　then return (成功）
　　else error
　　end . (重复结束)
　　对于上面的分析过程我们可以知道LR分析器的关键部分是分析表的构造,那么可提出以下问题：
　　一个文法的LR分析表是如何得到的？
　　对于一个文法，状态集是如何确定的？
　　为了解决这些问题引入可归前缀与活前缀概念
了解更多计算机相关基础课程胎儿在母体中，便可感受孕妇的言行举止的变化。为了给胎儿一个良好的影响，准妈妈们也必须有一个良好的行为习惯，给胎儿生长提供绝佳的内外生长环境。这些为促进胎儿健康成长所作出的举动，我们俗称为“胎教”。
在此可输入您对该资料的评论~
(window.slotbydup = window.slotbydup || []).push({
id: '4540180',
container: s,
size: '250,200',
display: 'inlay-fix'
热门资料排行
添加成功至
资料评价：
所需积分：0