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

[Hans Åberg]

> On 3 May 2018, at 23:29, Tim Shen <timshen91@gmail.com> wrote:
> 
> 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.

It computes all final state matches. An idea was as a replacement for Flex, where the same match chooses the rule that comes first. So put in a final state at all points where matches are needed, perform some action to modify the NFA.

> 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.

That is for static algorithms. Here, partial computation is fed back and modifying the NFA, branching into multiple ones.