woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

NFA DFA Regex

要深入了解正则表达式,必须首先理解有穷自动机。

有穷自动机(Finite Automate)是用来模拟实物系统的数学模型,它包括如下五个部分:

  • 有穷状态集States
  • 输入字符集Input symbols
  • 转移函数Transitions
  • 起始状态Start state
  • 接受状态Accepting state(s)


下图为一台有穷自动机
clip_image001

可以看到,该自动机包含四个状态q0, q1, q2, q3,两个输入字符a, b,转移函数如图所示,起始状态为q0,接受状态为q3

有穷自动机,按照转移函数的不同,又可分为确定型有穷自动机(Determinism Finite Automate, DFA),与非确定型有穷自动机(Non-determinism Finite Automate, NFA)。
非确定有穷自动机容许转移函数不确定,换句话说,对任意状态,输入任意一个字符,可以转移到0个,1个或者多个状态。
下图是一台非确定有穷自动机,可以看到,对状态q0输入字符a,既可以转移到q0,也可以转移到q1,这就是非确定的意义所在。
clip_image002


对某个自动机来说,如果从起始状态,接受一系列输入字符,可以转移到接受状态,即认为这一系列字符可以被自动机接受。

如果两台自动机能够接受的输入字符串(或者叫做正则语言”Regular Language)完全相同,则这两台自动机是等价的。
可以证明,对于每一个非确定有穷自动机,都存在与之等价的确定型有穷自动机(证明略)。

正则表达式就是建立在自动机的理论基础上的:用户写完正则表达式之后,正则引擎会按照这个表达式构建相应的自动机(可能是NFA,也可能是DFA,但它们必定是等价的),若输入一串文本之后,自动机抵达了接受状态,则这串文本可以匹配用户指定的正则表达式。

下面是同一个正则表达式 a|ab 对应的NFADFA

NFA

clip_image003

DFA

clip_image004



Mastering Regular Expression中,Friedl首先分析了NFADFA的区别,DFA比较快,但不提供Backtrack(回溯)功能,NFA比较慢,但提供了Backtrack功能。
在分析两种引擎的匹配过程时,Friedl指出,NFA是基于表达式的(Regex-Directed),而DFA是基于文本的(Text-Directed)。
举例来说,对于正则表达式 to(nite|knight|night)NFA在匹配最开始两个字符(to)之后,剩下的三个组件(component)是 nite, knight night,于是正则引擎会依次尝试这三个选择分支(每次尝试一个);而DFA在匹配最开始两个字符之后,会将剩下的三个选择拆分作字符,并行尝试,也就是说,匹配 to 之后,先匹配 k 或者 n ,如果 k 不能匹配,则放弃 knigth 所在的分支,再匹配 i ,再匹配 t g ……这样继续下去,直到匹配结束。

不幸的是,Friedl对匹配过程的分析,是完全错误的——引擎的不同,是指构建的自动机的不同,而不是匹配算法的不同!
DFA
引擎在任意时刻必定处于某个确定的状态,而NFA引擎可能处于一组状态之中的任何一个,所以,NFA引擎必须记录所有的可能路径(trace multiple possible routes through the NFA),NFA之所以能够提供Backtrack的功能,原因就在这里。
传统的NFA匹配算法是带回溯的深度优先搜索(backtracking depth-first search,就是上文所说的Regex-Based过程),而新的PCRE算法提供了效率更高的广度优先搜索,可以同时保持所有可能的NFA状态(请参考http://www.cl.cam.ac.uk/Teaching/current/RLFA/,尤其是Lecture Notessection 2.2)。

Friedl
的错误就在这里,他混淆了应用PCRE算法的NFADFA的匹配过程。
需要指出的是,即使应用PCRE算法,NFA的速度仍然低于DFA,这是由NFA需要同时保存多种可能的性质决定的。从理论上说,如果我们不需要应用 Backtrack,完全可以从NFA构造出等价的DFA,再进行匹配,这样能大大提高速度——代价是,DFA需要更多的空间。

posted on 2009-09-29 13:56 肥仔 阅读(2540) 评论(3)  编辑 收藏 引用 所属分类: 状态机 & 自动机 & 形式语言

评论

# re: NFA DFA Regex  回复  更多评论   

可以参考我的cppblog主页上的两篇关于如何开发一个正则表达式引擎的文章。我不仅讲了必要的理论知识,连实现的时候大多数情况下会遇到的问题也讲了。
2009-09-29 15:43 | 陈梓瀚(vczh)

# re: NFA DFA Regex  回复  更多评论   

因为现代化的regex实际上是不能用DFA来实现的。考虑一个例子:
(<abc>\d+)|(<def>\d*)
2009-09-29 15:45 | 陈梓瀚(vczh)

# re: NFA DFA Regex  回复  更多评论   

请问一下,你是用什么工具绘图的?
2011-12-22 23:33 | YorkTsai

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理