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

[Hans Åberg]

> On 3 May 2018, at 02:39, Tim Shen <timshen91@gmail.com> wrote:
> 
> Hi Hans, this is Tim from libstdc++.
> 
> I'm moving the conversation off the bug since it's already long, and has a low information density. I'll post a summary of the continued conversation. I'm not sure if you think it's a good idea?

I am cc-ing to the libstdc++ list, so others interested can follow. But get back if you want more info.

> I'm very interested in your algorithm that fixes the bug, but I'm not able to comprehend it. In the discussion, I often understand more on examples, but less on the algorithm itself. Unfortunately the example themselves don't explain the algorithm.
> 
> If you are happy and have time, perhaps you can start describing how you implemented the NFA matching algorithm?

The DFA algorithm departs from one in the book by Aho, Sethi & Ullman, "Compilers", sec. 3.9, subsection "From a Regular Expression to a DFA", only that I start with a NFA without empty transitions. One moves over sets of NFA states p, and there is a function q = follow(p, c) that computes the next sets of NFA states q, by simply tracing all the c transitions in all the states of p. If there are empty transitions, those must be traced, so not having them simplifies the computations.

Now, when follow(p, c) computes q, the reverse NFA information that I use is available: It records all the c transitions  found p_i -> q_j, but in reverse form q_j -> p_i, as sets q_j -> p' where p'. For use with a DFA, I record the data for a lookup on the (p, c) pair.

The DFA lexes forward until a final states is encountered; merely record the DFA states. Then starting with this final state and the last matched character, I work the matched string backwards on the reverse NFA data for each DFA state used to compute the sets of states involved.

So in effect, I extract by that the NFA that the lexing match uses, and nothing else: The NFA transitions can be computed from the states and the characters.

> From my understanding it can be a depth-first-search algorithm. I have a talk about this: https://www.youtube.com/watch?v=N_rkHzhXueo.

So the matching does not do any tree search at all.