正则表达式的真正威力（2012）

# 正则表达式的真正威力 Source: https://www.npopov.com/2012/06/15/The-true-power-of-regular-expressions.html 作为一个经常逛 StackOverflow 上 [PHP 标签](https://stackoverflow.com/questions/tagged/php) 的人，我经常看到关于如何使用正则表达式解析 HTML 某一部分的问题。对这种问题的常见回复是： > 你不能用正则表达式解析 HTML，因为 HTML 不是正则的。请改用 XML 解析器。 这种说法——在该问题的语境下——介于非常误导和完全错误之间。我在这篇文章中想要展示的是，现代正则表达式*真正*有多强大。 ## “正则”到底是什么意思？ 在[形式语言理论](https://en.wikipedia.org/wiki/Formal_language)的语境下，当一个文法满足所有产生式都具有以下形式之一时，我们称它为“正则的”： 你可以把这些 `->` 规则理解为“左边可以被右边替换”。所以第一条规则就是“B 可以被替换为 a”，第二条是“B 可以被替换为 aC”，第三条是“B 可以被替换为空字符串”（`ε` 是空字符串的符号）。 那么 `B`、`C` 和 `a` 又是什么呢？按惯例，大写字符表示所谓的“非终结符”——即*可以*进一步分解的符号；而小写字符表示“终结符”——即*不能*再进一步分解的符号。 这些听起来可能有点抽象，那我们来看一个例子：把自然数定义成一个文法。 ``` 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 使用它）。不过大多数其他正则表达式实现都相当类似，所以大部分内容也应该适用于它们。 ## 语言层级 为了分析正则表达式能匹配什么、不能匹配什么，我们首先需要看看还存在哪些其他类型的语言。一个很好的起点是[乔姆斯基层级](https://en.wikipedia.org/wiki/Chomsky_hierarchy)： ``` Chomsky hierarchy: /-------------------------------------------\ | | | Recursively enumerable languages Type 0 | | | | /-----------------------------------\ | | | | | | | Context-sensitive languages Type 1| | | | | | | | /---------------------------\ | | | | | | | | | | | Context-free languages | | | | | | Type 2 | | | | | | | | | | | | /-------------------\ | | | | | | | | | | | | | | | Regular languages | | | | | | | | Type 3 | | | | | | | \-------------------/ | | | | | \---------------------------/ | | | \-----------------------------------/ | \-------------------------------------------/ ``` 正如你所见，乔姆斯基层级把形式语言分为四种类型：正则语言（Type 3）能力最弱，其次是上下文无关语言（Type 2），再次是上下文相关语言（Type 1），最后是无所不能的递归可枚举语言（Type 0）。乔姆斯基层级是一个包含层级，因此上图中较小的方框被完全包含在较大的方框内。例如，每个正则语言同时也是上下文无关语言（但*反之*不然！） 那么，让我们在这个层级中向上迈一步：我们已经知道正则表达式能匹配任何正则语言。但它们也能匹配上下文无关语言吗？（提醒：这里说“正则表达式”，我显然是在程序员的意义上说的，而不是形式语言理论的意义。） ## 匹配上下文无关语言 答案是*可以*，它们能！让我们以经典的上下文无关语言为例，即 `{a^n b^n, n>0}`，意思是“一定数量的 `a` 字符，后面跟着*同样数量*的 `b` 字符”。这个语言的（PCRE）正则表达式是： ``` /^(a(?1)?b)$/ ``` 这个正则表达式非常简单：`(?1)` 是对第一个子模式的引用，即 `(a(?1)?b)`。所以基本上你可以用这个子模式替换 `(?1)`，从而形成一个递归依赖： ``` /^(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` 同样是一个非终结符，而 `β` 是终结符和非终结符组成的任意字符串。因此，上下文无关文法的每条产生式左侧都有一个非终结符，右侧是一个任意符号串。 举个例子，看一下下面的文法： ``` 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_SOMETHING` 名称也是终结符。这些通常被称为*token*的符号编码了更抽象的概念。例如，`T_FUNCTION` 代表 `function` 关键字，`T_STRING` 是一个标签 token（如 `getUserById` 或 `some_other_name`）。 我用这个例子来展示一件事：上下文无关文法已经强大到足以编码相当复杂的语言。这就是为什么几乎所有的编程语言都有上下文无关文法。特别是，这还包括结构良好的 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)? ) (?<quoted_string> (?&CFWS)? " (?: (?&FWS)? (?&qcontent) )* (?&FWS)? " (?&CFWS)? ) (?<qcontent> (?&qtext) | (?&quoted_pair) ) (?<qtext> \x21 | [\x23-\x5b] | [\x5d-\x7e] | (?&obs_qtext) ) # comments and whitespace (?<FWS> (?: (?&WSP)* \r\n )? (?&WSP)+ | (?&obs_FWS) ) (?<CFWS> (?: (?&FWS)? (?&comment) )+ (?&FWS)? | (?&FWS) ) (?<comment> \( (?: (?&FWS)? (?&ccontent) )* (?&FWS)? \) ) (?<ccontent> (?&ctext) | (?&quoted_pair) | (?&comment) ) (?<ctext> [\x21-\x27] | [\x2a-\x5b] | [\x5d-\x7e] | (?&obs_ctext) ) # obsolete tokens (?<obs_local_part> (?&word) (?: \. (?&word) )* ) (?<obs_domain> (?&atom) (?: \. (?&atom) )* ) (?<obs_dtext> (?&obs_NO_WS_CTL) | (?&quoted_pair) ) (?<obs_qp> \\ (?: \x00 | (?&obs_NO_WS_CTL) | \n | \r ) ) (?<obs_FWS> (?&WSP)+ (?: \r\n (?&WSP)+ )* ) (?<obs_ctext> (?&obs_NO_WS_CTL) ) (?<obs_qtext> (?&obs_NO_WS_CTL) ) (?<obs_NO_WS_CTL> [\x01-\x08] | \x0b | \x0c | [\x0e-\x1f] | \x7f ) # character class definitions (?<VCHAR> [\x21-\x7E] ) (?<WSP> [ \t] ) ) ^(?&addr_spec)$ /x ``` 上面看到的是用于匹配符合 [RFC 5322](http://tools.ietf.org/html/rfc5322) 的电子邮件地址的正则表达式。它仅仅是简单地将 RFC 中的 BNF 规则转换成 PCRE 能理解的表示法。语法非常简单：所有规则定义都被包裹在一个 `DEFINE` 断言中，这基本上意味着所有这些规则不应该被直接匹配，它们只是被定义。只有结尾的 `^(?&addr_spec)$` 部分指定了要匹配的内容。 这些规则定义实际上并不是真正的“规则”，而是命名子模式。在之前的 `(a(?1)?b)` 例子中，`1` 引用了第一个子模式。当子模式很多时，这显然不实用，因此它们可以被命名。`(?P<name>...)` 定义了一个名称为 `name` 的模式。`(?&name)` 则引用它。 另外，请注意另一个事实：上面这个正则表达式使用了 `x` 修饰符。这指示引擎忽略空白，并允许 `#` 风格的注释。这样你就可以把正则表达式格式得漂漂亮亮的，让别人真正看得懂。（完全不像[这个](http://www.ex-parrot.com/pdw/Mail-RFC822-Address.html) RFC 822 电子邮件地址正则表达式……） 因此，上面的语法允许从文法到正则表达式的简单映射： ``` A -> B C A -> C D // 变成 (?P<A> (?&B) (?&C) | (?&C) (?&D) ) ``` 唯一的问题是：正则表达式不支持左递归。例如，取上面参数列表的定义： ``` non_empty_parameter_list -> parameter non_empty_parameter_list -> non_empty_parameter_list ',' parameter ``` 你*不能*直接把它转换成基于文法的正则表达式。下面的写法是不行的： ``` (?P<non_empty_parameter_list> (?&parameter) | (?&non_empty_parameter_list) , (?&parameter) ) ``` 原因是，在这里 `non_empty_parameter_list` 作为其自身规则定义的最左部分出现。这被称为左递归，在文法定义中非常常见。原因是通常用于解析它们的 LALR(1) 解析器处理左递归比处理右递归好得多。 但是，别怕，这完全不影响正则表达式的能力。每个左递归文法都可以转换成右递归的。在上面的例子中，只需要交换两个部分： ``` non_empty_parameter_list -> parameter non_empty_parameter_list -> parameter ',' non_empty_parameter_list ``` 所以现在应该清楚了：正则表达式可以匹配任何上下文无关语言（因而也就能匹配几乎程序员会面对的所有语言）。唯一的问题是：尽管正则表达式能很好地*匹配*上下文无关语言，它们通常不能*解析*这些语言。解析意味着将某个字符串转换成抽象语法树。这对正则表达式来说是不可能的，至少 PCRE 是这样（当然，在 Perl 中你可以在正则表达式里嵌入任意代码，那几乎什么都能做……）。 尽管如此，上述基于 `DEFINE` 的正则表达式定义对我来说已经被证明*极为*有用。通常你并不需要完整的解析支持，而只是想匹配（例如电子邮件地址）或提取一小部分数据（而不是整个解析树）。大多数复杂的字符串处理问题，使用基于文法的正则表达式都会变得简单得多 :) 在这一点上，让我再次指出我之前已经简单提到过的内容：结构良好的 HTML 是上下文无关的。所以*可以*用正则表达式匹配它，这与流行的观点相反。但别忘了两件事：首先，你在现实中看到的大部分 HTML 都*不是*结构良好的（通常连接近都算不上）。其次，仅仅因为*可以*，并不意味着你*应该*。你也可以用 Brainfuck 写软件，但出于某种原因你并没有这么做。 我对这个问题的看法是：每当你需要通用的 HTML 处理时，使用你选择的 DOM 库。它能优雅地处理格式错误的 HTML，并为你承担解析的负担。另一方面，如果你处理的是特定情况，快速的正则表达式往往是正确的选择。而且我必须承认：尽管我经常告诉别人不要用正则表达式解析 HTML，但我自己也屡屡这么做。仅仅因为在大多数情况下，我面对的是特定而受控的场景，使用正则表达式更简单。 ## 上下文相关文法 既然我们已经深入讨论了上下文无关语言，让我们在乔姆斯基层级上再上一步：上下文相关语言。 在上下文相关语言中，所有产生式都具有以下形式： 这堆字符混合在一起可能看起来更复杂了，但实际上很简单。核心仍然是我们定义上下文无关文法时的模式 `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`。 ``` 上下文相关语言在“正常”编程中很少遇到。它们主要在处理自然语言时很重要（因为自然语言显然不是上下文无关的。词语根据上下文有不同的含义）。但即使在自然语言处理中，人们通常也使用所谓的“轻度上下文相关语言”，因为它们足以对语言进行建模，而且解析速度要快得多。 为了理解上下文相关文法到底有多强大，让我们看看另一个文法类别，它与上下文相关文法具有完全相同的表达能力：非收缩文法。在非收缩文法中，每条产生式的形式为 `α -> β`，其中 `α` 和 `β` 都是任意符号串，只有一个限制：右侧符号的数量不少于左侧。形式上表示为 `|α| <= |β|`，其中 `|x|` 表示符号串 `x` 的长度。所以非收缩文法允许任何形式的规则，只要它们不把输入变短。例如，`A B C -> H Q` 就是一条无效规则。