編譯原理實驗自動生成LR(0)分析表(共12頁)

1、精選優(yōu)質文檔-傾情為你奉上2016.12.14自動生成LR（0）分析表目錄一、實驗名稱自動生成LR（0）分析表二、實驗目的1、實現計算閉包函數CLOSURE的算法。2、實現轉向函數GO(I,X)的算法。 3、實現ACTION子表和GOTO子表的構造算法。4、輸入任意的壓縮了的上下文無關文法，輸出相應的LR（0）分析表（以表格形式輸出）。三、實驗原理1、閉包closure(I)若文法G已拓廣為G，而S為文法G的開始符號，拓廣后增加產生式S->S。如果I是文法G的一個項目集，定義和構造I的閉包closure(I)如下：a.I的項目在closure(I)中。b.若A->B屬于closur

2、e(I)，則每一形如B->的項目也屬于closure(I)。c.重復b直到不出現新的項目為止。即closure(I)不再擴大。2、轉換函數GO(I,X)GO(I,X)=closure(J)其中：I為包含某一項目集的狀態(tài)。X為一文法符號，XVnVtJ=任何形如A->X的項目|A->X屬于I3、ACTION子表和GOTO子表的構造a.若項目A.a屬于Ik且GO (Ik, a)= Ij, a為終結符，則置ACTIONk, a為“把狀態(tài)j和符號a移進?！保営洖椤皊j”； b.若項目A屬于Ik，那么，對任何終結符a，置ACTIONk，a為“用產生式A進行規(guī)約”，簡記為“rj”；其中，

3、假定A為文法G'的第j個產生式c.若項目S'S屬于Ik, 則置ACTIONk, #為“接受”，簡記為“acc”； d.若GO (Ik, A)= Ij, A為非終結符，則置GOTOk, A=j； e.分析表中凡不能用上述1至4填入信息的空白格均置上“出錯標志”。 按上述算法構造的含有ACTION和GOTO兩部分的分析表，如果每個入口不含多重定義，則稱它為文法G的一張LR(0)分析表。具有LR(0)表的文法G稱為一個LR（0）文法，LR(0)文法是無二義的。四、實驗思路本次實驗采用python完成。1、輸入構造一個LR類，輸入非終結符，終結符，開始符以及產生式分別存于LR類的成員：

4、Vn，Vt，start，production。2、建立項目構造函數Project，根據產生式建立項目，對每一條產生式的右部進行處理，依次在右部的每個終結符和非終結符前添加原點，并在最后添加原點。3、closure算法構造函數closure，求一個項目的閉包closure。分三種情況討論，對于S->·和E->·a這兩種情況，返回自身。對于E->b·B這種情況，對項目的右部進行處理，繼續(xù)求B->·r閉包，因此這是一個遞歸函數。最終函數以列表的形式返回每個項目集。4、轉向函數GO(I,X)的算法構造函數GO，求一個項目集的GO(I,X)

5、。建立字典go存放最終結果，對不是S->a·形式的項目進行討論，對項目的右部進行處理，將原點后移一位，利用closure函數得到圓點后移得到的項目的項目集，加入go中。直到處理完該項目集的所有項目。5、建立狀態(tài)及對應的項目集構造函數createDFA，建立狀態(tài)及對應的項目集。首先，從拓廣文法的第一個項目開始，建立初態(tài)，定義number存放狀態(tài)編號，初始值為0。設立字典status存放狀態(tài)編號及對應的項目集。將初態(tài)加入一個隊列qu中。每次從qu中取出一個狀態(tài)，求該狀態(tài)的項目集的Go(I,x)，再對得到的項目集進行判斷，若該項目集是已知的狀態(tài)，則不做處理，若該項目集是新的狀態(tài)，則將

6、其加入隊列qu中，number加1。每次從qu中取出一個狀態(tài)重復上述操作，直到隊列為空，說明已求得所有狀態(tài)。6、ACTION子表的構造分兩種情況討論：項目集只有一個項目和項目集不止一個項目。對于第一種情況，再分兩種情況，看該項目是否對應了初態(tài)，若是，則將#對應為acc，其余終結符對應為error，若不是，則求得該項目去掉圓點之后的產生式的編號i，終結符合#對應為ri。對于項目集不止一個項目的情況，依次對終結符和#尋找在該狀態(tài)的的GO(I,X)下是否有所對應，有則求得編號對應為Si，沒有則對于error。7、GOTO子表的構造對于每個狀態(tài)的GO(I,X)函數進行遍歷，尋找是否有對應的終結符，若有

7、則返回對應的項目集的編號，若沒有則返回error。五、實驗小結通過本次實驗，了解了LR(0)分析表的構造，對于構造過程所需要的一些算法有了深入的了解，通過實際的編寫程序代碼完成LR(0)分析表的構造，對于程序的編寫能力有了一定的提升。在實驗過程中，主要對于closure閉包函數的構造以及狀態(tài)的設置有問題。Closure閉包函數用了遞歸的結構，因此對于遞歸的結束條件需要標注清楚。對于狀態(tài)的建立，需要注意每次通過GO(I,X)得到的新的項目集是否是已經存在的狀態(tài)，若是則不做處理。對于狀態(tài)的遍歷使用隊列來完成，每次新的狀態(tài)都加入隊列中，隊列為空說明狀態(tài)遍歷完畢。有一點問題值得注意，由于狀態(tài)編號的項目

8、集的存儲結構使用了字典，字典是無序的結構，因此每次遍歷得到的狀態(tài)編號都不同，程序的每次運行得到的最終LR(0)分析表不唯一。六、附件1、源代碼import copyimport queueclass LR: def _init_(self): self.Vn = self.Vt = self.start = None # 開始符號 duction = # 產生式 ject = # 項目 self.status = # 存放狀態(tài)編號及對應的項目集 self.goto = # 存放goto表 0:E:'1',A:'error',B:&

9、#39;error' self.action = # 存放action表 0:a:'S2',b:'S3' def setVn(self): Vn = input('輸入非終結符(以空格區(qū)分, 回車結束):') self.Vn = Vn.split(' ') def setVt(self): Vt = input('輸入終結符(以空格區(qū)分, 回車結束):') self.Vt = Vt.split(' ') def setS(self): S = input('輸入開始符號(以回車結束)

10、:') self.start = S def setf(self): # 生成產生式 n = int(input('輸入產生式數目:') print('輸入產生式(以回車區(qū)分):') for i in range(n): f = input() duction.append(f) def Project(self): # 建立項目 for f in duction: temporary = copy.deepcopy(f) # temporary與f相同 temporary = temporary.split('-

11、>') l = temporary0 # 產生式左部 r = list(temporary1) # 產生式右部 for i in range(len(r)+1): # 對產生式右部處理 temporary1 = copy.deepcopy(r) temporary1.insert(i,'·') newf = l+'->'+''.join(temporary1) ject.append(newf) def closure(self, pro): # 求一個項目pro的閉包 E->· E-

12、>·b E->b·B 返回列表 temporary = # 最終返回的結果 temporary.append(pro) # 將pro自身加入 l1 = pro.split('->')0 # 左部 r1 = pro.split('->')1 # 右部 x = list(r1) # 存放右部的列表 index = x.index('·') # 得到圓點位置 if len(x) = 1: # S->· return temporary else: if index = len(r1)

13、-1 or xindex+1 in self.Vt: #E->·a return temporary else: # E->b·B for elem in range(len(ject): l = jectelem.split('->')0 # 左部 r = jectelem.split('->')1 # 右部 if l = xindex+1 and r.startswith('·'): # 繼續(xù)求B->·r閉包 conlist

14、= self.closure(jectelem) if len(conlist) = 0: pass else: temporary.extend(conlist) return temporary def GO(self, project): # 計算一個項目集的GO(I,x),返回字典形式 go = # 存放Go(I,x)結果，形式為a:,b: for elem in project: l = elem.split('->')0 # 項目左部 r = elem.split('->')1 # 項目右部 index = list(r)

15、.index('·') # 返回·的位置 if not r.endswith('·'): # 不是S->a·形式 if go.get(list(r)index+1) = None: # 說明x所對應的go中沒有項目 temporary = list(r) temporary.insert(index+2, '·') temporary.remove('·') # 將·后移一位 x = l+'->'+''.join(te

16、mporary) # 產生一個完整的項目 golist(r)index+1 = self.closure(x) # 將該項目對應的項目集加入x的go中 else: # 說明x所對應的go中已有項目 temporary = list(r) temporary.insert(index+2,'·') temporary.remove('·') # 將·后移一位 x = l+'->'+''.join(temporary) # 產生一個完整的項目 golist(r)index+1.extend(self

17、.closure(x) return go def createDFA(self): # 建立識別活前綴的DFA number = 0 # 初始狀態(tài)編號為0 first = 'S->·'+self.start # 初態(tài) x = self.closure(first) # 初態(tài)閉包 self.statusnumber = x qu = queue.Queue() # 構造隊列，用于存放得到的狀態(tài) qu.put(number:self.statusnumber) # 把初始狀態(tài)加入隊列中 number = number+1 while not qu.empty():

18、 # 隊列不為空，說明狀態(tài)沒有遍歷完畢 temporary = qu.get() # 隊列中取出一個狀態(tài) for k, v in temporary.items(): y = self.GO(v) # 求項目集的Go(I,x) for key, value in y.items(): flag = -1 # 標志位，判斷value是否是新的狀態(tài) for ke, va in self.status.items(): if set(va) = set(value): flag = ke # 狀態(tài)已存在，返回狀態(tài)編號 break if flag = -1: # 新的狀態(tài)，加入狀態(tài)集中 self.st

19、atusnumber = value qu.put(number:self.statusnumber) else: # 已有狀態(tài) pass # 不作處理 def GOTO(self): # goto表 for i in range(len(self.status): self.gotoi = temp = self.GO(self.statusi) # 每個狀態(tài)的GO for vn in self.Vn: # 對非終結符遍歷 if vn in temp.keys(): # 非終結符存在于狀態(tài)的Go中 for key, value in self.status.items(): if set(v

20、alue) = set(tempvn): number = key # 記錄編號 break self.gotoivn = number else: self.gotoivn = 'error' def ACTION(self): vtx = copy.deepcopy(self.Vt) vtx.append('#') # 終結符加# for i in range(len(self.status): self.actioni = if len(self.statusi) = 1: # 項目集只有一個項目 if self.statusi0.startswith(&

21、#39;S'): # S->E· for vt in self.Vt: self.actionivt = 'error' self.actioni'#' = 'acc' else: # 填寫rj的項目 E->aA· temp = self.statusi0.rstrip('·') # 刪去項目的· E->aA for n in range(len(duction): if ductionn = temp: m = n+1 # 產生式在

22、G'中下標從1開始 break for vt in vtx: self.actionivt = 'r'+str(m) else: # 填寫Sj的項目 temp = self.GO(self.statusi) # 字典形式a:,b: for vt in vtx: if vt in temp.keys(): for key, value in self.status.items(): # 確定到哪一個狀態(tài) if set(value) = set(tempvt): number = key # 返回狀態(tài)編號 break self.actionivt = 'S'

23、+str(number) else: self.actionivt = 'error' def output(self): # 輸出LR(0)分析表 表格形式 print('LR(0)分析表'.center(85) print('狀態(tài)'.center(5), 'ACTION'.center(50), 'GOTO'.center(30) print(' '.center(10),end='') for vt in self.Vt: # action print(vt.center(10),end='') print('#'.center(10),end=''