编译原理实验自动生成LR(0)分析表

1、 自动生成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一、实验(shíyàn)名称自动(zìdòng)生成LR（0）分析(fnx)表二、实验(shíyàn)目的1、实现(shíxi

2、àn)计算闭包函数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直到不出现新的项目为止。即closur

3、e(I)不再扩大。2、转换函数GO(I,X)GO(I,X)=closure(J)其中：I为包含某一项目集的状态。X为一文法符号，XVnVtJ=任何形如A->X的项目|A->X属于I3、ACTION子表和GOTO子表的构造a.若项目(xiàngmù)A.a属于(shyú)Ik且GO (Ik, a)= Ij, a为终结符，则置ACTIONk, a为“把状态(zhuàngtài)j和符号(fúhào)a移进栈”，简记(jin jì)为“sj”； b.若项目A属于Ik，那么，对任何终结符a，置ACTIONk，a

4、为“用产生式A进行规约”，简记为“rj”；其中，假定A为文法G'的第j个产生式c.若项目S'S属于Ik, 则置ACTIONk, #为“接受”，简记为“acc”； d.若GO (Ik, A)= Ij, A为非终结符，则置GOTOk, A=j； e.分析表中凡不能用上述1至4填入信息的空白格均置上“出错标志”。 按上述算法构造的含有ACTION和GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法G的一张LR(0)分析表。具有LR(0)表的文法G称为一个LR（0）文法，LR(0)文法是无二义的。四、实验思路本次实验采用python完成。1、输入构造一个LR类，输入非终结符

5、，终结符，开始符以及产生式分别存于LR类的成员：Vn，Vt，start，production。2、建立项目构造函数Project，根据产生式建立项目，对每一条产生式的右部进行处理，依次在右部的每个终结符和非终结符前添加原点，并在最后添加原点。3、closure算法构造函数closure，求一个项目的闭包closure。分三种情况讨论，对于S->·和E->·a这两种情况，返回自身。对于E->b·B这种情况，对项目的右部进行处理，继续求B->·r闭包，因此这是一个递归函数。最终函数以列表的形式返回每个项目集。4、转向函数GO(I,X)

6、的算法构造函数GO，求一个项目集的GO(I,X)。建立字典go存放最终结果，对不是S->a·形式的项目进行讨论，对项目的右部进行处理，将原点后移一位，利用closure函数得到圆点后移得到的项目的项目集，加入go中。直到处理完该项目集的所有项目。5、建立状态(zhuàngtài)及对应的项目(xiàngmù)集构造函数createDFA，建立状态及对应(duìyìng)的项目集。首先(shuxin)，从拓广文法(wénf)的第一个项目开始，建立初态，定义number存放状态编号，初始值为0。设立字典statu

7、s存放状态编号及对应的项目集。将初态加入一个队列qu中。每次从qu中取出一个状态，求该状态的项目集的Go(I,x)，再对得到的项目集进行判断，若该项目集是已知的状态，则不做处理，若该项目集是新的状态，则将其加入队列qu中，number加1。每次从qu中取出一个状态重复上述操作，直到队列为空，说明已求得所有状态。6、ACTION子表的构造分两种情况讨论：项目集只有一个项目和项目集不止一个项目。对于第一种情况，再分两种情况，看该项目是否对应了初态，若是，则将#对应为acc，其余终结符对应为error，若不是，则求得该项目去掉圆点之后的产生式的编号i，终结符合#对应为ri。对于项目集不止一个项目的情

8、况，依次对终结符和#寻找在该状态的的GO(I,X)下是否有所对应，有则求得编号对应为Si，没有则对于error。7、GOTO子表的构造对于每个状态的GO(I,X)函数进行遍历，寻找是否有对应的终结符，若有则返回对应的项目集的编号，若没有则返回error。五、实验小结通过本次实验，了解了LR(0)分析表的构造，对于构造过程所需要的一些算法有了深入的了解，通过实际的编写程序代码完成LR(0)分析表的构造，对于程序的编写能力有了一定的提升。在实验过程中，主要对于closure闭包函数的构造以及状态的设置有问题。Closure闭包函数用了递归的结构，因此对于递归的结束条件需要标注清楚。对于状态的建立，

9、需要注意每次通过GO(I,X)得到的新的项目集是否是已经存在的状态，若是则不做处理。对于状态的遍历使用队列来完成，每次新的状态都加入队列中，队列为空说明状态遍历完毕。有一点问题值得注意，由于状态编号的项目集的存储结构使用了字典，字典是无序的结构，因此每次遍历得到的状态编号都不同，程序的每次运行得到的最终LR(0)分析表不唯一。六、附件(fùjiàn)1、源代码import copyimport queueclass LR: def _init_(self): self.Vn = self.Vt = self.start = None # 开始符号 ducti

10、on = # 产生(chnshng)式 ject = # 项目(xiàngmù) self.status = # 存放状态(zhuàngtài)编号及对应的项目集 self.goto = # 存放(cúnfàng)goto表 0:E:'1',A:'error',B:'error' self.action = # 存放action表 0:a:'S2',b:'S3' def setVn(self): Vn = input('输入非终结符

11、(以空格区分, 回车结束):') self.Vn = Vn.split(' ') def setVt(self): Vt = input('输入终结符(以空格区分, 回车结束):') self.Vt = Vt.split(' ') def setS(self): S = input('输入开始符号(以回车结束):') self.start = S def setf(self): # 生成产生式 n = int(input('输入产生式数目:') print('输入产生式(以回车区分):')

12、for i in range(n): f = input() duction.append(f) def Project(self): # 建立(jiànlì)项目 for f in duction: temporary = copy.deepcopy(f) # temporary与f相同(xin tón) temporary = temporary.split('->') l = temporary0 # 产生(chnshng)式左部 r = list(temporary1) # 产生(chnshng)式右部

13、 for i in range(len(r)+1): # 对产生(chnshng)式右部处理 temporary1 = copy.deepcopy(r) temporary1.insert(i,'·') newf = l+'->'+''.join(temporary1) ject.append(newf) def closure(self, pro): # 求一个项目pro的闭包 E->· E->·b E->b·B 返回列表 temporary = # 最终返回的结果

14、 temporary.append(pro) # 将pro自身加入 l1 = pro.split('->')0 # 左部 r1 = pro.split('->')1 # 右部 x = list(r1) # 存放右部的列表 index = x.index('·') # 得到圆点位置 if len(x) = 1: # S->· return temporary else: if index = len(r1)-1 or xindex+1 in self.Vt: #E->·a return temp

15、orary else: # E->b·B for elem in range(len(ject): l = jectelem.split('->')0 # 左部 r = jectelem.split('->')1 # 右部 if l = xindex+1 and r.startswith('·'): # 继续求B->·r闭包 conlist = self.closure(jectelem) if len(conlist) = 0:

16、 pass else: temporary.extend(conlist) return temporary def GO(self, project): # 计算一个项目集的GO(I,x),返回字典形式 go = # 存放Go(I,x)结果，形式为a:,b: for elem in project: l = elem.split('->')0 # 项目左部 r = elem.split('->')1 # 项目右部 index = list(r).index('·') # 返回·的位置 if not r.endsw

17、ith('·'): # 不是S->a·形式 if go.get(list(r)index+1) = None: # 说明x所对应的go中没有项目 temporary = list(r) temporary.insert(index+2, '·') temporary.remove('·') # 将·后移一位 x = l+'->'+''.join(temporary) # 产生一个(y è)完整的项目 golist(r)index+1 = sel

18、f.closure(x) # 将该项目(xiàngmù)对应的项目集加入(jirù)x的go中 else: # 说明(shumíng)x所对应(duìyìng)的go中已有项目 temporary = list(r) temporary.insert(index+2,'·') temporary.remove('·') # 将·后移一位 x = l+'->'+''.join(temporary) # 产生一个完整的项目 golist(r

19、)index+1.extend(self.closure(x) return go def createDFA(self): # 建立识别活前缀的DFA number = 0 # 初始状态编号为0 first = 'S->·'+self.start # 初态 x = self.closure(first) # 初态闭包 self.statusnumber = x qu = queue.Queue() # 构造队列，用于存放得到的状态 qu.put(number:self.statusnumber) # 把初始状态加入队列中 number = number+1 w

20、hile not qu.empty(): # 队列不为空，说明状态没有遍历完毕 temporary = qu.get() # 队列中取出一个状态 for k, v in temporary.items(): y = self.GO(v) # 求项目集的Go(I,x) for key, value in y.items(): flag = -1 # 标志位，判断value是否是新的状态 for ke, va in self.status.items(): if set(va) = set(value): flag = ke # 状态已存在，返回状态编号 break if flag = -1: #

21、 新的状态，加入状态集中 self.statusnumber = value qu.put(number:self.statusnumber) else: # 已有状态 pass # 不作处理 def GOTO(self): # goto表 for i in range(len(self.status): self.gotoi = temp = self.GO(self.statusi) # 每个状态的GO for vn in self.Vn: # 对非终结符遍历 if vn in temp.keys(): # 非终结符存在于状态的Go中 for key, value in self.stat

22、us.items(): if set(value) = set(tempvn): number = key # 记录(jìlù)编号 break self.gotoivn = number else: self.gotoivn = 'error' def ACTION(self): vtx = copy.deepcopy(self.Vt) vtx.append('#') # 终结符加# for i in range(len(self.status): self.actioni = if len(self.statusi) = 1: # 项目集

23、只有(zhyu)一个项目 if self.statusi0.startswith('S'): # S->E· for vt in self.Vt: self.actionivt = 'error' self.actioni'#' = 'acc' else: # 填写(tiánxi)rj的项目(xiàngmù) E->aA· temp = self.statusi0.rstrip('·') # 删去(shn qù)项目的· E

24、->aA for n in range(len(duction): if ductionn = temp: m = n+1 # 产生式在G'中下标从1开始 break for vt in vtx: self.actionivt = 'r'+str(m) else: # 填写Sj的项目 temp = self.GO(self.statusi) # 字典形式a:,b: for vt in vtx: if vt in temp.keys(): for key, value in self.status.items(): # 确定到哪一个状

25、态 if set(value) = set(tempvt): number = key # 返回状态编号 break self.actionivt = 'S'+str(number) else: self.actionivt = 'error' def output(self): # 输出LR(0)分析表 表格形式 print('LR(0)分析表'.center(85) print('状态'.center(5), 'ACTION'.center(50), 'GOTO'.center(30) print(' '.center(10),end='') for vt in self.Vt: # action print(vt.center(10),end='') print('#'.center(10),end='