一、试验名称
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)