[译]递归正则表达式
Dec 16th
原文在此。rex译于2009年12月15~17日,翻译过程中使用的是google docs@prism@firefox@ubuntu 9.10,很爽的体验。感谢余晟老师在正则和翻译方面的悉心指导。
平时我们用到的正则表达式,其实没那么“规则”。多数编程语言所支持的扩展的正则表达式,其运算能力比起形式语言理论所定义的“规则”正则表达式要强得多。
rex注:在这里其实可以看到,如果将正则表达式译为正规表达式,一切就都通顺了:
平时我们用到的正规表达式,其实没那么“正规”。多数编程语言所支持的扩展的正规表达式,其运算能力比起正式语言理论所定义的“正规”正规表达式要强得多。regular expression的日文是“正规表现”,在鸟哥书中,好像也将其称为正规表达式。via
例如,经常用到的捕获缓存,就是用来帮助我们临时存储任意正则表达式模式,以便重复使用。 又如,“环视断言”能让正则表达式引擎在做决定之前先偷偷看看环视一下。这些扩展让正则表达式非常强大,足以描述一些“上下文无关语法”。
Perl语言的正则表达式引擎特性异常丰富,其特征之一是懒惰正则子表达式(Lazy regular subexpressions),格式为(??{code}),其中的“code”可以是任意一段perl程序,该子表达式可能匹配时,这段程序就会执行。
我们可以利用这一特征来编写出非常有趣的东西,即将正则表达式自身嵌在它的“code”部分,由此生成递归的正则表达式(a recursive regular expression)!
一直以来,正则表达式无法匹配0n1n这种表达式,也就是由若干个0以及同等数量的1所组成的字符串。如果使用懒惰正则子表达式,这一经典问题就迎刃而解。
下面是匹配0n1n字串的perl正则表达式代码。
$regex = qr/0(??{$regex})?1/;
rex注:紫龙书第四章有云:“文法是比正则表达式表达能力更强的表示方法。每个可以使用正则表达式描述的构造,都可以使用文法来描述,但是反之不成立。换句话说,每个正则语言都是一个上下文无关语言,但是反之不成立。”书中交待的正则,也应该是指的常规正则表达式,而非现代语言中的扩展的正则表达式。一般使用正则表达式来构造小部件,而使用文法来组建语言框架。
此正则表达式匹配一个字符0,之后是正则表达式自身0或1次,之后是字符1。如果正则表达式自身部分不能匹配,那么它只能匹配01;如果自身部分可以匹配,则正则表达式匹配的是00($regex)?11,此时若不能匹配自身则结果是0011,若可以匹配就是000($regex)?111,……依次顺延。
下面是匹配050000150000的Perl程序:
1 2 3 4 5 6 7 8 9 10 11 | #!/usr/bin/perl $str = "0"x50000 . "1"x50000; $regex = qr/0(??{$regex})*1/; if ($str =~ /^$regex$/) { print "yes, it matches"; } else { print "no, it doesn't match"; } |
现在来看题图所示的Yo Dawg正则表达式。你先猜猜它的作用?正确答案是,它匹配(foo(bar())baz)这样完全嵌套的括号表达式(fully parenthesized expression)或((()()())())这样的平衡括号表达式(balanced parentheses)。
1 2 3 4 5 6 7 8 9 | $regex = qr/ \( # (1) match an open paren ( #(1),此处匹配开括号 ( # followed by #(2),紧接着是 [^()]+ # (3) one or more non-paren character #(3),1个或多个非括号字符 | # OR #(4),或 (??{$regex}) # (5) the regex itself #(5),正则式自身 )* # (6) repeated zero or more times #(6),重复0或多次 \) # (7) followed by a close paren ) #(7),紧接着是闭括号 /x; |
rex注:关于Yo Dawg图片的含义,可以参考这里。基本上是全是“Yo dawg, I herd you like X, so we put a Y in your Y so you can Z while you Z”的结构的配图文字。
构造此正则表达式的思路是这样的。对于完全嵌套的括号表达式,它的开始字符是一个开括号。这是最简单的一步,我们直接写出(上面程序中的(1))。同理,它的结束字符是闭括号,于是得到(7)。现在该动脑筋了,括号中间是什么呢?对,它可以是既不是开括号又不是闭括号的任意字符(第(3)点),也可以是另一个完全嵌套的表达式(即第(5)点)。所有的这些,既可以只匹配0次(第(3)点),以便构造最小的完全嵌套括号表达式(),也可以匹配多次来匹配较复杂的表达式。
去掉 /x 选项(即,不再使用多行风格的注释模式),可以简记为:
$regex = qr/\(([^()]+|(??{$regex}))*\)/;
但是切勿在正式产品中使用这一特性,它太诡异,不好把握。建议使用较稳定成熟的Text::Balanced 或 Regexp::Common 模块。
rex注:对于(??{code}),perl官方的提示是:此正则表达式仅作测试使用,可能有更新而不作提示。代码执行时产生的副作用,因版本而异,运行结果或有不同,取决于正则引擎的后期优化。
最后提醒大家,在Perl 5.10中已经可以使用递归捕获缓存来替代懒惰代码子表达式了,运行结果相同。
下面是匹配0n1n的递归捕获缓存语法(?N)的实现:
my $rx = qr/(0(?1)*1)/;
(?1)*的含义是“匹配第一组0或多次”,这里的第一组是指整个正则表达式。
请自行动手,重写平衡括号的正则表达式,当作练习。
祝玩得开心!
[转]正则表达式高级技巧基本概念实例详解[译]
Jun 2nd
rex按:本文转自笨人干笨活的文章:正则表达式高级技巧基本概念实例详解[译],其RSS在这里:http://blog.benhuoer.com/subscribe/。
英文原文来自Smashing Magazine。由笨活儿翻译。转载请注明出处。
正则表达式(Regular Expression, abbr. regex) 功能强大,能够用于在一大串字符里找到所需信息。它利用约定俗成的字符结构表达式来发生作用。不幸的是,简单的正则表达式对于一些高级运用,功能远远不够。若要进行筛选的结构比较复杂,你可能就需要用到高级正则表达式。
本文为您介绍正则表达式的高级技巧。我们筛选出了八个常用的概念,并配上实例解析,每个例子都是满足某种复杂要求的简单写法。如果你对正则的基本概念尚缺乏了解,请先阅读这篇文章,或者这个教程,或者维基条目。
这里的正则语法适用于PHP,与Perl兼容。
1. 贪婪/懒惰

所有能多次限定的正则运算符都是贪婪的。他们尽可能多地匹配目标字符串,也就是说匹配结果会尽可能地长。不幸的是,这种做法并不总是我们想要的。因此,我们添加“懒惰”限定符来解决问题。在各个贪婪运算符后添加“?”能让表达式只匹配尽可能短的长度。另外,修改器“U”也能惰化能多次限定的运算符。理解贪婪与懒惰的区别是运用高级正则表达式的基础。
贪婪操作符
操作符 * 匹配之前的表达式零次或零次以上。它是一个贪婪操作符。请看下面的例子:
preg_match( '/<h1>.*<\/h1>/', '<h1>这是一个标题。</h1> <h1>这是另一个。</h1>', $matches );
句点(.)能代表除换行符外的任意字符。上面的正则表达式匹配 h1 标签以及标签内的所有内容。它用句点(.)和星号(*)来匹配标签内的所有内容。匹配结果如下:
<h1>这是一个标题。</h1><h1>这是另一个。</h1>
整个字串都被返回。* 操作符会连续匹配所有内容—— 甚至包括中间的 h1 闭合标签。因为它是贪婪的,匹配整个字串是符合其利益最大化原则。
懒惰操作符
把上面的式子稍作修改,加上一个问号(?),能让表达式变懒惰:
/<h1>.*?<\/h1>/
这样它会觉得,只需匹配到第一个 h1 结尾标签就完成任务了。
另一个有着类似属性的贪婪操作符是 {n,} 。它代表之前的匹配模式重复n次或n次以上,如果没有加上问号,它会寻找尽可能多的重复次数,加上的话,则会尽可能少重复(当然也就是“重复n次”最少)。
# 建立字串
$str = 'hihihi oops hi';
# 使用贪婪的{n,}操作符进行匹配
preg_match( '/(hi){2,}/', $str, $matches ); # matches[0] 将是 'hihihi'
# 使用堕化了的 {n,}? 操作符匹配
preg_match( '/(hi){2,}?/', $str, $matches ); # matches[0] 将是 'hihi'
2. 回返引用(Back referencing)

有什么用?
回返引用(Back referencing)一般被翻译成“反向引用”、“后向引用”、“向后引用”,个人觉得“回返引用”更为贴切[笨活儿]。它是在正则表达式内部引用之前捕获到的内容的方法。例如,下面这个简单例子的目的是匹配出引号内部的内容:
# 建立匹配数组 $matches = array(); # 建立字串 $str = ""This is a 'string'""; # 用正则表达式捕捉内容 preg_match( "/(\"|').*?(\"|')/", $str, $matches ); # 输出整个匹配字串 echo $matches[0];
它会输出:
"This is a'
显然,这并不是我们想要的内容。
这个表达式从开头的双引号开始匹配,遭遇单引号之后就错误地结束了匹配。这是因为表达式里说:("|'),也就是双引号(")和单引号(')均可。要修正这个问题,你可以用到回返引用。表达式\1,\2,…,\9 是对前面已捕获到的各个子内容的编组序号,能作为对这些编组的“指针”而被引用。在此例中,第一个被匹配的引号就由\1代表。
如何运用?
将上面的例子中,后面的闭合引号替换为1:
preg_match( '/(\"|').*?\1/', $str, $matches );
这会正确地返回字串:
"This is a 'string'"
译注思考题:
如果是中文引号,前引号和后引号不是同一个字符,怎么办?
还记得PHP函数 preg_replace 吗?其中也有回返引用。只不过我们没有用 \1 … \9,而是用了 $1 … $9 … $n (此处任意数目均可)作为回返指针。例如,如果你想把所有的段落标签<p>都替换成文本:
$text = preg_replace( '/<p>(.*?)</p>/', "<p>$1</p>", $html );
参数$1是一个回返引用,代表段落标签<p>内部的文字,并插入到替换后的文本里。这种简便易用的表达式写法为我们提供了一个获取已匹配文字的简单方法,甚至在替换文本时也能使用。
3. 已命名捕获组(Named Groups)
当在一个表达式内多次用到回调引用时,很容易就把事情搞混淆,要弄清那些数字(1 … 9)都代表哪一个子内容是件很麻烦的事。回调引用的一个替代方法是使用带名字的捕获组(下文简称“有名组”)。有名组使用(?P<name>pattern)来设定,name代表组名,pattern是配合该有名组的正则结构。请看下面的例子:
/(?P<quote>"|').*?(?P=quote)/
上式中,quote就是组名,"|'是改组匹配内容的正则。后面的(?P=quote)是在调用组名为quote的有名组。这个式子的效果和上面的回调引用实例一样,只不过是用了有名组来实现。是不是更加易读易懂了?
有名组也能用于处理已匹配内容之数组的内部数据。赋予特定正则的组名也能作为所匹配到的内容在数组内部的索引词。
preg_match( '/(?P<quote>"|\')/', "'String'", $matches ); # 下面的语句输出“'”(不包括双引号) echo $matches[1]; # 使用组名调用,也会输出“'” echo $matches['quote'];
所以,有名组并不只是让写代码更容易,它也能用于组织代码。
4. 字词边界(Word Boundaries)

字词边界是字串里的字词字符(包括字母、数字和下划线,自然也包括汉字)和非字词字符之间的位置。其特殊之处就在于,它并不匹配某个实在的字符。它的长度是零。 \b 匹配所有字词边界。
不幸的是,字词边界一般都被忽视掉了,大部分人都没有在意他的现实意义。 例如,如果你想要匹配单词“import”:
/import/
注意了!正则表达式有时候很调皮的。下面的字串也能和上面的式子匹配成功:
important
你或许觉得,只要在import前后加上空格,不就可以匹配这个独立的单词了:
/ import /
那如果遇上这种情况呢:
The trader voted for the import
当 import 这个词在字串开头或者结尾时,修改后的表达式仍然不能用。因此,考虑各种情况是必须的:
/(^import | import | import$)/i
别慌,还没完呢。如果遇到标点符号了呢?就为了满足这一个单词的匹配,你的正则可能就需要这样写:
/(^import(:|;|,)? | import(:|;|,)? | import(\.|\?|\!)?$)/i
对于只匹配一个单词来说,这样做实在是有点大动干戈了。正因如此,字词边界才显得意义重大。要适应上述要求,以及很多其他情况变种,有了字符边界,我们所需写的代码只是:
/\bimport\b/
上面所有情况都得到了解决。 \b 的灵活性就在于,它是一个没有长度的匹配。它只匹配两个实际字符之间想象出的位置。它检查两个相邻字符是否是一个为单字,另一个为非单字。情况符合,就返回匹配。如果遇到了单词的开头或结尾, \b 会把它当成是非单词字符对待。由于import里面的 i 仍然被看成是单词字符,import 就被匹配出来了。
注意,与\b相对,我们还有\B,此操作符匹配两个单字或者两个非单字之间的位置。因此,如果你想匹配在某个单词内部的‘hi’,可以使用:
\Bhi\B
“this”、“hight”,都会返回匹配,而“hi there”则不会返回匹配。
5. 最小组团(Atomic Groups)

最小组团是无捕捉的特殊正则表达式分组。通常用来提高正则表达式的效能,也能用于消除特定匹配。一个最小组团可以用(?>pattern) 来定义,其中pattern是匹配式。
/(?>his|this)/
当正则引擎针对最小组团进行匹配时,它会跳过组团内标记的回溯位置。以单词“smashing”为例,当用上面的正则表达式匹配时,正则引擎会先尝试在“smashing”里寻找“his”。显然,找不到任何匹配。此时,最小组团就发挥作用了:正则引擎会放弃所有回溯位置。也就是说,它不会尝试再从“smashing”里查找“this”。为什么要这样设置?因为“his”都没有返回匹配结果,包含有“his”的“this”当然就更匹配不了了!
上面的例子并没有什么实用性,我们用/t?his?/ 也能达到效果。再看看下面的例子:
/\b(engineer|engrave|end)\b/
如果把“engineering”拿去匹配,正则引擎会先匹配到“engineer”,但接下来就遇到了字词边界,\b,所以匹配不成功。然后,正则引擎又会尝试在字串里寻找下一个匹配内容:engrave。匹配到eng的时候,后面的又对不上了,匹配失败。最后,尝试“end”,结果同样是失败。仔细观察,你会发现,一旦engineer匹配失败,并且都抵达了字词边界,“engrave”和“end”这两个词就已经不可能匹配成功了。这两个词都比engineer短小,正则引擎不应该再多做无谓的尝试。
/\b(?>engineer|engrave|end)\b/
上面的替代写法更能节省正则引擎的匹配时间,提高代码的工作效率。
6. 递归(Recursion)

递归(Recursion)用于匹配嵌套结构,例如括弧嵌套, (this (that)),HTML标签嵌套<div><div></div></div>。我们使用(?R)来代表递归过程中的子模式。下面是一个匹配嵌套括弧的例子:
/\(((?>[^()]+)|(?R))*\)/
最外层使用了反义符的括号“\(”匹配嵌套结构的开端。然后是一个多选项操作符( * | * ),可能匹配除括号外的所有字符 “(?>[^()]+)”,也可能是通过子模式“(?R)”来再次匹配整个表达式。请注意,这个操作符会尽量多地匹配所有嵌套。
递归的另一个实例如下:
/<([\w]+).*?>((?>[^<>]+)|((?R)))*<\/\1>/
以上表达式综合运用了字符分组,贪婪操作符、回溯,以及最小化组团来匹配嵌套标签。第一个括弧内分组([w]+)匹配出标签名,用于接下来的应用。若找到这尖括号样式的标签,则尝试寻找标签内容的剩余部分。下一个括弧括起来的子表达式和上一个实例非常相似:要么匹配不包括尖括号的所有字符 ?>[^<>]+,要么递归匹配整个表达式(?R)。表达式最后的</1>代表闭合标签。
7. 回调(Callbacks)

匹配结果中的特定内容有时可能会需要某种特别的修改。要应用多重而复杂的修改,正则表达式的回调就有了用武之地。回调是用于函数preg_replace_callback中的动态修改字串的方式。你可以为preg_replace_callback指定某个函数为参数,此函数能接收匹配结果数组为参数,并将数组修改后返回,作为替换的结果。
例如,我们想将某字串中的字母全部转变成大写。十分不巧,PHP没有直接转化字母大小写的正则操作符。要完成这项任务,就可以用到正则回调。首先,表达式要匹配出所有需要被大写的字母:
/\b\w/
上式同时使用了字词边界和字符类。光有这个式子还不够,我们还需要一个回调函数:
function upper_case( $matches ) {
return strtoupper( $matches[0] );
}
函数upper_case接收匹配结果数组,并将整个匹配结果转化成大写。 在此例中,$matches[0]代表需要被大写化的字母。然后,我们再利用preg_replace_callback实现回调:
preg_replace_callback( '/\b\w/', "upper_case", $str );
一个简单的回调即有这般强大的力量。
8. 注释(Commenting)

注释不用来匹配字串,但确实是正则表达式中最重要的部分。当正则越写越深入,越写越复杂,要推译出究竟什么东西被匹配就会变得越来越困难。在正则表达式中间加上注释,是最小化将来的迷糊和困惑的最佳方式。
要在正则表达式内部加上注释,使用(?#comment)格式。把“comment”替换成你的注释语句:
/(?#数字)\d/
如果你打算把代码公之于众,为正则表达式加上注释就显得尤为重要。这样别人才能更容易看懂和修改你的代码。和其他场合的注释一样,这样做也能为你重访自己以前写的程序时提供方便。
考虑使用“x”或“(?x)”修改器来格式化注释。这个修改器让正则引擎忽略表达式参数之间的空格。“有用的”空格仍然能够通过[ ]或\ (反义符加空格)来匹配。
/ \d #digit [ ] #space \w+ #word /
上面的代码与下面的式子作用一样:
/\d(?#digit)[ ](?#space)\w+(?#word)/
请时刻注意代码的可读性。
更多资源(英文)
- Regular-Expressions.info Comprehensive website on regular expressions
- Cheat SheetInformative regular expressions cheat sheet
- Regex GeneratorJavaScript regular expressions generator
关于作者
Karthik Viswanathan 是一个喜欢编程和做网站的高中生。你可以到他的博客上查看他的作品:Lateral Code。你也可以关注一下他的线上Twitter应用。
[译]正则表达式:从菜鸟到大师
Feb 3rd
Author: Jan Goyvaerts
Publish Date: 2 Feb. 2009
Blog entry: http://www.regexguru.com/2009/02/from-regex-newbie-to-regex-guru/
Translated By: Rex (http://iregex.org)
Rex注:本文是Jan Goyvaerts为自己的著作《Regular Expression Cookbook》写的序言中的一段。
One of my last tasks for the Regular Expression Cookbook was to write the preface, including my author bio. I told the story of how I went from my first real encounter with regular expressions in 2000, to the expert I am almost a decade later.
《Regular Expression Cookbook》即将完工,剩余的工作之一是作序,包括写我的作者小传。我讲述了自己如何在2000年第一次遭遇正则表达式,并在近乎十年之后才成为专家的经历。

Comments