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

[Hans Åberg]

> On 4 May 2018, at 00:27, Tim Shen <timshen@google.com> wrote:
> 
> I'm not yet convinced that there is efficient way to implement the NFA
> modification approach, not efficient enough to fix PR 85472 without
> regressing the normal cases.
> 
> Even in the DFS case, if I want to walk back the path to generate captures
> once hit a "final state" or "back-reference state", it still looks
> expensive to me. The reverse matching takes O(s.size()) amount of time, and
> I only want to do it once.

An example illustrating idea with a dynamic version of Flex start conditions: Implement the pattern ([a-c]+)x\1y\1z as
  ([a-c]+)x { s = get(\1); begin(match1); }
  <match1>sysz {...}
This corresponds to setting a final state before the first \1, inserting the match, and continue lexing with the new pattern. In Flex, this does not work as it is not possible to dynamically create a new pattern.