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

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

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

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

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

第一件事情相对容易一些，我们知道一个正则表达式可以对应到一个有限状态机 (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

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