w.r.t. [Bug libstdc++/85472] Regex match bug

[Tim Shen]

On Thu, May 3, 2018 at 11:27 AM Hans Åberg <haberg-1@telia.com> wrote:
> Do you have a better description on how it is supposed to work.
Specifically, how do you get only an even number in this case?

Quoting [1]: When a backreference \N appears as an Atom, it matches the
same substring as what is currently stored in the N'th element of the
submatch array.

Therefore \1 always matches and only matches what (a+) captured. With the
input "aaaa", it's possible that (a+) captures "aa", and therefore \1
matches the rest "aa". With the input "aaa", this is not possible.

This feature makes the problem NP-complete [2].

> > Implementing back-reference matching requires the matches to be
> > available during the match, not after the match.

> Please illuminate this.

Following the example above, at the point when doing the "\1" state, the
algorithm has to know what "(a+)" already matched. In your description, the
first pass "merely record the DFA states", but it's not sufficient to tell
what "\1" state(s) transitions to.

back-references is rather well-known in industrial regex. I suggest you to
read related parts in [2].

[2] https://swtch.com/~rsc/regexp/regexp1.html


-- 
Regards,
Tim Shen