2007年01月18日

MasteringRegEx

一、问题

将一个数值字串,从右向左,每三位用逗号分开,比如,将“123456789”替换为“123,456,789”。

二、分析

替换算法的本质是将字串从右向左,每3个字符为一组进行分组,然后在组与组之间插入逗号。

三、语法

正则表达式引入了“预测”和“回顾”这两个概念,它们不是匹配字串,而是匹配一个“位置”,其中预测是正向(自左向右)查看,回顾是反向(自右向左)查看。

(下表中圆括号及其括住的内容,只匹配位置,不匹配文本)
正则表达式 名称 说明 示例
(?=…) 预测 断言子表达式在此位置的右侧 abcd(?=\d) 匹配右侧紧跟数字的abcd
(?!…) 否定预测 断言子表达式不在此位置的右侧 abcd(?!\d) 匹配右侧紧跟的不是数字的abcd
(?<=…) 回顾 断言子表达式在此位置的左侧 (?<=\d)abcd 匹配左侧是数字的abcd
(?<!…) 否定回顾 断言子表达式不在此位置的左侧 (?<!\d)abcd 匹配左侧不是数字的abcd

预测和回顾只是匹配一个位置,其中的子表达式并不被匹配。比如有字符“ABCDEFG”,则正则表达式

(?=EFG)(?<=ABCD)(?<=ABCD)(?=EFG)

就匹配D与E之间的那个位置,而不是匹配EFG,也不匹配ABCD,或其他任何一个字串。 注意,由于只是断言一个位置,所以上述预测和回顾的先后次序并不重要,二者同样都是匹配D与E之间的那个位置。前者的含义是“匹配一个位置,它的右边是 EFG,左边是ABCD”,后者的含义是“匹配一个位置,它的左边是ABCD,右边是EFG”,两者都是同一个意思。下面的Perl在ABCD和EFG之 间插入一个逗号:

$foo = "ABCDEFG";$foo =~ s/(?<=ABCD)(?=EFG)/,/;print $foo;

假定要把某段文本中所有的Jeffs都替换为Jeff’s(匹配到单词边界),那么,就会有如下几种方案:

方案
说明
s/\bJeffs\b/Jeff’s/g 这是最直观的方法,直接把匹配到的Jeffs替换为Jeff’s
s/\b(Jeff)(s)\b/$1′$2/g 分组构造,在两个组之间插入单引号
s/\bJeff(?=s\b)/Jeff’/g 预测,仅匹配“后面紧跟s并在单词边界的Jeff”的右侧那个位置
(其它的如Jeffrey中的Jeff不被匹配)
s/(?<=\bJeff)(?=s\b)/’/g 同时使用预测和回顾,在匹配位置处插入单引号
s/(?=s\b)(?<=\bJeff)/’/g 与上面的行为完全相同,由于预测和回顾只是匹配位置而不是匹配字串,所以先后次序不重要了。

四、解决问题

利用预测和回顾,就可以解决“在数值中插入逗号”的问题了。插入算法是:从右向左把数字,每3个分为一组,在组与组之间插入逗号。也就是说,只要匹配到这些位置,就可以在这些位置上插入逗号。

$foo = "123456789";$foo =~ s/(?=\d\d\d)/,/g;print $foo;

上面的结果是“,1,2,3,4,5,6,789”,显然不是想要的。

正则表达式 结果 说明
s/(?=\d\d\d)/,/g
s/(?=(\d\d\d)+)/,/g
,1,2,3,4,5,6,789 1左边的位置被匹配,因为该位置右边有3个数字(123)
同理,1右边的位置也被匹配,该位置右边有3个数字(234)……
而7的右边位置不再被匹配,因为该位置右边不再有3个数字
s/(?=\d\d\d$)/,/g 123456,789 只有7左边的位置被匹配,因为该点符合以下两个条件:
其右边是3个数字,
且这3个数字在行尾(其右侧什么也没有了)。
s/(?=(\d\d\d)+$)/,/g ,123,456,789 1左边的位置符合条件“其右侧有N组(每组3个数字),且最后一组在行尾”;
2左边的位置不符合该条件,因为其后面是234、567和89,最后的89无法构成一组;
其它同理……
s/(?=(\d\d\d)+$)(?<=\d)/,/g 123,456,789 1左边的位置不再被匹配,因为(?<=\d)的存在,它指示该位置的左侧必须是数字,
而1左边的位置显然不符合。

这个正则表达式替换单个的数字串没问题,但如果想要将“The population of 281421906 is growing”中的281421906替换成281,421,906就无能为力了,原因是$限定了最后一组(3个)数字必须在行尾,因此需要把条件修正为“最后一组数字的右边不是数字”,这就要用到“否定预测”:

s/(?=(\d\d\d)+(?!\d))(?<=\d)/,/g

(微软VBScript.DLL提供的COM对象IRegExp2,文档里说支持“回顾”语法,但实际运用却会抛出一个异常,不知何故)

2007年01月05日

MasteringRegEx

一、Non-Capturing

这个Non-Capturing的确不知道该如何翻译(非捕获?),但意思是明白了。用圆括号括起来的部分可以被捕获到$1、$2……中,但如果起始圆括号后面紧跟一个问号和冒号,就表示本组不需要被捕获到$1、$2……中。

例如,下列正则表达式中

^([-+]?\d+(\.\d*)?)([CF])$

  • 第1个被捕获的组:从第一个左圆括号,到与该左圆括号配对的右括号,被存储到$1中(整数+小数点+小数部分)
  • 第2个被捕获的组:从第二个左圆括号,到与该左圆括号配对的右括号,被存储到$2中(小数点+小数部分)
  • 第3个被捕获的组:从第三个左圆括号,到与该左圆括号配对的右括号,被存储到$3中(C或F)

如果是下面的正则表达式:

^([-+]?\d+(?:\.\d*)?)([CF])$

注意红色的部分,有了这个就表示本组不要捕获,这样,$2中存储的就是([CF])这一组,没有$3了。

二、字符转义

  • \bTAB字符(ASCII码9)
  • \n换行符(ASCII码10)
  • \r回车符(ASCII码13)
  • \s所有能代表“空白”的字符(包括空格、制表、换行等)
  • \S所有不是\s的字符
  • \w大小写字母、数字和下划线,与[a-zA-Z0-9_]等价
  • \W所有不是\w的字符,与[^a-zA-Z0-9_]等价
  • \d数字,与[0-9]等价
  • \D所有非数字字符,与[^0-9]等价

三、文本替换

先前知道了m的作用(匹配),把m换成s就成了“替换”,另外,好友告诉我有了m,就可以用任何一对符号来括住正则表达式,不必老是用/,说不定s也一样。

$name =~ s/\bSaddam\b/Bush/;

这句表示:把$name里面存储的内容,凡是匹配到单词边界的Saddam,通通替换为Bush。

四、Perl的一些语法

while ($var = <>) {}

这个“$var=<>”看起来有点古怪,其实就是“var = getline()”,也就是说,从输入流中取下一行的内容,并赋值变量中,如果输入流已结束,则变量值未定义,同时整个赋值表达式返回布尔假。

关键字last,与C里面的continue类似。

函数defined($var)测试一个变量里是否含有值,是则返回true,否则返回false。

2006年12月27日

Mastering Regular Expressiongs圆括号

圆括号有两种用法

  • 将“或”操作(“|“符号)的两个值括起来,比如(ABC|abc)
  • 将多个字符括起来做为一个整体,使之可以用?、+、* 或{m,n}来限定该整体的匹配次数

反向引用

当被圆括号括住的整体被匹配时,该匹配能够被正则表达式工具记住,并由\1、\2、\3……来引用第一个、第二个、第三个……匹配。例如,本书开篇所讲的那个找出重复单词的例子,可以由如下正则表达式来匹配:

\b([A-Za-z]+)\s+\1\b

其中\b匹配单词边界,\s匹配空格、制表符、换行符等“空白分界”,\1是反向引用,引用的是圆括号括起来的整体匹配。(要点,要使用反向引用,必须要用圆括号将匹配括起来,否则正则表达式无法记住那个匹配)


这本书的第2章,开始简单地介绍了一下Perl,首先是把开篇那个“查找重复单词”问题的解决方案列了出来,一段简短的Perl代码:

00001: $/ = ".\n";00002: while (<>) {00003:     next if !s/\b([a-z]+)((?:\s|<[^>]+>)+)(\1\b)/\e[7m$1\e[m$2\e[7m$3\e[m/ig;00004:     s/^(?:[^\e]*\n)+//mg;00005:     s/^/$ARGV: /mg;00006:     print;00007: }

Perl的一些基础语法是:

  • 变量由$开头,如$celsius
  • 变量的类型可以是数值型或字符型
  • 注释由#开头(可以是单行注释,也可以是行尾注释)
  • 字串常量用双引号括起来,与其它语言(如C)不同的是,用双引号内出现的变量名(由$开头),会被变量的值替换
  • 用print输出
  • Perl命令行的可选参数-w,让Perl使用更高级别的语法检查,并打印警告信息(比如变量未被始化就使用、声明了变量却未使用等)
  • if ($foo =~ m/^\d+$/) 这样的语法是在测试“$foo这个变量的值匹配^\d+$这个正则表达式”的布尔结果。=~这个操作符既不是等于(==),也不是赋值(=),而是“是否匹配”
  • 正则表达式用两个斜杠/字符括起来,前面的m表示匹配操作(可选),如果把m换成s,则表示“替换”

本书第2章简单地介绍了一下Perl,完全任自己的猜想臆断,总结了上面几条,下面是好友Buchi Automata的指正:

严格说,是scalar variable(标量变量?)由$开头。如果是矢量变量,则由@开头。比如@arr = [1, 2, 3, 4]。如果是hash,则用%开头。比如%h = {1=>’a', 2=>’b'}。RE前面的m有它的作用。有了m,我们可以用任何配对的符号表示RE。比如/pattern/ 和 m{pattern} 和m&pattern&都一个意思。

DONEWS与CSDN的BLOG都用的是同一个程序,有评论无法显示的BUG,在首页上能看到评论,但在文章后面看不到(好象过几天就能显示了,很诡异),所以网友指正的评论我干脆贴在原文的后面了

2006年12月20日

一个完整的域名,由根域、顶级域、二级、三级……域名构成,每级域名之间用点分开,每级域名由字母、数字和减号构成(第一个字母不能是减号),不区分大小写,长度不超过63。

很显然,单独的名字可以由正则表达式[a-zA-Z0-9][-a-zA-Z0-9]{0,62}来匹配,而完整的域名至少包括两个名字(比如google.com,由google和com构成),最后可以有一个表示根域的点(在规范中,最后有一个点的才是完整域名,但一般认为包括两个以上名字的域名也是完整域名,哪怕它后面没有点)。

匹配完整域名的正则表达式:

[a-zA-Z0-9][-a-zA-Z0-9]{0,62}(\.[a-zA-Z0-9][-a-zA-Z0-9]{0,62})+\.?

2006年12月19日

读了几页《Mastering Regular Expression》,有心想写一个能够匹配IP字串的正则表达式,实际尝试发现远没有自己写几行代码来判断来得容易,呵呵。

一个IP字串,由四段组成,每一段是0~255的数字,段与段之间用小数点隔开,比如61.139.2.69就是一个合法的IP字串。

如果正则表达式写成\d{1,3}(\.\d{1,3}){3}无疑是不负责的,因为它可以匹配300.400.555.666这样的非法IP字串。

要匹配一个0~255之间的数,有几种匹配方式,下面是其中一种:

匹配 正则表达式 说明
0~9 \d 单个数字
10~99 [1-9]\d 两位数
100~199 1\d\d 百位为1的三位数
200~249 2[0-4]\d 三位数,百位是2,十位是0~9
250~255 25[0-5] 三位数,百位是2,十位是5,个位是0~5

写成正则表达式,即:(\d|([1-9]\d)|(1\d\d)|(2[0-4]\d)|(25[0-5])),但是这样的正则表达式在匹配254这样的字串时,会分别匹配2、5、4,得到3个匹配,达不到预期效果,正确做法是将次序颠倒为((25[0-5])|(2[0-4]\d)|(1\d\d)|([1-9]\d)|\d),因为在(xxx|yyy)这种匹配行为中,是从左向右搜索的。

完整的正则表达式是:

((25[0-5])|(2[0-4]\d)|(1\d\d)|([1-9]\d)|\d)(\.((25[0-5])|(2[0-4]\d)|(1\d\d)|([1-9]\d)|\d)){3}

按:

  • 061这样的高位为0的数是不能被匹配的。
  • 太麻烦,不如自己写一小段代码解析来得容易,呵呵
2006年12月13日

Mastering Regular ExpressiongsMastering Regular Expressions

Jerffrey E.F.Friedl著的这本书,闻名已久。九月份从当当网邮购了一本,却一直没有时间坚持读,主要原因当然还是英文差,没有养成阅读英文的习惯和能力。

后悔呀,当初为什么不多花点时间在英语上面。

开篇说的那个可怕的、查找重复单词的需求非常生动,如果是我遇到这样的需求,肯定同样会很苦恼。

  • 检查N个文件,找到重复的单词(比如“this this”),然后报出它们在哪个文件的哪一行,还要用标准ANSI的转义序列来高度显示它们;
  • 不仅如此,还要正确处理这种情况:某行的最后一个单词,与紧跟着的下一(非空)行的第一个单词相同,也就是说要能够跨行工作。
  • 在查找过程中,还要忽略大小写的区别,并且能把单词之间的任意数量空格都等同于单个空格对待,最重要的是,两个重复单词中的某一个或两个被HTML标记包围着,那还是算重复单词!比如“…it is <B>very</B> very important…”

这样的需求听上去很讨厌,但有了正则表达式,一切就变得容易了。

下表是基本的元字符:

元字符
名称
匹配行为
备注
^ 脱字符 匹配行的起始位置  
$ 美圆符 匹配行的结束位置  
\< 反斜杠及小于符 匹配单词的起始边界 不是所有版本的的egrep都支持这个特性
\> 反斜杠及大于符 匹配单词的结束边界
. 匹配任意单个字符
[...] 字符集 匹配所有方括号中列出的字符
[^...] 字符非集 匹配所有不在方括号中列出的字符  
| 或符号 匹配或符号分开的的表达式  
(…) 圆括号 用于指定“或”符号的范围  

注:

  • 如果一个元字符出现在字符集中(被方括号括起来的字符列表),则它不再是元字符,比方,点字符在方括号以外时,它是一个元字符,代表任意字符,如果它出现在方括号里,则代表点字符本身。
  • 在字符集和字符非集中中,如果减号字符出现在第一个字符位置,则它代表减号本身,否则它表示一个范围,比如[-a-z0-9],第一个减号代表减号本身,第二个减号表示范围,与字符a和z一起表示从a至z的26个英文小写字母,第三个减号与第二个减号的意义一样。
  • 字符非集的概念需要仔细,比如,[^X]意味着“只要不是字符X就匹配”,而是“匹配一个不是X的任意字符”,前者的意义可以匹配一个空行,但[^X]并不匹配空行。
  • 某些版本的egrep支持-i参数,以执行忽略大小写的匹配操作。