Python實(shí)現(xiàn)LR1文法的完整實(shí)例代碼
更新時間：2020年10月25日 15:53:43 作者：計(jì)算機(jī)_小萌新
這篇文章主要給大家介紹了關(guān)于Python實(shí)現(xiàn)LR1文法的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
一、使用步驟
1.引入庫（安裝Python環(huán)境、PyQt、PyQt-tools)
from PyQt5 import QtCore, QtGui, QtWidgets import sys import datetime from PyQt5.QtGui import QStandardItemModel, QStandardItem from PyQt5.QtWidgets import QHeaderView from collections import defaultdict import numpy as np
2.全局變量
#text = "E -> E + T \nE -> T\nT -> T * F\nT -> F\nF ->(E)\nF -> i" #text = "S -> BB\nB -> aB\nB -> b" my_dict = defaultdict(list)#記錄各個終結(jié)符的產(chǎn)生式 my_dicts = defaultdict(list)#代表每組項(xiàng)目，暫時存儲 VNT = [] VT = set([]) MAX = 50 #生成最多的項(xiàng)目集個數(shù) Inum = 0 #記錄項(xiàng)目集的個數(shù) end = [] #記錄，上一個狀態(tài)數(shù)，通過的字符，下一個狀態(tài)數(shù)[最終結(jié)果] numset = []#列表，修訂狀態(tài)數(shù) endstate = [] #最終存儲項(xiàng)目集鏃 [最終結(jié)果] 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, QtWidgets
import sys
import datetime
from PyQt5.QtGui import QStandardItemModel, QStandardItem
from PyQt5.QtWidgets import QHeaderView
from collections import defaultdict
import numpy as np
#text = "E -> E + T \nE -> T\nT -> T * F\nT -> F\nF ->(E)\nF -> i"
#text = "S -> BB\nB -> aB\nB -> b"
my_dict = defaultdict(list)#記錄各個終結(jié)符的產(chǎn)生式
my_dicts = defaultdict(list)#代表每組項(xiàng)目，暫時存儲
VNT = []
VT = set([])
MAX = 50 #生成最多的項(xiàng)目集個數(shù)
Inum = 0 #記錄項(xiàng)目集的個數(shù)
end = [] #記錄，上一個狀態(tài)數(shù)，通過的字符，下一個狀態(tài)數(shù)[最終結(jié)果]
numset = []#列表，修訂狀態(tài)數(shù)
endstate = [] #最終存儲項(xiàng)目集鏃 [最終結(jié)果]
guiyue = [] #記錄每條文法
def isTerminal(c): # 若c介于A-Z之間則認(rèn)為是非終結(jié)符(注意添加 self參數(shù))
if c < 'A' or c > 'Z':
return True
else:
return False
def 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):#沒出現(xiàn)過的終結(jié)符
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):#計(jì)算目標(biāo)字符串的Frist集
Zlist = []
for i in mylist:
if(i not in VNT):
Zlist.append(i)
return Zlist
else:
for j in my_dict[i]: #遍歷非終結(jié)符的產(chǎn)生式
#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其實(shí)是指一個list
time += 1
else:
for vi in Firstlist:
Zlist.append(vi)
if(time == len(j)):
Zlist.append('ε')
return Zlist
def getSymbol(mystr):#根據(jù)Frist集得到下一個狀態(tài)的展望符
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,#'))#驗(yàn)證展望符是否正確
def CLOSURE(mystr,num): #用于項(xiàng)目集內(nèi)容的補(bǔ)充
my_dicts[num].append(mystr) #先加上它本身
zhanwang = getSymbol(mystr)#再計(jì)算展望符
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:
return
def deleteI(delnum): #刪除重復(fù)狀態(tài)
for i in delnum:
del my_dicts[i]
def DFA(mynum):
newstr = []
command = dict()
global Inum
for fs in my_dicts[mynum]: #用字典存儲 目標(biāo)字符和狀態(tài)集序號
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) #巧妙實(shí)現(xiàn)字符串的替換
CLOSURE(sq,mynums) #生成新的狀態(tài)集
#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 #修改狀態(tài)序號
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) #利用集合特性，修訂狀態(tài)數(shù)
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 -> T\nT -> T * F\nT -> F\nF ->(E)\nF -> i")
#初始化，編譯原理測試數(shù)據(jù)
#self.textEdit.setText("S -> BB\nB -> aB\nB -> 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#")
#初始化，編譯原理測試數(shù)據(jù)
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) # 將按鈕與函數(shù)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", "項(xiàng) 目 集 族"))
self.label_2.setText(_translate("Form", "文 法："))
self.label_3.setText(_translate("Form", "輸 入 框"))
self.pushButton.setText(_translate("Form", "運(yùn) 行 程 序"))
def Runs(self):
global VNT,VT,numset,Inum,endstate,guiyue,my_dict,my_dicts,end#初始化
Inum = 0 #記錄項(xiàng)目集的個數(shù)
my_dict = defaultdict(list)#記錄各個終結(jié)符的產(chǎn)生式
my_dicts = defaultdict(list)#代表每組項(xiàng)目，暫時存儲
VNT = []
VT = set([])
end = [] #記錄，上一個狀態(tài)數(shù)，通過的字符，下一個狀態(tài)數(shù)
numset = []#列表，修訂狀態(tài)數(shù) [最終結(jié)果]
endstate = [] #最終存儲項(xiàng)目集鏃 [最終結(jié)果]
guiyue = [] #記錄每條文法
times = datetime.datetime.now()
times_str = times.strftime(' %Y-%m-%d %H:%M:%S')
self.textBrowser_2.setText('運(yùn) 行 時 間：'+times_str)
text = self.textEdit.toPlainText()
SplitText(text)#1 處理文法
input0 = text[0]+"'->."+text[0]+',#' #輸入第一個項(xiàng)目
CLOSURE(input0,0) #2 生成I0項(xiàng)目集
for i in range(0,MAX):
DFA(i)
numset = list(set(numset))#3 消除重復(fù)元素
for i in end:#4 修訂狀態(tài)過程
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 將修訂后的項(xiàng)目集族寫入新的列表
#將項(xiàng)目集族寫入圖形界面
self.textBrowser_3.setText("\t\t\tLR(1)項(xiàng) 目 集 族\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)
#構(gòu)造分析表，寫入圖形界面
VT.discard('#')
VT = list(VT) #先刪除#
VT.append('#')#想讓#在ACTION表最后一列
label_x = ['狀 態(tài)']+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))] #存儲分析表內(nèi)容，為分析過程做準(zhǔn)備
GOTO = [['0'] * len(VNT) for i in range(len(endstate))]
for q in end: #移進(jìn)動作
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]+'.,#' #終結(jié)標(biāo)志
for i in range(len(endstate)):#規(guī)約動作
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")#結(jié)束
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]#狀 態(tài)
stack = '#' #符 號
inputstr = self.lineEdit.text()#輸 入 串
label_x = ['狀 態(tài)', '符 號', '輸 入 串', '動 作']
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('報(bào) 錯！')
else:
ch = ACTION[mystate[-1]][VT.index(inputstr[0])]#讀取action值
if(ch =='r0'):#本質(zhì)就是acc
self.textBrowser.setText('分 析 成 功！')
break
if(ch == '0'):
self.textBrowser.setText('報(bào) 錯！')
break
if(ch[0] == 's'):
mystate.append(int(ch[1:]))#狀態(tài)加一個
stack += inputstr[0]#移進(jìn)
inputstr = inputstr[1:]#相當(dāng)于刪除第一個元素
if(ch[0] == 'r'):
gylist = guiyue[int(ch[1:])].split('->')
g1 = str(gylist[1])[::-1]
g0 = str(gylist[0])[::-1]
gstack = stack[::-1]#逆序解決規(guī)約問題
gstack = gstack.replace(g1,g0,1)
stack = gstack[::-1]#完成規(guī)約任務(wù)
strlen = len(gylist[1]) #計(jì)算長度
for i in range(strlen):
mystate.pop()#連續(xù)出棧
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.運(yùn)行結(jié)果截圖
5.學(xué)會自己看注釋
6.用數(shù)據(jù)代碼，為我愛的世界添磚加瓦
到此這篇關(guān)于Python實(shí)現(xiàn)LR1文法的文章就介紹到這了,更多相關(guān)Python實(shí)現(xiàn)LR1文法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Python獲取江蘇疫情實(shí)時數(shù)據(jù)及爬蟲分析
為了關(guān)注疫情狀況，今天我們用python來爬一爬疫情的實(shí)時數(shù)據(jù)，本文通過實(shí)例圖文相結(jié)合給大家介紹的非常詳細(xì)，需要的朋友參考下吧2021-08-08
在Python中，繪圖是一個非常有趣的領(lǐng)域，其中比較流行的繪圖庫就有?Turtle，所以本文就來講講如何在Python中使用它來創(chuàng)建和修改圖形，需要的可以參考一下2023-06-06
Python爬蟲采集Tripadvisor數(shù)據(jù)案例實(shí)現(xiàn)
這篇文章主要為大家介紹了Python爬蟲采集Tripadvisor數(shù)據(jù)案例實(shí)現(xiàn)，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-06-06
Python SELENIUM上傳文件或圖片實(shí)現(xiàn)過程
這篇文章主要介紹了Python SELENIUM上傳文件或圖片實(shí)現(xiàn)過程,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-10-10
Python函數(shù)實(shí)現(xiàn)學(xué)員管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了Python函數(shù)實(shí)現(xiàn)學(xué)員管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-07-07
python實(shí)現(xiàn)文件路徑和url相互轉(zhuǎn)換的方法
這篇文章主要介紹了python實(shí)現(xiàn)文件路徑和url相互轉(zhuǎn)換的方法,以URL轉(zhuǎn)換成文件路徑為例分析了Python實(shí)現(xiàn)地址轉(zhuǎn)換的技巧,需要的朋友可以參考下2015-07-07
python使用paramiko模塊實(shí)現(xiàn)ssh遠(yuǎn)程登陸上傳文件并執(zhí)行
使用paramiko，ssh遠(yuǎn)程登陸，長傳文件并執(zhí)行。其中用到了多線程和隊(duì)列,paramiko是用python語言寫的一個模塊，遵循SSH2協(xié)議，支持以加密和認(rèn)證的方式，進(jìn)行遠(yuǎn)程服務(wù)器的連接。2014-01-01
這篇文章主要介紹了python查看FTP是否能連接成功的方法,實(shí)例分析了Python連接FTP的相關(guān)技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-07-07
python 如何用map()函數(shù)創(chuàng)建多線程任務(wù)
這篇文章主要介紹了python 使用map()函數(shù)創(chuàng)建多線程任務(wù)的操作，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-04-04
利用Python+Selenium破解春秋航空網(wǎng)滑塊驗(yàn)證碼的實(shí)戰(zhàn)過程
本文給大家介紹使用Python+Selenium破解春秋航空網(wǎng)滑塊驗(yàn)證碼的實(shí)戰(zhàn)過程，本文通過圖文實(shí)例相結(jié)合給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友參考下吧2021-08-08