(完整word版)編譯原理實(shí)驗(yàn)LL(1)文法的判斷及轉(zhuǎn)換(word文檔良心出品)

1、2016.11.30LL(1 文法的判斷及轉(zhuǎn)換1目錄一、實(shí)驗(yàn)名稱 .2二、實(shí)驗(yàn)?zāi)康?.2三、實(shí)驗(yàn)原理 .21、First集定義 .22、Follow集定義 .23、Select集定義 .34、含左遞歸文法 .3四、實(shí)驗(yàn)思路 .31、求非終結(jié)符是否能導(dǎo)出空 .32、求First集算法 .33、求Follow集算法 .34、求Select集算法 .4五、實(shí)驗(yàn)小結(jié) .4六、附件 .41、源代碼 .42、運(yùn)行結(jié)果截圖 .102、實(shí)驗(yàn)名稱LL(1 文法的判斷及轉(zhuǎn)換二、 實(shí)驗(yàn)?zāi)康妮斎耄喝我庖粋€(gè)文法輸出：(1)是否為 LL(1)文法(2) 若是，給出每條產(chǎn)生式的 select 集(3) 若不是， 看看是否含

2、有左公共因子或者含有左遞歸， 并用相應(yīng)的方 法將非 LL(1 文法變成 LL(1 文法，并輸出新文法中每條產(chǎn)生式的 select 集。三、 實(shí)驗(yàn)原理1、First集定義令 X 為一個(gè)文法符號(hào)(終止符或非終止符)或,則集合First (X)有終止符組成，此外可能還有&，它的定義如下：1. 若 X 是終止符或&，則 First (X) =X。2. 若 X是非終結(jié)符， 則對(duì)于每個(gè)產(chǎn)生式 X X1X2Xn, First (X)包含了 First (X1)- 。若對(duì)于某個(gè) iaAY，貝 U First (丫)- 在 Follow (A)中。3. 若存在產(chǎn)生式 B aAY，且&在

3、First ( 丫)中，貝 U Follow (A)包括 FollowB)3、Select集定義3對(duì)于產(chǎn)生式 A a。集合 select (A a)定義如下：1.若a不能推出&，則 select (A a)= first (a)2.若a能推出 則 select(Aa)= first(a)Ufollow(A)。4、 含左遞歸文法一個(gè)文法 G,若存在 P 經(jīng)過(guò)一次或多次推導(dǎo)得到 Pa (即能推導(dǎo)出以 P 開頭的 式子)，則稱 G 是左遞歸的。左遞歸分為直接左遞歸和間接左遞歸。直接左遞歸經(jīng)過(guò)一次推導(dǎo)就可以看出文法存在左遞歸，如i Pa| b。間接左遞歸側(cè)需多次推導(dǎo)才可以看出文法存在左遞歸，如

4、文法：STQc I c,Q Rb | b,RTSa I a 有 S =Qc =Rbc =Sabc四、實(shí)驗(yàn)思路本次實(shí)驗(yàn)采用 python 完成。1、 求非終結(jié)符是否能導(dǎo)出空a. 第一輪掃描。當(dāng)前的產(chǎn)生式還沒(méi)被刪除，非終結(jié)符 lp 可以導(dǎo)出空，將以 該非終結(jié)符為左部的產(chǎn)生式標(biāo)記為要?jiǎng)h除的。 產(chǎn)生式右部分解， 若該產(chǎn)生式右部 包含終結(jié)符， 刪除該產(chǎn)生式因?yàn)橛伤粫?huì)導(dǎo)出空。 判斷沒(méi)有被刪除的產(chǎn)生式中是 否還有以該非終結(jié)符為左部的產(chǎn)生式。b. 第二輪掃描。 逐一掃描每一條產(chǎn)生右部的每一個(gè)符號(hào)， 循化直至每個(gè)非終 結(jié)符的狀態(tài)都確定下來(lái)。2、 求First集算法存儲(chǔ)每一個(gè)非終結(jié)符對(duì)應(yīng)的 First 集，掃描

5、每一條產(chǎn)生式，記錄每一輪掃描是 每個(gè)非終結(jié)符 First 集是否增大過(guò)。全部初始化為沒(méi)有增大的狀態(tài)，對(duì)于課本的 五種類型依次求解，每次將結(jié)果加入對(duì)應(yīng)的集合中，若一次掃描First 集沒(méi)有增大，則說(shuō)明循環(huán)結(jié)束。3、求Follow集算法存儲(chǔ)每一個(gè)非終結(jié)符對(duì)應(yīng)的 Follow 集，將#加入文法的開始符號(hào)的 Follow 集4合中，記錄每一輪掃描是每個(gè)非終結(jié)符 Follow 集合是否增大過(guò)，全部初始化為 沒(méi)有增大的狀態(tài)，掃描每一條產(chǎn)生式的右部，掃描到非終結(jié)符,判斷在該非終結(jié)符之后的子串能否推導(dǎo)空，若該符號(hào)串可以推導(dǎo)出空，還要將 Follow(lp)加入到里面。4、求Select集算法初始化每條產(chǎn)生式對(duì)

6、應(yīng)的 Select 集合為空，若產(chǎn)生式右部不能推導(dǎo)出空，貝 U 將右部的 First 集加入 Select 集，如果可以推出空，則需要同時(shí)將左部的Follow集合右部的 First 集去掉空的部分加入 Select 集。五、 實(shí)驗(yàn)小結(jié)通過(guò)本次實(shí)驗(yàn)，知道了如何判斷一個(gè)文法是不是 L(L 1)文法，同時(shí)對(duì)于 First、Follow 以及 Select 集的求解原理變得更加熟悉，并且知道了如何用計(jì)算機(jī)語(yǔ)言求 解First，F(xiàn)ollow 以及 Select 集。不足之處是，沒(méi)有完成判斷文法是否為左遞歸文 法以及左遞歸文法的轉(zhuǎn)換部分。六、 附件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(非終結(jié)符:,self.Vn)print(終 結(jié) 符:：self.Vt)print(開始符號(hào):,self.start)print(產(chǎn)生式如下:)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( 非終結(jié)符能否推導(dǎo)出空的信息 :)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: