This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: w.r.t. [Bug libstdc++/85472] Regex match bug
On Thu, May 3, 2018 at 3:05 PM Hans Åberg <haberg-1@telia.com> wrote:
> 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.
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.
It's indeed O(s.size()) if no back-references are included, we will do it
for once at the end (as you suggested). It's also fine (from efficiency's
perspective) if we leave the bug as it is, since all captures updates are
amortized in _M_handle_subexpr_begin and _M_handle_subexpr_end.
--
Regards,
Tim Shen