我们如何匹配a^nb^n？

Question

_{这是一系列教育正则表达式文章的第二部分。它展示了如何使用前瞻和嵌套引用来匹配非常规语言 aⁿbⁿ。嵌套引用首先在：此正则表达式如何查找三角形数字？}

一种典型的非常规语言是：

L = { aⁿbⁿ: n >; 0 }

这是所有非空字符串的语言，由一定数量的 a 和后跟相同数量的 b 组成。这种语言中的字符串示例有 ab、aabb、aaabbb。

这种语言可以通过抽引理显示为非正则语言。它实际上是一种原型上下文无关语言，可以由上下文无关语法 S → aSb | ab.

尽管如此，现代正则表达式实现显然不仅仅识别常规语言。也就是说，根据正式语言理论的定义，它们不是“规则的”。 PCRE 和 Perl 支持递归正则表达式，.NET 支持平衡组定义。即使不太“花哨”的功能，例如反向引用匹配，也意味着正则表达式不是常规的。

但这个“基本”功能到底有多强大呢？例如，我们可以使用 Java 正则表达式识别 L 吗？我们是否可以将环视和嵌套引用结合起来，并拥有一种适用于例如 String.matches 匹配 ab、aabb、<代码>aaabbb等？

参考文献

• perlfaq6：我可以使用 Perl 正则表达式来匹配平衡文本吗？
• MSDN - 正则表达式语言元素 - 平衡组定义
• pcre.org - PCRE手册页
• regular-expressions.info - 环视 和 分组和反向引用
• java .util.regex.Pattern

链接问题

• lookaround 是否会影响正则表达式可以匹配哪些语言？
• .NET正则表达式平衡组与 PCRE 递归模式

Answer 1

鉴于没有提及 PCRE 支持递归模式，我只想指出描述相关语言的最简单、最有效的 PCRE 示例：

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

Answer 2

正如问题中提到的 - 使用 .NET 平衡组，类型的模式 aⁿbⁿcⁿdⁿ…zⁿ 可以轻松匹配，例如

^
  (?<A>a)+
  (?<B-A>b)+  (?(A)(?!))
  (?<C-B>c)+  (?(B)(?!))
  ...
  (?<Z-Y>z)+  (?(Y)(?!))
$

： http://www.ideone.com/usuOE

---

编辑：

对于具有递归模式的通用语言，还有一个 PCRE 模式，但需要先行查找。我认为这不是上述内容的直接翻译。

^
  (?=(a(?-1)?b))  a+
  (?=(b(?-1)?c))  b+
  ...
  (?=(x(?-1)?y))  x+
     (y(?-1)?z)
$

例如：http://www.ideone.com/9gUwF

Answer 3

不用说，答案是，是！您肯定可以编写 Java 正则表达式模式来匹配 aⁿbⁿ< /em>。它使用正向前瞻进行断言，并使用一个嵌套引用进行“计数”。

这个答案不会立即给出模式，而是引导读者完成推导模式的过程。随着解决方案的慢慢构建，会给出各种提示。在这方面，希望这个答案将包含的不仅仅是另一个简洁的正则表达式模式。希望读者也能学习如何“用正则表达式思考”，以及如何将各种结构和谐地组合在一起，这样他们将来就可以自己推导出更多模式。

由于其简洁性，用于开发该解决方案的语言将是 PHP。一旦模式最终确定，最终测试将在 Java 中完成。

---

第 1 步：断言的前瞻

让我们从一个更简单的问题开始：我们想要匹配字符串开头的 a+，但前提是它后面紧跟着 b+。我们可以使用 ^ 来锚定我们的匹配，因为我们只想匹配 a+ 而不匹配 b+，我们可以使用 前瞻断言(?=…)。

这是带有简单测试工具的模式：

function testAll($r, $tests) {
   foreach ($tests as $test) {
      $isMatch = preg_match($r, $test, $groups);
      $groupsJoined = join('|', $groups);
      print("$test $isMatch $groupsJoined\n");
   }
}
 
$tests = array('aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb');
 
$r1 = '/^a+(?=b+)/';
#          └────┘
#         lookahead

testAll($r1, $tests);

输出为（如 ideone.com 上所示）：

aaa 0
aaab 1 aaa
aaaxb 0
xaaab 0
b 0
abbb 1 a

这正是我们想要的输出：我们匹配 a+，仅当它位于字符串的开头，并且仅当它紧随其后的是 b+ 时。

教训：您可以在环视中使用模式来做出断言。

---

第 2 步：在前瞻（和自由间距模式）中捕获

现在假设即使我们不希望 b+ 成为匹配的一部分，但我们确实希望 将其捕获到第 1 组中。此外，由于我们预计会有更复杂的模式，因此我们使用 x free-spacing 修饰符，这样我们就可以使我们的正则表达式更具可读性。

在之前的 PHP 代码片段的基础上，我们现在具有以下模式：

$r2 = '/ ^ a+ (?= (b+) ) /x';
#             │   └──┘ │
#             │     1  │
#             └────────┘
#              lookahead
 
testAll($r2, $tests);

现在的输出（如 ideone.com 上所示 )：

aaa 0
aaab 1 aaa|b
aaaxb 0
xaaab 0
b 0
abbb 1 a|bbb

请注意，例如 aaa|b 是 join 的结果 - 每个组使用 '|' 捕获的内容。在本例中，组 0（即模式匹配的内容）捕获了 aaa，组 1 捕获了 b。

教训：您可以在环顾四周进行捕捉。您可以使用自由间距来增强可读性。

---

步骤 3：将前瞻重构为“循环”

在引入计数机制之前，我们需要对模式进行一项修改。目前，前瞻位于 + 重复“循环”之外。到目前为止这还不错，因为我们只是想断言 a+ 后面有一个 b+，但我们最终真正想要做的是断言对于我们在“循环”内匹配的每个 a，都有一个相应的 b 与之配合。

我们暂时不用担心计数机制，只需进行如下重构：

• 首先将 a+ 重构为 (?: a )+ （注意 (?: ...) 是一个非捕获组）
• 然后将前瞻移动到该非捕获组内
  • 请注意，我们现在必须“跳过”a*，然后才能“看到”b+，因此请相应地修改模式

所以我们现在有以下内容：

$r3 = '/ ^ (?: a (?= a* (b+) ) )+ /x';
#          │     │      └──┘ │ │
#          │     │        1  │ │
#          │     └───────────┘ │
#          │       lookahead   │
#          └───────────────────┘
#           non-capturing group

输出是相同的和以前一样（如 ideone.com 上所示），因此在这方面没有任何变化。重要的是，现在我们在 +“循环”的每次迭代处进行断言。对于我们当前的模式，这不是必需的，但接下来我们将使用自引用使组 1 为我们“计数”。

教训：您可以在非捕获组内进行捕获。环视可以重复。

---

第 4 步：这是我们开始计数的步骤

这是我们要做的：我们将重写组 1，以便：

• 在 + 的第一次迭代结束时，当第一个a 匹配，它应该捕获 b
• 在第二次迭代结束时，当另一个 a 匹配时，它应该捕获 bb
• 在第三次迭代结束时，它应该捕获 bbb
• ...
• 在第 n 次迭代结束时，组 1 应捕获 bⁿ
• 如果没有足够的 b 来捕获到组 1，那么断言就会失败，

所以组 1，现在是 (b+) ，必须重写为 (\1 b) 之类的内容。也就是说，我们尝试将 b“添加”到组 1 在上一次迭代中捕获的内容中。

这里有一个小问题，即该模式缺少“基本情况”，即无需自引用即可匹配的情况。需要基本情况​​，因为组 1 开始时“未初始化”；它还没有捕获任何内容（甚至没有空字符串），因此自引用尝试总是会失败。

有很多方法可以解决这个问题，但现在让我们将自引用匹配 可选 ，即\1?。这可能工作得很好，也可能不完美，但让我们看看它能做什么，如果有任何问题，那么当我们遇到问题时，我们就会跨过那座桥。此外，我们还将添加更多测试用例。

$tests = array(
  'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb'
);
 
$r4 = '/ ^ (?: a (?= a* (\1? b) ) )+ /x';
#          │     │      └─────┘ | │
#          │     │         1    | │
#          │     └──────────────┘ │
#          │         lookahead    │
#          └──────────────────────┘
#             non-capturing group

现在的输出是（如 ideone.com 上所示）：

aaa 0
aaab 1 aaa|b        # (*gasp!*)
aaaxb 0
xaaab 0
b 0
abbb 1 a|b          # yes!
aabb 1 aa|bb        # YES!!
aaabbbbb 1 aaa|bbb  # YESS!!!
aaaaabbb 1 aaaaa|bb # NOOOOOoooooo....

啊哈！看来我们现在已经非常接近解决方案了！我们成功地让第 1 组使用自我引用来“计数”！但是等等...第二个和最后一个测试用例出了问题！没有足够的 b，并且不知何故计数错误！我们将在下一步中检查为什么会发生这种情况。

教训：“初始化”自引用组的一种方法是使自引用匹配可选。

---

步骤 4½：了解出了什么

问题 问题是，由于我们将自引用匹配设为可选，因此当没有足够的 b 时，“计数器”可以“重置”回 0。让我们仔细检查一下以 aaaaabbb 作为输入的模式的每次迭代中发生的情况。

 a a a a a b b b
↑
# Initial state: Group 1 is "uninitialized".
           _
 a a a a a b b b
  ↑
  # 1st iteration: Group 1 couldn't match \1 since it was "uninitialized",
  #                  so it matched and captured just b
           ___
 a a a a a b b b
    ↑
    # 2nd iteration: Group 1 matched \1b and captured bb
           _____
 a a a a a b b b
      ↑
      # 3rd iteration: Group 1 matched \1b and captured bbb
           _
 a a a a a b b b
        ↑
        # 4th iteration: Group 1 could still match \1, but not \1b,
        #  (!!!)           so it matched and captured just b
           ___
 a a a a a b b b
          ↑
          # 5th iteration: Group 1 matched \1b and captured bb
          #
          # No more a, + "loop" terminates

啊哈！在第四次迭代中，我们仍然可以匹配 \1，但无法匹配 \1b！由于我们允许自引用匹配对于 \1? 是可选的，因此引擎回溯并采取“不，谢谢”选项，然后允许我们仅匹配和捕获 b!

但请注意，除了第一次迭代之外，您始终可以仅匹配自引用 \1。当然，这是显而易见的，因为这是我们在上一次迭代中刚刚捕获的内容，并且在我们的设置中我们总是可以再次匹配它（例如，如果我们上次捕获了 bbb ，我们保证有仍然是 bbb，但这次可能有也可能没有 bbbb）。

教训：谨防回溯。正则表达式引擎将进行尽可能多的回溯，直到给定的模式匹配为止。这可能会影响性能（即灾难性回溯）和/或正确性。

---

第五步：自我克制来拯救！

现在“修复”应该是显而易见的：将可选重复与 所有格 量词结合起来。也就是说，不要简单地使用 ?，而是使用 ?+ （请记住，被量化为所有格的重复不会回溯，即使这种“合作”可能会导致整体模式的匹配）。

用非常非正式的术语来说，?+、? 和 ?? 的意思是：

<代码>?+

• （可选）“它不必在那里，”
  • （占有欲）“但如果它在那里，你必须抓住它，不要放手！”

<代码>？

• （可选）“它不必在那里，”
  • （贪婪）“但如果是的话，你现在可以接受它，”
    • （回溯）“但稍后可能会要求您放手！”

<代码>??

• （可选）“它不必在那里，”
  • （不情愿）“即使是这样，你也不必马上接受它，”
    • （回溯）“但你可能会被要求稍后再拿！”

在我们的设置中，\1 第一次不会出现，但此后它始终会出现，而且我们始终那就想匹配一下。因此， \1?+ 将完全实现我们想要的效果。

$r5 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ /x';
#          │     │      └──────┘ │ │
#          │     │          1    │ │
#          │     └───────────────┘ │
#          │         lookahead     │
#          └───────────────────────┘
#             non-capturing group

现在输出是（如 ideone.com 上所示）：

aaa 0
aaab 1 a|b          # Yay! Fixed!
aaaxb 0
xaaab 0
b 0
abbb 1 a|b
aabb 1 aa|bb
aaabbbbb 1 aaa|bbb
aaaaabbb 1 aaa|bbb  # Hurrahh!!!

Voilà！！！问题解决了！！！我们现在正在正确计数，完全按照我们想要的方式进行！

教训：了解贪婪、不情愿和占有欲重复之间的区别。可选-所有格可以是一个强大的组合。

---

第 6 步：收尾工作

现在我们拥有的是一个重复匹配 a 的模式，并且对于每个匹配的 a ，都有一个对应的 b< /code> 在组 1 中捕获。当不再有 a 时，或者由于没有相应的 b 导致断言失败时，+ 终止code> 为 a。

要完成这项工作，我们只需附加到我们的模式 \1 $ 中。现在，这是对组 1 匹配的内容的反向引用，后跟行锚点的末尾。锚点确保字符串中没有任何额外的 b；换句话说，实际上我们有aⁿbⁿ。

这是最终确定的模式，带有其他测试用例，其中一个长度为 10,000 个字符：

$tests = array(
  'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb',
  '', 'ab', 'abb', 'aab', 'aaaabb', 'aaabbb', 'bbbaaa', 'ababab', 'abc',
  str_repeat('a', 5000).str_repeat('b', 5000)
);
 
$r6 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ \1 $ /x';
#          │     │      └──────┘ │ │
#          │     │          1    │ │
#          │     └───────────────┘ │
#          │         lookahead     │
#          └───────────────────────┘
#             non-capturing group

它找到 4 个匹配项：ab、aabb、aaabbb 和a⁵⁰⁰⁰b⁵⁰⁰⁰。 在 ideone.com 上运行只需 0.06 秒。

---

第 7 步：Java 测试

因此，该模式可以在 PHP 中运行，但最终目标是编写一个可以在 Java 中运行的模式。

public static void main(String[] args) {
 
        String aNbN = "(?x) (?:  a  (?= a* (\\1?+ b))  )+ \\1";
        String[] tests = {
                "",      // false
                "ab",    // true
                "abb",   // false
                "aab",   // false
                "aabb",  // true
                "abab",  // false
                "abc",   // false
                repeat('a', 5000) + repeat('b', 4999), // false
                repeat('a', 5000) + repeat('b', 5000), // true
                repeat('a', 5000) + repeat('b', 5001), // false
        };
        for (String test : tests) {
                System.out.printf("[%s]%n  %s%n%n", test, test.matches(aNbN));
        }
 
}
 
static String repeat(char ch, int n) {
        return new String(new char[n]).replace('\0', ch);
}

该模式按预期工作（如 ideone.com 上所示）。

---

现在我们得出结论...

需要指出的是，前瞻中的 a* 以及“main + 循环”实际上都允许回溯。鼓励读者确认为什么这在正确性方面不是问题，以及为什么同时使两个所有格也能起作用（尽管以相同模式混合强制和非强制所有格量词可能会导致误解）。

还应该说，虽然有一个正则表达式模式可以匹配aⁿbⁿ，但这并不总是“实践中最好的解决方案。更好的解决方案是简单地匹配 ^(a+)(b+)$，然后比较托管编程语言中组 1 和组 2 捕获的字符串的长度。

在 PHP 中，它可能看起来像这样（如 ideone.com 中所示）：

function is_anbn($s) {
   return (preg_match('/^(a+)(b+)$/', $s, $groups)) &&
      (strlen($groups[1]) == strlen($groups[2]));
}

本文的目的是 < em>不是让读者相信正则表达式几乎可以做任何事情；它显然不能，即使对于它可以做的事情，如果它能带来更简单的解决方案，至少应该考虑部分委托给托管语言。

正如顶部所提到的，虽然本文必须为 stackoverflow 标记为 [regex]，但它的含义可能不止于此。虽然学习断言、嵌套引用、所有格量词等当然是有价值的，但也许这里更大的一课是尝试解决问题的创造性过程，当你遇到困难时，它通常需要决心和努力工作。各种约束、由各个部分组成的系统性构建工作解决方案等。

---

奖励材料！ PCRE递归模式！

既然我们确实提出了 PHP，就需要说 PCRE 支持递归模式和子例程。因此，以下模式适用于 preg_match（如 ideone.com 上所示）

$rRecursive = '/ ^ (a (?1)? b) $ /x';

：正则表达式不支持递归模式。

---

更多奖励材料！匹配aⁿbⁿcⁿ！！

我们已经了解了如何匹配 aⁿbⁿ，它是非常规的，但仍然与上下文无关，但我们也可以匹配aⁿbⁿcⁿ，这甚至不是上下文无关的？

答案当然是，是！鼓励读者尝试自己解决这个问题，但解决方案在下面提供（ideone.com 上的 Java 实现）。

^ (?: a (?= a* (\1?+ b) b* (\2?+ c) ) )+ \1 \2 $