Java我们如何将a ^ nb ^ n与Java正则表达式匹配？

Z时代
2024-01-10
分类：问答

原型非常规语言之一是：

L = { an bn: n > 0 }

这是所有非空字符串的语言，其中包括一定数量的，a后跟相等数量b的。在这个语言字符串的例子有ab，aabb，aaabbb。

泵激引理可以证明这种语言是不规则的。实际上，它是原型上下文无关的语言，可以由上下文无关的语法生成S → aSb | ab。

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

但是，这种“基本”功能到底有多强大？L例如，我们可以用Java正则表达式识别吗？我们也许可以结合lookarounds和嵌套引用，并有一个模式，与如作品String.matches来匹配字符串一样ab，aabb，aaabbb，等？

回答：

答案是不用说，是的！您当然可以编写Java regex模式来匹配a n b n。它使用肯定的前瞻性进行断言，并使用一个嵌套的引用进行“计数”。

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

简洁起见，用于开发解决方案的语言将是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修饰符进行自由间距设置，这样我们可以使我们的正则表达式更具可读性。

在以前的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：将前瞻重构为“循环”

在介绍计数机制之前，我们需要对我们的模式进行一次修改。当前，前瞻位于+重复“循环”之外。到目前为止，这还不错，因为我们只是想断言b+我们后面有一个跟随符a+，但是最终我们真正想做的是断言，对于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 n

如果没有足够b的内容捕获到组1中，则断言将失败

因此，现在(b+)必须将第1组重写为(\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组“计数”！但是等等…第二个和最后一个测试用例出了问题！bs 不够，以某种方式它算错了！我们将在下一步研究为什么会发生这种情况。

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

步骤4½：了解出了什么问题

问题在于，由于我们将自引用匹配设置为可选，因此当计数器不足时，“计数器”可以“重置”为0 b。让我们仔细检查一下模式的每次迭代（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

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

请注意，但是，除了第一次迭代外，您始终可以只匹配self-reference \1。当然，这很明显，因为这是我们在上一次迭代中捕获的，并且在我们的设置中我们可以始终再次对其进行匹配（例如，如果我们bbb上次捕获，我们可以保证仍然存在bbb，但可能还是可能不是bbbb这次）。

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

第5步：自救。

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

用非常非正式的术语讲，这是什么?+，?并??说：

?+

- （optional）“不必在那里，”

- （possessive）“但是，如果存在，则必须将其拿起，不要放开！”

- （optional）“不必在那里，”

- （greedy）“但是如果可以的话，现在就可以接受，”

- （backtracking）“但可能会要求您稍后再放！”

??

（optional）“不必在那里，”

（reluctant）“即使是这样，您也不必立即接受它，”

（backtracking）“但可能会要求您稍后再购买！”

在我们的设置中，\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!!!

哎呀！问题解决了！！！现在，我们正按照我们想要的方式正确计数！

课程：了解贪婪，勉强和所有格重复之间的区别。可选拥有可能是强大的组合。

因此，我们现在拥有的是一个a反复匹配的模式，对于每个匹配的模式，在组1中a都有一个对应的b捕获。+当不再存在时a，或者如果断言失败，因为没有对应的b，则终止。一个a。

要完成这项工作，我们只需要追加到我们的pattern即可\1 $。现在，这是对第1组匹配项的后向引用，后面是行锚的末尾。锚确保b字符串中没有多余的；换句话说，实际上我们有一个n b n。

这是最终模式，其中包含其他测试用例，其中包括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 5000 b 5000。在ideone.com上运行仅需0.06s。

因此该模式可在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*是，前瞻和“主+循环”都允许回溯。鼓励读者确认为什么这不是正确性方面的问题，以及为什么同时拥有所有格也可以起作用（尽管以相同的方式混合强制性和非强制性所有格量词可能会导致误解）。

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

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

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

本文的目的不是要说服读者相信正则表达式几乎可以做任何事情；它显然不能，甚至对于它可以做的事情，如果可以导致更简单的解决方案，则至少应考虑对托管语言的部分委派。

如顶部所述，尽管本文必须标记[regex]为stackoverflow，但它可能不止于此。虽然学习断言，嵌套引用，所有格限定符等当然有价值，但是也许更大的一课是创造性的过程，通过该过程人们可以尝试解决问题，遇到困难时通常需要的决心和努力工作各种约束，从各个部分的系统组成，以建立有效的解决方案，等等。

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