截圖不想放了，我累了。python代碼是正確的
【實驗名稱】?? ?????????????正規(guī)文法與有限自動機的轉換????
【實驗目的】
?從文件打開，若文本內為正規(guī)文法，則轉化為有限自動機，若是合法自動機，則轉化為正規(guī)文法。
【實驗原理】
?1.文法轉自動機
（1）自動機的字母表與文法的終結符集相同。
（2）為文法中的每個非終結符生成自動機的一個狀態(tài)，文法的開始符是S，自動機的開始狀態(tài)S。
（3）增加一個新狀態(tài)Z，作為自動機的終態(tài)。
（4）對文法中的形如A→aB的規(guī)則，構造自動機f（A，t）=B。
（5）對文法中形如A→t的產生式，構造自動機f（A，t）=Z。
-----------------------------------------------
2.自動機轉文法
對自動機f（A，t）=B，可寫成一個產生式：A→tB
對終止狀態(tài)Z，增加一個產生式：Z→ε
【實驗內容】
1.文法的分割（再上一次實驗中也有）
#按照“|”語法分割
def splitgram(gram,K,W):
??? length=len(gram)
??? left=''
??? index=0
??? while index<length:
??????? gramindex=gram[index]
??????? lens=len(gramindex)
??????? if gramindex[0] not in K:
??????????? K.append(gramindex[0])
??????????? del gram[index]
??????????? j=3
??????????? while j<lens:
??????????????? if gramindex[j]!='|':
??????????????????? left=left+gramindex[j]
??????????????? if gramindex[j]=='|':
??????????????????? strs=gramindex[0]+'->'+left
??????????????????? gram.insert(index,strs)
??????????????????? left=''
??????????????? j=j+1
??????????? if? left!='':
??????????????? strs=gramindex[0]+'->'+left
??????????????? gram.insert(index,strs)
??????????????? left=''
??????? index=index+1
??????? length=len(gram)
2.DFA的打印
def scangram(gram,K,W):
??? Kindex=0
??? Wdict=dict()
??? print('對應的DFA如下:')
??? while len(gram)>0:
??????? gram0=gram[0]
??????? if gram0[3] not in W:
??????????? W.append(gram0[3])
??????? if len(gram0)==5:
??????????? printres(gram0[0],gram0[3],gram0[4])
??????? else:
??????????? if gram0[3] in Wdict:
??????????????? strs=Wdict[gram0[3]]
??????????????? printres(gram0[0],gram0[3],strs)
??????????? else:
??????????????? strs=Klist[Kindex]
??????????????? Kindex=Kindex+1
??????????????? Wdict[gram0[3]]=strs
??????????????? printres(gram0[0],gram0[3],strs)
??????? del gram[0]
3.自動機轉文法
def splitFA(FA,Vt,Vn):
??? length=len(FA)
??? index=0
??? while index<length:
??????? FAindex=FA[index]
??????? if FAindex[2] not in Vt:
??????????? Vt.append(FAindex[2])
??????? del FA[index]
??????? left=FAindex[2]
??????? right=FAindex[4]+FAindex[7]
??????? strs=left+'->'+right
??????? FA.insert(index,strs)
??????? index=index+1
??????? length=len(FA)
#這時候的FA實際上已經由上一步存儲為文法了
def scanFA(FA,Vt,Vn):
??? length=len(FA)
??? index=0
??? while index<length:
??????? FAindex=FA[index]
??????? if FAindex[3] not in Vn:
??????????? Vn.append(FAindex[3])
??????? if len(FAindex)>4 and FAindex[4] not in Vt:
??????????? strs=FAindex[0]+'->'+FAindex[3]
??????????? del FA[index]
??????????? FA.insert(index,strs)
??????? else:
??????????? index=index+1
??????? length=len(FA)
4.合并文法中有相同終結符號的語句
def combineFA(FA):
??? length=len(FA)
??? indexi=0
??? while indexi<length:
??????? FAKi=FA[indexi][0]
??????? lens=len(FA[indexi])-3
??????? strsi=''
??????? for i in range(lens):
?????????? strsi=strsi+FA[indexi][3+i]
??????? indexj=0
??????? while indexj<length:
??????????? FAKj=FA[indexj][0]
??????????? if indexi!=indexj and FAKi==FAKj:
??????????????? lens=len(FA[indexj])-3
??????????????? strsj=''
??????????????? for j in range(lens):
??????????????????? strsj=strsj+FA[indexj][3+j]
??????????????? del FA[indexj]
??????????????? strs=FAKi+'->'+strsi+'|'+strsj
??????????????? del FA[indexi]
??????????????? FA.insert(indexi,strs)
??????????????? length=len(FA)
??????????????? lens=len(FA[indexi])-3
??????????????? strsi=''
??????????????? for i in range(lens):
??????????????????? strsi=strsi+FA[indexi][3+i]
??????????? else:
??????????????? indexj=indexj+1
??????? indexi=indexi+1
5.打印
def printFA(FA,Vt,Vn):
??? print('對應的左線性RG如下:')
??? length=len(FA)
??? for i in range(length):
??????? print(FA[i])
??? print('其中終結符集Vt為:')
??? print(Vt)
??? print('其中非終結符集Vn為:')
??? print(Vn)
【小結或討論】
這次的實驗和上課的要求還是有很多不一樣的，上課的要求比較高，要求進行自動機的確定化，最小化。在實驗中都使用了左線性文法，沒有考慮比較困難的情況。核心內容就是兩個部分的轉換：一個是形如“A->aB”到“f(A,a)=B”的轉換，另一個是自動機的讀取轉回為文法。
【實驗截圖】
[if !supportLists]1.? [endif]txt文件中的內容
[if !supportLists]2.? [endif]功能演示
[if !supportLists]3.? [endif]代碼
# -*- coding:
utf-8 -*-
"""
Created on Sat
May 25 20:55:21 2019
@author: 培風
"""
'''
1.RG轉FA
（1）M的字母表與G的終結符集相同。
（2）為G中的每個非終結符生成M的一個狀態(tài)，G的開始符S是M的開始狀態(tài)S。
（3）增加一個新狀態(tài)Z，作為M的終態(tài)。
（4）對G中的形如A→tB的規(guī)則，構造M的一個轉換函數f（A，t）=B。
（5）對G中形如A→t的產生式，構造M的一個轉換函數f（A，t）=Z。
-----------------------------------------------
2.FA轉RG
對轉換函數f（A，t）=B，可寫成一個產生式：A→tB
對可接受狀態(tài)Z，增加一個產生式：Z→ε
'''
Klist=['A']
#按照“|”語法分割
def splitgram(gram,K,W):
??? length=len(gram)
??? left=''
??? index=0
??? while index<length:
??????? gramindex=gram[index]
??????? lens=len(gramindex)
??????? if gramindex[0] not in K:
??????????? K.append(gramindex[0])
??????????? del gram[index]
??????????? j=3
??????????? while j<lens:
??????????????? if gramindex[j]!='|':
??????????????????? left=left+gramindex[j]
??????????????? if gramindex[j]=='|':
??????????????????? strs=gramindex[0]+'->'+left
??????????????????? gram.insert(index,strs)
??????????????????? left=''
??????????????? j=j+1
??????????? if? left!='':
??????????????? strs=gramindex[0]+'->'+left
??????????????? gram.insert(index,strs)
??????????????? left=''
??????? index=index+1
??????? length=len(gram)
#DFA打印為形如f(A,b)->B類型
def printres(X,Y,Z):
??? print('f(%s,%s)=%s'%(X,Y,Z))
#字典存儲打印DFA?
def scangram(gram,K,W):
??? Kindex=0
??? Wdict=dict()
??? print('對應的DFA如下:')
??? while len(gram)>0:
??????? gram0=gram[0]
??????? if gram0[3] not in W:
??????????? W.append(gram0[3])
??????? if len(gram0)==5:
??????????? printres(gram0[0],gram0[3],gram0[4])
??????? else:
??????????? if gram0[3] in Wdict:
??????????????? strs=Wdict[gram0[3]]
??????????????? printres(gram0[0],gram0[3],strs)
??????????? else:
??????????????? strs=Klist[Kindex]
??????????????? Kindex=Kindex+1
??????????????? Wdict[gram0[3]]=strs
??????????????? printres(gram0[0],gram0[3],strs)
??????? del gram[0]
#列表存儲自動機“f(S,a)=A”???????????????
def splitFA(FA,Vt,Vn):
??? length=len(FA)
??? index=0
??? while index<length:
??????? FAindex=FA[index]
??????? if FAindex[2] not in Vt:
??????????? Vt.append(FAindex[2])
??????? del FA[index]
??????? left=FAindex[2]
??????? right=FAindex[4]+FAindex[7]
??????? strs=left+'->'+right
??????? FA.insert(index,strs)
??????? index=index+1
??????? length=len(FA)
#這時候的FA實際上已經由上一步存儲為文法了
def scanFA(FA,Vt,Vn):
??? length=len(FA)
??? index=0
??? while index<length:
??????? FAindex=FA[index]
??????? if FAindex[3] not in Vn:
??????????? Vn.append(FAindex[3])
??????? if len(FAindex)>4 and FAindex[4] not in Vt:
??????????? strs=FAindex[0]+'->'+FAindex[3]
??????????? del FA[index]
??????????? FA.insert(index,strs)
??????? else:
??????????? index=index+1
??????? length=len(FA)
#合并有相同非終結符的
def combineFA(FA):
??? length=len(FA)
??? indexi=0
??? while indexi<length:
??????? FAKi=FA[indexi][0]
??????? lens=len(FA[indexi])-3
??????? strsi=''
??????? for i in range(lens):
?????????? strsi=strsi+FA[indexi][3+i]
??????? indexj=0
??????? while indexj<length:
??????????? FAKj=FA[indexj][0]
??????????? if indexi!=indexj and FAKi==FAKj:
??????????????? lens=len(FA[indexj])-3
??????????????? strsj=''
??????????????? for j in range(lens):
??????????????????? strsj=strsj+FA[indexj][3+j]
??????????????? del FA[indexj]
??????????????? strs=FAKi+'->'+strsi+'|'+strsj
??????????????? del FA[indexi]
??????????????? FA.insert(indexi,strs)
??????????????? length=len(FA)
??????????????? lens=len(FA[indexi])-3
??????????????? strsi=''
??????????????? for i in range(lens):a
??????????????????? strsi=strsi+FA[indexi][3+i]
??????????? else:
??????????????? indexj=indexj+1
??????? indexi=indexi+1
#打印自動機
def printFA(FA,Vt,Vn):
??? print('對應的左線性RG如下:')
??? length=len(FA)
??? for i in range(length):
??????? print(FA[i])
??? print('其中終結符集Vt為:')
??? print(Vt)
??? print('其中非終結符集Vn為:')
??? print(Vn)
#功能選擇：1.正規(guī)文法轉自動機 2.自動機轉正規(guī)文法
n=int(input('選擇1.左線性RG轉FA 2.FA轉左線性RG\n'))
if n==1:
??? fp=open('grammar.txt','r')
??? print('讀入的左線性正規(guī)文法為:')
??? gram=[]
??? while True:
??????? line=fp.readline()
??????? line=line.strip('\n')
??????? if line=='':
??????????? break
??????? else:
??????????? gram.append(line)
??????????? print(line)
??? K=[] #終結符
??? W=[] #非終結符
??? splitgram(gram,K,W)
??? scangram(gram,K,W) #打印DFA
??? print('其中終結符集K為:')
??? print(K)
??? print('其中非終結符集W為:')
??? print(W)
elif n==2:
??? fp=open('FA.txt','r')
??? print('讀入的FA為:')
??? FA=[]
??? while True:
??????? line=fp.readline()
??????? line=line.strip('\n')
??????? if line=='':
??????????? break
??????? else:
??????????? FA.append(line)
??????????? print(line)
??? Vt=[]
??? Vn=[]
??? splitFA(FA,Vt,Vn)
??? scanFA(FA,Vt,Vn)
??? combineFA(FA)
??? printFA(FA,Vt,Vn)
else:
??? print("輸入無效")
