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 anbn. Nested references are first introduced in: How does this regex find triangular numbers?
非典型原型(prototype)之一 regular languages是:
L = { a
nb
n: 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
等?引用文献
java.util.regex.Pattern
相关问题
最佳答案
答案是,不用说,是的!您肯定可以编写一个 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
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 $
关于regex - 我们如何匹配 a^n b^n?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3644266/