pol*_*nts 94 java regex lookaround capturing-group nested-reference
这是一系列教育正则表达式文章的第二部分.它显示了向前看符号和嵌套引用如何可以用来匹配非正规languge ñ b ñ.嵌套引用首先介绍在:这个正则表达式如何找到三角形数字？
其中一种原型非常规语言是:
L = { añbñ: n > 0 }
这是所有非空字符串的语言,由一些数字a后跟相同数量的字符串组成b.在这个语言字符串的例子有ab,aabb,aaabbb.
这种语言可以通过泵浦引理显示为非规则的.它实际上是一种原型上下文无关语言,可以通过无上下文语法 生成S ? aSb | ab.
尽管如此,现代正则表达式实现清楚地认识到的不仅仅是常规语言.也就是说,它们不是形式语言理论定义的"规则".PCRE和Perl支持递归正则表达式,.NET支持平衡组定义.更少的"花哨"特征,例如反向引用匹配,意味着正则表达式不规则.
但这个"基本"功能有多强大？L例如,我们可以用Java正则表达式识别吗？我们也许可以结合lookarounds和嵌套引用,并具有与如工作模式String.matches来匹配字符串一样ab,aabb,aaabbb,等？
java.util.regex.Patternpol*_*nts 134
答案是,不用说,是的!你可以肯定写一个Java正则表达式匹配一个ñ b ñ.它使用正向前导进行断言,并使用一个嵌套引用进行"计数".
而不是立即发放的模式,这个答案将通过引导读者的过程中获得它的.随着解决方案的缓慢构建,给出了各种提示.在这方面,希望这个答案将包含更多不仅仅是另一个整洁的正则表达式模式.希望读者也将学习如何"在正则表达式中思考",以及如何将各种结构和谐地结合在一起,这样他们将来可以自己获得更多的模式.
用于开发解决方案的语言将是PHP的简洁性.模式完成后的最终测试将在Java中完成.
让我们从一个更简单的问题开始:我们希望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+.
课程:您可以在外观中使用模式来进行断言.
现在让我们说即使我们不希望它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内容的结果.在这种情况下,捕获组0(即模式匹配的内容),捕获组1 .join'|'aaab
课程:您可以在一个环视中捕获.您可以使用自由间距来增强可读性.
在我们介绍计数机制之前,我们需要对模式进行一次修改.目前,超前是在+重复"循环"之外.这是好的,到目前为止,因为我们只是想断言,有一个b+跟随我们的a+,但我们有什么真正希望最终做的是断言,每个a我们的"循环"内部匹配,有一个对应的b去用它.
我们现在不用担心计数机制,只需按以下方式进行重构:
a+,以(?: a )+(注意,(?:…)是一个非捕获组)a*才能"看到" b+,因此请相应地修改模式所以我们现在有以下内容:
$r3 = '/ ^ (?: a (?= a* (b+) ) )+ /x';
# ? ? ???? ? ?
# ? ? 1 ? ?
# ? ????????????? ?
# ? lookahead ?
# ?????????????????????
# non-capturing group
输出与之前相同(如ideone.com上所示),因此在这方面没有变化.重要的是,现在我们在"循环"的每次迭代中都进行断言+.使用我们当前的模式,这不是必需的,但接下来我们将使用自引用使组1"计数".
课程:您可以在非捕获组内捕获.外观可以重复.
这就是我们要做的事情:我们将重写组1,以便:
+时,当第一次a匹配时,它应该捕获ba匹配时,它应该捕获bbbbbb可以捕获到第1组,那么断言就会失败因此,现在的第1组(b+)必须被重写为类似的东西(\1 b).也就是说,我们尝试将"添加"a添加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....
A-HA!看起来我们现在非常接近解决方案!我们设法使用自我引用让第1组"计数"!但是等等......第二个和最后一个测试用例出了问题!没有足够的bs,不知怎的,它错了!我们将在下一步中研究为什么会发生这种情况.
课程:"初始化"自引用组的一种方法是使自引用匹配可选.
问题在于,由于我们将自引用匹配作为可选项,因此当没有足够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
A-HA!在我们的第四次迭代中,我们仍然可以匹配\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!!!
瞧!问题解决了!!!我们正在按照我们想要的方式正确计数!
课程:了解贪婪,不情愿和占有欲重复之间的区别.可选占有可以是一个强大的组合.
所以我们现在所拥有的是一个a重复匹配的模式,并且对于每个匹配的模式,在组1中a都有相应的b捕获.+当没有更多时a,或者如果断言失败,因为没有相应的b,则终止一个a.
为了完成这项工作,我们只需要附加到我们的模式\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,和一个5000 b 5000.在ideone.com上运行只需0.06秒.
因此该模式适用于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*在前瞻中,实际上是"主+循环",都允许回溯.鼓励读者确认为什么这不是正确性方面的问题,以及为什么同时使两者都具有占有性也会起作用(尽管在相同的模式中混合强制性和非强制性占有量词可能会导致误解).
还应该说,尽管有一个与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上所示):
$rRecursive = '/ ^ (a (?1)? b) $ /x';
目前Java的正则表达式不支持递归模式.
因此,我们已经看到了如何匹配一个ñ b ñ这是不正规,但还是上下文,但我们也匹配一个ñ b ñ ç ñ,这甚至不是上下文无关？
当然,答案是肯定的!我们鼓励读者自己尝试解决这个问题,但下面提供了解决方案(在ideone.com上使用Java实现).
^ (?: a (?= a* (\1?+ b) b* (\2?+ c) ) )+ \1 \2 $
jay*_*tea 20
鉴于没有提到支持递归模式的PCRE,我只想指出描述所讨论语言的最简单,最有效的PCRE示例:
/^(a(?1)?b)$/
ken*_*ytm 11
正如问题中所提到的 - 使用.NET平衡组,类型a n b n c n d n ... z n的模式可以很容易地匹配
^
(?<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
| 归档时间： |
|
| 查看次数： |
11202 次 |
| 最近记录： |