截图不想放了，我累了。python代码是正确的
【实验名称】 正规文法与有限自动机的转换
【实验目的】
从文件打开，若文本内为正规文法，则转化为有限自动机，若是合法自动机，则转化为正规文法。
【实验原理】
1.文法转自动机
（1）自动机的字母表与文法的终结符集相同。
（2）为文法中的每个非终结符生成自动机的一个状态，文法的开始符是S，自动机的开始状态S。
（3）增加一个新状态Z，作为自动机的终态。
（4）对文法中的形如A→aB的规则，构造自动机f（A，t）=B。
（5）对文法中形如A→t的产生式，构造自动机f（A，t）=Z。
-----------------------------------------------
2.自动机转文法
对自动机f（A，t）=B，可写成一个产生式：A→tB
对终止状态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的一个状态，G的开始符S是M的开始状态S。
（3）增加一个新状态Z，作为M的终态。
（4）对G中的形如A→tB的规则，构造M的一个转换函数f（A，t）=B。
（5）对G中形如A→t的产生式，构造M的一个转换函数f（A，t）=Z。
-----------------------------------------------
2.FA转RG
对转换函数f（A，t）=B，可写成一个产生式：A→tB
对可接受状态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.正规文法转自动机 2.自动机转正规文法
n=int(input('选择1.左线性RG转FA 2.FA转左线性RG\n'))
if n==1:
fp=open('grammar.txt','r')
print('读入的左线性正规文法为:')
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("输入无效")
网友评论