编译原理实验自动生成LR0分析表

-.z......资料....自动生成LR（0）分析表目录一、实验名称1二、实验目的1三、实验原理11、闭包closure(I)12、转换函数GO(I,*)13、ACTION子表和GOTO子表的构造1四、实验思路11、输入12、建立项目13、closure算法14、转向函数GO(I,*)的算法15、建立状态及对应的项目集16、ACTION子表的构造17、GOTO子表的构造1五、实验小结1六、11、源代码12、运行结果截图1一、实验名称自动生成LR（0）分析表二、实验目的1、实现计算闭包函数CLOSURE的算法。2、实现转向函数GO(I,*)的算法。3、实现ACTION子表和GOTO子表的构造算法。4、输入任意的压缩了的上下文无关文法，输出相应的LR（0）分析表（以表格形式输出）。三、实验原理1、闭包closure(I)若文法G已拓广为G’，而S为文法G的开始符号，拓广后增加产生式S’->S。如果I是文法G’的一个项目集，定义和构造I的闭包closure(I)如下：a.I的项目在closure(I)中。b.若A->α•Bβ属于closure(I)，则每一形如B->•γ的项目也属于closure(I)。c.重复b直到不出现新的项目为止。即closure(I)不再扩大。2、转换函数GO(I,*)GO(I,*)=closure(J)其中：I为包含*一项目集的状态。*为一文法符号，*∈Vn∪VtJ={任何形如A->α•*β的项目|A->α*•β属于I}3、ACTION子表和GOTO子表的构造a.若项目A→α.aβ属于Ik且GO(Ik,a)=Ij,a为终结符，则置ACTION[k,a]为“把状态j和符号a移进栈”，简记为“sj”；b.若项目A→α．属于Ik，则，对任何终结符a，置ACTION[k，a]为“用产生式A→α进行规约”，简记为“rj”；其中，假定A→α为文法G'的第j个产生式c.若项目S'→S．属于Ik,则置ACTION[k,*]为“接受”，简记为“acc”；d.若GO(Ik,A)=Ij,A为非终结符，则置GOTO[k,A]=j；e.分析表中凡不能用上述1至4填入信息的空白格均置上“出错标志”。按上述算法构造的含有ACTION和GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法G的一*LR(0)分析表。具有LR(0)表的文法G称为一个LR（0）文法，LR(0)文法是无二义的。四、实验思路本次实验采用python完成。1、输入构造一个LR类，输入非终结符，终结符，开始符以及产生式分别存于LR类的成员：Vn，Vt，start，production。2、建立项目构造函数Project，根据产生式建立项目，对每一条产生式的右部进行处理，依次在右部的每个终结符和非终结符前添加原点，并在最后添加原点。3、closure算法构造函数closure，求一个项目的闭包closure。分三种情况讨论，对于S->·和E->·a这两种情况，返回自身。对于E->b·B这种情况，对项目的右部进行处理，继续求B->·r闭包，因此这是一个递归函数。最终函数以列表的形式返回每个项目集。4、转向函数GO(I,*)的算法构造函数GO，求一个项目集的GO(I,*)。建立字典go存放最终结果，对不是S->a·形式的项目进行讨论，对项目的右部进行处理，将原点后移一位，利用closure函数得到圆点后移得到的项目的项目集，加入go中。直到处理完该项目集的所有项目。5、建立状态及对应的项目集构造函数createDFA，建立状态及对应的项目集。首先，从拓广文法的第一个项目开始，建立初态，定义number存放状态编号，初始值为0。设立字典status存放状态编号及对应的项目集。将初态加入一个队列qu中。每次从qu中取出一个状态，求该状态的项目集的Go(I,*)，再对得到的项目集进行判断，若该项目集是已知的状态，则不做处理，若该项目集是新的状态，则将其加入队列qu中，number加1。每次从qu中取出一个状态重复上述操作，直到队列为空，说明已求得所有状态。6、ACTION子表的构造分两种情况讨论：项目集只有一个项目和项目集不止一个项目。对于第一种情况，再分两种情况，看该项目是否对应了初态，若是，则将*对应为acc，其余终结符对应为error，若不是，则求得该项目去掉圆点之后的产生式的编号i，终结符合*对应为ri。对于项目集不止一个项目的情况，依次对终结符和*寻找在该状态的的GO(I,*)下是否有所对应，有则求得编号对应为Si，没有则对于error。7、GOTO子表的构造对于每个状态的GO(I,*)函数进行遍历，寻找是否有对应的终结符，若有则返回对应的项目集的编号，若没有则返回error。五、实验小结通过本次实验，了解了LR(0)分析表的构造，对于构造过程所需要的一些算法有了深入的了解，通过实际的编写程序代码完成LR(0)分析表的构造，对于程序的编写能力有了一定的提升。在实验过程中，主要对于closure闭包函数的构造以及状态的设置有问题。Closure闭包函数用了递归的结构，因此对于递归的结束条件需要标注清楚。对于状态的建立，需要注意每次通过GO(I,*)得到的新的项目集是否是已经存在的状态，若是则不做处理。对于状态的遍历使用队列来完成，每次新的状态都加入队列中，队列为空说明状态遍历完毕。有一点问题值得注意，由于状态编号的项目集的存储结构使用了字典，字典是无序的结构，因此每次遍历得到的状态编号都不同，程序的每次运行得到的最终LR(0)分析表不唯一。六、1、源代码importcopyimportqueueclassLR:def__init__(self):self.Vn=[]self.Vt=[]self.start=None*开始符号duction=[]*产生式ject=[]*项目self.status={}*存放状态编号及对应的项目集self.goto={}*存放goto表{0:{E:'1',A:'error',B:'error'}}self.action={}*存放action表{0:{a:'S2',b:'S3'}}defsetVn(self):Vn=input('输入非终结符(以空格区分,回车结束):')self.Vn=Vn.split('')defsetVt(self):Vt=input('输入终结符(以空格区分,回车结束):')self.Vt=Vt.split('')defsetS(self):S=input('输入开始符号(以回车结束):')self.start=Sdefsetf(self):*生成产生式n=int(input('输入产生式数目:'))print('输入产生式(以回车区分):')foriinrange(n):f=input()duction.append(f)defProject(self):*建立项目forfinduction:temporary=copy.deepcopy(f)*temporary与f相同temporary=temporary.split('->')l=temporary[0]*产生式左部r=list(temporary[1])*产生式右部foriinrange(len(r)+1):*对产生式右部处理temporary1=copy.deepcopy(r)temporary1.insert(i,'·')newf=l+'->'+''.join(temporary1)ject.append(newf)defclosure(self,pro):*求一个项目pro的闭包E->·E->·bE->b·B返回列表temporary=[]*最终返回的结果temporary.append(pro)*将pro自身加入l1=pro.split('->')[0]*左部r1=pro.split('->')[1]*右部*=list(r1)*存放右部的列表inde*=*.inde*('·')*得到圆点位置iflen(*)==1:*S->·returntemporaryelse:ifinde*==len(r1)-1or*[inde*+1]inself.Vt:*E->·areturntemporaryelse:*E->b·Bforeleminrange(len(ject)):l=ject[elem].split('->')[0]*左部r=ject[elem].split('->')[1]*右部ifl==*[inde*+1]andr.startswith('·'):*继续求B->·r闭包conlist=self.closure(ject[elem])iflen(conlist)==0:passelse:temporary.e*tend(conlist)returntemporarydefGO(self,project):*计算一个项目集的GO(I,*),返回字典形式go={}*存放Go(I,*)结果，形式为{a:[],b:[]}foreleminproject:l=elem.split('->')[0]*项目左部r=elem.split('->')[1]*项目右部inde*=list(r).inde*('·')*返回·的位置ifnotr.endswith('·'):*不是S->a·形式ifgo.get(list(r)[inde*+1])==None:*说明*所对应的go中没有项目temporary=list(r)temporary.insert(inde*+2,'·')temporary.remove('·')*将·后移一位*=l+'->'+''.join(temporary)*产生一个完整的项目go[list(r)[inde*+1]]=self.closure(*)*将该项目对应的项目集加入*的go中else:*说明*所对应的go中已有项目temporary=list(r)temporary.insert(inde*+2,'·')temporary.remove('·')*将·后移一位*=l+'->'+''.join(temporary)*产生一个完整的项目go[list(r)[inde*+1]].e*tend(self.closure(*))returngodefcreateDFA(self):*建立识别活前缀的DFAnumber=0*初始状态编号为0first='S->·'+self.start*初态*=self.closure(first)*初态闭包self.status[number]=*qu=queue.Queue()*构造队列，用于存放得到的状态qu.put({number:self.status[number]})*把初始状态加入队列中number=number+1whilenotqu.empty():*队列不为空，说明状态没有遍历完毕temporary=qu.get()*队列中取出一个状态fork,vintemporary.items():y=self.GO(v)*求项目集的Go(I,*)forkey,valueiny.items():flag=-1*标志位，判断value是否是新的状态forke,vainself.status.items():ifset(va)==set(value):flag=ke*状态已存在，返回状态编号breakifflag==-1:*新的状态，加入状态集中self.status[number]=valuequ.put({number:self.status[number]})else:*已有状态pass*不作处理defGOTO(self):*goto表foriinrange(len(self.status)):self.goto[i]={}temp=self.GO(self.status[i])*每个状态的GOforvninself.Vn:*对非终结符遍历ifvnintemp.keys():*非终结符存在于状态的Go中forkey,valueinself.status.items():ifset(value)==set(temp[vn]):number=key*记录编号breakself.goto[i][vn]=numberelse:self.goto[i][vn]='error'defACTION(self):vt*=copy.deepcopy(self.Vt)vt*.append('*')*终结符加‘*’foriinrange(len(self.status)):self.action[i]={}iflen(self.status[i])==1:*项目集只有一个项目ifself.status[i][0].startswith('S'):*S->E·forvtinself.Vt:self.action[i][vt]='error'self.action[i]['*']='acc'else:*填写rj的项目E->aA·temp=self.status[i][0].rstrip('·')*删去项目的·E->aAforninrange(len(duction)):ifduction[n]==temp:m=n+1*产生式在G'中下标从1开始breakforvtinvt*:self.action[i][vt]='r'+str(m)else:*填写Sj的项目temp=self.GO(self.status[i])*字典形式{a:[],b:[]}forvtinvt*:ifvtintemp.keys():forkey,valueinself.status.items():*确定到哪一个状态ifset(value)==set(temp[vt]):number=key*返回状态编号breakself.action[i][vt]='S'+str(number)else:self.action[i][vt]='error'defoutput(self):*输出LR(0)分析表表格形式print('LR(0)分析表'.center(85))print('状态'.center(5),'ACTION'.center(50),'GOTO'.center(30))print(''.center(10),end='')forvtinself.Vt:*actionprint(vt.center(10),end='')print('*'.center(10),end='')forvninself.Vn:*goto