回溯一个均衡组中一个贪婪的重复可能导致失衡? [英] Backtracking a balancing group in a greedy repetition may cause imbalance?
问题描述
作为一般酿造例如对于这个问题的目的,我的目的是要匹配 A
的,那么同样数量的 B
的,再加上多了一个 B
。
As a generically brewed example for the purpose of this question, my intent is to match some number of a
's, then an equal number of b
's, plus one more b
.
检查两种模式呈现在这个片段(也ideone.com ):
Examine the two patterns exhibited in this snippet (also on ideone.com):
var r1 = new Regex(@"(?xn)
(?<A> a)+ (?<B-A> b)+ (?(A)(?!)) b
");
var r2 = new Regex(@"(?xn)
(?<A> a)+ (?<B-A> b)+? (?(A)(?!)) b
");
Console.WriteLine(r1.Match("aaabbb"));
// aaabbb
Console.WriteLine(r2.Match("aaabbb"));
// aabbb
请注意,有在两个图案的匹配的差。 R1
,它使用一个贪婪的重复的均衡组结构,匹配3 A
的3 B
的,这是的不是的预期效果。 R2
,它使用一个不愿意重复,给了我2 A
的3 B
的,它的是的预期效果。
Note that there is a difference in the matches of the two patterns. r1
, which uses a greedy repetition on the balancing group construct, matches 3 a
's and 3 b
's, which is NOT as intended. r2
, which uses a reluctant repetition, gives me 2 a
's and 3 b
's, which IS as intended.
我可以解释这一点的唯一方法是,当(LT; B-A&GT; B)+
回溯匹配少了一个 B
,它会弹出从 B
叠,而不的推背什么也相应地从弹出的 A
堆栈。因此,即使少了一个 B
现在由于回溯匹配,则 A
栈是空的。这是我可以解释如何 R1
可以匹配的唯一途径 AAABBB
。
The only way I can explain this is that when (?<B-A> b)+
backtracks to match one less b
, it pops from the B
stack but DOES NOT push back what was correspondingly popped from the A
stack. Thus, even though one less b
is now matched due to backtracking, the A
stack remains empty. This is the only way I can explain how r1
can match aaabbb
.
请注意,使用不愿意 +
在 R2
不会导致此问题。我看到它的方式,这是因为不像贪婪的重复,一个不愿意重复不具备撤消损害对 A
栈,所以到说话。相比之下,贪婪的重复使得尽可能多的损害成为可能,但回溯没有留下的东西,因为他们对 A
堆栈。
Note that using reluctant +?
in r2
doesn't cause this problem. The way I see it, this is because unlike greedy repetition, a reluctant repetition doesn't have to "undo the damage" to the A
stack, so-to-speak. By contrast, the greedy repetition causes as much "damage" as possible, but the backtracking fails to "leave things as they were" to the A
stack.
这是发生了什么正确的分析?如果是的话,是由设计这种行为?因为它基本上看起来像我的是,回溯一个均衡组中一个贪婪的重复可能导致失衡,因此这可能被归类为一个错误(或者至少是一个被充分证明有些令人惊讶的行为)。
Is this a correct analysis of what happened? And if so, is this behavior by design? Because what it basically looks like to me is that backtracking a balancing group in a greedy repetition may cause imbalance, and thus this could potentially be categorized as a bug (or at the very least a somewhat astonishing behavior that is inadequately documented).
推荐答案
这是一个错误在单声道。
为什么人们越来越.NET类 Environment.Version
上IdeOne的原因是与.NET的向后兼容性,包括与该承担的基础上决定应用程序的兼容性的单要求该框架的版本。
The reason why people are getting .NET-like Environment.Version
on IdeOne is Mono requirement of backward compatibility with .NET, including compatibility with applications that take decisions based on the framework version.
这篇关于回溯一个均衡组中一个贪婪的重复可能导致失衡?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!