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

/自动生成LR〔0分析表目录一、实验名称2二、实验目的2三、实验原理21、闭包closure<I>22、转换函数GO<I,X>23、ACTION子表和GOTO子表的构造2四、实验思路31、输入32、建立项目33、closure算法34、转向函数GO<I,X>的算法35、建立状态及对应的项目集36、ACTION子表的构造47、GOTO子表的构造4五、实验小结4六、附件51、源代码52、运行结果截图9一、实验名称自动生成LR〔0分析表二、实验目的1、实现计算闭包函数CLOSURE的算法。2、实现转向函数GO<I,X>的算法。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,X>GO<I,X>=closure<J>其中：I为包含某一项目集的状态。X为一文法符号.X∈Vn∪VtJ={任何形如A->α•Xβ的项目|A->αX•β属于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.Vduction。2、建立项目构造函数Project.根据产生式建立项目.对每一条产生式的右部进行处理.依次在右部的每个终结符和非终结符前添加原点.并在最后添加原点。3、closure算法构造函数closure.求一个项目的闭包closure。分三种情况讨论.对于S->·和E->·a这两种情况.返回自身。对于E->b·B这种情况.对项目的右部进行处理.继续求B->·r闭包.因此这是一个递归函数。最终函数以列表的形式返回每个项目集。4、转向函数GO<I,X>的算法构造函数GO.求一个项目集的GO<I,X>。建立字典go存放最终结果.对不是S->a·形式的项目进行讨论.对项目的右部进行处理.将原点后移一位.利用closure函数得到圆点后移得到的项目的项目集.加入go中。直到处理完该项目集的所有项目。5、建立状态及对应的项目集构造函数createDFA.建立状态及对应的项目集。首先.从拓广文法的第一个项目开始.建立初态.定义number存放状态编号.初始值为0。设立字典status存放状态编号及对应的项目集。将初态加入一个队列qu中。每次从qu中取出一个状态.求该状态的项目集的Go<I,x>.再对得到的项目集进行判断.若该项目集是已知的状态.则不做处理.若该项目集是新的状态.则将其加入队列qu中.number加1。每次从qu中取出一个状态重复上述操作.直到队列为空.说明已求得所有状态。6、ACTION子表的构造分两种情况讨论：项目集只有一个项目和项目集不止一个项目。对于第一种情况.再分两种情况.看该项目是否对应了初态.若是.则将#对应为acc.其余终结符对应为error.若不是.则求得该项目去掉圆点之后的产生式的编号i.终结符合#对应为ri。对于项目集不止一个项目的情况.依次对终结符和#寻找在该状态的的GO<I,X>下是否有所对应.有则求得编号对应为Si.没有则对于error。7、GOTO子表的构造对于每个状态的GO<I,X>函数进行遍历.寻找是否有对应的终结符.若有则返回对应的项目集的编号.若没有则返回error。五、实验小结通过本次实验.了解了LR<0>分析表的构造.对于构造过程所需要的一些算法有了深入的了解.通过实际的编写程序代码完成LR<0>分析表的构造.对于程序的编写能力有了一定的提升。在实验过程中.主要对于closure闭包函数的构造以及状态的设置有问题。Closure闭包函数用了递归的结构.因此对于递归的结束条件需要标注清楚。对于状态的建立.需要注意每次通过GO<I,X>得到的新的项目集是否是已经存在的状态.若是则不做处理。对于状态的遍历使用队列来完成.每次新的状态都加入队列中.队列为空说明状态遍历完毕。有一点问题值得注意.由于状态编号的项目集的存储结构使用了字典.字典是无序的结构.因此每次遍历得到的状态编号都不同.程序的每次运行得到的最终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]#右部x=list<r1>#存放右部的列表index=x.index<'·'>#得到圆点位置iflen<x>==1:#S->·returntemporaryelse:ifindex==len<r1>-1orx[index+1]inself.Vt:#E->·areturntemporaryelse:#E->b·Bforeleminrange<len<ject>>:l=ject[elem].split<'->'>[0]#左部r=ject[elem].split<'->'>[1]#右部ifl==x[index+1]andr.startswith<'·'>:#继续求B->·r闭包conlist=self.closure<ject[elem]>iflen<conlist>==0:passelse:temporary.extend<conlist>returntemporarydefGO<self,project>:#计算一个项目集的GO<I,x>,返回字典形式go={}#存放Go<I,x>结果.形式为{a:[],b:[]}foreleminproject:l=elem.split<'->'>[0]#项目左部r=elem.split<'->'>[1]#项目右部index=list<r>.index<'·'>#返回·的位置ifnotr.endswith<'·'>:#不是S->a·形式ifgo.get<list<r>[index+1]>==None:#说明x所对应的go中没有项目temporary=list<r>temporary.insert<index+2,'·'>temporary.remove<'·'>#将·后移一位x=l+'->'+''.join<temporary>#产生一个完整的项目go[list<r>[index+1]]=self.closure<x>#将该项目对应的项目集加入x的go中else:#说明x所对应的go中已有项目temporary=list<r>temporary.insert<index+2,'·'>temporary.remove<'·'>#将·后移一位x=l+'->'+''.join<temporary>#产生一个完整的项目go[list<r>[index+1]].extend<self.closure<x>>returngodefcreateDFA<self>:#建立识别活前缀的DFAnumber=0#初始状态编号为0first='S->·'+self.start#初态x=self.closure<first>#初态闭包self.status[number]=xqu=queue.Queue<>#构造队列.用于存放得到的状态qu.put<{number:self.status[number]}>#把初始状态加入队列中number=number+1whilenotqu.empty<>:#队列不为空.说明状态没有遍历完毕temporary=qu.get<>#队列中取出一个状态fork,vintemporary.items<>:y=self.GO<v>#求项目集的Go<I,x>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>:vtx=copy.deepcopy<self.Vt>vtx.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开始breakforvtinvtx:self.action[i][vt]='r'+str<m>else:#填写Sj的项目temp=self.GO<self.status[i]>#字典形式{a:[],b:[]}forvtinvtx: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