https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #22 from Hans Åberg ---
(In reply to Tim Shen from comment #16)
> ...I meant to observe whether the example triggers a O(k^2) behavior. It
> should be less than quadratic. ...
> Here is the updated example, to re-arrange the
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #21 from Hans Åberg ---
(In reply to Tim Shen from comment #20)
> (In reply to Hans Åberg from comment #18)
> > (In reply to Tim Shen from comment #14)
> > > I have a C++ test case for this:
> >
> > I get segmentation fault on the
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #19 from Hans Åberg ---
(In reply to Tim Shen from comment #16)
> I set (kStart, kEnd) to be (1000, 2000), (1000, 3000), ..., (1000, 9000) to
> see how the time grows. ...
> Here are my numbers for end ranging 2000 to 9000, in ms:
>
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #18 from Hans Åberg ---
(In reply to Tim Shen from comment #14)
> I have a C++ test case for this:
I get segmentation fault on the regex_match line with g++ 7.3.0.
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #17 from Hans Åberg ---
(In reply to Tim Shen from comment #16)
> (In reply to Hans Åberg from comment #15)
> > (In reply to Tim Shen from comment #14)
> > > How fast does your prototype run on the following example?
> > >
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #15 from Hans Åberg ---
(In reply to Tim Shen from comment #14)
> How fast does your prototype run on the following example?
> ((10)|(11)|(12)|...|(98)|(99))* matching "10111213141516...9899"
> how about this:
>
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #13 from Hans Åberg ---
(In reply to Tim Shen from comment #11)
> If you think it's time and space efficiently doable, maybe you can develop a
> prototype first.
I put action number lists on the NFA transitions (no markup of the
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #12 from Hans Åberg ---
(In reply to Tim Shen from comment #11)
> > The problem is that #4 has an earlier capture, making it impossible to see
> > that it is left undefined later.
>
> I wouldn't say it's impossible. libc++
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #10 from Hans Åberg ---
(In reply to Tim Shen from comment #9)
> Ah with the example it's clear, thanks!
You are welcome.
> > The last line gives for #1 the sub-string "z" , and for #2 "aacbbbcac".
>
> This is not what ECMAScript
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #8 from Hans Åberg ---
(In reply to Tim Shen from comment #5)
> I'm not following the meaning of "action number" and "the partial reverse
> NFA is recorded".
>
> How many actions numbers are recorded? for regex_match(s, regex(re)),
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #7 from Hans Åberg ---
(In reply to Tim Shen from comment #5)
> (In reply to Hans Åberg from comment #4)
> > I wrote an NFA/DFA that computes all matches, it seems, in an efficient
> > manner: Action numbers are marked on the states
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #6 from Hans Åberg ---
(In reply to Tim Shen from comment #5)
> (In reply to Hans Åberg from comment #4)
> > I wrote an NFA/DFA that computes all matches, it seems, in an efficient
> > manner: Action numbers are marked on the states
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #4 from Hans Åberg ---
(In reply to Tim Shen from comment #1)
> I know exactly how libc++ produces this result. It creates an empty
> match_result during each repetition ("*" operator). It's less confusing but
> much slower.
I wrote
: unassigned at gcc dot gnu.org
Reporter: haberg-1 at telia dot com
Target Milestone: ---
Created attachment 43993
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=43993=edit
The regex example mentioned in the report.
In the regex "(z)((a+)?(b+)?(c))*" example at [1], also atta
14 matches
Mail list logo
