将正则表达式翻译成DFA的最简单算法是通过中间构造，在它之中，正则表达式派生出一个NFA，接着就用该NFA构造一个同等的DFA。。因此我们只关心两个算法：一个是将正则表达式翻译成N FA，另一个是将N FA翻译成D FA。构造一个扫描程序的自动过程可分为3步，如下所示：

(1)利用Thompson结构将正则表达式转换成NFA

1. 基本正则表达式 基本正则表达式格式a、 或，其中a表示字母表中单个字符的匹配，表示空串的匹配，而则表示根本不是串的匹配。与正则表达式a等同的NFA（即在其语言中 准确接受）的是：

2. 构造一个与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 + '\0')

   self.g = Graph()

   self.top = 0

   self.token =self.sIter.next()

   #生成NFA的方法，返回State和Graph

   def generate(self):

   self.state =self.P1()

   if self.token !='\0':

   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=LR\n")
   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=LR\n")
   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")