简介:regex engine的特点

发信人: sunnavy (Shire·Wait·Patient), 信区: Perl
标 题: Re: 活跃一下气氛，出个regex题目
发信站: 水木社区 (Sat Jul 15 23:00:40 2006), 转信

我简单介绍一下regex engine的特点吧。
如果想详细了解，看我推荐的书目。

regex engine 主要有两种：DFA和NFA。

先说DFA(Deterministic Finite Automaton)
DFA提供的功能比较少，我们常用的capture，lazy quantifiers等特性它都不支持。
DFA是text-directed，目标字符串中的字符最多只检查一次(不像NFA，每个字符会来
来回检查很多次)，所以速度一般会快些。
DFA限制了用户对regex的优化可能，只要regex的效果是一样的(比如/a/和
/[a-a]|a|a{1}/)，它们的速度就基本是一样的。
使用DFA的程序主要有：lex，MySQL以及大多数版本的egrep和awk

说说NFA(Nodeterministic Finite Automaton)
NFA提供的功能比DFA要多，它支持capture，lazy quantifiers特性。
NFA是regex-directed，目标字符串中的字符经常会来来回会检查多次，速度一般会慢些。
由于是regex-directed，NFA对regex的写法是比较敏感的，同样效果的两种写法的效率有
时会差别很大，这样就对要求用户写regex时格外注意，也给了用户优化regex的空间。

NFA又分为两种：traditional NFA和POSIX NFA。
traditional NFA的应用很广泛，Perl，Python，Ruby，Emacs，Java，.Net等等都用的这
个。

POSIX NFA即是符合POSIX标准的NFA，有些规定和traditional的很不一样。用户优化的空
间比traditional的要小些。

有的程序使用混合的NFA和DFA engine，比如Tcl，GNU awk和GNU grep/egrep。

推荐书目：O'REILLY mastering regular expressions 2nd edition.
国内有影印版卖
【 在 happierbee (吾生也有涯，而知也无涯) 的大作中提到: 】
: 无从想起，还没有看过有文章介绍正则表达式是怎么实现的。
: 要不你给我们讲一讲？


--
我们希望被爱，却不知道爱是什麽，我们不快乐，我们渴求真实，于是我们转向圣书，在
语句中迷失。不论在任何地方，人心都是相似的，它只是在不同的天空下，以不同的方式
表达罢了。


※ 来源:·水木社区 newsmth.net·[FROM: 88.191.22.*]