@Python實作LR1文法
提示：合肥工業大學編譯原理實驗三，
文章目錄
- 一、使用步驟
- 1.引入庫（安裝Python環境、PyQt、PyQt-tools)
- 2.全域變數
- 3.完整代碼
- 4.運行結果截圖
- 5.學會自己看注釋
- 6.用資料代碼，為我愛的世界添磚加瓦
一、使用步驟
1.引入庫（安裝Python環境、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)#記錄各個終結符的產生式
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, 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)#記錄各個終結符的產生式
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 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):#沒出現過的終結符
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其實是指一個list
time += 1
else:
for vi in Firstlist:
Zlist.append(vi)
if(time == len(j)):
Zlist.append('ε')
return Zlist
def 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:
return
def 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 -> T\nT -> T * F\nT -> F\nF ->(E)\nF -> i")
#初始化，編譯原理測驗資料
#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#")
#初始化，編譯原理測驗資料
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("\t\t\tLR(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.用資料代碼，為我愛的世界添磚加瓦
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/190430.html
標籤：其他
上一篇：八數碼寬度優先極簡版