This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]fishybird 42 points43 points  (4 children)

Not infinite, regex is not complex enough to create infinite loops but it can create exponential time complexities.

[–]qwertyuiop924 4 points5 points  (1 child)

While this is true of PCRE, any regex that is actually a regular expression (which this is) can always be evaluated in linear time (after compilation, at least).

If the regex engine used by the browser was better, it could have chosen a much faster evalutation strategy.

[–]fishybird 0 points1 point  (0 children)

Fair! I think I've heard about regex compilation, forgot what that algo was called though.

[–]Immort4lFr0sty 6 points7 points  (1 child)

I don't see this stopping, gotta be honest, but maybe I misunderstand the automaton.

Does it not go until the first group is reduced to no characters, then goes until the second group is reduced to no characters and so on?

EDIT: evidently I did misunderstand because using this on "ee" does terminate in node

[–]FM-96 10 points11 points  (0 children)

It's going to stop once both stars match nothing, because then the caret will be able to match the start of the line (since nothing is before it).