太行新闻网

主页 > 教育科技 > > 正文

C/C++中使用的正则表达式库

2014-04-28 23:07
来源: 未知
【字号: 】【打印

正则表达式

正则表达式是对字符串操作的一种逻辑公式,就是用事先定义好的一些特定字符、及这些特定字符的组合,组成一个“规则字符串”,这个“规则字符串”用来表达对字符串的一种过滤逻辑。
正则引擎主要可以分为两大类:一种是DFA,一种是NFA。主流的正则引擎又分为3类:1. DFA引擎
DFA 引擎在线性时状态下执行,因为它们不要求回溯(并因此它们永远不测试相同的字符两次)。DFA 引擎还可以确保匹配最长的可能的字符串。但是,因为 DFA 引擎只包含有限的状态,所以它不能匹配具有反向引用的模式;并且因为它不构造显示扩展,所以它不可以捕获子表达式。
使用DFA引擎的程序主要有:awk、egrep、flex、lex、MySQL、Procmail等。
2. 传统型NFA
传统的 NFA 引擎运行所谓的“贪婪的”匹配回溯算法,以指定顺序测试正则表达式的所有可能的扩展并接受第一个匹配项。因为传统的 NFA 构造正则表达式的特定扩展以获得成功的匹配,所以它可以捕获子表达式匹配和匹配的反向引用。但是,因为传统的 NFA 回溯,所以它可以访问完全相同的状态多次(如果通过不同的路径到达该状态)。因此,在最坏情况下,它的执行速度可能非常慢。因为传统的 NFA 接受它找到的第一个匹配,所以它还可能会导致其他(可能更长)匹配未被发现。
使用传统型NFA引擎的程序主要有:GNUEmacs,Java,ergp,less,more,.NET语言,PCRE library,Perl,PHP,Python,Ruby,sed,vi等。
3. POSIX NFA。
POSIX NFA 引擎与传统的 NFA 引擎类似,不同的一点在于:在它们可以确保已找到了可能的最长的匹配之前,它们将继续回溯。因此,POSIX NFA 引擎的速度慢于传统的 NFA 引擎;并且在使用 POSIX NFA 时,您恐怕不会愿意在更改回溯搜索的顺序的情况下来支持较短的匹配搜索,而非较长的匹配搜索。
使用POSIX NFA引擎的程序主要有:mawk,MorticeKern Systems’ utilities,GNU Emacs(使用时可以明确指定)。
注:也有使用DFA/NFA混合的引擎:GNUawk,GNU grep/egrep,Tcl。
Tags:
分享到:
( 编辑: 3.wanshehui.com ) 【字号: 】【打印】【关闭

 
Copyright © 2009 - 2013 wanshehui.com
Copyright © 2009-2013 太行新闻网 冀ICP备11009293号 网站地图