編譯原理實驗自動生成LR0分析表

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