regex - 我们如何匹配 a^n b^n？

Question

_{This is the second part of a series of educational regex articles. It shows how lookaheads and nested references can be used to match the non-regular languge aⁿbⁿ. Nested references are first introduced in: How does this regex find triangular numbers?}

非典型原型(prototype)之一 regular languages是:

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

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

此语言可以通过 pumping lemma 显示为非常规语言.它实际上是一个原型(prototype) context-free language ，可以由 context-free grammar 生成 S → aSb | ab .

尽管如此，现代正则表达式实现清楚地识别出的不仅仅是常规语言。也就是说，它们不是形式语言理论定义的“常规”。 PCRE 和 Perl 支持递归正则表达式，.NET 支持平衡组定义。甚至更少的“花哨”功能，例如反向引用匹配，意味着正则表达式不规则。

但这个“基本”功能到底有多强大？我们能认出 L例如，使用 Java 正则表达式？我们能否将环视和嵌套引用结合起来，并有一个适用于例如的模式 String.matches 匹配像 ab 这样的字符串, aabb , aaabbb等？

引用文献

perlfaq6: Can I use Perl regular expressions to match balanced text?

MSDN - Regular Expression Language Elements - Balancing Group Definitions

pcre.org - PCRE man page

regular-expressions.info - Lookarounds和 Grouping and Backreferences

java.util.regex.Pattern

相关问题

Does lookaround affect which languages can be matched by regular expressions?

.NET Regex Balancing Groups vs PCRE Recursive Patterns

Answer 1

答案是，不用说，是的!您肯定可以编写一个 Java 正则表达式模式来匹配 anbn。它对断言使用正向前瞻，对“计数”使用一个嵌套引用。
这个答案不会立即给出模式，而是引导读者完成推导它的过程。随着解决方案的慢慢构建，给出了各种提示。在这方面，希望这个答案不仅仅包含另一个简洁的正则表达式模式。希望读者也能学会如何“用正则表达式思考”，如何将各种结构和谐地组合在一起，以便日后自己推导出更多的模式。
用于开发解决方案的语言将是 PHP，因为它的简洁性。模式完成后的最终测试将在 Java 中完成。

第 1 步:前瞻断言
让我们从一个更简单的问题开始:我们想要匹配字符串开头的a+，但前提是它后面紧跟b+。我们可以使用^到anchor来匹配，因为我们只想匹配a+而没有b+，我们可以使用lookahead断言(?=…)。
这是我们使用简单测试工具的模式:

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);

输出是( as seen on ideone.com):

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

这正是我们想要的输出:我们匹配 a+，仅当它位于字符串的开头，并且仅当它紧跟在 b+之后。
类(class):您可以在环视中使用模式来做出断言。

第 2 步:在前瞻中捕获(和 f r e - s p a c i n g 模式)
现在让我们说，即使我们不希望 b+成为比赛的一部分，我们仍然希望将它 capture放入第 1 组。此外，由于我们预计会有更复杂的模式，让我们使用 x ” 修饰符 free-spacing，这样我们就可以使我们的正则表达式更具可读性。
在我们之前的 PHP 代码段的基础上，我们现在有以下模式:

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

输出现在是( as seen on 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。
类(class):您可以在环视中捕捉。您可以使用自由间距来增强可读性。

第 3 步:将前瞻重构为“循环”
在我们介绍我们的计数机制之前，我们需要对我们的模式做一个修改。目前，前瞻在 +重复“循环”之外。到目前为止这很好，因为我们只是想断言在我们的 b+之后有一个 a+，但我们最终真正想做的是断言对于我们在“循环”中匹配的每个 a，有一个相应的 b与之配套。
暂时不用担心计数机制，只需进行如下重构:

首先将a+重构为(?: a )+(注意(?:…)是非捕获组)

然后在这个非捕获组内移动前瞻

请注意，我们现在必须“跳过”a*才能“看到”b+，因此相应地修改模式

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

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

输出与之前相同( as seen on ideone.com)，因此在这方面没有变化。重要的是，现在我们在 +“循环”的每次迭代中进行断言。对于我们当前的模式，这不是必需的，但接下来我们将使用自我引用为我们“计数”组 1。
类(class):您可以在非捕获组内进行捕获。环视可以重复。

第 4 步:这是我们开始计数的步骤
这是我们要做的:我们将重写第 1 组，使其:

在+的第一次迭代结束时，当第一个a匹配时，它应该捕获b

在第二次迭代结束时，当匹配到另一个a时，它应该捕获bb

在第三次迭代结束时，它应该捕获bbb

...

在第 n 次迭代结束时，组 1 应捕获 bn

如果没有足够的b来捕获到组 1 中，那么断言只会失败

因此，现在是 (b+)的第 1 组必须重写为 (\1 b)之类的内容。也就是说，我们尝试将 b“添加”到第 1 组在前一次迭代中捕获的内容。
这里有一个小问题，因为这种模式缺少“基本情况”，即它可以在没有自引用的情况下进行匹配的情况。需要一个基本情况，因为第 1 组开始“未初始化”；它尚未捕获任何内容(甚至不是空字符串)，因此自引用尝试将始终失败。
有很多方法可以解决这个问题，但现在让我们让自引用匹配 optional，即 \1?。这可能会也可能不会完美地工作，但让我们看看它的作用，如果有任何问题，那么当我们来到它时我们会越过那座桥。此外，我们将在此过程中添加更多测试用例。

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

输出现在是( as seen on 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，不知怎么算错了!我们将在下一步中研究为什么会发生这种情况。
类(class):“初始化”自引用组的一种方法是使自引用匹配成为可选。

步骤 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)。
课:小心回溯。正则表达式引擎将尽可能多地进行回溯，直到给定的模式匹配为止。这可能会影响性能(即 catastrophic backtracking)和/或正确性。

第 5 步:自我占有来拯救!
“修复”现在应该很明显了:将可选的重复与 possessive量词结合起来。也就是说，不是简单的 ?，而是使用 ?+(记住，被量化为所有格的重复不会回溯，即使这种“合作”可能导致整体模式的匹配)。
用非常非正式的术语来说，这就是 ?+、 ?和 ??所说的:

?+

• (optional) "It doesn't have to be there,"
  • (possessive) "but if it is there, you must take it and not let go!"

?

• (optional) "It doesn't have to be there,"
  • (greedy) "but if it is you can take it for now,"
    • (backtracking) "but you may be asked to let it go later!"

??

• (optional) "It doesn't have to be there,"
  • (reluctant) "and even if it is you don't have to take it just yet,"
    • (backtracking) "but you may be asked to take it later!"

在我们的设置中， \1不会在第一次出现，但之后的任何时候它都会出现，我们总是想匹配它。因此， \1?+将完成我们想要的。

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

现在输出是( as seen on 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!!!

瞧!!!问题解决!!!我们现在正在正确地计数，正是我们想要的方式!
课:了解贪婪、勉强和占有性重复之间的区别。 Optional-possessive 可以是一个强大的组合。

第 6 步:收尾工作
所以我们现在拥有的是一个重复匹配 a的模式，对于每个匹配的 a，在第 1 组中捕获到一个对应的 b。当没有更多的 +时， a终止” ，或者如果断言失败，因为 b没有对应的 a。
为了完成这项工作，我们只需要附加到我们的模式 \1 $。现在这是对第 1 组匹配内容的反向引用，后跟行 anchor 的结尾。 anchor 确保字符串中没有任何额外的 b；换句话说，事实上我们有anbn。
这是最终的模式，带有额外的测试用例，包括一个长度为 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和 a5000b5000。它需要 only 0.06s to run on ideone.com。

第 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);
}

该模式按预期工作( as seen on ideone.com)。

现在我们得出结论......
需要说明的是，前瞻中的 a*和“主 +循环实际上都允许回溯。鼓励读者确认为什么这在正确性方面不是问题，以及为什么同时使两个所有格都有效(尽管在同一模式中混合强制性和非强制性所有格可能会导致误解)。
还应该说，虽然有一个匹配 anbn 的正则表达式模式很好，但这并不总是实践中的“最佳”解决方案。更好的解决方案是简单地匹配 ^(a+)(b+)$，然后比较托管编程语言中第 1 组和第 2 组捕获的字符串的长度。
在 PHP 中，它可能看起来像这样( as seen in ideone.com):

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

这篇文章的目的不是让读者相信正则表达式几乎可以做任何事情；它显然不能，即使对于它可以做的事情，如果它导致更简单的解决方案，至少应该考虑将部分委派给托管语言。
正如顶部所提到的，虽然这篇文章对于 stackoverflow 必须标记为 [regex]，但它可能不止于此。虽然学习断言、嵌套引用、所有格量词等当然很有值(value)，但也许这里更大的教训是一个人可以尝试解决问题的创造性过程，当你遇到问题时通常需要决心和努力工作各种约束，从各个部分的系统组合以构建工作解决方案等。

奖励 Material ! PCRE递归模式!
既然我们确实提出了 PHP，那么需要说明的是 PCRE 支持递归模式和子程序。因此，以下模式适用于 preg_match( as seen on ideone.com):

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

目前 Java 的正则表达式不支持递归模式。

更多的奖励 Material !匹配 anbncn !!
所以我们已经看到了如何匹配非规则但仍然是上下文无关的 anbn，但是我们是否也可以匹配甚至不是上下文无关的 anbncn？
答案当然是肯定的!鼓励读者尝试自己解决这个问题，但下面提供了解决方案(带有 implementation in Java on ideone.com)。

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