Extended Examples
下面的几个例子讲解了一些关于正则表达式的重要诀窍。讨论会稍微多一些,关于解决办法和错误思路的着墨也会更多一些,最终会给出正确答案。
保持数据的协调性
Keeping in Sync with Your Data
我们来看一个长一点的例子,它有点极端,但很清楚地说明了保持协调的重要性(同时提供了一些保持协调的方法)。
假设,需要处理的数据是一系列连续的5位数美国邮政编码(ZIP Codes),而需要提取的是以44开头的那些编码。下面是一点抽样,我们需要提取的数值用粗体表示:
03824531449411615213441829505344272752010217443235
最容易想到的「ddddd」,它能匹配所有的邮政编码。在 Perl 中可以用@zips=m/ddddd/g;来生成以邮政编码为元素的list(为了让这些例子看起来更整洁,我们假设需要处理的文本在Perl的默认目标变量$_中,见☞79)。如果使用其他语言,也只需要循环调用正则表达式的 find 方法。我们关注的是正则表达式本身,而不是语言的实现机制,所以下面继续使用Perl。
回到「ddddd」,下面提到的这一点很快就会体现出其价值;在整个解析过程中,这个正则表达式任何时候都能够匹配——绝对没有传动装置的驱动和重试(我假设所有的数据都是规范的,此假设与具体情况密切相关)。
很明显,把「ddddd」改为「44ddd」来查找以 44 开头的邮政编码不是个好办法——匹配失败之后,传动装置会驱动前进一个字符,对「44…」的匹配不再是从每个邮政编码的第一位开始。「44ddd」会错误地匹配‘…5314494116…’。
当然,我们可以在正则表达式的开头添加「A」,但是这样只能对付一行文本中的第一个邮政编码。我们需要手动保持正则引擎的协调,才能忽略不需要的邮政编码。这里的关键是,要跳过完整的邮政编码,而不是使用传动装置的驱动过程(bump-along)来进行单个字符的移动。
根据期望保持匹配的协调性
下面列举了几种办法用来跳过不需要的邮政编码。把它们添加到正则表达式「44ddd」之前,可以获得期望的结果。非捕获型括号用来匹配不期望的邮政编码,这样能够快速地略过它们,找到匹配的邮政编码,在第一个$1的捕获括号中:
「(?:[^4]dddd|d[^4]ddd)*…」
这种硬办法(brute-force method)主动略过非44开头的邮政编码(当然,用「[1235-9]」替代「[^4]」可能更合适,但我之前说过,假设处理的是规范的数据)。注意,我们不能使用「(?:[^4][^4]ddd)*」,因为它不会匹配(也就无法略过)43210 这样不期望的邮政编码。
「(?:(?!44)ddddd)*…」
这个办法跳过非44开头的邮政编码。其中的想法与之前并无差别,但用正则表达式写出来就显得大不一样。比较这两段描述和相关的正则表达式就会发现,在这里,期望的邮政编码(以44开头)导致逆序环视(?!44)失败,于是略过停止。
「(?:ddddd)*?…」
这个办法使用忽略优先量词,只有在需要的时候才略过某些文本。我们把它放在真正需要匹配的正则表达式前面,所以如果那个表达式失败,它就会匹配一个邮政编码。忽略优先「(…)*?」导致这一切的发生。因为存在忽略优先量词,「(?:ddddd)」甚至都不会尝试匹配,在后面的表达式失败之前。星号确保了,它会重复失败,直到最终找到匹配文本,这样就能只跳过我们希望跳过的文本。
把这个表达式和「(44ddd)」合起来,就得到:
它能够提取以44开头的邮编,而主动跳过其他的邮编(在“@array=m/…/g”的情况下,Perl会用每次尝试中找到的匹配文本来填充这个数组,☞311)。这个表达式能够重复应用于字符串,因为我们知道每次匹配的“起始匹配位置”都是某个邮政编码的开头位置,也就保证下一次匹配是从一个邮政编码的开始,这正是正则表达式期望的。
不匹配时也应当保证协调性
我们是否能保证,每次正则表达式都在邮政编码字符串的开头位置应用?显然不是!我们手动跳过了不符合要求的邮政编码,可一旦不需要继续匹配,本轮匹配失败之后自然就是驱动过程和重试,这样就会从邮政编码字符串之中的某个位置开始——我们的方法不能处理这种情况。
再来看数据样本:
匹配的代码以粗体标注(第三组不符合要求),主动跳过的代码以下画线标注,通过驱动过程-重试略过的字符也标记出来。在44272匹配之后,目标文本中再也找不到匹配,所以本轮尝试宣告失败。但总的尝试并没有宣告失败。传动机构会进行驱动,从字符串的下一个字符开始应用正则表达式,这样就破坏了协调性。在第四次驱动之后,正则表达式略过10217,错误地匹配44323。
如果在字符串的开头应用,这三个表达式都没有问题,但是传动装置的驱动过程会破坏协调性。如果我们能取消驱动过程,或者保证驱动过程不会添麻烦,问题就解决了。
办法之一是禁止驱动过程,即在前两种办法中的「(44ddd)」之后添加「?」,将其改为匹配优先的可选项。这样,刻意安排的「(?:(?!44)ddddd)*…」或「(?:[^4]dddd|d[^4]ddd)*…」就只会在两种情况下停止:发生符合要求的匹配,或者邮政编码字符串结束(这也是此方法不适用于第三个表达式的原因)。这样,如果存在符合要求的邮政编码,「(44ddd)?」就能匹配,而不会强迫回溯。
这个办法仍然不够完善。原因之一是,即便目标字符串中没有符合要求的邮政编码,也会匹配成功,接下来的处理程序会变得更复杂。不过,其优点在于速度很快,因为不需要回溯,也不需要传动装置进行任何驱动过程。
使用G保证协调
更通用的办法是在这三个表达式末尾添加「G」(☞130)。因为每个表达式的每次匹配都以符合要求的邮政编码结尾,下次匹配开始时就不会进行驱动。而如果有驱动过程,开头的「G」会立刻导致匹配失败,因为在大多数流派中,只有在未发生驱动过程的情况下,它才能成功匹配(但在Ruby和其他规定「G」表示“本次匹配起始位置”的流派中不成立☞131)
所以第二个表达式就变成了:
匹配之后不需要进行任何特殊检查。
本例的意义
我首先承认,这个例子有点极端,不过,它包含了许多保证正则表达式与数据协调性的知识。如果现实生活中需要处理这样的问题,我可能不会完全用正则表达式来解决。我会直接用「ddddd」来提出每个邮政编码,然后检查它是否以‘44’开头。在Perl中是这样:
对「G」有兴趣的读者请参考132页的补充内容,尽管本书写作时只能举Perl的例子。
解析CSV文件
Parsing CSV Files
解析CSV(逗号分隔值)文件有点麻烦,因为每个程序都有自己的CSV文件格式。首先来看如何解析Microsoft Excel生成的CSV文件,然后再看其他格式(注3)。幸运的是,Microsoft的格式是最简单的。以逗号分隔的值要么是“纯粹的”(仅仅包含在括号之前),要么是在双引号之间(这时数据中的双引号以一对双引号表示)。
下面是个例子:
Ten Thousand,10000,2710,,"10,000","It/'s ""10 Grand"",baby",10K这一行包含七个字段(fields):
为了从此行解析出各个字段,我们的正则表达式需要能够处理两种格式。非引号格式包含引号和逗号之外的任何字符,可以用「[^",]+」匹配。
双引号字段可以包含逗号、空格,以及双引号之外的任何字符。还可以包含连在一起的两个双引号。所以,双引号字段可以由「"…"」之间任意数量的「[^"]|""」匹配,也就是「"(?:[^"]|"")*"」(为效率考虑,我们可以使用固化分组「(?>…)」来替代「(?:…)」,不过这个话题留到下一章☞259)。
综合起来,「[^",]+|"(?:[^"]|"")*"」能够匹配一个字段。这可能有点难看懂,下面我们给出宽松排列(☞111)格式:
现在这个表达式可以实际应用到包含CSV文本行的字符串上了,但如果我们希望真正利用匹配结果,就应该知道具体是哪个多选分支匹配了。如果是双引号字符串,就需要去掉首尾两端的双引号,把其中紧挨着的两个双引号替换为单个双引号。
我能想到的办法有两个。其一是检查匹配结果的第一个字符是否双引号,如果是,则去掉第一个和最后一个字符(双引号),然后把中间的‘""’替换为‘"’。这办法够简单,但如果使用捕获型括号会更简单。如果我们给捕获字段的每个子表达式添加捕获型括号,可以在匹配之后检查各个分组的值:
如果是第一个分组捕获,则不需要进行任何处理,如果是第二个分组,则只需要把‘""’替换为‘"’即可。
下面给出Perl的程序,稍后(找出某些bug之后)给出Java和VB.NET(在第10章给出PHP 的程序☞480)。下面是Perl 程序,假设数据位于$line中,而且已经去掉了结尾的换行符(换行符不属于最后的字段!):
将其应用于测试数据,结果为:
[Ten·Thousand][10000][·2710·][10,000][It/'s·"10·Grand",·baby][10K]
看来没问题,但不幸的是它不会输出为空的第四个字段。如果“处理$field”是将字段的值存入数组,完成后访问数组的第五个元素得到第五个字段(“10,000”)。这显然不对,因为数组的元素与空字段不对应。
想到的第一个办法是把「[^",]+」改为「[^",]*」,这看来是显而易见的,但它正确吗?
测试一下,下面是结果:
[Ten·Thousand][10000][·2710·][10,000][It/'s·"10·Grand",…
哇,现在出来了一堆空字段!仔细检查检查,就不会这么吃惊。「(…)*」的匹配可以不占用任何字符。如果真的遇到空字段,确实能匹配,那么考虑第一个字段匹配之后的情况呢,此时正则表达式从开始应用。如果表达式中没有元素可以匹配逗号(就本例来说),就会发生长度为0的成功匹配。实际上,这样的匹配可能有无穷多次,因为正则引擎可能在同一位置重复这样的匹配,现代的正则引擎会强迫进行驱动过程,所以同一位置不会发生两次长度为 0 的匹配(☞131)。所以每个有效匹配之间还有一个空匹配,在每个引号字段之前会多出一个空匹配(而且数组末尾还会有一个空匹配,只是此处没有列出来)。
分解驱动过程
要解决问题,我们就不能依赖传动机构的驱动过程来越过逗号。所以,我们需要手工来控制。能想到的办法有两个:
1.手工匹配逗号。如果采取此办法,需要把逗号作为普通字段匹配的一部分,在字符串中“迈步(pace ourselves)”。
2.确保每次匹配都从字段能够开始的位置开始。字段可以从行首,或者是逗号开始。
可能更好的办法是把两者结合起来。从第一种办法(匹配逗号本身)出发,只需要保证逗号出现在第一个字段之外的所有字段开头。或者,保证逗号出现在最后一个字段之外的所有字段的末尾。可以在表达式前面添加「^|,」,或者后面添加「$|,」,用括号控制范围。
在前面添加,就得到:
看起来它应当没错,但实际的结果却是:
[Ten·Thousand][10000][·2710·][000][·baby][10K]
而我们期望的是:
[Ten·Thousand][10000][·2710·][10,000][It/'s·"10•Grand",·baby][10K]
问题出在哪里呢?似乎是双引号字段没有正确处理,所以问题出在它身上,对吗?不对,问题在前面。或许 176 页的告诫有所帮助:如果多个多选分支能够在同一位置匹配,必须小心地排列顺序。第一个多选分支「[^",]*」不需要匹配任何字符就能成功,除非之后的元素强迫,否则第二个多选分支不会获得尝试的机会。而这两个多选分支之后没有任何元素,所以第二个多选分支永远不会得到尝试的机会,这就是问题所在!
哇,现在我们已经找到了问题所在。OK,交换一下多选分支的顺序:
对了!至少对测试数据来说是对了。如果数据变了,还是这样吗?本节的标题是“分解驱动过程”,而最保险的办法就是以完整测试作为基础的思考,故可以用「G」来确保每次匹配从上一次匹配结束的位置开始。考虑到构建和应用正则表达式的过程,这样做应该绝对没问题。如果在表达式开始添加「G」,就会禁止引擎的驱动过程。我们希望这样修改不会出问题,但是结果并非如此。之前输出
[Ten·Thousand][10000][·2710·][000][·baby][10K]
的正则表达式添加G之后,得到
[Ten·Thousand][10000][·2710·]
如果起初没看明白,这样看会更明显。
另一个办法
本节的开头提到有两种办法正确匹配各个字段。之二是确保匹配只能在容许出现字段的地方开始。从表面上看,这类似于添加「^|,」,只是使用了逆序环视「(?<=^|,)」。
不幸的是,按照第3章(☞133)的解释,即使可以使用逆序环视,也不见得能够使用变长的逆序环视,所以此方法可能无法使用。如果问题在于长度可变,我们可以把「(?<=^|,)」替换为「(?:^|(?<=,))」,但是相比第一种办法,它太麻烦了。而且,它仍然依赖传动装置的驱动过程来越过逗号,如果别的地方出了什么差错,它会容许在‘…"10,☞000"…’处的匹配。总的来说就是,不如第一种办法保险。
不过我们可以略施小计——要求匹配在逗号之前(或者是一行结束之前)结束。在表达式结尾添加「(?=$|,)」可以确保它不会进行错误的匹配。实际生活中,我会这样做吗?直率地说我觉得第一种方法很合用,所以遇到这种情况我可能不会采取第二种办法,不过如果需要,这技巧却是很有用的。
进一步提高效率
尽管在下一章之前都不会谈论效率,但对于支持固化分组(☞139)的系统,我还是愿意在这里给出提高效率的修改:把匹配双引号字段的子表达式从「(?:[^"]|"")*」改为「(?>[^"]+|"")*」。下一页用VB.NET的例子做了说明。
如果像Sun的Java regex package那样支持占有优先量词(☞142),也可以使用占有优先量词。Java CSV程序的补充内容说明了这一点。
这些修改背后的道理会在下一章讲解,最终我们会在271页给出效率最高的办法。
其他CSV格式
Micorsoft的CSV格式很流行,因为它是Microsoft的CSV格式,但其他程序可能有不同格式,我见过的情况还有:
●使用任意字符,例如/';/'或者制表符作为分隔。(不过这样名字还能叫“逗号分隔值”吗?)
●容许分隔符之后出现空格,但不把它们作为值的一部分。
●用反斜线转义引号(例如用‘"’而不是‘""’类表示值内部的引号)。通常这意味着反斜线可以在任何字符前出现(并忽略)。
这些变化都很容易处理。第一种情况只需要把逗号替换为对应的分隔符,第二种只需要在第一个分隔符之后添加「s*」,例如以「(?:^|,s*)」开头。
第三种情况,我们可以用之前的办法(☞198),把「[^"]+|""」替换为「[^//"]+|//.」。当然,我们必须把后面的s/""/"/g改为更通用的s///(.)/$1/g,或者对应语言中的代码。