編譯原理實(shí)驗(yàn)LL1文法的判斷及轉(zhuǎn)換_第1頁(yè)
編譯原理實(shí)驗(yàn)LL1文法的判斷及轉(zhuǎn)換_第2頁(yè)
編譯原理實(shí)驗(yàn)LL1文法的判斷及轉(zhuǎn)換_第3頁(yè)
編譯原理實(shí)驗(yàn)LL1文法的判斷及轉(zhuǎn)換_第4頁(yè)
編譯原理實(shí)驗(yàn)LL1文法的判斷及轉(zhuǎn)換_第5頁(yè)
已閱讀5頁(yè),還剩7頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、2016.11.30LL(1)文法的判斷及轉(zhuǎn)換目錄一、實(shí)驗(yàn)名稱2二、實(shí)驗(yàn)?zāi)康?三、實(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é)果截圖10一、實(shí)驗(yàn)名稱LL(1)文法的判斷及轉(zhuǎn)換二、實(shí)驗(yàn)?zāi)康妮斎耄喝我庖粋€(gè)文法輸出:(1)是否為L(zhǎng)L(1)文法 (2)若是,給出每條產(chǎn)生式的select集 (3)若不是,看看是否含有左公共因子或者含有左遞歸,并用相應(yīng)的方法將非LL(1)文法變成LL(1)文

2、法,并輸出新文法中每條產(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)生式XX1X2Xn,F(xiàn)irst(X)包含了First(X1)-。 若對(duì)于某個(gè)iA,則First()- 在Follow(A)中。3. 若存在產(chǎn)生式BA,且在First()中,則Follow(A)包括Follow(B)。3、Select集定義對(duì)于產(chǎn)生式A。集合select(A)定義如下:1. 若不能推出,則select(A) = firs

3、t()。2. 若能推出,則select(A)= first() follow(A)。4、含左遞歸文法一個(gè)文法G,若存在P經(jīng)過(guò)一次或多次推導(dǎo)得到Pa(即能推導(dǎo)出以P開頭的式子), 則稱G是左遞歸的。 左遞歸分為直接左遞歸和間接左遞歸。 直接左遞歸經(jīng)過(guò)一次推導(dǎo)就可以看出文法存在左遞歸,如PPab。 間接左遞歸側(cè)需多次推導(dǎo)才可以看出文法存在左遞歸,如文法:SQcc,QRbb,RSaa有S =Qc =Rbc =Sabc四、實(shí)驗(yàn)思路本次實(shí)驗(yàn)采用python完成。1、求非終結(jié)符是否能導(dǎo)出空a. 第一輪掃描。當(dāng)前的產(chǎn)生式還沒被刪除,非終結(jié)符lp可以導(dǎo)出空,將以該非終結(jié)符為左部的產(chǎn)生式標(biāo)記為要?jiǎng)h除的。產(chǎn)生式右

4、部分解,若該產(chǎn)生式右部包含終結(jié)符,刪除該產(chǎn)生式因?yàn)橛伤粫?huì)導(dǎo)出空。判斷沒有被刪除的產(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集,掃描每一條產(chǎn)生式,記錄每一輪掃描是每個(gè)非終結(jié)符First集是否增大過(guò)。全部初始化為沒有增大的狀態(tài),對(duì)于課本的五種類型依次求解,每次將結(jié)果加入對(duì)應(yīng)的集合中,若一次掃描First集沒有增大,則說(shuō)明循環(huán)結(jié)束。3、求Follow集算法存儲(chǔ)每一個(gè)非終結(jié)符對(duì)應(yīng)的Follow集,將#加入文法的開始符號(hào)的Follow集合中,記錄每一輪掃

5、描是每個(gè)非終結(jié)符Follow集合是否增大過(guò),全部初始化為沒有增大的狀態(tài),掃描每一條產(chǎn)生式的右部,掃描到非終結(jié)符,判斷在該非終結(jié)符之后的子串能否推導(dǎo)空,若該符號(hào)串可以推導(dǎo)出空,還要將Follow(lp)加入到里面。4、求Select集算法初始化每條產(chǎn)生式對(duì)應(yīng)的Select集合為空,若產(chǎn)生式右部不能推導(dǎo)出空,則將右部的First集加入Select集,如果可以推出空,則需要同時(shí)將左部的Follow集合右部的First集去掉空的部分加入Select集。五、實(shí)驗(yàn)小結(jié)通過(guò)本次實(shí)驗(yàn),知道了如何判斷一個(gè)文法是不是LL(1)文法,同時(shí)對(duì)于First、Follow以及Select集的求解原理變得更加熟悉,并且知道

6、了如何用計(jì)算機(jī)語(yǔ)言求解First,F(xiàn)ollow以及Select集。不足之處是,沒有完成判斷文法是否為左遞歸文法以及左遞歸文法的轉(zhuǎn)換部分。六、附件1、源代碼class Gw: def _init_(self): 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 =

7、 self.right = for i in range(3,len(content): duce.append(contenti) self.left.append(contenti.split(-)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)

8、def canEmpty(self): self.isEmpty = dict() for i in range(len(self.Vn): self.isEmptyself.Vni = -1 print(self.isEmpty) temp = duce: deleteIndex= pointer = 0 while pointer)0 rp = temppointer.split(-)1 if rp=!: self.isEmptylp = 1 for i in range(len(temp): if tempi.split(-)0=lp and i not in delet

9、eIndex: 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 tempk.split(-)0=lp: break else: self.isEmptylp = 0 pointer = pointer+1 while -1 in self.isEmpty.values(): for i i

10、n range(len(temp): if i not in deleteIndex: lp = tempi.split(-)0 rp = tempi.split(-)1 rlsit = list(rp) for j in range(len(rlsit): if self.isEmptyrlsitj=1: if j=len(rlsit)-1: self.isEmptylp=1 elif self.isEmptyrlsitj=0: deleteIndex.append(i) for k in range(len(temp): if k not in deleteIndex: if tempk.

11、split(-)0=lp: break else: self.isEmptylp = 0 else: continue def show(self): print(非終結(jié)符能否推導(dǎo)出空的信息:) for v in self.Vn: if self.isEmptyv=1: yon = 是 else: yon = 否 print(%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

12、.Vn: isChangek = 0 for i in range(len(duce): lp = ducei.split(-)0 rp = ducei.split(-)1 rlist = list(rp) if rlist0=! or rlist0 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

13、 = len(self.Firstlp) templist = self.Firstj: if ! in templist: templist.remove(!) for x in templist: if x not in self.Firstlp: self.Firstlp.append(x) if rp.endswith(j) and ! not in self.Firstlp: self.Firstlp.append(!) newsize = len(self.Firstlp) if oldsize!=newsize: isChangelp=1 else: oldsize = len(

14、self.Firstlp) if j in self.Vn: templist = self.Firstj: for x in templist: if x not in self.Firstlp: self.Firstlp.append(x) else: if j not in self.Firstlp: self.Firstlp.append(x) newsize = len(self.Firstlp) if oldsize!=newsize: isChangelp=1 break if 1 not in isChange.values(): print(First集合不在增大!) bre

15、ak else: print(First集合有增大!) pass def showFirst(self): print(First集合信息:) for v in self.Vn: print(v,self.Firstv) def canCauseEmpty(self,plist): first = list() if len(plist)=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:

16、 if k not in first: 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) 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

17、i = 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.split(-)1 rlist = list(rp) for j in range(len(rlist): if rlistj in self.Vn: reslist = self.canCauseEmpty(rlistj+1

18、:) if ! in reslist: oldsize = len(self.Followrlistj) for y in self.Followlp: if y not in self.Followrlistj: self.Followrlistj.append(y) newsize = len(self.Followrlistj) if oldsize!=newsize: isChangerlistj = 1 else: pass oldsize = len(self.Followrlistj) for x in reslist: if x!=! and x not in self.Fol

19、lowrlistj: self.Followrlistj.append(x) newsize = len(self.Followrlistj) if oldsize!=newsize: isChangerlistj = 1 if 1 not in isChange.values(): break def showFollow(self): print(Follow集合信息:) for key in self.Vn: print(key,self.Followkey) def getSelect(self): self.Select = dict() for i in duce:

20、 self.Selecti = list() for i in range(len(duce): lp = ducei.split(-)0 rp = ducei.split(-)1 rlist = list(rp) if rlist0=!: for v in self.Followlp: if v not in self.Sducei: self.Sducei.append(v) elif rlist0 in self.Vt: self.Sducei.append(rl

21、ist0) 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.Sducei.append(v) for v in self.Followlp: if v not in self.Selectself.

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論