（最新）正则表达式ppt模版课件.ppt

1、正则表达式-张进平主要内容一正则表达式基本语法二正则表达式的特性和流派概述三正则表达式的匹配原理四正则表达式的使用技巧和性能改善五具体语言（java）中的正则表达式六附录- JavaScript的RegExp对象七参考资料一.正则表达式的基本语法1. 模式（Pattern） 文件名模式（文件名模式（filename Pattern） 在文件系统中提供了某些特殊的字符，作为通配符如：*.txt 等。能找到所有扩展名为txt的文件。在很多系统中都自己系统描述的特定字符，表示特殊的 意义，但是这种描述相当有限-只涉及到文件名。 通用模式语言（通用模式语言（generalized Pattern la

2、nguage） 要处理我们所想到得任何文本，如：报表，散文，诗歌，表格，html，程序代码，单词表等，简单的文件模式显得无能为力。一种新的，功能强大的不同语言以各种方式来实现和使用的模式语言来弥补它的不足。这种通用模式语言和本身被称为“正则表达式正则表达式（regular expression）”2.正则表达式的测试 正则表达式本身不能完成任何工作，它的使用需要有支持正则表达式的宿主语言。以后讲解中我们用java和javascript完成。这里的测试我们用一个支持正则表达式的文本检索器（agrep）来测试。 agrep的下载网站：http:/www.tgries.de/agrep/#DOWNL

3、OAD agrep有各种版本，我这里下了win32的，方便测试也不用安装。 agrep命令格式： agrep “ 正则表达式正则表达式” 文件名文件名 3.正则表达式的组成正则表达式元字符（metachearacter）普通文本（normal text）普通文本就像英语的基本单词而元字符就是它的语法体系正则表达式和文件名模式的区别在于，正则表达式的元字符提供了更强大的描述能力。4.正则表达式的元字符l行的起始和结束 行的起始用脱字符 表示，结束用美元符 $ 表示。 行开始和结束只匹配位置，不指具体文本。 如： cat 表示匹配一个行起始，一个字符c,一个字符a一个 字符t , 意思是匹配以ca

4、t开始的行。 cat$ 表示匹配一个行起始，一个字符c,一个字符a一个 字符t ，一个$ , 意思是匹配只有cat的行。 举例测试 4.正则表达式的元字符l字符组 匹配这里列出来的任何字符。 如：你要检索html标签h1到h6,你可以这么写 h 123456 手机号码前两位可以这么写：1358 再如： 你不确定grey怎么拼，不知道grey 还是gray对 你可以这么检索如：greay举例测试 4.正则表达式的元字符l连字符 - 表示一个范围，在字符组内部的元字符，叫字符组元字字符组元字符。符。 如： 上面的html标签h123456,我们现在可以写成h1-6, 它先匹配一个h，然后再匹配1到

5、6中任意一个字符。 再如:a-z举例测试注意：连字符在字符组的开头不是元字符，只有在中间表示范围的时候才是元字符。其他元字符在字符组内也不是元字符。 4.正则表达式的元字符l排除型字符组 它的意思是匹配除了这里列出的任何字符。 这里的 和行开始是一样的字符。但是意义截然不同。 如： 1-6 意思是除了1到6之外任何字符。 c 表示不是字符c开始的行。举例测试 4.正则表达式的元字符l多选结构或 | 它的意思就是 或（or） 它能任意的子表达式，能把多个字表达式合并。 我们回头看我们的例子greay,在这里我们可以这么 写：grey|gray 也可写成：gr(a|e)y 这里括号也是元字符，它表

6、示我们划定多选结构的范围。 举例测试 4.正则表达式的元字符问题：基于原来上面的问题，请gr(a|e)y,gra|ey,graey 的区别？ gra|ey表示的不是我们所需要的东西，因为|在字符组 内不是元字符，它表示的是grey，gr|y，gray中的一 个。gr(a|e)y和graey都能达到我们的目的，但如果你觉得 gr(a|e)y没什么大的用处，那么你错了！他们的本 质区别在于一个是多选结构，一个是字符组，字符 组只能匹配单个字符，多选结构匹配的是完整的分 支结构。举例测试 4.正则表达式的元字符l单词分界符 匹配单词开始，单词结束 如：表示单词开始，然后匹配单词cat，然后匹配单词结

7、束。 有些版本不支持，我用的这个就不支持，而且在java，.net，Perl语言中都是b来表示的，所以我们这里只有用java的b来测试。举例测试java测试PatternTset6.java 4.正则表达式的元字符l可选项 ？ 放在一个字符后面表示可选字符，它的出现并非匹配成功的必要条件。 在英语中color和 colour表示的同一个意思，我们检索的时候两个都检索，如下表示。 如：colou?r 注：agrep不支持 “？”符号举例测试java测试 PatternTset.java 4.正则表达式的元字符l其他量词 * 和 + 和？一样，*，+ 他们称作量词，表示出现的次数。 + 表示一次或

8、多次，那么就有了至少一次的限制。 * 表示任意多次或者不出现。因为可以不出现，所以*和？不会影响整个正则表达式的匹配是否成功。他们只会影响匹配的最终结果，也就是匹配成功的字符串。 如正整数我们可以这么写:1-90-9*举例测试java测试 PatternTset.java 4.正则表达式的元字符l区间量词 min,max 表示重复出现的次数。 对上面的正整数做限制条件4位以内的正整数我们可以这么写：1-90-90,3举例测试java测试PatternTest5.java 4.正则表达式的元字符l括号及反向引用 在很多软件和文本工具中，括号能捕获匹配过的字符， 再用1,2这样的字符序列来记住他们

9、。 javaScript测试： var ret = /(d)1$/; var b = ret.test(“22”); alert(b); 有些版本的grep是不支持的，我用的这个就不支持。 有些语言也不支持，但是它支持捕获组和非捕获组的 概念，原理一样，具体看下节。 举例测试 java测试BackRefence.java4.正则表达式的元字符l捕获组和非捕获组 捕获型括号捕获型括号 () 在用括号的时候它会自动记住从左到右从第一个开 括号匹配成功的字符作为第一组，放在一个所谓捕获组的变量里，第二个放在第二个变量里，以此类推。Perl5语言它放在$1,$2,$3中，java语言它也可以放在$1中

10、，也可放在一个叫groups 的数组变量里。每次取的时候就可以直接getgroup(index)来取到。 举例测试 java测试BackRefence.java4.正则表达式的元字符l捕获组和非捕获组 非捕获型括号非捕获型括号 (?:) 括号内的开始加了问号和冒号。 大多数情况下我们并不想捕获匹配数据，这样对我们系统的效率和性能消耗很大。那么我们就可以用非捕获型括号，提高我们的效率。关于正则表达式的效率问题在后面章节里讲解 如: (fffff|dddd)|eeeee) 举例测试 java测试BackRefence.java4.正则表达式的元字符l捕获组和非捕获组 如：有这么个需求，允许客户端数

11、据手机号码或电话号码，还可以是邮箱，我们根据正则表达式可以获得具体是什么，再根据我们捕获到的数据进行后续处 理，如打电话，或发邮件。 举例测试 java测试 groupTset.java4.正则表达式的元字符l转义字符 也许你已经发现，正则表达式里有很多元字符，如果想 检索元字符，那么怎么办，转义字符就是解决这个问题的，如果你想查找 . 这个元字符，那么你应该写成.这种形式。 如：检索 那么我们应该写成：举例测试 4.正则表达式的元字符l其他软件程序中的元字符 d 相当于0-9 D 相当于0-9 w 相当于0-9a-zA-Z_ 这里包括下划线 W 相当于0-9a-zA-Z_ s 包括空格符，回

12、车符，制表符，进纸符等 S 除了所有空白符s外的所有字符 r 回车符制表符t 制表符 n 换行符举例测试 java测试PatternTest3.java4.正则表达式的元字符l环视(lookaround) 它不匹配任何字符，只匹配文本中的特定位置，这一点和单词边界符b，起始符,结束符$很相似。 环视分为四种，如下：肯定型顺序环视 (?=)子表达式能够匹配右侧文本肯定性逆序环视 (?=)子表达式能够匹配左侧文本否定型顺序环视 (?!)子表达式不能匹配右侧文本否定型逆序环视 (?!)子表达式不能匹配左侧文本4.正则表达式的元字符l肯定型顺序环视 如正则表达式Jeffrey匹配 by Jeffrey

13、 friedl时可以成功匹配Jeffrey 而正则表达式(?=Jeffrey)匹配的是如下位置： 这样看着好像没什么意思，也看不出什么作用，现在我们把我们的正则表达式改成(?=Jeffrey)Jeff, 这个时候我们再去匹配这两个行： 1 . by Jeffrey friedl 2 . by Thomas Jefferson4.正则表达式的元字符l肯定型顺序环视 (java测试：PatternTset7.java) 我们会惊奇的发现字符串1被分割了，而字符串2没有被分割。答案很简单，本身字符Jeff是匹配的，只是没匹配环视(?=Jeffrey) ，这样把范围缩小到了Jeffrey，意思是只有J

14、effrey里的Jeff才是我们真正想找的那个字符串，才能真正被匹配。请看下图：肯定型顺序环视图4.正则表达式的元字符l逆序，否定 顺序环视明白了，逆序就很容易了，意思就是当前位置的左边要匹配环视的文本。也就是环视的结果在环视匹配文本的右面。 否定更简单了，肯定就是要环视的测试文本匹配才算成功，否定就是要环视测试的文本和要测试的文本不匹配才算环视匹配成功。5. 元字符-总结起始符，结束符 , $,单词边界符 , b环视符 (?=), (?=), (?!.), (?!.)数量词符号 ?, * , +, max,min字符组，派出字符组 , 连字符，或 - , |捕获型括号，非捕获型括号 (),

15、(?:)反向引用 1, 2 ,.回车，换行 r, n制表符 t单字符，非单字符 w, W数字符，非数字符 d, D空白符，非空白符 s, S二.正则表达式的特性和流派概述1.正则表达式的起源 20世纪40年代两位神经学家Warren McCulloch和Walter Pitts研究出一种模型来描述神经系统的神经元。 20世纪50年代和60年代理论数学界对正则表达式进行了充分研究。 1968年Ken Thompson发表了Regular Expression Search Algorihm描述了正则表达式编译器。该编译器后来成了IBM的Object代码，由此诞生了qed，这种编译器后来成了Uni

16、x中的ed编辑器的基础。 ed的正则表达式随然没qed的先进，但是得到了大规模应用，有条命令叫“g/Regular Expression/p”,读作“Global Regular Expression Print(应用正则表达式全局输出)”，这个实用的功能最终独立成了grep，之后又产生了egrep,agrep-都是grep的扩展。 grep经过漫长的发展形成egrep的同时，其他程序awk，lex，sed也在发展，并添加了新的功能，众多程序员的修改，结果就形成了巨大的迷局。 1986年POSI(Portable Operating SysTem Interface)(可移植操作系统接口)为了

17、理清正则表达式的混乱局面，把长见的正则表达式分为两类Basic Regular Expressions(BREs)和Extended Regular Expressions(EREs).POSI正则表达式流派概览正则表达式特性BREsEREs点号,$,“任意”数量词*+ 和？量词+，？区间量词min,maxmin,max分组()()量词是否作用于括号反向引用1到9多选结构2.各种语言之间的差异在于以下三点：l支持的元字符，以及这些元字符的意义。也就是我们说的流派（flavor）。l正则表达式与语言或工具的“交互“(inteface)方式。譬如如何进行正则表达式的操作，容许进行哪些操作，以及这些

18、操作的目标文本类型。l正则表达式引擎如何将表达式应用到文本中。语言或工具的设计者实现正则表达式方法，对正则表达式能够取得到的结果又重要的影响。若干工具正则表达式流派的简要参考特性ModerngrepModern egrepGNU EmacsTclPerl.NETJava*,$,?,+,|? + |? + |? + |? + |? + | ? + | ? + |分组()()()()()()(?:)单词分界符bBn M Yb B b B b Bw,W反向引用程序设计语言3种处理正则表达式的方式：l集成式（integrated）l程序式（procedural）l面向对象式（object-orient

19、ed） 第一种方式中，正则表达式是直接内建在语言中的，Perl就是如此，在其他两种方式中，正则表达式不属于语言的低级语法。相反，普通的函数接受普通的字符，把他们当做正则表达式进行处理。由不同的的函数进行不同的、关系到一个或多个正则表达式的操作。大多数语言（不包括Perl）PHP，Java，.net，Python，Ruby等采用的是这两种方式之一。Perl(一种脚本语言)例子：$/ = “.n”;while() next if !s/b(a-z+)(?:s|+)+)(1b)/e7m$1em$2e7m$3em/ig; s/(?:e*n)+/mg; s/$ARGV:/mg; Print; 这里并不奢

20、望能看懂上面代码，何况我们不懂Perl，就算懂Perl的人也未必一下看的明白，只想用这个例子说明不同语言对正则表达式的交互方式程度的不同。在这里给我们的感觉就是正则表达式和程序代镶嵌很紧，所谓正则表达式和代码搭配天衣无缝，正因为正则表达式找到了Perl这块肥土，才让正则表达式在Perl里显得相当出色。java例子：public static void main(String args) Pattern p = Ppile(b n +#把捕获到得地址保存到$1. n +( n +w-.w* n + n + -w+(.-w+)*.(com|edu|info) n +) n +b n,Pattern

21、.CASE_INSENSITIVE|Pattern.COMMENTS);Matcher m = p.matcher(text);text = m.replaceAll($1); System.out.println(text);java例子： 看如上代码，你发现，元字符w写成了w,这是因为java把所有正则表达式都做字符串输入，在程序代码里他不认识w是什么,这么写也会报错误。 注意：这里的换行”n”，是java里的转义字符，不属于正则表达式的内容。这里加换行的目有两个：一让我的代码看的更清楚，二是正则表达式#开始的为注释行，不换行的话都属于注释部分了。 测试（EmailChange.java）

22、 分析代码作用。通过Perl和java代码的对比,我们看到语言之间正则表达式运用的差异，也看出集成式和程序式及面向对象式之间的差别。2.正则表达式匹配模式：l不区分大小写的匹配模式。（忽略大小写）l宽松排列和注释模式。（忽略制表符空格等）l点号通配模式（单行模式）。（点号可以匹配换行等）l增强的行锚点模式（多行模式）。（行锚点符能匹配任何行终止符）l文字文本模式。（不认识任何元字符，全部当简单字符串处理，不当做正则表达处理）3.常见元字符和特性（略） 第一节讲了最常用的元字符，其实还有很多元字符的定义规则特性及其用法，如Unicode字符集，POSIX字符集，模式修饰符等。有兴趣的同学可以去看

23、下资料： Mastering Regular Expressiongs,3rd Edition 美Jeffref E.F. Friedl 精通正则表达式第三版 余晟 译4.总结l 发展起源l 软件工具和语言支持情况l 各种程序设计支持的差异l 正则编译的模式下面我们接着讲 第三节第三节 正则表达式的匹配原理正则表达式的匹配原理三.正则表达式的匹配原理1. 引擎 汽车引擎燃油发动机符合排放的燃油发动机电动发动机 不符合排放标准符合排放标准符合排放标准1.引擎 最初正则引擎和汽车引擎一样，分为两种，DFA(相当于电动机)和NAF(相当于汽油机)。后来，NFA和DFA都发展了20多年了，产生了一些变

24、体，POSIX标准出台后（相当于出了排放标准），DFA是符合POSIX的，而NFA是不符合的，所以出现了修改后符合POSIX的 NFA。这样一来正则引擎和汽车引擎的例子很相似，大概分为三种：l DFA（符合POSIX标准）-电动机l 传统NFA（不符合POSIX）-汽油机l POSIX NFA （符合POSIX）-符合排放的汽油机1.引擎部分程序及其使用的正则引擎DFAAwk(大多数版本)，egrp（大多数版本），flex，lex，MySQL传统NFA GNU Emacs，Java，grep，.net，Perl，PHP，Ruby，PythonPOSI NFA Mawk，GUNEmas（明确指定

25、时使用）DFA/NFA GUN awk，GNU grep/egrep,Tcl1.引擎 测试引擎类型 传统型NFA是广泛使用的，且很好区分，如果支持忽略优先量词。那么它就是传统型NFA（Java是支持忽略优先量词的，Java API明确说明是传统的NFA正则引擎,可查看API）。 是DFA还是POSIX NFA DFA不支持捕获型括号和回溯，这一点可以明确判断DFA还是POSIX NFA，不过有双引擎的就列外了。 2.匹配基础 匹配的两条规则：l 优先选择最左端（最开头）的匹配结果。优先选择最左端（最开头）的匹配结果。l 标准匹配量词（标准匹配量词（*，+，？，？，m,n ）是匹配优先）是匹配优

26、先(greedy)的。的。这里给大家补充下三种量词概念（原因是在前面省略了一小段内容）测试：PatternTest5.java三种量词： 1.匹配优先量词（greedy） （*，+，?，m,n ） 2.忽略优先量词（Reluctant ） （*?，+?，?，m,n ?） 3. 占有优先量词（Possessive ） （*+，+，?+，m,n +）这两条规则是所有匹配的基础。下面我们分别来阐述。2.匹配基础优先选择最左端（最开头）的匹配结果。优先选择最左端（最开头）的匹配结果。这条规则很好理解,，看下面的例子：l 用oa匹配float。 这里它会一个一个字符去找，所以我们在匹配应该说先匹配一个f

27、，发现匹配失败，继续向前，匹配一个l，再次失败，再向前移动，匹配o成功，同时它会记住匹配成功的o，把自身向前移一位，匹配a，匹配成功并记住a，引擎停止，宣告全局匹配成功。l 用cat去匹配The dragging belly indicates that you cat is too fat. 。 这个匹配和上面一样，他最先匹配indicates里的cat，而不是you后面的cat。2.匹配基础标准匹配量词（标准匹配量词（*，+，？，？，m,n ）是匹配优先的。）是匹配优先的。现在看看这条规则怎么理解。 标准匹配优先就是匹配尽可能多的字符，一直到匹配上限位置。 如：d*匹配dddddd,他会匹

28、配所有的d。过程是这样的，先匹配一个d，匹配成功，那么把匹配成功的先保存起来，然后再尝试下一个d，如果失败，那么匹配结束，返回一已经保存的那个d，如果匹配成功，它再把第二个d保存起来，再尝试匹配下一个如此下去，直到所有尝试结束，返回保存的那些字符。 它会尝试匹配尽可能多的字符。2.匹配基础过度匹配优先。过度匹配优先。大家看看 .*(0-90-9) 匹配 about 24 characters long应该如何匹配。按照基本量词匹配优先原则， .* 会匹配所有字符，而导致(0-90-9)匹配不到，导致整个正则表达式匹配失败？其实不是这样的，当然基本量词匹配优先基本量词匹配优先这条原则不会变，就是

29、说.*还是会吃掉整个字符串，但是当(0-90-9)匹配不到的时候，它会说哥们儿你吃多了，我没的吃了，我饿死了你也会死，于是 .* 为了它自己不死，就吐给(0-90-9)一个字符g， (0-90-9)吃了g，发现自己匹配不了，又说哥们儿别那么小气，于是 .* 再吐给一个n，还是匹配不了，又要，.*再吐，知道吐了2的时候， (0-90-9)才勉强生存， .*不会再吐，引擎停止，返回匹配结果。所以正确的匹配结果应该是about 24 。这叫做过度匹配过度匹配2.匹配基础先来先服务。先来先服务。依照上面的法则请问.*(0-9+)匹配 copyright 2003后括号捕获到的是什么？这个和上面的基本一

30、致，.*会吃掉所有字符，但是(0-9+)不能饿死，于是.*会吐出一个给(0-9+)匹配，会不会再吐，肯定的回答是不会，因为我们知道.*是很小气的，也是很贪婪的，只有在强迫无奈的情况才会吐给(0-9+)，吐一个3后，.*发现(0-9+)能活了，于是不再吐了，整个表达式匹配完成，括号捕获到的只有3。这就是先来先服务，.*先到达的，所以(0-9+)你再能吃也不给你吃了。这就是先来先来先服务先服务。2.回谈引擎 DFA和NFA反应了正则表达式在应用算法上的根本差异，我们把对应汽油机的NFA成为“表达式主导（regex-directed）”的引擎，把DFA电动机对应的DFA称为“文本主导（text-di

31、rected）”的引擎。NFA引擎（表达式主导）引擎（表达式主导）我们来看to(nite|knight|night)匹配tonight的一种办法。还是依照我们规则一，从最左边开始先匹配字符t，并记住t,然后再匹配个字符o，记住o，接下来呢？接下来会拿nite去匹配，匹配一个字符n，ok匹配成功，再拿i去匹配，结果失败，换knight去匹配，第一个k失败，直接换下一个night来匹配。结果成功。2.回谈引擎NFA引擎（表达式主导）引擎（表达式主导）NFA的优点: 通过上述例子，我们发现在整个匹配过程中，每个字表达式是相对独立的，字表达式之间不存在内在联系。只是整个表达式的各个部分。字表达式与正则

32、表达式的控制结构的层级关系控制了整个匹配过程。 这样的表达式主导引擎，有利于编写表达式的人有充足的机会来实现他期望的结果（也就是说这里存在着表达式性能改善的可能和编写表达式的技巧，下面会到性能和效率问题）。2.回谈引擎DFA引擎（文本主导）引擎（文本主导）与表达式主导不同的是，DFA在扫描字符串时，会记录当前有效的所有匹配可能。 我们还是来看tonight例子。当引擎移动到t时，匹配t成功，然后记住t有个可能成功的位置就在后面，然后再拿o匹配，同样匹配成功，可能成功的位置在o后面，继续下一个字符n，这时候，knight被淘汰了，并记住可能匹配的位置有两个，nite中n的后面，和night中的n

33、后面。再匹配下一个i，记录当前匹配成功的字符，并记录可能匹配成功的位置。再下移一位，到g字符，这时候nite被淘汰了，最后匹配了night，真个匹配成功返回的是tonight，如果整个失败。当然如果第一个不是t，就会拿t去和o去匹配，如果都不需要t，那么把t扔掉。2.回谈引擎 通过上述理论，发现NFA和DFA的差别，大家可能会看出，一般情况下DFA应该比NFA快一点，的确如此。在NFA的匹配过程中，目标文本可能会被正则表达式中不同的部分重复检测多次，这种匹配在未到达正则表达式末尾之前，我们无法预知全局是否匹配成功。相反，DFA引擎室确定的-目标文本中的每个字符只会检查（最多）一遍。对一个已经匹

34、配的字符来说无法知道他最终是否成功，但是因为引擎同时记录了所有可能的匹配，这个字符只需要检查一次。正则表达式所用的两种技术对应的叫：非确定型有穷非确定型有穷自动机（自动机（NFA）和确定型自动机（）和确定型自动机（DFA）。 关于自动机理论的知识，大家可以阅读自动机理论自动机理论.语言和计语言和计算机导论算机导论(英文版英文版)(第第3版版) 作者作者:(美美)霍普克罗夫特霍普克罗夫特 等，可惜的是（我没找到等，可惜的是（我没找到中文版）只有英文版，好书往往都是如此。中文版）只有英文版，好书往往都是如此。3.回溯学过数据结构与算法的都知道有个经典的迷宫问题。在走到没有出路的死胡同时，要回溯到原

35、来的分叉路口重新下一轮尝试。还有遍历树的时候，等遍历完了叶子节点后要回溯到邻近的分叉处，继续遍历其他的分支。这里讲的回溯和这些都是一样的。3.回溯 回溯是NFA的重要性质。当NFA一次处理各个字表达式或组成元素的时候，遇到两个以上成功可能的时候，它会选择其中之一，同时记住另外一个，以备稍候可能的需要。要做出选择的情形包括量词（决定是否尝试另外一次）和多选分支结构（决定选择哪个多选分支，留下哪个稍候尝试）。不论哪种途径，如果他能匹配成功，而且正则表达式余下的部分也成功了，即宣告整个匹配成功，如果余下的部分失败了，那么他就会回溯到之前做出选择的地方。选择其他备用的分支继续尝试。这样直到成功或者所有

36、可途径都走完，宣告匹配失败。 3.回溯 回溯的两个要点：l 如果需要在“进行尝试”和“跳过尝试”之间选择，对于匹配优先量词。引擎会优先选择“进行尝试”，对于忽略优先量词会选择“跳过尝试”。l 距离当前最近存储的选项就是本地失败强制回溯时返回的。使用的原则是LIFO（last in first out）。第二条说的有点难理解，但是你这么想，用哪个迷宫来考虑，就是说如果走到一个死胡同了，那你要原路返回，返回的路口是进来时的逆向，那么进来时最后碰到的那个岔路口，就是你要返回的端点，也就是说距离你最近的那个岔道口。这点对熟悉迷宫算法和遍历树的算法的人来说很容易。3.回溯 匹配优先和忽略优先，占有优先的

37、区别。 举例PatternTest5.java 下面我们来看看下面这些匹配的过程。 ab?c abc ab?c abc ab?c abx ab?c ac3.回溯 我们先看ab?c abc，它先匹配一个字符a，匹配成功，然后下一个是b?,引擎会选择，是忽略还是尝试匹配呢？发现是匹配优先量词，所以选择匹配b，同时记录当前备用状态（如果余下的匹配失败，要回溯到这里的），匹配b成功，最后匹配c也成功，返回匹配结果abc。 再看ab?c abc，它先匹配个a，成功，移动下一位，发现的是b?，正则引擎又要来选择是尝试匹配还是忽略呢？发现时忽略优先量词b?，忽略量词是最小匹配，所以忽略b，并记录当前备用状态

38、，接下来直接配c，发现，匹配c的是字符b，匹配失败，这是要回溯到b?这里，尝试匹配b，结果b匹配成功，再匹配c，c也匹配成功，最终真个正则表达式匹配成功，返回匹配结果abc。 从这里可以看出，随然结果都匹配成功，但是整个过程是截然不同的，也许你已经看出不同写法对效率影响很大。3.回溯 看了如上例子，请描述以下匹配过程 ab?c abx ab?c ac第一个，先匹配a，匹配成功，选择下一个进行匹配，当到下一个字符是，发现是匹配优先量词，那么选择尝试匹配，同时记录一个忽略b的备用状态，匹配b成功，继续匹配下一个c，匹配失败，这时候要回溯到距离当前最近存储的选距离当前最近存储的选项，项，也就是b?处

39、，忽略字符b，继续用c尝试匹配，匹配失败，最终宣告这个正则表达式匹配失败。第二个，和第一个匹配过程基本一样，只是回溯到备用状态继续匹配的时候，字符c匹配成功，导致整个正则表达式匹配成功，引擎返回ac而已。3.回溯 通过以上的分析我们发现，不管是匹配优先还是忽略优先，我们得出如下结论： 只要引擎报告匹配失败，那么它必然就尝试了所有的可能。只要引擎报告匹配失败，那么它必然就尝试了所有的可能。 下面我们看看什么是占有优先量词以及固化分组4.占有量词和固化分组 我们用这个(.dd1-9?)d*来替换处理浮点型数据存储的问题。如存3.00和1.235，可能就会成3.00000000028822和1.23

40、500000002282，我们可以用如下代码完成替换：String input = 1.23300000000032;Pattern p = Ppile(.dd1-9?)d*);Matcher m =p.matcher(input);input = m.replaceAll($1);System.out.println(input);测试代码SolidifyGroup.java仔细分析这个(.dd1-9?)d*正则表达式，我们会发现当input的值为1.235的时候它依然去替换一次，因为(.dd1-9?)能匹配匹配.235但是后面d*,没有匹配的数字，所以括号捕获的只有.235,匹配成功进行替

41、换。 4.占有量词和固化分组 我们想到如果给后面的d*改成d+，那么就确保了至少后面有一位时匹配成功。就说对于1.2350000002288这种数字还是有效，对于1.235这种数字因为后面没有数字而匹配失败，不进行替换，这样做对吗？测试SolidifyGroup.java 固然是不对的，因为(.dd1-9?)d+是匹配优先，当d+匹配失败后，它会回溯到1-9?这里的备用状态，尝试配置下一个数字，结果匹配成功，最终括号捕获到的结果是.23,这明显不是我们想要的结果！ 通过上述分析，原因在于那个回溯和捕获型括号，这么想如果括号里原来匹配是捕获的值不变或者没有那个回溯，随然匹配失败了，但是捕获的内容

42、的确是我们想要的。这个就可以用占有量词和固化分组来解决。4.占有优先量词和固化分组 占有优先量词占有优先量词 占有量词的表示方法是在匹配优先量词后面加+，占有量词和匹配优先量词很相似，只是它们从来不交还已经匹配的字符。还是那个例子我们来看看占有优先量词。 .*(0-9+)匹配 copyright 2003 -匹配优先 .*?(0-9+)匹配 copyright 2003 -忽略优先.*+(0-9+)匹配 copyright 2003 -占有优先我们已经很明白前两个匹配过程，现在主要来看第三个，占有优先其实和匹配优先有点像，.*他会吃掉所有字符，但是匹配优先中.*不会让自己和(0-9+)饿死，它

43、会施舍字符给(0-9+)，而占有优先不会施舍，就算自己死掉也不会吐一个字符给(0-9+)，占着不放，从而导致整个表达式匹配失败！4.占有量词和固化分组 还记得ab?c匹配ac的例子吗？ 如果写成这样：ab?+c 匹配ac ，那么按照占有优先原则字符b一定是要匹配的，匹配失败后，它不会回溯，直接宣告整个表达式匹配失败。这是因为占有优先量词在b?+处没有创造任何状态。 现在我们重新来看那个浮点问题: 我们可以这么写(.dd1-9?+)d+，当后面匹配失败的时候，它就不会回溯到1-9?,因为这里就没记录备用状态。 它也不会归还任何字符给d+,导致匹配失败，但是括号捕获的是我们想要的，我们依然能达到替

44、换的目的。 java测试： SolidifyGroup.java3.占有量词和固化分组固化分组固化分组 (?)使用(?)和普通的用法没有太大差别，只是如果匹配进行到此结构的结束之后（也就是，进行到闭括号之后），那么此结构体中的所有备用状态都会被放弃。在固化分组匹配结束后，它已经匹配的文本已经固化成一个单元，只能作为整体保留或放弃。括号内未尝试过的备用状态都将不复存在。现在我们来看那个浮点问题，我们可以这么写：(?.dd1-9?)d+ ,一样能达到我们的目的。3.占有量词和固化分组我们在匹配优先和忽略优先的时候得到一个结论是只要引擎只要引擎报告匹配失败，那么它必然就尝试了所有的可能。报告匹配失败

45、，那么它必然就尝试了所有的可能。也就是说他们不会影响结果，只会影响匹配过程，而占有优先和固化分组根据不同的情况可能导致如下不同的结果：l 毫无影响毫无影响l 导致匹配失败导致匹配失败l 改变匹配结果改变匹配结果l 加快报告失败的速度加快报告失败的速度下面我们再来看看这个例子：w+: 匹配 subject3.占有量词和固化分组l 加快报告失败的速度加快报告失败的速度 w+: 匹配 subject ，我们能一眼看出匹配是失败的，因为冒号 ：无法匹配，我们已经知道正则引擎的匹配过程，一眼看出来的问题，引擎并不知道，它还是要一次又一次的回溯，知道回溯到最初状态，才报告匹配失败，但是如果我们加上固化分组

46、 (?w+): 这么写后，第一次导致失败，不会回溯，这就加快了报告失败的速度。 也许你已经看到了固化分组在效率中的作用。后面我们还会讲到。4.关于回溯更多内容l 环视中的回溯环视中的回溯 在环视中的字表达式在整个正则表达式中式独立的”世界“，在环视结束后，整个环视产生的所有备用状态将都被放弃。l 多选结构也是匹配优先吗多选结构也是匹配优先吗? 我们来看看tour|to|tournaments来匹配three tournaments won时会得到什么结果？ 我们看到如果to匹配成功了，那么就像是忽略优先了，如果tournaments匹配了，就好像是匹配优先了。其实在传统的NFA中它是按照前后顺

47、序的，就是说上面这个匹配返回的是tour，并非所有的正则引擎都是这样，DFA和 POSIX NFA,他们返回的是文本最多的那个结果。4.关于回溯更多内容l 有序结果中的陷阱有序结果中的陷阱 我们来看看这个例子， 我希望匹配日期的一个数字，返回时1到31，当然01这种写法也算正确。 分析：有三段第一段0?1-9 ，第二段120-9，第三段301,然后拼起来得到如下表达式： (0?1-9|120-9|301)，这里加捕获型括号我们要捕获它的匹配结果。Ok,我们现在来试试看，用10来测试，结果是什么？ 我们惊奇的发现，捕获到的只有1了，根本不是我们想要的，这里错误的原因是我们NFA和顺序有关，它不会

48、匹配最长的，第一个分支匹配成果则整个匹配结束，这里我们解决的方法是调换顺序，写成(120-9|301 |0?1-9)这样，就能正确获得想要的结果。5.NFA、DFA和POSIXl 最左最长规则最左最长规则DFA在匹配过程中遇到一个或多个匹配的可能，DFA就会选择这些中最长的。因为在所有同样从最左边开始可能的匹配文本中它是最长的，所以叫最左最长最左最长匹配。还是这个例子： tour|to|tournaments来匹配three tournaments won NFA匹配的结果是tour我们已经知道了，而DFA它匹配的是tournaments，因为它的依据是最左最长原则。l POSIX和最左最长规

49、则和最左最长规则 POSIX标准规定，如果在字符串的某个位置存在多个可能的匹配，应当返回最长的匹配。但是NFA的本质是一个一个回溯，要找到最长的文本，意味着要回溯所有的备用状态，这样 POSIX NFA 效率就值得考虑了。5.NFA、DFA和POSIXl 速度和效率速度和效率DFA在第一次遇到正则表达式开始尝试匹配的时候，它就会内建一张线路图，遇到那个字符就走那条路，有时候构造这张图需要相当的时间和内存，不过只要建立了针对特定的正则表达式的路线图，结果就可以应用到任意长度的文本。这样DFA在编译的时候速度就稍慢点，而NFA在编译的时候快点，消耗的内存也比DFA 要少，但是在匹配过程中的回溯是一

50、个问题，POSIX NFA要回溯更多个备用状态，效率更值得关注。前面我们讲过，NFA更多的我们可以控制匹配过程和结果，以及失败速度，而DFA我们基本不能控制匹配过程。6.总结：l 正则引擎的分类：NFA，DFA，POSIX NFAl 文本主导（DFA）和正则主导（NFA）l NFA的回溯机制l 匹配优先，忽略优先，l 占有优先 ，固化分组（?）l NFA,DFA,POSIX NFA的效率四.正则表达式的使用技巧和性能改善1.正则表达式的平衡法则 好的正则表达式应该在这些方面求的平衡：l 只匹配期望的文本，排除不期望的文本l 必须易于控制和理解l 如果用NFA，必须保证效率(如果能够匹配，必须很