Anrs Hu

前两天为了准备关于lambda递归的简报又把我的 SICP 翻出来看了几页，看到 Lisp 的狗血发展史时，忍不住想邪恶的美帝可真能折腾呀。

呼，终于写完了，第一次写技术八卦呀，比想象中的累多了，g9 我赞美你…

“匹配过程”应该是学习正则表达式的第一堂课，但国内出版的相关图书大多对这一主题语焉不详，结果导致很多使用正则表达式的程序员都知其然却不知其所以然，想要对表达式进行优化也完全不知道从何入手。所以下面尽量用简单的例子来把匹配过程描述清楚，欢迎大家拍砖。

首先是最简单的情况，用表达式 a 匹配目标文本 django 的过程。正则引擎首先用 a 和目标文本中的 d 进行比较，此时匹配失败，引擎会将当前待匹配目标字符前推到第2个字符 j 后再进行比较，结果还是匹配失败，引擎继续前推当前待匹配目标字符到 a 并进行比较，这回匹配成功，于是引擎返回匹配的内容并退出。当前待匹配目标字符就是第一次等待匹配的实际参与者，如果匹配失败，引擎就会将当前待匹配目标字符符前推到目标文本的下一个字符，然后再与当前待匹配表达式字符进行比较（在第1个例子中，当前待匹配表达式字符始终都是 a。当前待匹配目标字符的说法实在太绕舌，下面分别将之简称为当前表达式和当前字符），一旦目标文本已经结束却依然没有匹配成功，那么引擎就会报告整个正则表达式匹配失败并退出。

接下来将原来的表达式扩展为 an，目标文本依然是 django，首先将当前表达式 a 和当前字符 d 进行比较，匹配失败，所以前推当前字符到 j 并与当前表达式 a 进行比较，还是失败，继续前推当前字符到 a，这次匹配成功，于是将当前表达式和当前字符都向前推进，得到当前表达式 n 和当前字符 n，进行比较时还是匹配，再继续前推当前表达式时，引擎发现表达式已经结束，于是返回匹配的内容并退出。当正则表达式包含多个字符时，如果当前匹配成功，就同时前推当前表达式和当前字符并进行下一次比较，否则就只前推当前字符并将之继续与当前表达式进行比较。

再考虑以 an 匹配 there is a django boy 的情形。首先是当前表达式 a 和当前字符 t 进行比较，匹配失败，前推当前字符，继续比较，还是失败，直到前推当前字符到第1个 a 时，才匹配成功。这时因表达式尚未结束，所以除了前推当前字符到 a 以外，还同时前推当前表达式到 n，结果匹配失败。这时，正则引擎会做两件事，重置当前表达式为整个正则表达式的第1个字符，其次是将当前字符设置为第1次成功匹配字符的下1个字符，这里的第1次成功匹配字符是 a，a 的下一个字符就是空格符，然后再重新开始匹配，也就是将 a 与空格符进行比较，匹配失败，于是前推当前字符，比较、前推，再比较、再前推，直到当前表达式 a 再次与 django 中的 a 匹配成功之后，引擎又同时前推当前表达式与当前字符并进行比较，匹配成功后继续前推时发现表达式已经结束，于是引擎返回匹配的内容并退出。这里的关键点是如果当前表达式和当前字符同时前推后匹配失败，那么当前表达式重置到整个正则表达式的第1个字符，当前字符重置为第1次成功匹配字符的下1个字符，并继续进行比较。

上面几个都是不断前推并进行比较的例子，在遇到需要进行最长匹配的量词元字符时，正则引擎则可能会不断后退当前字符并和当前表达式进行比较，还是以实例来说话，考虑以正则表达式 a.*g 匹配目标文本 there is an elegant django 的情况。当 a 和点号元字符都匹配成功，前推当前表达式后发现是需要最长匹配的元字符 *，于是直接将当前字符彻底前推到整个目标文本的末尾结束符（由于结束符不可见，可以将其想成 C 中的 ‘\0′），并将中间忽略过的字符统统设为匹配成功，这时引擎侦测到表达式并未结束，前推当前表达式到 g 时发现与结束符并不匹配，于是引擎回退当前字符到 o 后再进行比较，还是匹配失败，于是当前字符继续回退到 g，终于匹配成功，之后引擎发现整个正则表达式已经结束，于是返回匹配的内容并退出，匹配的内容就是 an elegant djang

(这里顺便感谢 .rex 同学今天送我 O’Reilly 最新出版的”Regular Expressions Cookbook“一书，你大无畏的奉献精神深深感动了我…)

最早匹配和量词的最多匹配是两条基本的正则表达式匹配原则，其直接影响到表达式的运行效率甚至关系到是否能获得期望的匹配结果。重要的是，这也是所有类型的正则引擎都遵循的普适原则之一。

以表达式 go 匹配目标文本 django is elegance, go to it 的情况来说，当匹配到第一个 go 时，引擎就会停止前进，匹配结果也就是 django 中的 go。所谓最早匹配正是“第一次匹配成功，引擎即告退出，绝不多做”的意思。

而在带分支的情况下，正则引擎会先尝试所有分支条件，有一个分支匹配成功即退出，全部分支都匹配失败就前进到目标文本的下一个字符重新开始尝试匹配所有分支。这样就能保证更早地获得匹配结果（这里的“早”是指目标文本中最左边或最右边的空间概念，而非通常意义下运行效率的时间概念）。

举例来说，以表达式 ruby|python|perl 来匹配 there’re python, perl, ruby and etc 的话，结果就是 python 而非 ruby，因为正则引擎总是先尝试所有分支，有一个分支匹配成功就退出，全部分支都匹配失败就前进到目标文本的下一个字符。比较类似于程序中的逻辑短路，但表达式中分支的排列顺序对匹配结果没有丝毫影响，因为正则引擎总是返回目标文本中能满足最早（最左或最右）匹配的结果

星晨大海间无数刚跨入 regex 领域的童鞋们总会混淆 single line 和 multiline 这两种模式，认为这是两种互斥的模式，这都怪 Larry 大叔胡搞瞎搞的起名字，还是小鄙视一下大叔吧，但是大叔的丰功伟绩依然让我辈心向往之。

单行模式主要用于改变点号的匹配规则，而多行模式用于改变 ^ 和 $ 的匹配规则；默认情况下单行模式和多行模式均处于 off 状态，可以分别激活或同时激活这两种模式。

默认情况下，点号能够匹配除换行符外的所有字符，如果想要匹配到换行符的话，就需要激活单行模式，单行模式下点号就能匹配天地间的一切字符了，所以余大将之译为点号通配模式。

而 ^ 和 $ 在默认情况下是匹配整个目标文本起始和结束的锚，也就是说等价于 \A 和 \Z 的，如果激活了多行模式的话，^ 和 $ 就变成了能够匹配到行起始和行结束的锚。

所以，最后说一句，单行模式和多行模式之间，一毛钱关系都没有。

很多时候我们在构造正则表达式时不会考虑编码的问题，因为默认的 ASCII 编码已经足够我们应对大多数开发场景，但这并不代表对编码的需求就不存在，典型的例子就是用户注册时，要求用户名一定要是中文的情况，这种情况下 ASCII 编码就无能为力了。现在轮到 Unicode 这砣灵丹妙药出场了。

通常情况下我们都认为一个字符就对应到一个 Unicode 代码点，即一一对应的关系。但这里存在理解上的偏差，一般人所谓的单个字符在 Unicode 编码中可能并不和单个代码点对应而是由多个代码点组合而成。比如 å 这种带声调修饰的单个字符在 Unicode 编码中就是由 \u0061 和 \u030A 这两个代码点组合而成。这就又给我们带来了新的问题，正则表达式的点号元字符在匹配这样的由多个代码点组合而成的字符时，是匹配一个代码点映射的单字符还是匹配多个代码点合成后映射到的单字符？

my $str = “å”;
$str =~ m/(.)/;
print “normal: $1\n”;
$str =~ m/(\X.)/;
print “\\X mode: $1\n\n”;

上面代码输出效果如下：

可以看到要想正确的匹配 å 单字，必须通过 \X 来显示通知正则引擎“匹配一个 Unicode 代码点组合”。不幸的是并不是所有编程语言的正则表达式引擎都实现了 \X 模式。（所以到目前为止，在字符处理方面 Perl/PCRE 还是当之无愧的王者啊！）

昨天 RubyConf China 在上海召开，与会嘉宾包括 Ruby 教主 Matz 在内的多位国内外顶级大牛，虽然身在成都，但我还是通过曹力向现场嘉宾提了一个问题“如何说服老板和客户使用 Rails 开发企业级应用程序”，答曰：

• 快速响应需求变更
• 系统可维护性更高
• 所需开发人员更少

相信这会给使用各种 Rails 类框架的程序员们相当的启发吧。顺便说一下曹力同学是《Professional JavaScript for Web Developers》中文版的译者之一，功力相当深厚的说，这里是他的博客，大家去围观啊！:)

djrum 这个名字还是有一些特殊含义的。这个词由 dj- 前缀加 -rum 后缀组合而成，前面的 dj 是为了向 django 致敬，因为没有 django 就没有 djrum 项目；后面的 rum 则是为了纪念我人生第一个 .NET 项目 sarum，虽然 sarum 已经消失在岁月的沧桑中…

一句话概括 Project Djrum 就是：基于 Project Babel 的 UI 原型，用 Django 搭建起来的怪异工具集。

btw. babel 和 djrum 均遵循 GPL v3 协议，所以敬请期待吧…