首页 分类 维基 链接 关于
SITEMAP订阅

理解正则表达式（程序员第3期文章）收藏

理解正则表达式（程序员第3期文章）收藏

新一篇: 小学教育的问题 旧一篇: C++0x草案将于年内发表，C++即将重大升级

本文为《程序员》07年3月号《七种武器》专题所做。有兴趣的读者可以到 这里 来投一票，表达您对于程序员基本功的看法。

在程序员日常工作中，数据处理占据了相当的比重。而在所有的数据之中，文本又占据了相当的比重。文本能够被人理解，具有良好的透明性，利于系统的开发、测试和维护。然而，易于被人理解的文本数据，机器处理起来就不一定都那么容易。文本数据复杂多变，特定性强，甚至是千奇百怪。因此，文本处理程序可谓生存环境恶劣。一般来说，文本处理程序都是特定于应用的，一个项目有一个项目的要求，彼此之间很难抽出共同点，代码很难复用，往往是“一次编码，一次运行，到处补丁”。其程序结构散乱丑陋，谈不上有什么“艺术性”，基本上与“模式”、“架构”什么的无缘。在这里，从容雅致、温文尔雅派不上用场，要想生存就必须以暴制暴。

事实上，几十年的实践证明，除了正则表达式和更高级的parser技术，在这样一场街头斗殴中别无利器。而其中，尤以正则表达式最为常用。所以，对于今天的程序员来说，熟练使用正则表达式着实应该是一种必不可少的基本功。然而现实情况却是，知道的人很多，善于应用的人却很少，而能够洞悉其原理，理智而高效地应用它的人则少之又少。大多数开发者被它的外表吓倒，不敢也不耐烦深入了解其原理。事实上，正则表达式背后的原理并不复杂，只要耐心学习，积极实践，理解正则表达式并不困难。下面列举的一些条款，来自我本人学习和时间经验的不完全总结。由于水平和篇幅所限，只能浮光掠影，不足和谬误之处，希望得到有识之士的指教。

  1. 了解正则表达式的历史

正则表达式萌芽于1940年代的神经生理学研究，由著名数学家Stephen Kleene第一个正式描述。具体地说，Kleene归纳了前述的神经生理学研究，在一篇题为《正则集代数》的论文中定义了“正则集”，并在其上定义了一个代数系统，并且引入了一种记号系统来描述正则集，这种记号系统被他称为“正则表达式”。在理论数学的圈子里被研究了几十年之后，1968年，后来发明了UNIX系统的Ken Thompson第一个把正则表达式用于计算机领域，开发了qed和grep两个实用文本处理工具，取得了巨大成功。在此后十几年里，一大批一流计算机科学家和黑客对正则表达式进行了密集的研究和实践。在1980年代早期，UNIX运动的两个中心贝尔实验室和加州大学伯克利分校分别围绕grep工具对正则表达式引擎进行了研究和实现。与之同时，编译器“龙书”的作者Alfred Aho开发了Egrep工具，大大扩展和增强了正则表达式的功能。此后，他又与《C程序设计语言》的作者Brian Kernighan等三人一起发明了流行的awk文本编辑语言。到了1986年，正则表达式迎来了一次飞跃。先是C语言顶级黑客Henry Spencer以源代码形式发布了一个用C语言写成的正则表达式程序库（当时还不叫open source），从而把正则表达式的奥妙带入寻常百姓家，然后是技术怪杰Larry Wall横空出世，发布了Perl语言的第一个版本。自那以后，Perl一直是正则表达式的旗手，可以说，今天正则表达式的标准和地位是由Perl塑造的。Perl 5.x发布以后，正则表达式进入了稳定成熟期，其强大能力已经征服了几乎所有主流语言平台，成为每个专业开发者都必须掌握的基本工具。

  1. 掌握一门正则表达式语言

使用正则表达式有两种方法，一种是通过程序库，另一种是通过内置了正则表达式引擎的语言本身。前者的代表是Java、.NET、C/C++、Python，后者的代表则是Perl、Ruby、JavaScript和一些新兴语言，如Groovy等。如果学习正则表达式的目标仅仅是应付日常应用，则通过程序库使用就可以。但只有掌握一门正则表达式语言，才能够将正则表达式变成编程的直觉本能，达到较高的水准。不但如此，正则表达式语言也能够在实践中提供更高的开发和执行效率。因此，有心者应当掌握一门正则表达式语言。

  1. 理解DFA和NFA

正则表达式引擎分成两类，一类称为DFA（确定性有穷自动机），另一类称为NFA（非确定性有穷自动机）。两类引擎要顺利工作，都必须有一个正则式和一个文本串，一个捏在手里，一个吃下去。DFA捏着文本串去比较正则式，看到一个子正则式，就把可能的匹配串全标注出来，然后再看正则式的下一个部分，根据新的匹配结果更新标注。而NFA是捏着正则式去比文本，吃掉一个字符，就把它跟正则式比较，匹配就记下来：“某年某月某日在某处匹配上了！”，然后接着往下干。一旦不匹配，就把刚吃的这个字符吐出来，一个个的吐，直到回到上一次匹配的地方。

DFA与NFA机制上的不同带来5个影响：

  1. DFA对于文本串里的每一个字符只需扫描一次，比较快，但特性较少；NFA要翻来覆去吃字符、吐字符，速度慢，但是特性丰富，所以反而应用广泛，当今主要的正则表达式引擎，如Perl、Ruby、Python的re模块、Java和.NET的regex库，都是NFA的。

  2. 只有NFA才支持lazy和backreference等特性；

  3. NFA急于邀功请赏，所以最左子正则式优先匹配成功，因此偶尔会错过最佳匹配结果；DFA则是“最长的左子正则式优先匹配成功”。

  4. NFA缺省采用greedy量词（见item 4）；

  5. NFA可能会陷入递归调用的陷阱而表现得性能极差。

我这里举一个例子来说明第3个影响。

例如用正则式/perl perlman/来匹配文本 ‘perlman book’。如果是NFA，则以正则式为导向，手里捏着正则式，眼睛看着文本，一个字符一个字符的吃，吃完 ‘perl’ 以后，跟第一个子正则式/perl/已经匹配上了，于是记录在案，往下再看，吃进一个 ‘m’，这下糟了，跟子式/perl/不匹配了，于是把m吐出来，向上汇报说成功匹配 ‘perl’，不再关心其他，也不尝试后面那个子正则式/perlman/，自然也就看不到那个更好的答案了。

如果是DFA，它是以文本为导向，手里捏着文本，眼睛看着正则式，一口一口的吃。吃到/p/，就在手里的 ‘p’ 上打一个钩，记上一笔，说这个字符已经匹配上了，然后往下吃。当看到 /perl/ 之后，DFA不会停，会尝试再吃一口。这时候，第一个子正则式已经山穷水尽了，没得吃了，于是就甩掉它，去吃第二个子正则式的/m/。这一吃好了，因为又匹配上了，于是接着往下吃。直到把正则式吃完，心满意足往上报告说成功匹配了 ‘perlman’。

由此可知，要让NFA正确工作，应该使用 /perlman perl/ 模式。

通过以上例子，可以理解为什么NFA是最左子式匹配，而DFA是最长左子式匹配。实际上，如果仔细分析，关于NFA和DFA的不同之处，都可以找出道理。而明白这些道理，对于有效应用正则表达式是非常有意义的。

  1. 理解greedy和lazy量词

由于日常遇到的正则表达式引擎全都是NFA，所以缺省都采用greedy量词。Greedy量词的意思不难理解，就是对于/.*/、/\w+/这样的“重复n”次的模式，以贪婪方式进行，尽可能匹配更多字符，直到不得以罢手为止。

举一个例子，以 /<.*>/ 模式匹配 ‘ Perl Hacks \t’文本，匹配结果不是 ‘’，而是 ‘ Perl Hacks ’。原因就在于NFA引擎以贪婪方式执行“重复n次”的命令。让我们来仔细分析一下这个过程。

条款3指出，NFA的模型是以正则式为导向，拿着正则式吃文本。在上面的例子里，当它拿着/.*/这个正则式去吃文本的时候，缺省情况下它就这么一路吃下去，即使碰到 ‘>’字符也不罢手――既然 /./ 是匹配任意字符， ‘>’ 当然也可以匹配！所以就尽管吃下去，直到吃完遇到结尾（包括\t字符）也不觉得有什么不对。这个时候它突然发现，在正则表达式最后还有一个 />/，于是慌了神，知道吃多了，于是就开始一个字符一个字符的往回吐，直到吐出倒数第二个字符 ‘>’，完成了与正则式的匹配，才长舒一口气，向上汇报，匹配字符串从第一个字符 ‘<’ 开始，到倒数第二个字符 ‘>’结束，即‘ Perl Hacks ’。

Greedy量词的行为有时确实是用户所需要的，有时则不是。比如在这个例子里，用户可能实际上想得到的是 ‘book’ 串。怎么办呢？这时候lazy量词就派上用场了。把模式改为/<.?>/就可以得到 ‘book’。这个加在 ‘’号后面的 ‘?’ 把greedy量词行为变成lazy量词行为，从而由尽量多吃变为尽量少吃，只要吃到一个 ‘>’立刻停止。

问号在正则表达式里用途最广泛，这里是很重要的一个用途。

  1. 理解backtracking

在条款4的基础上解释backtracking就很容易了。当NFA发现自己吃多了，一个一个往回吐，边吐边找匹配，这个过程叫做backtracking。由于存在这个过程，在NFA匹配过程中，特别是在编写不合理的正则式匹配过程中，文本被反复扫描，效率损失是不小的。明白这个道理，对于写出高效的正则表达式很有帮助。

发表于 @ 2007年03月03日 23:02:00 评论(16) 编辑
新一篇: 小学教育的问题 旧一篇: C++0x草案将于年内发表，C++即将重大升级评论

#g9yuayon 发表于2007-03-04 12:37:15 IP: 74.123.144.*

孟岩老大，有些地方没有看明白啊。我一条一条说吧。

  1. 掌握一门正则表达式语言。”因此，有心者应当掌握一门正则

表达式语言。”

这里的语言到底指什么呢？用库也好，用内置Regex支持也好，本质都是写出正确的表达式吧。API调用方式只是末节。不管是Pattern.compile(“ab”).matcher(“aaaab”).maches()，还是 “aaaab” =~ /ab/, 还是Regexp.new(“ab”).match(“aaaaab”), 核心都是ab这个regex。而通俗讲，regex的集合就是正则语言了。那这里孟老师单独提出的“正则表达式语言”指什么呢？

  1. 理解DFA和NFA。

这一节有好些我不明白的地方。

DFA捏着文本串去比较正则式，看到一个子正则式，就把可能的匹

配串全标注出来，然后再看正则式的下一个部分，根据新的匹配结

果更新标注。

有个例子甚至图例就好了。按理说DFA就一状态机，我们用它匹配的时候也是一个一个读入被匹配的字串的字符，根据DFA箭头上的字符走到DFA不同的状态上。 如果最后能走到结束状态，就表示匹配成功。如果走不下去了，就表示匹配结束。把可能匹配的串全标注出来是什么意思啊？感觉孟老大想说把已经匹配的字串标注出来？如果说是具体的实现方法，应该不是DFA的本质吧？

而NFA是捏着正则式去比文本，吃掉一个字符，就把它跟正则式比

较，匹配就记下来：“某年某月某日在某处匹配上了！”，然后接

着往下干。一旦不匹配，就把刚吃的这个字符吐出来，一个个的

吐，直到回到上一次匹配的地方。

这是对NFA做backtracking的通俗说法吧？个人以为这样说没有点到NFA的关键：在某个状态上相同的输入可以导致不同的路径（稍微严格一点，NFA的过渡函数返回的是一个状态集合，而不是单值）。而这样可以直观对应(abc def)这样带分支选择的表达式。孟老大解释的backtracking应该算具体的实现方法吧？这种方法比较流行，但并不唯一。还有种效率更高的方法是遇到需要猜哪条路径的时候，NFA克隆自己，同时走上所有可能路径。每一步匹配得到的状态是多个可能状态的集合。这种方法是1968年一个叫Thompson的老大提出来的，号称可以得到更有效率的regex引擎。这里有比较通俗的讲解：http://swtch.com/~rsc/regexp/regexp1.html

关于NFA和DFA的区别好像也是指实现上的区别。孟老大列出的5条从原理上来说好像都不是本质区别。

  1. DFA对于文本串里的每一个字符只需扫描一次，比较快，但特

性较少；NFA要翻来覆去吃字符、吐字符，速度慢，但是特性丰

富，所以反而应用广泛，当今主要的正则表达式引擎，如Perl、>Ruby、Python的re模块、Java和.NET的regex库，都是NFA的。

这里提到的有些区别是不是该算作所用正则表达式的区别啊？如果我们的表达式是(abc def)，而我们又把这个表达式翻译成NFA（最自然的选择），当然就需要backtracking。问题是，每一个NFA都有对应它的DFA（用幂集转换法）。所以上面说的区别#g9yuayon 发表于2007-03-04 12:44:25 IP: 74.123.144.*

PS., 投票结果有点意思。居然有老大认为正则表达式不是必备技术。如果不是，那老大们怎么回答诸如“找出1000个文件里所有10位电话号码，电话号码中可能有空格，破折号。区号可能被括号括起来”这类仅仅是用于电话初选的题目呢？如果不能说出诸如一行grep或者regex的老大肯定被筛掉的说。#myan 发表于2007-03-04 17:30:47 IP: 221.218.163.*

g9的问题我得回答。

为什么要掌握一个正则表达式语言，我是从实践出发提出这一点的。根据我的观察，即使配备了Regex库，C、Java、C#、VB等语言的使用者也不太愿意使用。为什么呢？那些语言的文化传统就不是用regex解决问题，再加上使用库还是有那么一点点麻烦，所以Java 1.4推出也不下5年了，Java开发者中熟悉regex的人还是不多。别说Java/.NET，Python中re用起来够方便的吧，我发现一般Python用户的regex使用也不积极，大家还是用string类中提供的那些函数哼哧哼哧去攒结果。反之，一个熟悉Perl或者awk的人，regex几乎肯定比较熟练，用regex解决问题几乎成了本能。这就是不同的工具在实践中对其用户产生的不同效果。在实际当中，我遇到的能够熟练使用Java regex的人，通常都有一些Perl背景，或者更甚，具有比较深厚的编译基础。否则，面对类似 “截取一个字符串的第一个字（可能是汉字，也可能是英文单词）” 这样的问题，即使是用了很多年C、Java的人，也很可能自己去攒一个while loop。

至于NFA和DFA，碰巧你给出的那篇文章我也认真读过。我这里给出的确实是一种通俗的说法，不精确也不本质。一方面因为我对这个问题的认识还不到位，这是非科班出身的我不得不承认的现实，需要时间去克服。另一方面，我写这篇文章的目的，是帮助一般正则表达式工具的用户理解他们手里的工具的实际情况。大部分用户根本不会去自己写一个正则表达式引擎，所以告诉他们另外的可能算法没什么意义，关键是知道自己手上现成工具的优缺点，扬长避短。这也是我写这篇文章的出发点。Perl没有采用Thompson算法，Java和.NET也没有，这就是现实，一般开发者还是要面对这个现实。

感谢你高质量的评论。#g9yuayon 发表于2007-03-05 00:06:33 IP: 74.123.144.*

我明白了，孟老师文中的“正则表达式语言”就是那些内置了正则表达式的语言，而且编程文化上鼓励用正则表达式的编程语言，比如Perl。的确象孟老师说的那样，文化的感染力巨大。网上铺天盖地的Perl教程和代码，少有不用到regex的，再加上/regex/这样的句式使用方便，初学者自然会积极使用。

才发现评论有字数限制。最后结尾的部分被截掉了。接着第一个评论末尾：

所以上面说的区别里的“特性丰富”并不一定成立。既然每一个NFA都有对应的DFA，区别里的2, 3, 4也就是实现上的细节差异了吧？

  1. NFA可能会陷入递归调用的陷阱而表现得性能极差。

递归本身并不是导致速度低的原因吧？我觉得说backtracking更准确一点。一点完全题外话，我们编程时用的正则表达式已经超出了正则语言的范畴。应该是间于正则语言和Context-free语言之间的东东了，学名squares。比如说使用了grouping和back referencing的表达式(.*)\1，就不属于正则语言里的表达式。当然，这样的开销也增大了。有闲人证明过，如果\1这种back reference不限制数目，匹配的时间复杂度是NP-Hard。用Larry Wall在Apocalypse 5（http://www.perl.com/pub/a/2002/06/04/apo5.html）里的话来说，就是编程上正则表达式已经和理论上的正则表达式联系不多了。所以Larry Wall建议大家用regex，而不要用正则表达式，以示区别。

最后不得不感谢一下，孟老师肯写、CSDN肯登这些扎实提高我们基础水平的好文章，是我们的福气。

#chai2010 发表于2007-03-05 13:27:05 IP:

觉得http://www.zuijia.net/list/show/101的投票分类就有问题。

像正则表达式与编译原理本来就是属于算法的一部分。

还有SQL一条也让人也觉得不论不类。

==

http://qdevelop.googlepages.com#lanzhengpeng2 发表于2007-03-05 20:17:46 IP: 221.216.249.*

好久没有看到孟大出来喷了。最近一次看到孟大的文章的时候，附带一个光头的照片――吓了我一大跳，怎么传说中的孟岩是一个老头？！然后翻了一页后，看到了上半身的像――哦，推测起来也就30多岁，然后心理终于舒服了点。

关于正则表达式，说得很贴切。我原来也是不太立即有限自动机里的DFA和NFA的区别，自写完了自己那个正则表达式后，算是彻底的明白了。看了这文章，深有共鸣之处！#lyx791009 发表于2007-03-05 21:56:40 IP:

正则表达式是编译原理里面的一部分，认真学过的话，都不会陌生。正则表达式、NFA、DFA在计算理论中是等价的，其中我觉得最有价值的部分是NFA和DFA的数学等价性，在书写某个具体文法时NFA比较好写，但是最终到程序部分时，还是要靠DFA，需要一个算法上的转换，当年看证明的时候，花了好几个月才明白。它们通常应用于编译器的词法扫描部分，然后是比有限自动机更高级的下推自动机，这个对应编译器中的语法生成部分，构造语法树。在Linux下，可以用Flex和Bison这两个工具来学习，弄得好的话，写个小小的编译器或解释器也是挺好玩的。#turingbook 发表于2007-03-06 00:38:47 IP: 222.130.196.*

这一期程序员的专题令我大有戚戚焉的感觉，图灵计划出版一系列基本功小册子，就包括正则表达式和SQL等等。

正则表达式好像很多术语没有统一，不知g9和孟兄是否有时间帮我们审审？#limodou 发表于2007-03-06 10:31:42 IP: 202.106.78.*

用不用，是否可以用好，是人的问题，不仅仅是语言的问题。正则式不管怎么样都有一定的学习的门槛，如果有更简单的方法，实是没有必要一定要使用正则式。如果说python人用得少，我想主要是这个原因。其实在python中有关词法解析的东西简直是太多了。甚至象django项目的url配置就是使用正则表达式来控制的。#dewy61786 发表于2007-03-06 14:02:31 IP: 218.80.198.*

我已经使用了几年了,习惯了.主要是使用LEX&YACC工具进行代码分析,做的就是编译方面的工具,所以个人人为正则表达式使用起来还是可以的,而且工作效率非常的高!#zhanghandong 发表于2007-03-09 17:39:47 IP:

http://blog.csdn.net/’http://blog.csdn.net/myan//’

我从圈子里点击楼主的blog，是上面的URL地址。。。。。。

CSDN不会正则表达式？楼主没有教他们啊。。。#iambic 发表于2007-03-11 22:50:37 IP:

在实际当中，我遇到的能够熟练使用Java regex的人，通常都有一些Perl背景，或者更甚，具有比较深厚的编译基础。

呵呵，同感。正则表达式在使用上其实很简单，但是习惯用的并不太多。

不过有UNIX背景的应该都没问题。#steel_de_lee 发表于2007-03-12 21:59:38 IP: 221.219.198.*

最好别去钻研正则表达式，这是个无底洞……

俺当年研究正规式，然后就入魔了，现在正在研究LL(n)的分析器，其实写代码，什么快就什么好，我研究了两年多的词法/语法分析，最终觉得还是直观简单才是最好，所以不要以不会正规式而懊悔，除非你干得东西实在无法用常规方法解决了，否则还是使用string吧！！#cuilj 发表于2007-03-23 13:48:23 IP: 221.219.117.*

c++老师说过必备的知识中包括正则表达式的应用，但到现在还没接触过，现在既然有机会学习一下，决不放过。#chenrongjie 发表于2007-04-20 17:48:27 IP: 121.31.14.*

简单的才是最美的

简单的才是最强大的

简单的才是最有未来的#Kim4Apple 发表于2007-06-26 13:53:41 IP: 219.136.219.*

做程序员就要做 操作系统 和 编译器

Published on Aug 22, 2008 in categories non-tech 

Powered by Jekyll and Theme by solid

本站总访问量次