(完整word版)编译原理实验LL(1)文法的判断及转换(word文档良心出品)

1、2016.11.30LL(1 文法的判断及转换1目录一、实验名称 .2二、实验目的 .2三、实验原理 .21、First集定义 .22、Follow集定义 .23、Select集定义 .34、含左递归文法 .3四、实验思路 .31、求非终结符是否能导出空 .32、求First集算法 .33、求Follow集算法 .34、求Select集算法 .4五、实验小结 .4六、附件 .41、源代码 .42、运行结果截图 .102、实验名称LL(1 文法的判断及转换二、 实验目的输入：任意一个文法输出：(1)是否为 LL(1)文法(2) 若是，给出每条产生式的 select 集(3) 若不是， 看看是否含

2、有左公共因子或者含有左递归， 并用相应的方 法将非 LL(1 文法变成 LL(1 文法，并输出新文法中每条产生式的 select 集。三、 实验原理1、First集定义令 X 为一个文法符号(终止符或非终止符)或,则集合First (X)有终止符组成，此外可能还有&，它的定义如下：1. 若 X 是终止符或&，则 First (X) =X。2. 若 X是非终结符， 则对于每个产生式 X X1X2Xn, First (X)包含了 First (X1)- 。若对于某个 iaAY，贝 U First (丫)- 在 Follow (A)中。3. 若存在产生式 B aAY，且&在

3、First ( 丫)中，贝 U Follow (A)包括 FollowB)3、Select集定义3对于产生式 A a。集合 select (A a)定义如下：1.若a不能推出&，则 select (A a)= first (a)2.若a能推出 则 select(Aa)= first(a)Ufollow(A)。4、 含左递归文法一个文法 G,若存在 P 经过一次或多次推导得到 Pa (即能推导出以 P 开头的 式子)，则称 G 是左递归的。左递归分为直接左递归和间接左递归。直接左递归经过一次推导就可以看出文法存在左递归，如i Pa| b。间接左递归侧需多次推导才可以看出文法存在左递归，如

4、文法：STQc I c,Q Rb | b,RTSa I a 有 S =Qc =Rbc =Sabc四、实验思路本次实验采用 python 完成。1、 求非终结符是否能导出空a. 第一轮扫描。当前的产生式还没被删除，非终结符 lp 可以导出空，将以 该非终结符为左部的产生式标记为要删除的。 产生式右部分解， 若该产生式右部 包含终结符， 删除该产生式因为由它不会导出空。 判断没有被删除的产生式中是 否还有以该非终结符为左部的产生式。b. 第二轮扫描。 逐一扫描每一条产生右部的每一个符号， 循化直至每个非终 结符的状态都确定下来。2、 求First集算法存储每一个非终结符对应的 First 集，扫描

5、每一条产生式，记录每一轮扫描是 每个非终结符 First 集是否增大过。全部初始化为没有增大的状态，对于课本的 五种类型依次求解，每次将结果加入对应的集合中，若一次扫描First 集没有增大，则说明循环结束。3、求Follow集算法存储每一个非终结符对应的 Follow 集，将#加入文法的开始符号的 Follow 集4合中，记录每一轮扫描是每个非终结符 Follow 集合是否增大过，全部初始化为 没有增大的状态，扫描每一条产生式的右部，扫描到非终结符,判断在该非终结符之后的子串能否推导空，若该符号串可以推导出空，还要将 Follow(lp)加入到里面。4、求Select集算法初始化每条产生式对

6、应的 Select 集合为空，若产生式右部不能推导出空，贝 U 将右部的 First 集加入 Select 集，如果可以推出空，则需要同时将左部的Follow集合右部的 First 集去掉空的部分加入 Select 集。五、 实验小结通过本次实验，知道了如何判断一个文法是不是 L(L 1)文法，同时对于 First、Follow 以及 Select 集的求解原理变得更加熟悉，并且知道了如何用计算机语言求 解First，Follow 以及 Select 集。不足之处是，没有完成判断文法是否为左递归文 法以及左递归文法的转换部分。六、 附件1、源代码class Gw: def _init_(sel

7、f): with open(Gw.txt) as f: content = f.readlines() content =line.strip() for line in content self.Vn = content0.split( ) self.Vt = content1.split( )self.start = content2 duce = self.left = self.right = for i in range(3,len(content): duce.append(contenti)self.left.append(contenti.spl

8、it(-)0)self.right.append(contenti.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)5def canEmpty(self):self.isEmpty = dict()for i in range(len(self.Vn):self.isEmptyself.Vni =-1 print(self.isEmpty

9、) temp = duce:deleteIndex= pointer = 0 while pointer)0rp = temppointer.split( -)1if rp=!:self.isEmptylp = 1for i in range(len(temp):if tempi.split(-)0=lp and i not in deleteIndex:deleteIndex.append(i)l = list(rp)isContainVt = i in self.Vt for i in lif True in isContainVt:deleteIndex.append(p

10、ointer)for k in range(len(temp):if k not in deleteIndex:if tempk . s p l i t ( - )0=l p :breakelse:self.isEmptylp = 0pointer = pointer+1while -1 in self.isEmpty.values():for i in range(len(temp):if i not in deleteIndex:lp = tempi.split(-)0rp = tempi.split(-)1rlsit = list(rp)for j in range(len(rlsit)

11、:if self.isEmptyrlsitj=1:if j=len(rlsit)-1: self.isEmptylp=1elif self.isEmptyrlsitj=0: deleteIndex.append(i) for kin range(len(temp): if k not in deleteIndex:if tempk.split( -)0=lp: breakelse: self.isEmptylp = 0else: continue def show(self):print( 非终结符能否推导出空的信息 :)for v in self.Vn:if self.isEmptyv=1:

12、yon = 是 else:yon = 否 6print(%s:%s%(v,yon)def getFirst(self):self.First = dict()for i in self.Vn:self.Firsti = list()isChange = dict()while True:for k in self.Vn: isChangek = 0for i in range(len(duce):lp = ducei.split(-)0rp = ducei.split(-)1rlist = list(rp)if rlist0=! or rlist

13、0 in self.Vt:if rlist0 not in self.Firstlp: self.Firstlp.append(rlist0)isChangelp=1 else:for j in rlist:if j in self.Vn:if self.isEmptyj=1: oldsize = len(self.Firstlp)templist = self.Firstj: if ! in templist:templist.remove(!) for x in templist: if x not inself.Firstlp: self.Firstlp.append(x)if rp.e

14、ndswith(j) and ! not in self.Firstlp:self.Firstlp.append(!)newsize = len(self.Firstlp)if oldsize!=newsize: isChangelp=1 else:oldsize = len(self.Firstlp)if j in self.Vn:templist = self.Firstj: for x in templist: ifx not in self.Firstlp: self.Firstlp.append(x)else:if j not in self.Firstlp:self.Firstlp

15、.append(x) newsize =len(self.Firstlp) if oldsize!=newsize:isChangelp=1 breakif 1 not in isChange.values(): print(First 集合不在增大 !) breakelse: print(First 集合有增大 !) passdef showFirst(self):print(First 集合信息 :)for v in self.Vn:print(v,self.Firstv)def canCauseEmpty(self,plist):7first = list()if len(plist)=

16、0:first.append(!)else:for i in plist:if i in self.Vn:if self.isEmptyi=1:t = self.Firsti: if ! in t: t.remove(!) for k in t: if k not infirst: first.append(k)if .join(plist).endswith(i) and ! not in first: first.append(!)else:for k in self.Firsti: if k not in first: first.append(k) breakelse: if i no

17、t in first: first.append(i) break return firstdef getFollow(self):self.Follow = dict()for i in self.Vn: self.Followi = list() self.Followself.start.append(#)isChange = dict() while True:for k in self.Vn: isChangek = 0 for i in range(len(duce): lp =ducei.split(-)0 rp = ducei.s

18、plit(-)1 rlist = list(rp)for j in range(len(rlist): if rlistj in self.Vn:reslist = self.canCauseEmpty(rlistj+1:) if ! in reslist:oldsize = len(self.Followrlistj) for y inself.Followlp: if y not in self.Followrlistj:self.Followrlistj.append(y) newsize =len(self.Followrlistj) if oldsize!=newsize:isCha

19、ngerlistj = 1else:passoldsize = len(self.Followrlistj) for x in reslist:if x!=! and x not in self.Followrlistj:self.Followrlistj.append(x) newsize =len(self.Followrlistj) if oldsize!=newsize:isChangerlistj = 1if 1 not in isChange.values():breakdef showFollow(self):print(Follow 集合信息 :)for key in self

20、.Vn:print(key,self.Followkey)def getSelect(self):self.Select = dict()8for i in duce:self.Selecti = list()for i in range(len(duce):lp = ducei.split(-)0rp = ducei.split(-)1rlist = list(rp)if rlist0=!:for v in self.Followlp:if v not in self.Sducei:self.Selec

21、ducei.append(v) elif rlist0 in self.Vt:self.Sducei.append(rlist0) else:res = self.canCauseEmpty(rlist)if ! not in res:for v in res:if v not in self.Sducei:self.Sducei.append(v) else:for v in res:if v not in self.Sducei and v!=!:self.Select

22、ducei.append(v) for v in self.Followlp:if v not in self.Sducei:self.Sducei.append(v)def showSelect(self): print(Select 集合信息 :) for key in duce:print(key,self.Selectkey)def isLLone(self):isright = for k in self.Vn: tset = set() tset.add(#) tset = tset | set(self.Vt) for l,r inzip(self.left,self.right): if k=l: