一、试验名称
LL(1) 文法的判断及转换
二、试验目标
输出：任意一个文法
输入：(1) 是否为 LL(1) 文法
(2) 若是，给出每条产生式的 select 集
(3) 若不是，看看是否含有左公共因子或者含有左递归，并用相应的办法将非 LL(1) 文法变成 LL(1) 文法，并输入新文法中每条产生式的 select 集。
三、试验原理
1、First 集定义
令 X 为一个文法符号（终止符或非终止符）或 ε，则汇合 First（X）有终止符组成，此外可能还有 ε，它的定义如下：
\1. 若 X 是终止符或 ε，则 First（X）= {X}。
\2. 若 X 是非终结符，则对于每个产生式 X—>X1X2…Xn，First（X）蕴含了 First（X1）-{ε}。若对于某个 i < n，所有的汇合 First（X1），…，First（Xi）都蕴含了 ε，则 First（X）也包 括了 First（Xi+1）- {ε}。若所有汇合 First（X1），…，First（Xn）都包含了 ε，则 First（X）也包含了 ε。
2、Follow 集定义
给出一个非终结符 A，那么汇合 Follow（A）则是由终结符组成，此外可能还含有 #（# 是题目约定的字符串结束符）。汇合 Follow（A）的定义如下：
\1. 若 A 是开始符号，则 #在 Follow（A）中。
\2. 若存在产生式 B—>αAγ，则 First（γ）- {ε} 在 Follow（A）中。
\3. 若存在产生式 B—>αAγ，且 ε 在 First（γ）中，则 Follow（A）包含 Follow（B）。
3、Select 集定义
对于产生式 A—>α。汇合 select（A—>α）定义如下：
\1. 若 α 不能推出 ε，则 select（A—>α）= first（α）。
\2. 若 α 能推出 ε，则 select（A—>α）= first（α）∪ follow(A)。
4、含左递归文法
一个文法 G，若存在 P 通过一次或屡次推导失去 Pa（即能推导出以 P 结尾的式子），则称 G 是左递归的。
左递归分为间接左递归和间接左递归。
间接左递归通过一次推导就能够看出文法存在左递归，如 P→Pa|b。
间接左递归侧需屡次推导才能够看出文法存在左递归，如文法：S→Qc|c，Q→Rb|b，R→Sa|a 有 S =>Qc =>Rbc =>Sabc
四、试验思路
本次试验采纳 python 实现。
1、求非终结符是否能导出空
a. 第一轮扫描。以后的产生式还没被删除，非终结符 lp 能够导出空，将以该非终结符为左部的产生式标记为要删除的。产生式右局部解，若该产生式右部蕴含终结符，删除该产生式因为由它不会导出空。判断没有被删除的产生式中是否还有以该非终结符为左部的产生式。
b. 第二轮扫描。逐个扫描每一条产生右部的每一个符号，循化直至每个非终结符的状态都确定下来。
2、求 First 集算法
存储每一个非终结符对应的 First 集，扫描每一条产生式，记录每一轮扫描是每个非终结符 First 集是否增大过。全副初始化为没有增大的状态，对于课本的五种类型顺次求解，每次将后果退出对应的汇合中，若一次扫描 First 集没有增大，则阐明循环完结。
3、求 Follow 集算法
存储每一个非终结符对应的 Follow 集，将 ’#’ 退出文法的开始符号的 Follow 汇合中，记录每一轮扫描是每个非终结符 Follow 汇合是否增大过，全副初始化为没有增大的状态，扫描每一条产生式的右部，扫描到非终结符, 判断在该非终结符之后的子串是否推导空，若该符号串能够推导出空, 还要将 Follow(lp) 退出到外面。
4、求 Select 集算法
初始化每条产生式对应的 Select 汇合为空，若产生式右部不能推导出空，则将右部的 First 集退出 Select 集，如果能够推出空，则须要同时将左部的 Follow 汇合右部的 First 集去掉空的局部退出 Select 集。
五、试验小结
通过本次试验，晓得了如何判断一个文法是不是 LL（1）文法，同时对于 First、Follow 以及 Select 集的求解原理变得更加相熟，并且晓得了如何用计算机语言求解 First，Follow 以及 Select 集。不足之处是，没有实现判断文法是否为左递归文法以及左递归文法的转换局部。
六、附件
1、源代码
class Gw:
def __init__(self):
with open('D:\\test\\Gw.txt') as f:
content = f.readlines()
content = [line.strip() for line in content]
self.Vn = content[0].split(' ')
self.Vt = content[1].split(' ')
self.start = content[2]
self.produce = []
self.left = []
self.right = []
for i in range(3,len(content)):
self.produce.append(content[i])
self.left.append(content[i].split('->')[0])
self.right.append(content[i].split('->')[1])
def showGw(self):
print('非终结符:',self.Vn)
print('终 结 符:',self.Vt)
print('开始符号:',self.start)
print('产生式如下:')
for l,r in zip(self.left,self.right):
print(l+'->'+r)
def canEmpty(self):
self.isEmpty = dict()
for i in range(len(self.Vn)):
self.isEmpty[self.Vn[i]] = -1
print(self.isEmpty)
temp = self.produce[::]
deleteIndex=[]
pointer = 0
while pointer<len(temp):
if pointer not in deleteIndex:
lp = temp[pointer].split('->')[0]
rp = temp[pointer].split('->')[1]
if rp=='!':
self.isEmpty[lp] = 1
for i in range(len(temp)):
if temp[i].split('->')[0]==lp and i not in deleteIndex:
deleteIndex.append(i)
l = list(rp)
isContainVt = [i in self.Vt for i in l]
if True in isContainVt:
deleteIndex.append(pointer)
for k in range(len(temp)):
if k not in deleteIndex:
if temp[k].split('->')[0]==lp:
break
else:
self.isEmpty[lp] = 0
pointer = pointer+1
while -1 in self.isEmpty.values():
for i in range(len(temp)):
if i not in deleteIndex:
lp = temp[i].split('->')[0]
rp = temp[i].split('->')[1]
rlsit = list(rp)
for j in range(len(rlsit)):
if self.isEmpty[rlsit[j]]==1:
if j==len(rlsit)-1:
self.isEmpty[lp]=1
elif self.isEmpty[rlsit[j]]==0:
deleteIndex.append(i)
for k in range(len(temp)):
if k not in deleteIndex:
if temp[k].split('->')[0]==lp:
break
else:
self.isEmpty[lp] = 0
else:
continue
def show(self):
print('非终结符是否推导出空的信息:')
for v in self.Vn:
if self.isEmpty[v]==1:
yon = '是'
else:
yon = '否'
print('%s:%s'%(v,yon))
def getFirst(self):
self.First = dict()
for i in self.Vn:
self.First[i] = list()
isChange = dict()
while True:
for k in self.Vn:
isChange[k] = 0
for i in range(len(self.produce)):
lp = self.produce[i].split('->')[0]
rp = self.produce[i].split('->')[1]
rlist = list(rp)
if rlist[0]=='!' or rlist[0] in self.Vt:
if rlist[0] not in self.First[lp]:
self.First[lp].append(rlist[0])
isChange[lp]=1
else:
for j in rlist:
if j in self.Vn:
if self.isEmpty[j]==1:
oldsize = len(self.First[lp])
templist = self.First[j][::]
if '!' in templist:
templist.remove('!')
for x in templist:
if x not in self.First[lp]:
self.First[lp].append(x)
if rp.endswith(j) and '!' not in self.First[lp]:
self.First[lp].append('!')
newsize = len(self.First[lp])
if oldsize!=newsize:
isChange[lp]=1
else:
oldsize = len(self.First[lp])
if j in self.Vn:
templist = self.First[j][::]
for x in templist:
if x not in self.First[lp]:
self.First[lp].append(x)
else:
if j not in self.First[lp]:
self.First[lp].append(x)
newsize = len(self.First[lp])
if oldsize!=newsize:
isChange[lp]=1
break
if 1 not in isChange.values():
print('First 汇合不再增大!')
break
else:
print('First 汇合有增大!')
pass
def showFirst(self):
print('First 汇合信息:')
for v in self.Vn:
print(v,self.First[v])
def canCauseEmpty(self,plist):
first = list()
if len(plist)==0:
first.append('!')
else:
for i in plist:
if i in self.Vn:
if self.isEmpty[i]==1:
t = self.First[i][::]
if '!' in t:
t.remove('!')
for k in t:
if k not in first:
first.append(k)
if ''.join(plist).endswith(i) and'!' not in first:
first.append('!')
else:
for k in self.First[i]:
if k not in first:
first.append(k)
break
else:
if i not in first:
first.append(i)
break
return first
def getFollow(self):
self.Follow = dict()
for i in self.Vn:
self.Follow[i] = list()
self.Follow[self.start].append('#')
isChange = dict()
while True:
for k in self.Vn:
isChange[k] = 0
for i in range(len(self.produce)):
lp = self.produce[i].split('->')[0]
rp = self.produce[i].split('->')[1]
rlist = list(rp)
for j in range(len(rlist)):
if rlist[j] in self.Vn:
reslist = self.canCauseEmpty(rlist[j+1::])
if '!' in reslist:
oldsize = len(self.Follow[rlist[j]])
for y in self.Follow[lp]:
if y not in self.Follow[rlist[j]]:
self.Follow[rlist[j]].append(y)
newsize = len(self.Follow[rlist[j]])
if oldsize!=newsize:
isChange[rlist[j]] = 1
else:
pass
oldsize = len(self.Follow[rlist[j]])
for x in reslist:
if x!='!' and x not in self.Follow[rlist[j]]:
self.Follow[rlist[j]].append(x)
newsize = len(self.Follow[rlist[j]])
if oldsize!=newsize:
isChange[rlist[j]] = 1
if 1 not in isChange.values():
break
def showFollow(self):
print('Follow 汇合信息:')
for key in self.Vn:
print(key,self.Follow[key])
def getSelect(self):
self.Select = dict()
for i in self.produce:
self.Select[i] = list()
for i in range(len(self.produce)):
lp = self.produce[i].split('->')[0]
rp = self.produce[i].split('->')[1]
rlist = list(rp)
if rlist[0]=='!':
for v in self.Follow[lp]:
if v not in self.Select[self.produce[i]]:
self.Select[self.produce[i]].append(v)
elif rlist[0] in self.Vt:
self.Select[self.produce[i]].append(rlist[0])
else:
res = self.canCauseEmpty(rlist)
if '!' not in res:
for v in res:
if v not in self.Select[self.produce[i]]:
self.Select[self.produce[i]].append(v)
else:
for v in res:
if v not in self.Select[self.produce[i]] and v!='!':
self.Select[self.produce[i]].append(v)
for v in self.Follow[lp]:
if v not in self.Select[self.produce[i]]:
self.Select[self.produce[i]].append(v)
def showSelect(self):
print('Select 汇合信息:')
for key in self.produce:
print(key,self.Select[key])
def isLLone(self):
isright = []
for k in self.Vn:
tset = set()
tset.add('#')
tset = tset | set(self.Vt)
for l,r in zip(self.left,self.right):
if k==l:
p = l+'->'+r
tset = tset & set(self.Select[p])
if len(tset)==0:
isright.append(1)
else:
isright.append(0)
if 0 in isright:
print('不是 LL(1) 文法!')
self.isll1 = False
else:
print('是 LL(1) 文法!')
self.isll1 = True
print(isright)
if __name__=='__main__':
w = Gw()
#w.showGw() #文件中读到的内容
w.canEmpty()
w.show()
w.getFirst()
w.showFirst()
w.getFollow()
#res = w.canCauseEmpty(['A','D'])
#print('res=',res)
w.showFollow()
w.getSelect()
w.showSelect()
w.isLLone()2、运行后果截图
输出：
文法的判断及转换 /2.png)
输入：
文法的判断及转换 /1.png)