一、试验名称
主动生成 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__':
a = LR()
a.setVn()
a.setVt()
a.setS()
a.setf()
a.Project()
a.createDFA()
a.ACTION()
a.GOTO()
a.show()
a.output()2、程序运行后果
语法分析表 /1.png)
语法分析表 /2.png)