译文：正则表达式的真正实力

，其他任何文本都不匹配。因此，表达式 (.*)\1 表示「一段文本后跟其自身的副本」。这个简单的正则表达式匹配的文本称为「副本语言」（copy language），是另一种典型的上下文相关语言。

类似地，可以使用反向引用匹配上面举例过的其他文法：

# {a^n b^n, n>0} (上下文无关) 可表示为
/^ (?: a (?= a* (\1?+ b) ) )+ \1 $/x
# {a^n b^n c^n, n>0} (上下文相关) 可表示为
/^ (?: a (?= a* (\1?+ b) b* (\2?+ c) ) )+ \1 \2 $/x

这些正则表达式的原理超出了本文的范围，但可以看 StackOverflow 上一篇精彩的解释。

可见，仅仅添加反向引用（即使不支持 subpattern 递归）就已经大大充实了正则表达式的功能。实际上，加上这个功能意义重大，因为它使正则表达式的匹配成为一个「NP 完全」（NP-Complete）问题。

NP 完全是什么意思？这是从计算复杂性角度对决策问题的一种分类，许多「难题」都属于这一类。例如，旅行商问题（traveling salesman problem, TSP）、布尔可满足性问题（boolean satisfiability problem, SAT）和背包问题（knapsack problem, BKP）都属于 NP 完全问题。

（译注：上述三个问题的粗略描述如下——TSP 问，一个旅行商要访问 n 个城市，每个城市只访问一次，最后回到起点，如何找出总距离最短的路线？SAT 问，给定一个布尔表达式，是否存在一组变量的真值赋值，使得整个表达式为真？BKP 问，给定一组物品，每个物品有特定的重…

类似地，可以使用反向引用匹配上面举例过的其他文法：

# {a^n b^n, n>0} (上下文无关) 可表示为
/^ (?: a (?= a* (\1?+ b) ) )+ \1 $/x
# {a^n b^n c^n, n>0} (上下文相关) 可表示为
/^ (?: a (?= a* (\1?+ b) b* (\2?+ c) ) )+ \1 \2 $/x

这些正则表达式的原理超出了本文的范围，但可以看 StackOverflow 上一篇精彩的解释。

（译注：上述三个问题的粗略描述如下——TSP 问，一个旅行商要访问 n 个城市，每个城市只访问一次，最后回到起点，如何找出总距离最短的路线？SAT 问，给定一个布尔表达式，是否存在一组变量的真值赋值，使得整个表达式为真？BKP 问，给定一组物品，每个物品有特定的重量和价值，如何在背包承重限制下，找出总价值最大的物品组合？）

如果要构成一个 NP 完全问题，主要条件之一就是其他 NP 问题都可以归约到这个问题。换言之，所有 NP 完全问题都是可互换的。找到了其中一个的快速解决方案，就找到了所有问题的快速解决方案。

因此，如果有人找到了 NP 完全问题的快速解决方案，那么几乎所有人类的计算难题都将一举解决。这将意味着我们所知文明的终结。

为了证明具有反向引用的正则表达式确实是 NP 完全的，只要找一个已知的 NP 完全问题，并证明它可以使用正则表达式来解决。这里用 3-CNF SAT 问题来举例：

3-CNF SAT 代表「合取范式 3 布尔可满足问题」（3-conjunctive normal form boolean satisfiability problem），也很容易理解。取以下形式的布尔表达式：

(!$a ||  $b ||  $d)
&& ( $a || !$c ||  $d)
&& ( $a || !$b || !$d)
&& ( $b || !$c || !$d)
&& (!$a ||  $c || !$d)
&& ( $a ||  $b ||  $c)
&& (!$a || !$b || !$c)

也就是说，这个布尔表达式由多个 AND 分隔的子句组成，每个子句都包含三个变量（或其相反值），由 OR 分隔。而 3-CNF SAT 问题就是在问这个公式是否有解（使其为真）。

该布尔表达式可以转换为以下正则表达式：

$regex = '/^
(x?)(x?)(x?)(x?) .* ;
(?: x\1 | \2  | \4  ),
(?: \1  | x\3 | \4  ),
(?: \1  | x\2 | x\4 ),
(?: \2  | x\3 | x\4 ),
(?: x\1 | \3  | x\4 ),
(?: \1  | \2  | \3  ),
(?: x\1 | x\2 | x\3 ),
$/x';
$string = 'xxxx;x,x,x,x,x,x,x,';
var_dump(preg_match($regex, $string, $matches));
var_dump($matches);

运行上述代码，将获得以下 $matches 结果：

array(5) {
[0]=> string(19) "xxxx;x,x,x,x,x,x,x,"
[1]=> string(1) "x"
[2]=> string(1) "x"
[3]=> string(0) ""
[4]=> string(0) ""
}

这意味着如果 $a = true、$b = true、$c = false 且 $d = false，则上述表达式为真。

上述正则表达式用了一个简单的技巧：每个三元子句（译注：即布尔表达式中的每一行）都对应于待匹配字符串 $string 中的一个 x,。例如，对于正则表达式中 (?: \1 | x\3 | \4 ), 这个部分，只有当 \1 为 x（即 $a 为真）、\3 为空字符串（即 $c 为假）或 \4 为 x（即 $d 为真）时，才能匹配。

（译注：这里的思路是构造一个与布尔表达式等价的正则匹配问题。其中，$string 的构造让 \1 到 \4 每个捕获组依次对应于 3-CNF 表达式中的布尔变量 $a 到 $d；捕获组为 x 代表对应的变量为真，捕获组为空代表对应的变量为假；匹配成功代表对应的布尔表达式为真。上述代码通过枚举找出完全匹配 $string 的捕获组取值，从而就找出了令 3-CNF 表达式为真的变量值。）

其余的工作留给匹配引擎。它将尝试不同的方式来匹配字符串，直到找到解，或被迫放弃。

总结

由于文章很长，这里总结一下要点：

程序员所说的「正则表达式」，与形式语言理论语境下的原始「正则」概念，几乎没有共同之处。
正则表达式（至少是 PCRE）可以匹配所有上下文无关语言，因此还可以匹配格式正确的 HTML 和其他几乎所有编程语言。
正则表达式至少可以匹配某些上下文相关语言。
正则表达式的匹配是一个 NP 完全问题。因此，可以使用正则表达式解决其他任何 NP 问题。但不要忘了：「你行」不代表「你上」。有些时候，使用正则表达式处理 HTML 真的是馊主意；而又有些时候，这可能是最好的做法。

正确做法是，判断手头问题用哪个方法解决最简单，就用哪个方案。如果选择正则表达式，不要忘记 x 修饰符，这样就可以把正则表达式整理成易读的格式。对于复杂的正则表达式，也不要忘记使用 DEFINE 断言和给 subpattern 命名，以便保持代码的整洁和可读性。

就写这么多吧。

总结

Similar Posts