Python實現LR1文法的完整實例代碼

一、使用步驟

1.引入庫（安裝Python環境、PyQt、PyQt-tools)

from PyQt5 import QtCore, QtGui, QtWidgetsimport sysimport datetimefrom PyQt5.QtGui import QStandardItemModel, QStandardItemfrom PyQt5.QtWidgets import QHeaderViewfrom collections import defaultdictimport numpy as np

2.全局變量

#text = 'E -> E + T nE -> TnT -> T * FnT -> FnF ->(E)nF -> i'#text = 'S -> BBnB -> aBnB -> b'my_dict = defaultdict(list)#記錄各個終結符的產生式my_dicts = defaultdict(list)#代表每組項目，暫時存儲VNT = []VT = set([])MAX = 50 #生成最多的項目集個數Inum = 0 #記錄項目集的個數end = [] #記錄，上一個狀態數，通過的字符，下一個狀態數[最終結果]numset = []#列表，修訂狀態數 endstate = [] #最終存儲項目集鏃 [最終結果]guiyue = [] #記錄每條文法

3.完整代碼

# -*- coding: utf-8 -*-# Form implementation generated from reading ui file ’LR1.ui’## Created by: PyQt5 UI code generator 5.15.1## WARNING: Any manual changes made to this file will be lost when pyuic5 is# run again. Do not edit this file unless you know what you are doing.from PyQt5 import QtCore, QtGui, QtWidgetsimport sysimport datetimefrom PyQt5.QtGui import QStandardItemModel, QStandardItemfrom PyQt5.QtWidgets import QHeaderViewfrom collections import defaultdictimport numpy as np#text = 'E -> E + T nE -> TnT -> T * FnT -> FnF ->(E)nF -> i'#text = 'S -> BBnB -> aBnB -> b'my_dict = defaultdict(list)#記錄各個終結符的產生式my_dicts = defaultdict(list)#代表每組項目，暫時存儲VNT = []VT = set([])MAX = 50 #生成最多的項目集個數Inum = 0 #記錄項目集的個數end = [] #記錄，上一個狀態數，通過的字符，下一個狀態數[最終結果]numset = []#列表，修訂狀態數 endstate = [] #最終存儲項目集鏃 [最終結果]guiyue = [] #記錄每條文法def isTerminal(c): # 若c介于A-Z之間則認為是非終結符(注意添加 self參數) if c < ’A’ or c > ’Z’: return True else: return Falsedef SplitText(text): # 把文法中E->A|B 切分為E->A和E->B mytext = '' for i in text: if(i != ’ ’):#刪除字符串的空格 mytext += i; i = mytext.split(’n’) guiyue.append(text[0]+'’->'+text[0]) for j in i: if(VNT.count(j[0])==0):#沒出現過的終結符 VNT.append(j[0]) for k in range(1,len(j)): if(j[k]==’-’ and j[k+1]==’>’): k = k+2 break guiyue.append(j) my_dict[j[0]].append(j[k:])def getFirst(mylist):#計算目標字符串的Frist集 Zlist = [] for i in mylist: if(i not in VNT): Zlist.append(i) return Zlist else: for j in my_dict[i]: #遍歷非終結符的產生式 #print(j) if(j[0] == i): continue time = 0 for ch in j: if(ch not in VNT): Zlist.append(ch) break else: Firstlist = getFirst(ch)#遞歸得到Frist集 if ’ε’ in Firstlist: # Firstlist其實是指一個listtime += 1 else: for vi in Firstlist:Zlist.append(vi) if(time == len(j)): Zlist.append(’ε’) return Zlistdef getSymbol(mystr):#根據Frist集得到下一個狀態的展望符 for i in range(0,len(mystr)): if(mystr[i] ==’.’): mylist = list(mystr[i+2:]) break Zlist = [’#’] if(mylist[0]==’,’): mylist = mylist[1:] if(mylist[0]==’#’): VT.add(’#’) return Zlist a = getFirst(mylist) VT.update(set(a)) return a #存儲展望符#print(getSymbol(’E->.E+T,#’))#驗證展望符是否正確def CLOSURE(mystr,num): #用于項目集內容的補充 my_dicts[num].append(mystr) #先加上它本身 zhanwang = getSymbol(mystr)#再計算展望符 for i in range(0,len(mystr)): if(mystr[i] ==’.’): ch = mystr[i+1] if(ch in VNT): for j in range(0,len(my_dict[ch])): ch2 = my_dict[ch][j] for k in range(0,len(zhanwang)): mystr = ch+'->.'+ch2+','+zhanwang[k] if(my_dicts[num].count(mystr)==0): my_dicts[num].append(mystr) if(ch2[0] in VNT): for ss in my_dict[ch2[0]]: zhanwangs = getSymbol(mystr) for kk in range(0,len(zhanwangs)): mystr2 = ch2[0]+'->.'+ss+','+zhanwangs[kk] if(my_dicts[num].count(mystr2)==0):CLOSURE(mystr2,num) else: returndef deleteI(delnum): #刪除重復狀態 for i in delnum: del my_dicts[i] def DFA(mynum): newstr = [] command = dict() global Inum for fs in my_dicts[mynum]: #用字典存儲 目標字符和狀態集序號 for i in range(0,len(fs)): if(fs[i]==’.’): if(fs[i+1]==’,’): break else: if(newstr.count(fs[i+1])==0): newstr.append(fs[i+1]) Inum += 1 command[fs[i+1]] = Inum for fs in my_dicts[mynum]: for i in range(0,len(fs)): if(fs[i]==’.’): if(fs[i+1]==’,’): break else: mynums = command[fs[i+1]] s1 = list(fs) s1[i] = s1[i+1] s1[i+1]=’.’ sq = ’’.join(s1) #巧妙實現字符串的替換 CLOSURE(sq,mynums) #生成新的狀態集 #print(command) delnum = [] for key,value in command.items(): for j in range(0,value): if(set(my_dicts[j]) == set(my_dicts[value])): command[key] = j #修改狀態序號 delnum.append(value) #print(delnum) deleteI(delnum) for key,value in command.items(): #print(mynum,’(’,key,’)->’,value) end.append([mynum,key,value]) numset.append(mynum) numset.append(value) #利用集合特性，修訂狀態數 class Ui_Form(object): def setupUi(self, Form): Form.setObjectName('Form') Form.resize(994, 824) self.textBrowser = QtWidgets.QTextBrowser(Form) self.textBrowser.setGeometry(QtCore.QRect(520, 770, 461, 51)) self.textBrowser.setObjectName('textBrowser') self.textBrowser_2 = QtWidgets.QTextBrowser(Form) self.textBrowser_2.setGeometry(QtCore.QRect(25, 771, 421, 41)) self.textBrowser_2.setObjectName('textBrowser_2') self.label = QtWidgets.QLabel(Form) self.label.setGeometry(QtCore.QRect(460, 770, 51, 41)) self.label.setObjectName('label') self.tabWidget = QtWidgets.QTabWidget(Form) self.tabWidget.setGeometry(QtCore.QRect(20, 240, 941, 521)) self.tabWidget.setObjectName('tabWidget') self.First = QtWidgets.QWidget() self.First.setAccessibleName('') self.First.setObjectName('First') self.tableView = QtWidgets.QTableView(self.First) self.tableView.setGeometry(QtCore.QRect(10, 10, 911, 471)) self.tableView.setObjectName('tableView') self.tabWidget.addTab(self.First, '') self.Analyse = QtWidgets.QWidget() self.Analyse.setObjectName('Analyse') self.tableView_2 = QtWidgets.QTableView(self.Analyse) self.tableView_2.setGeometry(QtCore.QRect(10, 10, 911, 471)) self.tableView_2.setObjectName('tableView_2') self.tabWidget.addTab(self.Analyse, '') self.Process = QtWidgets.QWidget() self.Process.setObjectName('Process') self.tableView_3 = QtWidgets.QTableView(self.Process) self.tableView_3.setGeometry(QtCore.QRect(10, 10, 911, 471)) self.tableView_3.setObjectName('tableView_3') self.tabWidget.addTab(self.Process, '') self.States = QtWidgets.QWidget() self.States.setObjectName('States') self.textBrowser_3 = QtWidgets.QTextBrowser(self.States) self.textBrowser_3.setGeometry(QtCore.QRect(10, 10, 911, 471)) self.textBrowser_3.setObjectName('textBrowser_3') self.tabWidget.addTab(self.States, '') self.label_2 = QtWidgets.QLabel(Form) self.label_2.setGeometry(QtCore.QRect(40, 10, 51, 41)) self.label_2.setObjectName('label_2') self.textEdit = QtWidgets.QTextEdit(Form) self.textEdit.setGeometry(QtCore.QRect(33, 46, 441, 181)) self.textEdit.setObjectName('textEdit') self.textEdit.setText('E -> E + T nE -> TnT -> T * FnT -> FnF ->(E)nF -> i') #初始化，編譯原理測試數據 #self.textEdit.setText('S -> BBnB -> aBnB -> b') self.lineEdit = QtWidgets.QLineEdit(Form) self.lineEdit.setGeometry(QtCore.QRect(640, 200, 271, 41)) self.lineEdit.setObjectName('lineEdit') self.lineEdit.setText('i*i+i#') #初始化，編譯原理測試數據 self.label_3 = QtWidgets.QLabel(Form) self.label_3.setGeometry(QtCore.QRect(550, 200, 81, 41)) self.label_3.setObjectName('label_3') self.pushButton = QtWidgets.QPushButton(Form) self.pushButton.setGeometry(QtCore.QRect(650, 110, 251, 71)) self.pushButton.setObjectName('pushButton') self.pushButton.clicked.connect(self.Runs) # 將按鈕與函數Runs()綁定,啟動主程序 self.retranslateUi(Form) self.tabWidget.setCurrentIndex(0) QtCore.QMetaObject.connectSlotsByName(Form) def retranslateUi(self, Form): _translate = QtCore.QCoreApplication.translate Form.setWindowTitle(_translate('Form', 'LR(1)文法')) self.label.setText(_translate('Form', '分 析：')) self.tabWidget.setTabText(self.tabWidget.indexOf(self.First), _translate('Form', 'FIRST集')) self.tabWidget.setTabText(self.tabWidget.indexOf(self.Analyse), _translate('Form', '分 析 表')) self.tabWidget.setTabText(self.tabWidget.indexOf(self.Process), _translate('Form', '分 析 過 程')) self.tabWidget.setTabText(self.tabWidget.indexOf(self.States), _translate('Form', '項 目 集 族')) self.label_2.setText(_translate('Form', '文 法：')) self.label_3.setText(_translate('Form', '輸 入 框')) self.pushButton.setText(_translate('Form', '運 行 程 序')) def Runs(self): global VNT,VT,numset,Inum,endstate,guiyue,my_dict,my_dicts,end#初始化 Inum = 0 #記錄項目集的個數 my_dict = defaultdict(list)#記錄各個終結符的產生式 my_dicts = defaultdict(list)#代表每組項目，暫時存儲 VNT = [] VT = set([]) end = [] #記錄，上一個狀態數，通過的字符，下一個狀態數 numset = []#列表，修訂狀態數 [最終結果] endstate = [] #最終存儲項目集鏃 [最終結果] guiyue = [] #記錄每條文法 times = datetime.datetime.now() times_str = times.strftime(’ %Y-%m-%d %H:%M:%S’) self.textBrowser_2.setText(’運 行 時 間：’+times_str) text = self.textEdit.toPlainText() SplitText(text)#1 處理文法 input0 = text[0]+'’->.'+text[0]+’,#’ #輸入第一個項目 CLOSURE(input0,0) #2 生成I0項目集 for i in range(0,MAX): DFA(i) numset = list(set(numset))#3 消除重復元素 for i in end:#4 修訂狀態過程 i[0] = numset.index(i[0]) i[2] = numset.index(i[2]) for i in range(0,len(my_dicts)): if my_dicts[i] != []: endstate.append(my_dicts[i])#5 將修訂后的項目集族寫入新的列表 #將項目集族寫入圖形界面 self.textBrowser_3.setText('tttLR(1)項 目 集 族n') j = 0 for i in endstate: self.textBrowser_3.append(’I’+str(j)+’: ’+str(i)+’n’) j += 1 #將Frist集寫入圖形界面 self.model = QStandardItemModel(len(VNT), 5) label_y = [] for s in VNT: label_y.append(s) self.model.setVerticalHeaderLabels(label_y) for row in range(len(VNT)): flist = [VNT[row]]#First集要輸入一個列表 Flist = list(set(getFirst(flist))) for column in range(len(Flist)): item = QStandardItem(Flist[column]) self.model.setItem(row, column, item) self.tableView.horizontalHeader().setStretchLastSection(True) self.tableView.horizontalHeader().setSectionResizeMode(QHeaderView.Stretch) self.tableView.setModel(self.model) #構造分析表，寫入圖形界面 VT.discard(’#’) VT = list(VT) #先刪除# VT.append(’#’)#想讓#在ACTION表最后一列 label_x = [’狀 態’]+VT+VNT self.model2 = QStandardItemModel(len(endstate),len(VNT)+len(VT)) self.model2.setHorizontalHeaderLabels(label_x) label_y = [] for i in range(0,len(endstate)): label_y.append(str(i)) self.model2.setVerticalHeaderLabels(label_y) ACTION = [[’0’] * len(VT) for i in range(len(endstate))] #存儲分析表內容，為分析過程做準備 GOTO = [[’0’] * len(VNT) for i in range(len(endstate))] for q in end: #移進動作 if(q[1] not in VNT): ss = ’s’+str(q[2]) ACTION[int(q[0])][VT.index(q[1])] = ss else: ss = str(q[2]) GOTO[int(q[0])][VNT.index(q[1])] = ss item = QStandardItem(ss) self.model2.setItem(int(q[0]),label_x.index(q[1]),item) endstr = text[0]+'’->'+text[0]+’.,#’ #終結標志 for i in range(len(endstate)):#規約動作 for j in range(len(endstate[i])): for k in range(len(endstate[i][j])): if(endstate[i][j][k]==’.’): if(endstate[i][j][k+1]== ’,’): #print(guiyue) ii = guiyue.index(endstate[i][j][:k]) item = QStandardItem('r'+str(ii)) ACTION[i][VT.index(endstate[i][j][k+2])] = 'r'+str(ii) self.model2.setItem(i,label_x.index(endstate[i][j][k+2]),item) if(endstate[i][0] == endstr): item = QStandardItem('acc')#結束 self.model2.setItem(i,label_x.index(’#’),item) self.tableView_2.horizontalHeader().setStretchLastSection(True) self.tableView_2.horizontalHeader().setSectionResizeMode(QHeaderView.Stretch) self.tableView_2.setModel(self.model2) self.model3 = QStandardItemModel(32,4) #print(ACTION) #print(GOTO) mystate = [0]#狀 態 stack = ’#’ #符 號 inputstr = self.lineEdit.text()#輸 入 串 label_x = [’狀 態’, ’符 號’, ’輸 入 串’, ’動 作’] self.model3.setHorizontalHeaderLabels(label_x) tabnum = 0 while(1): self.model3.setItem(tabnum,0,QStandardItem(str(mystate))) self.model3.setItem(tabnum,1,QStandardItem(stack)) self.model3.setItem(tabnum,2,QStandardItem(inputstr)) tabnum += 1 if(inputstr[0] not in VT): self.textBrowser.setText(’報 錯！’) else: ch = ACTION[mystate[-1]][VT.index(inputstr[0])]#讀取action值 if(ch ==’r0’):#本質就是acc self.textBrowser.setText(’分 析 成 功！’) break if(ch == ’0’): self.textBrowser.setText(’報 錯！’) break if(ch[0] == ’s’): mystate.append(int(ch[1:]))#狀態加一個 stack += inputstr[0]#移進 inputstr = inputstr[1:]#相當于刪除第一個元素 if(ch[0] == ’r’): gylist = guiyue[int(ch[1:])].split(’->’) g1 = str(gylist[1])[::-1] g0 = str(gylist[0])[::-1] gstack = stack[::-1]#逆序解決規約問題 gstack = gstack.replace(g1,g0,1) stack = gstack[::-1]#完成規約任務 strlen = len(gylist[1]) #計算長度 for i in range(strlen): mystate.pop()#連續出棧 mystate.append(int(GOTO [mystate[-1]] [VNT.index(gylist[0])] )) self.tableView_3.horizontalHeader().setStretchLastSection(True) self.tableView_3.horizontalHeader().setSectionResizeMode(QHeaderView.Stretch) self.tableView_3.setModel(self.model3)if __name__ == '__main__': app = QtWidgets.QApplication(sys.argv) Form = QtWidgets.QWidget() ui = Ui_Form() ui.setupUi(Form) Form.show() sys.exit(app.exec_())

4.運行結果截圖

5.學會自己看注釋

6.用數據代碼，為我愛的世界添磚加瓦

到此這篇關于Python實現LR1文法的文章就介紹到這了,更多相關Python實現LR1文法內容請搜索好吧啦網以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持好吧啦網！