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)#代表每組項目，暫時存儲
VNT = []
VT = set([])
MAX = 50 #生成最多的項目集個數(shù)
Inum = 0 #記錄項目集的個數(shù)
end = [] #記錄，上一個狀態(tài)數(shù)，通過的字符，下一個狀態(tài)數(shù)[最終結(jié)果]
numset = []#列表，修訂狀態(tài)數(shù) 
endstate = [] #最終存儲項目集鏃 [最終結(jié)果]
guiyue = [] #記錄每條文法

# -*- 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)#代表每組項目，暫時存儲
VNT = []
VT = set([])
MAX = 50 #生成最多的項目集個數(shù)
Inum = 0 #記錄項目集的個數(shù)
end = [] #記錄，上一個狀態(tài)數(shù)，通過的字符，下一個狀態(tài)數(shù)[最終結(jié)果]
numset = []#列表，修訂狀態(tài)數(shù) 
endstate = [] #最終存儲項目集鏃 [最終結(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):#計算目標(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其實是指一個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,#'))#驗證展望符是否正確

def CLOSURE(mystr,num): #用于項目集內(nèi)容的補(bǔ)充
 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): #刪除重復(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) #巧妙實現(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", "項 目 集 族"))
  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 #記錄項目集的個數(shù)
  my_dict = defaultdict(list)#記錄各個終結(jié)符的產(chǎn)生式
  my_dicts = defaultdict(list)#代表每組項目，暫時存儲
  VNT = []
  VT = set([])
  end = [] #記錄，上一個狀態(tài)數(shù)，通過的字符，下一個狀態(tài)數(shù)
  numset = []#列表，修訂狀態(tài)數(shù) [最終結(jié)果]
  endstate = [] #最終存儲項目集鏃 [最終結(jié)果]
  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 消除重復(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 將修訂后的項目集族寫入新的列表
  #將項目集族寫入圖形界面
  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)
  #構(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('報 錯！')
   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('報 錯！')
    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]) #計算長度
    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_())