译文 | 正则表达式的真正实力 - 少数派

[guevara]

译文 | 正则表达式的真正实力 - 少数派



https://ift.tt/tKjfhdT



PlatyHsu

按：本文作者为 nikic (Nikita Popov)，是 Red Hat 高级软件工程师，参与 LLVM、Clang 和 Rust 等项目。原文题为 “The true power of regular expressions”，于 2012 年发表在其博客上。我第一次看到这篇文章是好几年前，虽然有点晦涩，但硬着头皮看下来，还是对理解正则表达式的本质有很大启发。最近回顾旧书签，又重新想起、复习了一遍，并得作者惠允翻译后发布。

根据个人阅读体验和理解，对于原文中一些较生僻的术语和较跳跃的推理，通过译注加以补充，仅供参考。请注意本文并非正则表达式教程，其中讨论假定读者对正则表达式语法（PCRE 风格）有基础了解，但除此之外并无编程基础要求。如对相关话题感兴趣，可以关键词「形式语言」及「自动机」搜索相关百科词条和教科书。由于我在这方面也完全外行，提前就可能存在的术语和理解错误致歉。

---

我经常浏览 StackOverflow 打着 PHP 标签的帖子，其中总能看到有人问如何使用正则表达式解析 HTML 的特定部分。对此，常见回答是：

不能用正则表达式解析 HTML，因为 HTML 不是正则语言。麻烦用 XML 解析器。

但取决于问题语境，这么说要么颇为误导，要么完全错误。本文将尝试说明现代正则表达式的真正实力。

「正则」到底是什么意思？

根据形式语言理论，如果某种语言所有文法（grammar）的产生式规则（production rule）都具有以下形式之一，则称其为「正则」（regular）语言：

B -> a
B -> aC
B -> ε

（译注：形式语言中所谓的「字母表」「语言」「文法」等概念都是高度抽象化的，与日常语境有较大不同。其中，「字母表」可以是任意元素的有限集合，「语言」仅仅是从一个字母表取某些有限长字符串构成的集合。而「文法」可以理解为一种语言「生成器」，它给出一套规则，说明如何用字母表生成语言。至于这些字符、语言的含义和作用，在所不问。）

这些包含 -> 的规则可以理解为「左侧可以替换为右侧」。因此，第一个规则是「B 可以替换为 a」，第二个规则是「B 可以替换为 aC」，第三个规则是「B 可以替换为空字符串」（ε 是空字符串的记号）。

那么 B、C 和 a 是什么？按照惯例，大写字母代表「非终结符」（non-terminal），即可以进一步拆分的符号；而小写字母表示「终结符」（terminal），即不能再进一步拆分的符号。

干说这么多可能有点抽象，那来看一个例子：用文法定义自然数。

N -> 0
N -> 1
N -> 2
N -> 3
N -> 4
N -> 5
N -> 6
N -> 7
N -> 8
N -> 9
N -> 0N
N -> 1N
N -> 2N
N -> 3N
N -> 4N
N -> 5N
N -> 6N
N -> 7N
N -> 8N
N -> 9N

这个文法是说：

一个自然数 (N) 是
……0 到 9 之间的一个数字
或者
……0 到 9 之间的一个数字，后接另一个自然数 (N)

在这个例子中，数字 0 到 9 是终结符（因为不能再进一步拆分），而 N 将是唯一的非终结符（因为可以进一步拆分，并且确实拆分了）。

比较这些规则与上述正则文法定义，会发现它们符合定义：前十条规则的形式为 B -> a，后十条规则遵循 B -> aC。因此，定义自然数的文法是正则文法。

你可能还注意到，尽管上述文法的定义对象如此简单，但写出来却相当臃肿。如果能以更简洁的方式表达相同的概念，岂不是更好？

这就是正则表达式的用武之地：上述文法等价于正则表达式 [0-9]+（简洁得多）。任何正则文法都可以做这种转换：每个正则文法都能找到一个对应的正则表达式，使其定义了该文法下全部有效字符串。

正则表达式可以匹配什么？

于是问题来了：正则表达式只能匹配正则文法吗？还是也能匹配其他文法？答案是肯定的，却也是否定的——

在形式文法的意义上，正则表达式（根据定义）只能解析正则文法，而不能解析其他任何文法。

但是，当程序员提到「正则表达式」时，并不是在说形式文法，而是各编程语言实现的正则表达式衍生形态。而这些实现与「正则」的原始概念只有很微弱的联系。

任何现代的正则表达式风格能匹配的范围都远超正则语言。后文将说明究竟能超出多少。

简单起见，下文重点介绍 PCRE 正则表达式实现，原因仅仅是我了解最多（因为通过 PHP 在用）。不过，其他大多正则表达式实现都很相似，因此论述也应该大体适用。

语言层次结构

为了分析正则表达式可以匹配什么、不能匹配什么，首先必须知道还有哪些其他类型的语言。为此，乔姆斯基层次结构（Chomsky hierarchy）是一个很好的起点：

乔姆斯基层次结构：
/-------------------------------------------

|                                           |

|      递归可枚举 (Recursively enumerable)    | 0 型 (Type 0)

|                                           |

|   /-----------------------------------\   |

|   |                                   |   |

|   |   上下文相关 (Context-sensitive)    |   | 1 型 (Type 1)

|   |                                   |   |

|   |   /---------------------------\   |   |

|   |   |                           |   |   |

|   |   |  上下文无关 (Context-free)  |   |   | 2 型 (Type 2)

|   |   |                           |   |   |

|   |   |   /-------------------\   |   |   |

|   |   |   |   正则 (Regular)   |   |   |   | 3 型 (Type 3)

|   |   |   -------------------/   |   |   |

|   |   ---------------------------/   |   |

|   -----------------------------------/   |

-------------------------------------------/

如图所示，乔姆斯基层次结构将形式语言分为四种类型：正则语言（regular language，3 型）的功能最弱，在其之上的是上下文无关语言（context-free language，2 型）、上下文相关语言（context-sensitive language，1 型），而最上层是「全能」的递归可枚举语言（recursively enumerable language，0 型）。

乔姆斯基层次结构是一个包含关系，因此上图中的小框完全包含在大框中。例如，每种正则语言都是上下文无关语言（但反之不然）。

那么来试试上探一层：已知正则表达式可以匹配任何正则语言，但它能否匹配上下文无关语言？

（再次提醒：这里的「正则表达式」显然是编程意义上的，而不是形式语言理论意义上的。）

匹配上下文无关语言

答案是肯定的，可以匹配！

来看一种典型的上下文无关语言，{a^n b^n, n>0}，意思是「若干个字符 a 后跟相同数量的字符 b」。这种语言的正则表达式（PCRE 风格）是：

/^(a(?1)?b)$/x

这条正则表达式很简单：其中 (?1) 是指引用第一个 subpattern（子模式）(a(?1)?b)。因此，实际上可以把 (?1) 替换成这个 subpattern，这就形成了一种递归关系：

/^(a(?1)?b)$/
/^(a(a(?1)?b)?b)$/
/^(a(a(a(?1)?b)?b)?b)$/
/^(a(a(a(a(?1)?b)?b)?b)?b)$/
# 等等

根据上述展开式，这个表达式显然可以匹配任何含有 a 和 b 个数相同的字符串。

因此，正则表达式至少可以匹配某些非正则的上下文无关文法。但是它能匹配所有上下文无关文法吗？为了回答这个问题，首先必须了解上下文无关文法的定义。

在上下文无关文法中，所有产生式规则都具有以下形式：

A -> β

这里，A 仍然是一个非终结符，β 是终结符和非终结符组成的任意字符串。因此，在每个上下文无关文法的产生式规则中，左侧都是一个非终结符，右侧是一个任意符号组成的字符串。

例如，考虑以下文法：

function_declaration -> T_FUNCTION is_ref T_STRING '(' parameter_list ')' '{' inner_statement_list '}'
is_ref -> '&'

is_ref -> ε
parameter_list -> non_empty_parameter_list

parameter_list -> ε
non_empty_parameter_list -> parameter

non_empty_parameter_list -> non_empty_parameter_list ',' parameter
// ... ... ...

这是 PHP 语言定义的一小截（只是几条规则演示）。格式与之前略有不同，但应该容易理解。需要说明的是，这里的各处大写 T_某某 也是终结符。这些符号通常称为 token（标记），用于指代多个抽象概念。例如，T_FUNCTION 表示 function 关键字，T_STRING 标记指代一个 label（标签，如 getUserById 或 别的什么函数名）。

这个例子说明，上下文无关文法已经强大到足以编码相当复杂的语言。这就是为什么几乎所有编程语言都使用上下文无关文法来定义；特别一提，也包括格式正确的 HTML。

好了，回到手头的问题：正则表达式可以匹配所有上下文无关文法吗？重复一遍，答案是肯定的！

这很容易证明，因为正则表达式（至少是 PCRE 和类似风格）提供了一种跟上面很相似的文法构造格式：

/
    (?(DEFINE)
        (?<addr_spec> (?&local_part) @ (?&domain) )
        (?<local_part> (?&dot_atom) | (?&quoted_string) | (?&obs_local_part) )
        (?<domain> (?&dot_atom) | (?&domain_literal) | (?&obs_domain) )
        (?<domain_literal> (?&CFWS)? \[ (?: (?&FWS)? (?&dtext) )* (?&FWS)? \] (?&CFWS)? )
        (?<dtext> [\x21-\x5a] | [\x5e-\x7e] | (?&obs_dtext) )
        (?<quoted_pair> \\ (?: (?&VCHAR) | (?&WSP) ) | (?&obs_qp) )
        (?<dot_atom> (?&CFWS)? (?&dot_atom_text) (?&CFWS)? )
        (?<dot_atom_text> (?&atext) (?: \. (?&atext) )* )
        (?<atext> [a-zA-Z0-9!#$%&'*+/=?^_`{|}~-]+ )
        (?<atom> (?&CFWS)? (?&atext) (?&CFWS)? )
        (?<word> (?&atom) | (?&quoted_string) )
        (?<quoted_string> (?&CFWS)? " (?: (?&FWS)? (?&qcontent) )* (?&FWS)? " (?&CFWS)? )
        (?<qcontent> (?&qtext) | (?&quoted_pair) )
        (?<qtext> \x21 | [\x23-\x5b] | [\x5d-\x7e] | (?&obs_qtext) )
    # 注释和空格符
    (?&lt;FWS&gt; (?: (?&amp;WSP)* \r\n )? (?&amp;WSP)+ | (?&amp;obs_FWS) )
    (?&lt;CFWS&gt; (?: (?&amp;FWS)? (?&amp;comment) )+ (?&amp;FWS)? | (?&amp;FWS) )
    (?&lt;comment&gt; \( (?: (?&amp;FWS)? (?&amp;ccontent) )* (?&amp;FWS)? \) )
    (?&lt;ccontent&gt; (?&amp;ctext) | (?&amp;quoted_pair) | (?&amp;comment) )
    (?&lt;ctext&gt; [\x21-\x27] | [\x2a-\x5b] | [\x5d-\x7e] | (?&amp;obs_ctext) )

    # 已弃用 token
    (?&lt;obs_domain&gt; (?&amp;atom) (?: \. (?&amp;atom) )* )
    (?&lt;obs_local_part&gt; (?&amp;word) (?: \. (?&amp;word) )* )
    (?&lt;obs_dtext&gt; (?&amp;obs_NO_WS_CTL) | (?&amp;quoted_pair) )
    (?&lt;obs_qp&gt; \\ (?: \x00 | (?&amp;obs_NO_WS_CTL) | \n | \r ) )
    (?&lt;obs_FWS&gt; (?&amp;WSP)+ (?: \r\n (?&amp;WSP)+ )* )
    (?&lt;obs_ctext&gt; (?&amp;obs_NO_WS_CTL) )
    (?&lt;obs_qtext&gt; (?&amp;obs_NO_WS_CTL) )
    (?&lt;obs_NO_WS_CTL&gt; [\x01-\x08] | \x0b | \x0c | [\x0e-\x1f] | \x7f )

    # 字符类别定义
    (?&lt;VCHAR&gt; [\x21-\x7E] )
    (?&lt;WSP&gt; [ \t] )
)
^(?&amp;addr_spec)$

/x

上面是一个根据 RFC 5322 匹配电子邮件地址的正则表达式。将 RFC 中的 BNF 规则转换为符合 PCRE 的表示法，就得到了这个表达式。

它的格式很简单：所有规则定义（rule definition）都包含在 DEFINE 断言中。换句话说，这些规则都不直接用来匹配，只用作定义。只有末尾的 ^(?&addr_spec)$ 代表需要匹配的内容。

规则定义并不是真正的「规则」，只是获得命名的 subpattern。在上面例子提到的 (a(?1)?b) 中，(?1) 是指引用第一个 subpattern。显然，subpattern 数量一多，这么编号就不好使了，因此不妨起名。例如，(?<xyz> ...) 就定义了一个名为 xyz 的模式，然后可以用 (?&xyz) 引用它。

另请注意：上面的正则表达式结尾使用了修饰符 x。这要求匹配引擎忽略空格，并允许用 # 做注释。这样就可以把正则表达式整理成易读的格式，方便他人理解。（比长成这样的 RFC 822 邮件地址表达式不知道高到哪里去了……）

通过这种格式，可以简洁地将文法映射为正则表达式：

A -> B C
A -> C D
// 可表示为
(?<A> (?&B) (?&C)
    | (?&C) (?&D)
)

但需注意：正则表达式不支持左递归。例如，上面的 PHP 参数组定义：

non_empty_parameter_list -> parameter
non_empty_parameter_list -> non_empty_parameter_list ',' parameter

是不能从文法直接转换为正则表达式的，即如下写法无效：

(?<non_empty_parameter_list>
    (?&parameter)
  | (?&non_empty_parameter_list) , (?&parameter)
)

原因是，这里 non_empty_parameter_list 出现在它自身规则定义的最左侧。这种写法称为左递归（left-recursion），在文法定义中很常见，因为常用于解析文法的 LALR(1) 解析器处理左递归的效果远好于处理右递归。

但不用担心，这完全不会影响正则表达式的功能：所有左递归文法都可以转换为右递归文法。在上例中，只需交换两部分再转换即可：

non_empty_parameter_list -> parameter
non_empty_parameter_list -> parameter ',' non_empty_parameter_list

（译注：这里表达的意思大致是，如果一组参数可以拆分为一组参数加上一个参数，那么当然也可以拆分为一个参数加上一组参数；反之亦然。所以，左右两个方向的递归展开是等价的。严格证明从略。）

由此可见，正则表达式能匹配任何上下文无关语言（即程序员遇到的几乎所有编程语言）。唯一的问题是：尽管正则表达式可以轻松匹配（match）上下文无关语言，但一般不能解析（parse）。所谓解析，是指将字符串转换为抽象语法树（abstract syntax tree）。正则表达式不可能做到这点，至少 PCRE 做不到。（当然，Perl 可以在正则表达式中嵌入任意代码，那就几乎无所不能了。）

（译注：抽象语法树将编程语言的语法结构绘制为树形图，树上的每个节点都表示源代码中的一种结构，例如条件分支、变量等。「抽象」是指略去了真实语法中的某些细节，例如缩进格式、语法标记等。）

尽管如此，这种利用 DEFINE 的正则表达式定义在我看来很实用。因为一般来说，也不需要完整支持解析，只要能匹配（例如匹配电子邮件地址）或提取小段数据（而不是生成完整的解析树）就够了。通过将文法转写为正则表达式，大多数复杂的字符串处理问题都会简单很多 :)

行文至此，我想重提一句之前一笔带过的话：格式正确的 HTML 是上下文无关语言。因此，与主流观点相反，它可以通过正则表达式匹配。但有两点要注意：首先，大多数野生的 HTML 格式都不正确（很多时候说「不正确」都是抬举了）。其次，「你行」不代表「你上」。这就像你可以用 Brainfuck 语言（译注：一种语法只包含 8 个符号的异类语言）写程序，但你当然有理由不这么做。

我对这个问题的看法是：如果需要宽泛的 HTML 处理能力，就找个顺手的 DOM 库。它会优雅地处理格式错误的 HTML，减轻解析的负担。相反，如果只是处理特定情况，快手写个正则表达式通常是可行的。不得不承认，尽管我经常让人别用正则表达式解析 HTML，但自己却经常这样做。因为在大多数情况下，我处理的是特定、有限的情况，这时用正则表达式更简单。

上下文相关文法

至此，我们已经充分讨论了上下文无关语言，可以在乔姆斯基层次结构中再上一层，讨论上下文相关语言（context-sensitive language）。

在上下文相关语言中，所有产生式规则都具有以下形式：

αAβ -> αγβ

这种杂烩乍看复杂，但实际很简单。它的核心仍然是 A -> γ 这一模式，也就是上下文无关文法的定义方式。新出现的是两侧的 α 和 β，它们构成了「上下文」（所以叫做「上下文相关」文法）。换言之，只在左侧有 α、右侧有 β 时，A 才能替换为 γ。

为了理解更清楚，请尝试解读以下规则：

a b A -> a b c
a B c -> a Q H c
H B -> H C

翻译成人话：

将 `A` 替换为 `c`，但前提是其左侧有 `a b`。
将 `B` 替换为 `Q H`，但前提是其左侧有 `a` 且右侧有 `c`。
将 `B` 替换为 `C`，但前提是其左侧有 `H`。

上下文相关语言在「普通」编程中很少会遇到，主要在自然语言处理中发挥作用（因为自然语言显然不是上下文无关的，单词根据上下文具有不同的含义）。但即使在自然语言处理中，更常用的也是所谓「轻度（mildly）上下文相关语言」，因为这已经足以为语言建模，但解析起来更快。

要理解上下文相关文法的能力，不妨先了解另一类「表达能力」与其完全相同的文法：不可收缩文法（non-contracting grammar）。

在不可收缩文法中，每个产生式规则都具有 α -> β 的形式，其中 α 和 β 都是任意符号组成的字符串，只有一个限制：右侧的符号数不少于左侧的符号数，形式上用公式 |α| <= |β| 表示，其中 |x| 表示字符串长度。

因此，只要不缩短输入，不可收缩文法就允许任何形式的规则。例如，A B C -> H Q 是无效规则，因为左侧有三个符号，而右侧只有两个。因此，这条规则缩短了输入（即产生「收缩」）。反之，H Q -> A B C 是有效规则，因为右侧的符号多于左侧，没有缩短输入。

既然上下文相关文法和不可收缩文法有等价关系，显然可以用上下文相关文法匹配几乎任何东西，只要不收缩就行 :)

至于为什么两种文法具有等价的表达能力，考虑如下变形示例：

// 如下的不可收缩文法
A B -> C D
// 可以依次转换为如下的上下文相关文法
A B -> A X
A X -> Y X
Y X -> Y D
Y D -> C D

（译注：这个例子旨在说明任意给定的不可收缩文法都能转换为等价的上下文相关文法。每一步中都保留了一个非终结符作为上下文，而引入了另一个非终结符，因此符合上下文相关文法的定义。经过这一系列上下文相关变换，起始的 A B 最终会被替换为 C D，与原始的不可收缩变换效果相同。这就说明了非收缩文法与上下文相关文法的等价性：两者描述的语言集合是相同的。）

言归正传，正则表达式能匹配上下文相关语言吗？

这次，恕我无法给出明确答案。正则表达式当然可以匹配某些上下文相关语言，但我不知道能否可以匹配所有上下文相关语言。

例如，有一种上下文相关语言可以用正则表达式轻松匹配：对 {a^n b^n, n>0} 略作修改，把它变成 {a^n b^n c^n, n>0}（即若干个 a 后跟相同数量的 b 和 c），就成了上下文相关语言。

该语言的 PCRE 正则表达式如下：

/^
    (?=(a(?-1)?b)c)
     a+(b(?-1)?c)
$/x

暂且忽略 (?=...) 断言，先看剩下的 a+(b(?-1)?c)。这个部分检查是否存在任意数量的 a，后跟相同数量的 b 和 c。(?-1) 其中，是一个相对 subpattern 引用，表示「定义的最后一个 subpattern」，在本例中指向 (b(?-1)?c)。

至于新面孔 (?=...)，属于所谓「零宽先行断言」（zero-width lookahead assertion）。这种断言检查后续文本是否匹配，但实际上并不「消耗」（consume）文本。（译注：正则匹配中的「消耗」是指将一个字符视为处理完毕，不再继续参与匹配。）换言之，文本同时受到两个模式的检查。a+(b(?-1)?c) 检查 b 和 c 的数量是否相同，而 (a(?-1)?b)c 检查 a 和 b 的数量是否相同。这两个模式从而确保了三个字符的数量都相同。

上式已经表明了如何用正则表达式实现「上下文」的概念：使用断言。回到上下文相关文法的定义，可以说如下形态的产生式规则：

αAβ -> αγβ

能转换为如下含 DEFINE 断言的正则表达式：

(?<A> (?<= α ) γ (?= β ) )

这个正则表达式表示 A 可替换为 γ，但前提是其左侧有 α 且右侧有 β。

由此，似乎可以轻松地将上下文相关文法转换为正则表达式，但实际并非如此。原因是后行断言（lookbehind assertion, (?<= ... )）有一个重大限制：宽度必须是固定的。这意味着后行断言匹配的文本长度必须已知。例如，可以写 (?<= a(bc|cd) )，但不能写 (?<= ab+)。前一个断言总是恰好匹配三个字符，宽度固定；而第二个断言可以匹配 ab、abb、abbb 等，宽度各异。要是允许这样，匹配引擎就分不清从何处开始匹配了，因此这种写法受到禁止。

这条限制几乎抹杀了上下文相关文法到正则表达式的简单转换，因为上下文相关文法几乎都依赖可变宽度的后行断言。

但是，说「上下文相关文法不能直接转换为正则表达式」，并不等于说「正则表达式不能匹配所有上下文相关文法」。例如，上面的 {a^n b^n c^n, n>0} 虽然存在含有变宽后行断言的表达方式，但是正则表达式用的规则不一定要和文法一致，可以通过改变写法来曲径通幽。也许其他上下文相关文法也都可以这样绕过，但老实说我不确定。

所以结论是？正则表达式至少可以匹配某些上下文相关语言，但尚不清楚是否可以匹配所有上下文相关语言。

（译注：答案在理论上似乎是肯定的，即对于每个上下文相关文法，都可以构造一个等价、但只包含一侧递归的上下文相关文法，从而改写为正则表达式支持的形式。但我的理解是，这在实际中还会受到复杂度、性能等额外限制，因此不总是可行的。）

无限制文法

乔姆斯基层次结构中的下一类文法是无限制文法（unrestricted grammar）。无限制文法能形成的语言，是所有递归可枚举语言（recursively enumerable language）的集合。

无限制文法没什么好多解释的，毕竟「无限制」嘛。无限制文法的产生式规则具有 α -> β 的形式，其中 α 和 β 是没有任何限制的符号组成的字符串。

换言之，无限制文法取消了不可收缩文法的「不可收缩」限制。因此，到了无限制文法中，A B C -> H Q 就变成了有效规则。

无限制文法到底有多强大？要多强就有多强：无限制文法是图灵完备（Turin complete）的。甚至还有一种基于无限制文法的「编程语言」：Thue。这个语言的图灵完备性意味着它能做其他语言能做的所有事情。

如果一个文法图灵完备，意味着在一般情况下，无法判定某个字符串是否符合它。

很遗憾，关于正则表达式和无限制文法之间的关系，我也没什么能说的。哎呀，我甚至找不到一个有意义的无限制文法的例子（不可收缩文法除外）。

但是既然聊到了图灵完备，就也得聊聊——

匹配包含反向引用的正则表达式是 NP 完全问题

我之前没有提到另一个很强大的正则表达式功能：反向引用（backreference）。

例如，考虑这个很简单的正则表达式：

/^(.*)\1$/

(.*) 匹配一段任意文本，\1 匹配相同的文本。通常，\n 表示「第 n 个 subpattern 匹配的文本」。例如，如果 (.*) 匹配到了 foo，则 \1 也将仅匹配 foo，其他任何文本都不匹配。因此，表达式 (.*)\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 问，给定一组物品，每个物品有特定的重量和价值，如何在背包承重限制下，找出总价值最大的物品组合？）

如果要构成一个 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 命名，以便保持代码的整洁和可读性。

就写这么多吧。

via 少数派 - 高品质数字消费指南 https://sspai.com

February 13, 2025 at 09:39AM