編譯原理實(shí)驗(yàn)自動(dòng)生成LR0分析表

-.z......資料....自動(dòng)生成LR（0）分析表目錄一、實(shí)驗(yàn)名稱(chēng)1二、實(shí)驗(yàn)?zāi)康?三、實(shí)驗(yàn)原理11、閉包c(diǎn)losure(I)12、轉(zhuǎn)換函數(shù)GO(I,*)13、ACTION子表和GOTO子表的構(gòu)造1四、實(shí)驗(yàn)思路11、輸入12、建立項(xiàng)目13、closure算法14、轉(zhuǎn)向函數(shù)GO(I,*)的算法15、建立狀態(tài)及對(duì)應(yīng)的項(xiàng)目集16、ACTION子表的構(gòu)造17、GOTO子表的構(gòu)造1五、實(shí)驗(yàn)小結(jié)1六、11、源代碼12、運(yùn)行結(jié)果截圖1一、實(shí)驗(yàn)名稱(chēng)自動(dòng)生成LR（0）分析表二、實(shí)驗(yàn)?zāi)康?、實(shí)現(xiàn)計(jì)算閉包函數(shù)CLOSURE的算法。2、實(shí)現(xiàn)轉(zhuǎn)向函數(shù)GO(I,*)的算法。3、實(shí)現(xiàn)ACTION子表和GOTO子表的構(gòu)造算法。4、輸入任意的壓縮了的上下文無(wú)關(guān)文法，輸出相應(yīng)的LR（0）分析表（以表格形式輸出）。三、實(shí)驗(yàn)原理1、閉包c(diǎn)losure(I)若文法G已拓廣為G’，而S為文法G的開(kāi)始符號(hào)，拓廣后增加產(chǎn)生式S’->S。如果I是文法G’的一個(gè)項(xiàng)目集，定義和構(gòu)造I的閉包c(diǎn)losure(I)如下：a.I的項(xiàng)目在closure(I)中。b.若A->α?Bβ屬于closure(I)，則每一形如B->?γ的項(xiàng)目也屬于closure(I)。c.重復(fù)b直到不出現(xiàn)新的項(xiàng)目為止。即closure(I)不再擴(kuò)大。2、轉(zhuǎn)換函數(shù)GO(I,*)GO(I,*)=closure(J)其中：I為包含*一項(xiàng)目集的狀態(tài)。*為一文法符號(hào)，*∈Vn∪VtJ={任何形如A->α?*β的項(xiàng)目|A->α*?β屬于I}3、ACTION子表和GOTO子表的構(gòu)造a.若項(xiàng)目A→α.aβ屬于Ik且GO(Ik,a)=Ij,a為終結(jié)符，則置ACTION[k,a]為“把狀態(tài)j和符號(hào)a移進(jìn)?！?，簡(jiǎn)記為“sj”；b.若項(xiàng)目A→α．屬于Ik，則，對(duì)任何終結(jié)符a，置ACTION[k，a]為“用產(chǎn)生式A→α進(jìn)行規(guī)約”，簡(jiǎn)記為“rj”；其中，假定A→α為文法G'的第j個(gè)產(chǎn)生式c.若項(xiàng)目S'→S．屬于Ik,則置ACTION[k,*]為“接受”，簡(jiǎn)記為“acc”；d.若GO(Ik,A)=Ij,A為非終結(jié)符，則置GOTO[k,A]=j；e.分析表中凡不能用上述1至4填入信息的空白格均置上“出錯(cuò)標(biāo)志”。按上述算法構(gòu)造的含有ACTION和GOTO兩部分的分析表，如果每個(gè)入口不含多重定義，則稱(chēng)它為文法G的一*LR(0)分析表。具有LR(0)表的文法G稱(chēng)為一個(gè)LR（0）文法，LR(0)文法是無(wú)二義的。四、實(shí)驗(yàn)思路本次實(shí)驗(yàn)采用python完成。1、輸入構(gòu)造一個(gè)LR類(lèi)，輸入非終結(jié)符，終結(jié)符，開(kāi)始符以及產(chǎn)生式分別存于LR類(lèi)的成員：Vn，Vt，start，production。2、建立項(xiàng)目構(gòu)造函數(shù)Project，根據(jù)產(chǎn)生式建立項(xiàng)目，對(duì)每一條產(chǎn)生式的右部進(jìn)行處理，依次在右部的每個(gè)終結(jié)符和非終結(jié)符前添加原點(diǎn)，并在最后添加原點(diǎn)。3、closure算法構(gòu)造函數(shù)closure，求一個(gè)項(xiàng)目的閉包c(diǎn)losure。分三種情況討論，對(duì)于S->·和E->·a這兩種情況，返回自身。對(duì)于E->b·B這種情況，對(duì)項(xiàng)目的右部進(jìn)行處理，繼續(xù)求B->·r閉包，因此這是一個(gè)遞歸函數(shù)。最終函數(shù)以列表的形式返回每個(gè)項(xiàng)目集。4、轉(zhuǎn)向函數(shù)GO(I,*)的算法構(gòu)造函數(shù)GO，求一個(gè)項(xiàng)目集的GO(I,*)。建立字典go存放最終結(jié)果，對(duì)不是S->a·形式的項(xiàng)目進(jìn)行討論，對(duì)項(xiàng)目的右部進(jìn)行處理，將原點(diǎn)后移一位，利用closure函數(shù)得到圓點(diǎn)后移得到的項(xiàng)目的項(xiàng)目集，加入go中。直到處理完該項(xiàng)目集的所有項(xiàng)目。5、建立狀態(tài)及對(duì)應(yīng)的項(xiàng)目集構(gòu)造函數(shù)createDFA，建立狀態(tài)及對(duì)應(yīng)的項(xiàng)目集。首先，從拓廣文法的第一個(gè)項(xiàng)目開(kāi)始，建立初態(tài)，定義number存放狀態(tài)編號(hào)，初始值為0。設(shè)立字典status存放狀態(tài)編號(hào)及對(duì)應(yīng)的項(xiàng)目集。將初態(tài)加入一個(gè)隊(duì)列qu中。每次從qu中取出一個(gè)狀態(tài)，求該狀態(tài)的項(xiàng)目集的Go(I,*)，再對(duì)得到的項(xiàng)目集進(jìn)行判斷，若該項(xiàng)目集是已知的狀態(tài)，則不做處理，若該項(xiàng)目集是新的狀態(tài)，則將其加入隊(duì)列qu中，number加1。每次從qu中取出一個(gè)狀態(tài)重復(fù)上述操作，直到隊(duì)列為空，說(shuō)明已求得所有狀態(tài)。6、ACTION子表的構(gòu)造分兩種情況討論：項(xiàng)目集只有一個(gè)項(xiàng)目和項(xiàng)目集不止一個(gè)項(xiàng)目。對(duì)于第一種情況，再分兩種情況，看該項(xiàng)目是否對(duì)應(yīng)了初態(tài)，若是，則將*對(duì)應(yīng)為acc，其余終結(jié)符對(duì)應(yīng)為error，若不是，則求得該項(xiàng)目去掉圓點(diǎn)之后的產(chǎn)生式的編號(hào)i，終結(jié)符合*對(duì)應(yīng)為ri。對(duì)于項(xiàng)目集不止一個(gè)項(xiàng)目的情況，依次對(duì)終結(jié)符和*尋找在該狀態(tài)的的GO(I,*)下是否有所對(duì)應(yīng)，有則求得編號(hào)對(duì)應(yīng)為Si，沒(méi)有則對(duì)于error。7、GOTO子表的構(gòu)造對(duì)于每個(gè)狀態(tài)的GO(I,*)函數(shù)進(jìn)行遍歷，尋找是否有對(duì)應(yīng)的終結(jié)符，若有則返回對(duì)應(yīng)的項(xiàng)目集的編號(hào)，若沒(méi)有則返回error。五、實(shí)驗(yàn)小結(jié)通過(guò)本次實(shí)驗(yàn)，了解了LR(0)分析表的構(gòu)造，對(duì)于構(gòu)造過(guò)程所需要的一些算法有了深入的了解，通過(guò)實(shí)際的編寫(xiě)程序代碼完成LR(0)分析表的構(gòu)造，對(duì)于程序的編寫(xiě)能力有了一定的提升。在實(shí)驗(yàn)過(guò)程中，主要對(duì)于closure閉包函數(shù)的構(gòu)造以及狀態(tài)的設(shè)置有問(wèn)題。Closure閉包函數(shù)用了遞歸的結(jié)構(gòu)，因此對(duì)于遞歸的結(jié)束條件需要標(biāo)注清楚。對(duì)于狀態(tài)的建立，需要注意每次通過(guò)GO(I,*)得到的新的項(xiàng)目集是否是已經(jīng)存在的狀態(tài)，若是則不做處理。對(duì)于狀態(tài)的遍歷使用隊(duì)列來(lái)完成，每次新的狀態(tài)都加入隊(duì)列中，隊(duì)列為空說(shuō)明狀態(tài)遍歷完畢。有一點(diǎn)問(wèn)題值得注意，由于狀態(tài)編號(hào)的項(xiàng)目集的存儲(chǔ)結(jié)構(gòu)使用了字典，字典是無(wú)序的結(jié)構(gòu)，因此每次遍歷得到的狀態(tài)編號(hào)都不同，程序的每次運(yùn)行得到的最終LR(0)分析表不唯一。六、1、源代碼importcopyimportqueueclassLR:def__init__(self):self.Vn=[]self.Vt=[]self.start=None*開(kāi)始符號(hào)duction=[]*產(chǎn)生式j(luò)ect=[]*項(xiàng)目self.status={}*存放狀態(tài)編號(hào)及對(duì)應(yīng)的項(xiàng)目集self.goto={}*存放goto表{0:{E:'1',A:'error',B:'error'}}self.action={}*存放action表{0:{a:'S2',b:'S3'}}defsetVn(self):Vn=input('輸入非終結(jié)符(以空格區(qū)分,回車(chē)結(jié)束):')self.Vn=Vn.split('')defsetVt(self):Vt=input('輸入終結(jié)符(以空格區(qū)分,回車(chē)結(jié)束):')self.Vt=Vt.split('')defsetS(self):S=input('輸入開(kāi)始符號(hào)(以回車(chē)結(jié)束):')self.start=Sdefsetf(self):*生成產(chǎn)生式n=int(input('輸入產(chǎn)生式數(shù)目:'))print('輸入產(chǎn)生式(以回車(chē)區(qū)分):')foriinrange(n):f=input()duction.append(f)defProject(self):*建立項(xiàng)目forfinduction:temporary=copy.deepcopy(f)*temporary與f相同temporary=temporary.split('->')l=temporary[0]*產(chǎn)生式左部r=list(temporary[1])*產(chǎn)生式右部foriinrange(len(r)+1):*對(duì)產(chǎn)生式右部處理temporary1=copy.deepcopy(r)temporary1.insert(i,'·')newf=l+'->'+''.join(temporary1)ject.append(newf)defclosure(self,pro):*求一個(gè)項(xiàng)目pro的閉包E->·E->·bE->b·B返回列表temporary=[]*最終返回的結(jié)果temporary.append(pro)*將pro自身加入l1=pro.split('->')[0]*左部r1=pro.split('->')[1]*右部*=list(r1)*存放右部的列表inde*=*.inde*('·')*得到圓點(diǎn)位置iflen(*)==1:*S->·returntemporaryelse:ifinde*==len(r1)-1or*[inde*+1]inself.Vt:*E->·areturntemporaryelse:*E->b·Bforeleminrange(len(ject)):l=ject[elem].split('->')[0]*左部r=ject[elem].split('->')[1]*右部ifl==*[inde*+1]andr.startswith('·'):*繼續(xù)求B->·r閉包c(diǎn)onlist=self.closure(ject[elem])iflen(conlist)==0:passelse:temporary.e*tend(conlist)returntemporarydefGO(self,project):*計(jì)算一個(gè)項(xiàng)目集的GO(I,*),返回字典形式go={}*存放Go(I,*)結(jié)果，形式為{a:[],b:[]}foreleminproject:l=elem.split('->')[0]*項(xiàng)目左部r=elem.split('->')[1]*項(xiàng)目右部inde*=list(r).inde*('·')*返回·的位置ifnotr.endswith('·'):*不是S->a·形式ifgo.get(list(r)[inde*+1])==None:*說(shuō)明*所對(duì)應(yīng)的go中沒(méi)有項(xiàng)目temporary=list(r)temporary.insert(inde*+2,'·')temporary.remove('·')*將·后移一位*=l+'->'+''.join(temporary)*產(chǎn)生一個(gè)完整的項(xiàng)目go[list(r)[inde*+1]]=self.closure(*)*將該項(xiàng)目對(duì)應(yīng)的項(xiàng)目集加入*的go中else:*說(shuō)明*所對(duì)應(yīng)的go中已有項(xiàng)目temporary=list(r)temporary.insert(inde*+2,'·')temporary.remove('·')*將·后移一位*=l+'->'+''.join(temporary)*產(chǎn)生一個(gè)完整的項(xiàng)目go[list(r)[inde*+1]].e*tend(self.closure(*))returngodefcreateDFA(self):*建立識(shí)別活前綴的DFAnumber=0*初始狀態(tài)編號(hào)為0first='S->·'+self.start*初態(tài)*=self.closure(first)*初態(tài)閉包self.status[number]=*qu=queue.Queue()*構(gòu)造隊(duì)列，用于存放得到的狀態(tài)qu.put({number:self.status[number]})*把初始狀態(tài)加入隊(duì)列中number=number+1whilenotqu.empty():*隊(duì)列不為空，說(shuō)明狀態(tài)沒(méi)有遍歷完畢temporary=qu.get()*隊(duì)列中取出一個(gè)狀態(tài)fork,vintemporary.items():y=self.GO(v)*求項(xiàng)目集的Go(I,*)forkey,valueiny.items():flag=-1*標(biāo)志位，判斷value是否是新的狀態(tài)forke,vainself.status.items():ifset(va)==set(value):flag=ke*狀態(tài)已存在，返回狀態(tài)編號(hào)breakifflag==-1:*新的狀態(tài)，加入狀態(tài)集中self.status[number]=valuequ.put({number:self.status[number]})else:*已有狀態(tài)pass*不作處理defGOTO(self):*goto表foriinrange(len(self.status)):self.goto[i]={}temp=self.GO(self.status[i])*每個(gè)狀態(tài)的GOforvninself.Vn:*對(duì)非終結(jié)符遍歷ifvnintemp.keys():*非終結(jié)符存在于狀態(tài)的Go中forkey,valueinself.status.items():ifset(value)==set(temp[vn]):number=key*記錄編號(hào)breakself.goto[i][vn]=numberelse:self.goto[i][vn]='error'defACTION(self):vt*=copy.deepcopy(self.Vt)vt*.append('*')*終結(jié)符加‘*’foriinrange(len(self.status)):self.action[i]={}iflen(self.status[i])==1:*項(xiàng)目集只有一個(gè)項(xiàng)目ifself.status[i][0].startswith('S'):*S->E·forvtinself.Vt:self.action[i][vt]='error'self.action[i]['*']='acc'else:*填寫(xiě)rj的項(xiàng)目E->aA·temp=self.status[i][0].rstrip('·')*刪去項(xiàng)目的·E->aAforninrange(len(duction)):ifduction[n]==temp:m=n+1*產(chǎn)生式在G'中下標(biāo)從1開(kāi)始breakforvtinvt*:self.action[i][vt]='r'+str(m)else:*填寫(xiě)Sj的項(xiàng)目temp=self.GO(self.status[i])*字典形式{a:[],b:[]}forvtinvt*:ifvtintemp.keys():forkey,valueinself.status.items():*確定到哪一個(gè)狀態(tài)ifset(value)==set(temp[vt]):number=key*返回狀態(tài)編號(hào)breakself.action[i][vt]='S'+str(number)else:self.action[i][vt]='error'defoutput(self):*輸出LR(0)分析表表格形式print('LR(0)分析表'.center(85))print('狀態(tài)'.center(5),'ACTION'.center(50),'GOTO'.center(30))print(''.center(10),end='')forvtinself.Vt:*actionprint(vt.center(10),end='')print('*'.center(10),end='')forvninself.Vn:*goto