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

[Tim Shen]

On Thu, May 3, 2018 at 1:29 PM, Hans Åberg <haberg-1@telia.com> wrote:
>
>> On 3 May 2018, at 20:42, Tim Shen <timshen91@gmail.com> wrote:
>>
>> ... \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.
>
>>>> 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.
>
> This might be implemented by inserting a final state state after (a+), as my implementation computes the matches when a final state appears.

Except it really isn't "final". For example, "(a+)\1\1" matches number
of 'a's that's a multiple of 3.

The NFA/DFA-based algorithm wouldn't work, as they are guaranteed
polynomial. On the other hand, regex with back-references is proved to
be NP-complete.


-- 
Regards,
Tim Shen