編譯原理實(shí)驗(yàn)LL(1)文法的判斷及轉(zhuǎn)換

2023.11.30LL(1)文法的判斷及轉(zhuǎn)換

目錄一、實(shí)驗(yàn)名稱(chēng) 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é)果截圖 10

輸入：任意一個(gè)文法輸出：(1)是否為L(zhǎng)L(1)文法(2)若是，給出每條產(chǎn)生式的select集(3)若不是，看看是否含有左公共因子或者含有左遞歸，并用相應(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—>X1X2…Xn，F(xiàn)irst（X）包含了First（X1）-{ε}。若對(duì)于某個(gè)i

<

n，所有的集合First（X1），...

，F(xiàn)irst（Xi）都包含了ε，則First（X）也包括了First（Xi+1）-

{ε}。若所有集合First（X1），...，F(xiàn)irst（Xn）都包括了ε，則First（X）也包括了ε。2、Follow集定義給出一個(gè)非終結(jié)符A，那么集合Follow（A）則是由終結(jié)符組成，此外可能還含有#（#是題目約定的字符串結(jié)束符）。集合Follow（A）的定義如下：1.若A是開(kāi)始符號(hào)，則#在Follow（A）中。2.若存在產(chǎn)生式B—>αAγ，則First（γ）-{ε}在Follow（A）中。3.若存在產(chǎn)生式B—>αAγ，且ε在First（γ）中，則Follow（A）包括Follow（B）。3、Select集定義4、含左遞歸文法一個(gè)文法G，若存在P經(jīng)過(guò)一次或多次推導(dǎo)得到Pa（即能推導(dǎo)出以P開(kāi)頭的式子），則稱(chēng)G是左遞歸的。左遞歸分為直接左遞歸和間接左遞歸。直接左遞歸經(jīng)過(guò)一次推導(dǎo)就可以看出文法存在左遞歸，如P→Pa｜b。間接左遞歸側(cè)需多次推導(dǎo)才可以看出文法存在左遞歸，如文法：S→Qc｜c(diǎn)，Q→Rb｜b，R→Sa｜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集，掃描每一條產(chǎn)生式，記錄每一輪掃描是每個(gè)非終結(jié)符First集是否增大過(guò)。全部初始化為沒(méi)有增大的狀態(tài)，對(duì)于課本的五種類(lèi)型依次求解，每次將結(jié)果加入對(duì)應(yīng)的集合中，若一次掃描First集沒(méi)有增大，則說(shuō)明循環(huán)結(jié)束。3、求Follow集算法存儲(chǔ)每一個(gè)非終結(jié)符對(duì)應(yīng)的Follow集，將'#'加入文法的開(kāi)始符號(hào)的Follow集合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集的求解原理變得更加熟悉，并且知道了如何用計(jì)算機(jī)語(yǔ)言求解First，F(xiàn)ollow以及Select集。不足之處是，沒(méi)有完成判斷文法是否為左遞歸文法以及左遞歸文法的轉(zhuǎn)換部分。六、附件1、源代碼classGw:def__init__(self):withopen('Gw.txt')asf:content=f.readlines()content=[line.strip()forlineincontent]self.Vn=content[0].split('')self.Vt=content[1].split('')self.start=content[2]duce=[]self.left=[]self.right=[]foriinrange(3,len(content)):duce.append(content[i])self.left.append(content[i].split('->')[0])self.right.append(content[i].split('->')[1])defshowGw(self):print('非終結(jié)符:',self.Vn)defcanEmpty(self):self.isEmpty=dict()foriinrange(len(self.Vn)):self.isEmpty[self.Vn[i]]=-1print(self.isEmpty)temp=duce[::]deleteIndex=[]pointer=0whilepointer<len(temp):ifpointernotindeleteIndex:lp=temp[pointer].split('->')[0]rp=temp[pointer].split('->')[1]ifrp=='!':self.isEmpty[lp]=1foriinrange(len(temp)):iftemp[i].split('->')[0]==lpandinotindeleteIndex:deleteIndex.append(i)l=list(rp)isContainVt=[iinself.Vtforiinl]ifTrueinisContainVt:deleteIndex.append(pointer)forkinrange(len(temp)):ifknotindeleteIndex:iftemp[k].split('->')[0]==lp:breakelse:self.isEmpty[lp]=0pointer=pointer+1while-1inself.isEmpty.values():foriinrange(len(temp)):ifinotindeleteIndex:lp=temp[i].split('->')[0]rp=temp[i].split('->')[1]rlsit=list(rp)forjinrange(len(rlsit)):ifself.isEmpty[rlsit[j]]==1:ifj==len(rlsit)-1:self.isEmpty[lp]=1else:self.isEmpty[lp]=0else:continuedefshow(self):print('非終結(jié)符能否推導(dǎo)出空的信息:')forvinself.Vn:ifself.isEmpty[v]==1:yon='是'else:yon='否'print('%s:%s'%(v,yon))defgetFirst(self):self.First=dict()foriinself.Vn:self.First[i]=list()isChange=dict()whileTrue:forkinself.Vn:isChange[k]=0foriinrange(len(duce)):lp=duce[i].split('->')[0]rp=duce[i].split('->')[1]rlist=list(rp)ifrlist[0]=='!'orrlist[0]inself.Vt:ifrlist[0]notinself.First[lp]:self.First[lp].append(rlist[0])isChange[lp]=1else:forjinrlist:ifjinself.Vn:ifself.isEmpty[j]==1:oldsize=len(self.First[lp])templist=self.First[j][::]if'!'intemplist:templist.remove('!')forxintemplist:else:oldsize=len(self.First[lp])ifjinself.Vn:templist=self.First[j][::]forxintemplist:ifxnotinself.First[lp]:self.First[lp].append(x)else:ifjnotinself.First[lp]:self.First[lp].append(x)newsize=len(self.First[lp])ifoldsize!=newsize:isChange[lp]=1breakif1notinisChange.values():print('First集合不在增大!')breakelse:print('First集合有增大!')passdefshowFirst(self):print('First集合信息:')forvinself.Vn:print(v,self.First[v])defcanCauseEmpty(self,plist):first=list()iflen(plist)==0:first.append('!')else:foriinplist:ifiinself.Vn:ifself.isEmpty[i]==1:t=self.First[i][::]if'!'int:t.remove('!')forkint:breakelse:ifinotinfirst:first.append(i)breakreturnfirstdefgetFollow(self):self.Follow=dict()foriinself.Vn:self.Follow[i]=list()self.Follow[self.start].append('#')isChange=dict()whileTrue:forkinself.Vn:isChange[k]=0foriinrange(len(duce)):lp=duce[i].split('->')[0]rp=duce[i].split('->')[1]rlist=list(rp)forjinrange(len(rlist)):ifrlist[j]inself.Vn:reslist=self.canCauseEmpty(rlist[j+1::])if'!'inreslist:oldsize=len(self.Follow[rlist[j]])foryinself.Follow[lp]:ifynotinself.Follow[rlist[j]]:self.Follow[rlist[j]].append(y)newsize=len(self.Follow[rlist[j]])ifoldsize!=newsize:isChange[rlist[j]]=1else:passoldsize=len(self.Follow[rlist[j]])forxinreslist:ifx!='!'andxnotinself.Follow[rlist[j]]:if1notinisChange.values():breakdefshowFollow(self):print('Follow集合信息:')forkeyinself.Vn:print(key,self.Follow[key])defgetSelect(self):self.Select=dict()foriinduce:self.Select[i]=list()foriinrange(len(duce)):lp=duce[i].split('->')[0]rp=duce[i].split('->')[1]rlist=list(rp)ifrlist[0]=='!':forvinself.Follow[lp]:ifvnotinself.Select[duce[i]]:self.Select[duce[i]].append(v)elifrlist[0]inself.Vt:self.Select[duce[i]].append(rlist[0])else:res=self.canCauseEmpty(rlist)if'!'notinres:forvinres:ifvnotinself.Select[duce[i]]:self.Select[duce[i]].append(v)