Categories

(\d+|\d*\.\d+)

GreaseMonkey我在之前的 blog 上专门有一个分类叫做 Bug Archive ,用于记录自己平时碰到的应该记录下来的 bug ,现在我觉得这个分类大概还得继续下去吧。因为记录的目的是希望自己以后不要再犯同样的错误,所以通常实际记录下来的其实也都是非常低级的 bug 了。毕竟复杂的 bug 一方面本身也比较难重现,再者遇到了也不是很羞愧的事情。

但是低级的 bug 就不一样了,低级的 bug 并不是指它本身很低级,而是对于你来说不应该会犯的错误——比如,在你最熟悉的地方出现问题。就像今天要说的这个 bug 一样。我想,如果你熟悉正则表达式,大概在打开本文之前就看出来标题里的正则表达式有问题了;如果一开始没有看出来,现在我告诉你它有问题,你再去看一眼,应该也知道问题的所在了。当然,如果你对正则表达式不熟悉,那也只能说这个问题对你来说不是低级的 bug 。

这个表达式的原意是要匹配一个数字,希望同时匹配整数和浮点数的情况,比如 3 、2.5 、.73 等。当然这样的正则表达式有很多种写法,我偷懒用了这种,结果就出问题了。

不过要理清楚这个问题大概也不是那么“显然”的事情。首先,正则表达式主要有两种用法,一种是 match ,另一种是 search/scan 。前者测试一个字符串是否能严格匹配到一个正则表达式,而后者则是在一个(通常比较大的)字符串中寻找一个字串,使其能匹配到给定的正则表达式。

dfa第一件事情相对容易一些,我们知道一个正则表达式可以对应到一个有限状态机 (DFA) ,例如,a.*b 这个正则表达式就可以等价于右图所示的 DFA ,从正则表达式到非确定性有限状态机 (NFA) 的转化,以及从 NFA 到 DFA 的转化都是由标准算法的,而看一个字符串是否能和一个 DFA 匹配,也只需要以字符串为输入跑一遍 DFA 就可以了,一切都是顺理成章的事情。

然而在做 search 的时候就有不那么明确的地方了。例如,我给定字符串 fooabbbc ,照理说里面有不少能匹配的子串,比如 fooabbbc 、fooabbbc 以及 fooabbbc 。出现 ambiguity 了,于是大家约定,除非特别指明,否则都采取 greedy 的做法,亦即匹配最长的子串:fooabbbc 。这样,你不能在看到第一个 b 的时候就停下来,而是希望匹配尽量多的任意字符 (.) 之后最后再出现一个字母 b 。然而你并不知道最后会不会有 b 出现,因此你需要记录下之前成功匹配的那些状态,这样当你最后走入死胡同(例如,发现一直到字符串结尾都再没有 b 出现)的时候可以进行回溯——于是 search 操作相对于 match 操作来说,时间上和空间上都更加复杂了。

稍微扯得有些远了。这里我是想提一下 greedy 的问题,因为我在标题里给的那个正则表达式,我之所以会这么写,大概也是收到 greedy 这个概念的影响吧。这里竖线分隔表示两种情况都接受。这在做 matching 的时候没有任何问题,因为结果只有一个:要么整个字符串能匹配,要么不能匹配;而在做 searching 的时候又有可能会碰到 ambiguity 的问题:如果两种情况都能匹配,应该选择哪一种呢?咋一看似乎应该按照 greedy 原则选择匹配最多的那一种吧,但是其实这里和之前说的 greedy 又是不同的情况。具体原因我也不清楚,或许是为了让实现稍微简单一点,或许是为了让正则表达式的行为更加确定一点,又或许只是历史原因——大家一开始就是那么做的罢了,总之这里实际上有一个明确的优先级存在:竖线前面的选择相对于后面的选择来说优先级高一些,如果两种情况都能匹配的话,会选择前者。所以我在标题中的那个正则表达式永远也匹配不到浮点数的小数部分。

或许像 Treetop 中那样用一个斜杠 / 而不是竖直的 | 来分隔更能够体现出这里“有优先级”这个事实,让人们不要犯错误。 :p

其实这样的错误,在出现问题之后几乎能立马看出问题出在哪里以及为什么出问题了,但是却总是不能在第一次写出来的程序中就直接避免掉这些问题。我也一直都在想有没有什么解决办法,但是到目前为止也只有记录下这些问题希望以后能避免这种被动的方法。 :-/

9 comments to (\d+|\d*\.\d+)

  • |在正则表达式里是分组选择,对于你所说的优先级,应该是与实现有关系。在传统型NFA中,是实现来选择哪一个优先;在Posix NFA中,两个分支都会遍历,选择匹配长度大的分支。
    不考虑 .3这样的情况,写作 \d+(\.\d+)?应该可以

  • @kevinmiter
    确实是实现的差别,因为这并不是正则表达式这个数学概念本身的问题,只是在做 searching 的时候才会有的。不过我确实不知道 Posix 的标准里还规定了这样的东西。不过正则表达式也就是这点不好,各个实现之间的细微差别实在太多了,稍不注意就会出错。你说的那个 Posix 标准,有哪个程序里面有实际实现了吗?

  • @pluskid
    好像没有实际实现,我接触的正则表达式多数和perl实现兼容。

  • 运算符优先级一直可以导致错误.
    我在写C/C++程序的时候,拿不准又不愿意加括号,就man operator,很多次了,但下次用到还是不太确定 :-S
    正则若有方便的文档就好一些.
    说到文档,真是一个痛苦的话题,程序员似乎觉得这个没什么”技术含量”就不太在意.有的开源项目我感觉就是”代码即文档” -.-b

  • @quark
    开源的东西很多是大家业余时间弄出来的,本来时间就不多,所以主要都会花在相对紧急一些的地方,所以文档时常会残缺不全或者太过陈旧。 :/

    正则表达式的文档的话,一般就看具体实现的文档就好了,例如 Emacs 、Python 之类的文档其实都还不错的。我比较喜欢看 example 式的文档,而不是罗列条条款款式的文档。

  • Darren

    请问在您的blog的图是用什么画的?

  • @Darren
    你说那个 DFA 吗?那是 reAnimator 画出来的。

  • […] NFA 到 DFA 的转换工作 。在 pluskid 的这篇日志里面看到了 reAnimator […]

  • conan

    如果你把两个分支反过来写应该就可以了