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

2016.12.14
自动生成LR（0）分析表

目录
一、实验名称 2
二、实验目的 2
三、实验原理 2
1、闭包closure(I) 2
2、转换函数GO(I,X) 2
3、ACTION子表和GOTO子表的构造 2
四、实验思路 3
1、输入 3
2、建立项目 3
3、closure算法 3
4、转向函数GO(I,X)的算法 3
5、建立状态及对应的项目集 3
6、ACTION子表的构造 4
7、GOTO子表的构造 4
五、实验小结 4
六、附件 5
1、源代码 5
2、运行结果截图 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∪Vt
J={任何形如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，Vt，start，production。
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、源代码
import copy
import queue
class LR:
def __init__(self):
self.Vn = []
self.Vt = []
self.start = None # 开始符号
self.production = [] # 产生式
self.project = [] # 项目
self.status = {} # 存放状态编号及对应的项目集
self.goto = {} # 存放goto表 {0:{E:'1',A:'error',B:'error'}}
self.action = {} # 存放action表 {0:{a:'S2',b:'S3'}}
def setVn(self):
Vn = input('输入非终结符(以空格区分, 回车结束):')
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('输入产生式(以回车区分):')
for i in range(n):
f = input()
self.production.append(f)

def Project(self): # 建立项目
for f in self.production:
temporary = copy.deepcopy(f) # temporary与f相同
temporary = temporary.split('->')
l = temporary[0] # 产生式左部
r = list(temporary[1]) # 产生式右部
for i in range(len(r)+1): # 对产生式右部处理
temporary1 = copy.deepcopy(r)
temporary1.insert(i,'·')
newf = l+'->'+''.join(temporary1)
self.project.append(newf)

def closure(self, pro): # 求一个项目pro的闭包 E->· E->·b E->b·B 返回列表
temporary = [] # 最终返回的结果
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 x[index+1] in self.Vt: #E->·a
return temporary
else: # E->b·B
for elem in range(len(self.project)):
l = self.project[elem].split('->')[0] # 左部
r = self.project[elem].split('->')[1] # 右部
if l == x[index+1] and r.startswith('·'): # 继续求B->·r闭包
conlist = self.closure(self.project[elem])
if len(conlist) == 0:
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.endswith('·'): # 不是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) # 产生一个完整的项目
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))
return go

def createDFA(self): # 建立识别活前缀的DFA
number = 0 # 初始状态编号为0
first = 'S->·'+self.start # 初态
x = self.closure(first) # 初态闭包
self.status[number] = x
qu = queue.Queue() # 构造队列，用于存放得到的状态
qu.put({number:self.status[number]}) # 把初始状态加入队列中
number = number+1
while 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: # 新的状态，加入状态集中
self.status[number] = value
qu.put({number:self.status[number]})
else: # 已有状态
pass # 不作处理

def GOTO(self): # goto表
for i in range(len(self.status)):
self.goto[i] = {}
temp = self.GO(self.status[i]) # 每个状态的GO
for vn in self.Vn: # 对非终结符遍历
if vn in temp.keys(): # 非终结符存在于状态的Go中
for key, value in self.status.items():
if set(value) == set(temp[vn]):
number = key # 记录编号
break
self.goto[i][vn] = number
else:
self.goto[i][vn] = 'error'

def ACTION(self):
vtx = copy.deepcopy(self.Vt)
vtx.append('#') # 终结符加‘#’
for i in range(len(self.status)):
self.action[i] = {}
if len(self.status[i]) == 1: # 项目集只有一个项目
if self.status[i][0].startswith('S'): # S->E·
for vt in self.Vt:
self.action[i][vt] = 'error'
self.action[i]['#'] = 'acc'
else: # 填写rj的项目 E->aA·
temp = self.status[i][0].rstrip('·') # 删去项目的· E->aA
for n in range(len(self.production)):
if self.production[n] == temp:
m = n+1 # 产生式在G'中下标从1开始
break
for vt in vtx:
self.action[i][vt] = 'r'+str(m)
else: # 填写Sj的项目
temp = self.GO(self.status[i]) # 字典形式{a:[],b:[]}
for vt in vtx:
if vt in temp.keys():
for key, value in self.status.items(): # 确定到哪一个状态
if set(value) == set(temp[vt]):
number = key # 返回状态编号
break
self.action[i][vt] = 'S'+str(number)
else:
self.action[i][vt] = '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='')
for vn in self.Vn: # goto
print(vn.center(10),end='')
print() # 换行
vtx = copy.deepcopy(self.Vt)
vtx.append('#')
for i in range(len(self.status)): # 输出每一行
print(str(i).center(10),end='')
for vt in vtx:
for key in self.action[i]: # {0:{'b':'S1'}}
if vt == key:
print(self.action[i][key].center(10),end='')
break
for vn in self.Vn:
for key in self.goto[i]:
if vn == key:
print(str(self.goto[i][key]).center(10),end='')
break
print() # 换行

def show(self): # 显示各个状态及对应的项目集
print('所有状态及对应的项目集:')
for key, value in self.status.items():
print(key, value)

if __name__ == '__main__':
print('E21414020 陈国柱')
a = LR()
a.setVn()
a.setVt()
a.setS()
a.setf()
a.Project()
a.createDFA()
a.ACTION()
a.GOTO()
a.show()
a.output()
2、运行结果截图

11