我们怎样才能匹配一个Java正则expression式？

_{这是一系列教育正则expression式文章的第二部分。} _{它展示了如何使用前瞻和嵌套的引用来匹配非规范的语言。} _{首先介绍嵌套引用：这个正则expression式如何find三angular形数字？}

其中一种典型的非正规语言是：

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

这是所有非空string的语言，由一些数字a组成，后面跟着相同数量的b 。这种语言的string的例子是ab ， aabb ， aaabbb 。

这个语言可以通过抽象引理显示为不规则的。它实际上是一个典型的上下文无关语言，可以由上下文无关文法 S → aSb | ab S → aSb | ab 。

尽pipe如此，现代的正则expression式实现清楚地认识到不仅仅是正规的语言。也就是说，它们不是由forms语言理论定义的“规则”。 PCRE和Perl支持recursion正则expression式，.NET支持平衡组定义。更less的“奇特”特征，例如反向引用匹配，意味着正则expression式不规则。

但是这个“基本”function有多强大呢？我们可以用Java正则expression式来识别L吗？我们是否可以将lookaround和嵌套的引用结合在一起，并且有一个与例如String.matches匹配的模式来匹配像ab ， aabb ， aaabbb等string？

参考

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

链接的问题

Lookaround是否影响哪些语言可以通过正则expression式匹配？
.NET正则expression式均衡组与PCRErecursion模式

答案是，不用说， 是的！ 你当然可以编写一个Java正则expression式来匹配一个ⁿ b ⁿ 。它使用肯定的前瞻来进行断言，并使用一个嵌套的“计数”参考。

这个答案不是立即给出模式，而是引导读者通过推导过程。解决scheme缓慢构build时提供了各种提示。在这方面，希望这个答案不仅仅包含另一个整洁的正则expression式模式。希望读者也能学会如何“正确思考”，如何把各种构build和谐地融合在一起，以便将来能够自己衍生出更多的模式。

用于开发解决scheme的语言是简洁的PHP。一旦模式完成，最后的testing将在Java中完成。

第1步：前瞻断言

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

这是我们的一个简单的testing用具模式：

 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+ ，只有当它在string的开头，并且只有紧跟在b+ 。

课程：你可以使用模式来改变断言。

第2步：以前瞻（和自由间隔模式）

现在让我们假设即使我们不想让b+成为匹配的一部分，我们仍然希望将其捕获到组1中。另外，当我们预计有一个更复杂的模式时，让我们使用x修饰符来表示自由间距所以我们可以使我们的正则expression式更具可读性。

基于我们之前的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 。

课程：你可以在一个lookaround中捕获。您可以使用自由间距来增强可读性。

第3步：将前瞻重构成“循环”

在介绍我们的计算机制之前，我们需要对我们的模式做一个修改。目前，前瞻是在+重复“循环”之外。到目前为止，这很好，因为我们只是断言有一个b+跟在我们的a+ ，但是我们最终想要做的是断言每a我们在“循环”内部匹配的对象都有一个相应的b 。

我们现在不用担心计数机制，只是重构如下：

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

所以我们现在有以下几点：

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

输出和以前一样（如在ideone.com上看到的），所以在这方面没有任何改变。重要的是，现在我们在+ “循环”的每一次迭代中断言。按照我们目前的模式，这不是必要的，但接下来我们将使用自引用让组1“为我们计数”。

课程：您可以在非捕获组内捕获。 Lookarounds可以重复。

第四步：这是我们开始计算的步骤

以下是我们要做的事情：我们将重写组1，使得：

在+的第一次迭代结束时，当第一个a匹配时，它应该捕获b
在第二次迭代结束时，当另一个匹配时，它应该捕获bb
在第三次迭代结束时，它应该捕获bbb
…
在第n次迭代结束时，组1应该捕获b ⁿ
如果没有足够的b捕获到组1，则断言简单地失败

所以现在(b+)将被重写为(\1 b) 。也就是说，我们试图将b添加到前一次迭代中捕获的组1中。

这里有一个小问题，就是这个模式缺less了“基本情况”，也就是说它没有自我引用就可以匹配。基本情况是必需的，因为组1开始“未初始化”; 它还没有捕获任何东西（甚至没有空string），所以自我引用尝试总是失败。

有很多方法可以解决这个问题，但是现在让我们让自我引用匹配可选，即\1? 。这可能会也可能不完美，但我们只是看看有什么问题，如果有任何问题，那么当我们到达时，我们会穿过那座桥。另外，我们还会添加更多的testing用例。

 $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....

A-HA！看起来我们现在真的很接近解决scheme！我们设法让第一组使用自我参考“计数”！但是等等…第二个和最后一个testing用例是错误的！没有足够的b ，不知何故它算错了！我们将研究为什么在下一步发生这种情况。

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

第四步½：了解哪里出了问题

问题是，由于我们使自我引用匹配成为可选的，所以当“计数器”没有足够的b时，“计数器”可以“重置”回0。让我们仔细研究在aaaaabbb作为input的模式的每一次迭代中发生了什么。

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

A-HA！在我们的第四次迭代中，我们仍然可以匹配\1 ，但是我们不能匹配\1b ！既然我们允许自引用匹配在\1?是可选的\1? ，引擎回溯，并采取“不要感谢”的select，这使我们能够匹配和捕获只是b ！

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

教训：小心回溯。正则expression式引擎将尽可能多的回溯，直到给定的模式匹配。这可能会影响性能（即灾难性的回溯）和/或正确性。

第五步：自救来拯救！

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

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

?+

（可选）“它不必在那里”

（占有）“，但如果它在那里，你必须拿走它，不要放弃！

?

（可选）“它不必在那里”

（贪婪）“，但如果是现在你可以拿它，”

（回溯）“，但是你可能会被要求放下！

??

（可选）“它不必在那里”

（不情愿的）“，即使是你不需要这样做，”

（回溯）“，但你可能会被要求稍后拿走！”

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

瞧！问题解决了！！！我们现在正在计数正确，正是我们想要的方式！

教训：学习贪婪，不情愿和重复占有的区别。可选的所有格可以是一个强大的组合。

第6步：完成触摸

所以我们现在所拥有的是a重复匹配的模式，对于每a被匹配的对象，在组1中都有一个对应的b 。当没有更多的a ， +终止，或者如果断言失败，因为没有对于一个对应的b 。

为了完成这个工作，我们只需要追加到我们的模式\1 $ 。现在这是对第1组匹配的反向引用，接下来是行锚的结尾。锚确保了在string中没有任何额外的b ; 换句话说，实际上我们有一个ⁿ b ⁿ 。

下面是最终的模式，附加的testing用例，包括一个长度为10000个字符的testing用例：

 $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

它find了4个匹配： ab ， aabb ， aaabbb和a ⁵⁰⁰⁰ b ⁵⁰⁰⁰ 。在ideone.com上运行只需要0.06秒。

第7步：Javatesting

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

还应该说，虽然有一个正则expression式可以匹配ⁿ b ⁿ ，但这并不总是实践中的“最佳”解决scheme。一个更好的解决scheme是简单地匹配^(a+)(b+)$ ，然后比较主机编程语言中组1和组2所捕获的string的长度。

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

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

这篇文章的目的不是说服读者，正则expression式几乎可以做任何事情; 它显然不能，甚至对于它所能做的事情，如果导致更简单的解决办法，至less应该考虑使用主办语言的部分授权。

正如上面提到的，虽然这篇文章有必要为[regex] stackoverflow [regex]标记[regex] ，但它可能不止于此。当然，学习断言，嵌套引用，占有量词等都是有价值的，也许这里更重要的一个教训就是人们可以尝试解决问题的创造性过程，当你遭遇到时经常需要的决心和努力各种制约因素，各部分的系统构成，构build工作解决scheme等。

奖金材料！ PCRErecursion模式！

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

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

目前Java的正则expression式不支持recursion模式。

我们怎样才能匹配一个Java正则expression式？

参考

链接的问题

第1步：前瞻断言

第2步：以前瞻（和自由间隔模式）

第3步：将前瞻重构成“循环”

第四步：这是我们开始计算的步骤

第四步½：了解哪里出了问题

第五步：自救来拯救！

`?+`

`?`

`??`

第6步：完成触摸

第7步：Javatesting

现在我们来得出结论

奖金材料！ PCRErecursion模式！

更多的奖金材料！匹配一个ⁿ b ⁿ c ⁿ ！

这个正则expression式如何find三angular形数字？

我们怎样才能匹配一个Java正则expression式？

参考

链接的问题

第1步：前瞻断言

第2步：以前瞻（和自由间隔模式）

第3步：将前瞻重构成“循环”

第四步：这是我们开始计算的步骤

第四步½：了解哪里出了问题

第五步：自救来拯救！

?+

?

??

第6步：完成触摸

第7步：Javatesting

现在我们来得出结论

奖金材料！ PCRErecursion模式！

更多的奖金材料！ 匹配一个n b n c n ！

这个正则expression式如何find三angular形数字？

`?+`

`?`

`??`

更多的奖金材料！匹配一个ⁿ b ⁿ c ⁿ ！