构造一个与rs相对应的NFA： 构造一个与r | s 相对应的N FA：
4）构造与r *相对应的NFA：
（2）利用子集构造法将NFA转换成DFA
1) 状态集合的 Epsilon-闭包 我们将单个状态s的Epsilon-闭包定义为可由一系列的零个或多个Epsilon-转换能达到的状态集合。
2) 从开始状态开始，不断构造转换后等价状态集合的Epsilon-闭包，直到没有新的集合产生或者得到了全集。
三、算法设计与实现：
NFA和DFA实质上是有向图，可用以下结构体表示
#结点信息
class Node():
def __init__(self,v,f):
self.v = v #当前结点的出点
self.f = f #动作
class Graph():
def __init__(self):
self.e = [[]] #边
self.node_count =0 #结点数目
def addEdge(self,u,f): #加边
self.e[u].append(Node(v,f))
def addNode(self): #加点
self.e.append([])
self.node_count+= 1
returnself.node_count
#定义EPSILONG = ‘ε’
#基本表达式结构，只需要开始节点和结束状态，不用知道内部联系
class State():
self.entry =entry
self.exit = exit
#正则表达式到NFA类
class Re2NFA():
self.sIter =iter(ss + ' ')
self.g = Graph()
self.top = 0
self.token =self.sIter.next()
#生成NFA的方法，返回State和Graph
def generate(self):
self.state =self.P1()
if self.token !=' ':
error()
return self.state,self.g
def match(self,ch):
if(self.token !=ch):
#构造单个字符的NFA
def createAtom(self,0)"> A =self.g.addNode()
B =self.g.addNode()
self.g.addEdge(A,B,ch)
return State(A,B)
#重复
def rep(self,R):
global cstate
c1 =self.g.addNode()
c2 =self.g.addNode()
self.g.addEdge(c1,R.entry,EPSILON)
self.g.addEdge(R.exit,c2,0)"> self.g.addEdge(c1,0)"> return State(c1,c2)
#并置
def uni(self,R,S):
self.g.addEdge(S.exit,0)">#连接
def cat(self,0)"> returnState(R.entry,S.exit)
#递归下降分析法处理正则表达式的语法结构
def P1(self):
R = self.P2()
while(self.token== '|'):
self.match('|')
S = self.P2()
R =self.uni(R,S)
return R
def P2(self):
R = self.P3()
while(self.token.isalpha() orself.token.isdigit() or self.token == '('):
S = self.P3()
R =self.cat(R,0)"> def P3(self):
R = self.P4()
while(self.token== '*'):
self.match('*')
R = self.rep(R)
def P4(self):
if(self.token =='('):
self.match('(')
R = self.P1()
self.match(')')
elifself.token.isalpha() or self.token.isdigit():
R = self.createAtom(self.token)
self.match(self.token)
else: error()
# NFA转换成DFA的类
classNFA2DFA():
self.nfa = nfa
self.g = g
self.retg = Graph()
self.term = []
self.Q = []
#检查状态集合出现过没有如是出现过没有
def checkIn(self,cset,tset):
idx = 0
for ts in tset:
idx += 1
if cset == ts:
return idx
return 0
#获取状态集合的E-闭包
def getClosure(self,0)"> vis = [1 for i inxrange(self.g.node_count+1)]
mque = Queue.Queue()
for item in tset:
mque.put(item)
while not mque.empty():
v = mque.get()
vis[v] = 0
for node in self.g.e[v]:
print node.f == EPSILON
if node.f == EPSILON andvis[node.v] == 1:
tset.add(node.v)
mque.put(node.v)
print tset
#获取当前状态可转换到的所有状态集合
def getNextTrans(self,0)"> tdict = dict()
for node in self.g.e[item]:
if node.f == EPSILON:pass
else :
if nottdict.has_key(node.f):
tdict[node.f] = set()
tdict[node.f].add(node.v)
print tdict
for k,value in tdict.items():
self.getClosure(tdict[k])
return tdict
#生成NFA的方法返回Graph和终结状态列表
cur = 0
Q = []
Qset = set([self.nfa.entry])
self.getClosure(Qset)#获到开始状态的闭包
self.retg.addNode()
Q.append(Qset)#将开始状态的闭包加入到Q中
while cur < len(Q):#当Q中没有新的状态算法结束
nextdict =self.getNextTrans(Q[cur])#获取当前状态集合的转换状态集合
if self.nfa.exit in Q[cur]:#如果新状态集合包含终结符，则把该状态标志为终结状态
self.term.append(cur+1)
idx = self.checkIn(v,Q)
if idx == 0:
self.retg.addEdge(cur+1,self.retg.addNode(),k)
Q.append(v)
else:self.retg.addEdge(cur+1,idx,0)"> cur += 1
print Q
return self.retg,self.term
最后用Graphviz显示结果
#!/usr/bin/env python
# -*- coding:GBK -*-
import os
from nfa2dfa import Re2NFA
from nfa2dfa import NFA2DFA
def dfs(u):
vis[u] = 0
for node in e[u]:
fp.write("%d->%d[label="%s"];n"%(u,node.v,node.f))
if vis[node.v] == 1:
dfs(node.v)
ss = raw_input()
nfa,g = Re2NFA(ss).generate()
vis = []
for i in xrange(g.node_count+1):
vis.append(1)
e = g.e
fp = open('re2nfa.gv',"w")
fp.write("digraph G{nrankdir=LRn")
fp.write('edge [fontname="FangSong"];n')
dfs(nfa.entry)
fp.write("%d[style=filled,color=lightgrey];n"%(nfa.entry))
fp.write("%d[shape=doublecircle];n"%(nfa.exit));
fp.write("}n")
fp.close()
g,term= NFA2DFA(g,nfa).generate()
vis = []
for i in xrange(g.node_count+1):
vis.append(1)
e = g.e
fp = open('nfa2dfa.gv',"w")
fp.write("digraph E{nrankdir=LRn")
fp.write('edge [fontname="FangSong"];n')
fp.write("1[style=filled,color=lightgrey];n")
print "term",term
for it in term:
fp.write("%d[shape=doublecircle];n"%(it))
dfs(1)
fp.write("}n")
fp.close()
os.system("dot -Tpng re2nfa.gv -o re2nfa.png")
os.system("dot -Tpng nfa2dfa.gv -o nfa2dfa.png")
