正则表达式的真正威力 (2012)

作为经常在 StackOverflow 上使用 PHP 标签的人，我经常看到有关如何使用正则表达式解析 HTML 某些特定方面的问题。对于此类问题的常见回答是：您无法使用正则表达式解析 HTML，因为 HTML 不是正则表达式。请改用 XML 解析器。在问题的背景下，这种说法介于非常误导性和完全错误之间。我将在本文中尝试展示现代正则表达式的真正强大之处。 “常规”到底意味着什么？在形式语言理论的背景下，当某种东西具有一种语法，其中所有产生式规则都具有以下形式之一时，它被称为“常规”：您可以将这些 -> 规则读作“左侧可以替换为右侧”。所以第一条规则是“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 这个语法说的是： A自然数 (N) 是 ... 数字 0 到 9 之一或 ... 数字 0 到 9 之一后跟另一个自然数 (N) 在此示例中，数字 0 到 9 将是终结符（因为它们不能进一步分解），而 N 将是唯一的非终结符（因为它可以是并且可以进一步分解）。如果您再看一下这些规则并将它们与上面的正则语法的定义进行比较，您会发现它们满足标准：前十个规则的形式为 B -> a ，后十个规则遵循形式 B -> aC 。因此定义自然数的语法是规则的。你可能会注意到的另一件事是，尽管上面的语法定义了这么简单的东西，但它已经相当臃肿了。如果我们能用更简洁的方式表达同样的概念不是更好吗？这就是正则表达式的用武之地：上面的语法相当于正则表达式 [0-9]+ （这要简单得多）。这种转换可以用任何正则语法来完成：每个正则语法都有一个相应的正则表达式，它定义了它的所有有效字符串。正则表达式可以匹配什么？那么问题来了：正则表达式可以只匹配正则语法，还是可以匹配更多的语法？答案既是肯定的，也是否定的：正式语法意义上的正则表达式（几乎根据定义）只能解析正则语法，仅此而已。但是，当程序员谈论“正则表达式”时，他们并不是在谈论形式语法。他们正在谈论他们的语言实现的正则表达式派生。这些正则表达式的实现与最初的正则性概念只有非常轻微的关系。任何现代正则表达式风格都可以匹配比常规语言更多的内容。到底是多少，这就是本文其余部分的内容。为了简单起见，我将在下面重点介绍 PCRE 正则表达式实现，因为我最了解它（因为 PHP 使用它）。大多数其他正则表达式实现都非常相似，因此大多数内容也应该适用于它们。语言层次结构 为了分析正则表达式可以匹配什么和不能匹配什么，我们首先必须看看还有哪些其他类型的语言。乔姆斯基层次结构是一个很好的起点：乔姆斯基层次结构：/--------------------------------------------------------\ | | |递归可枚举语言 |类型 0 | | | /------------------------------------------------\ | | | | | | |上下文相关语言 | |类型 1 | | | | | | /----------------------------\ | | | | | | | | | | |上下文无关语言 | | |类型 2 | | | | | | | | | /--------------------\ | | | | | | |常规语言 | | | |类型 3 | | | \--------------------/ | | | | | \----------------------------/ | | | \------------------------------------/ | \--------------------------------------------/ 如您所见，乔姆斯基层次结构将形式语言分为四种类型：常规语言（类型 3）是最弱的，其次是上下文无关语言（类型 2），上下文相关语言（类型 1），最后是全能的递归可枚举语言（类型 0）。乔姆斯基层次结构是包含层次结构，因此上图中较小的盒子完全包含在较大的盒子中。例如，每种正则语言也是一种上下文无关语言（但反之则不然！）因此，让我们在该层次结构中向上移动一步：我们已经知道正则表达式可以匹配任何正则语言