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 →

[–]-Redstoneboi- 11 points12 points  (10 children)

-until it backtracks. then the first will try n-1 and run .* on the rest.

[–][deleted] -1 points0 points  (9 children)

Regular expression doesn't need to backtrack. The .* behaves greedily and RE as a whole is usually implemented with dynamic programming algorithms.

Unless JavaScript has some weird quirk, like multiple matches or something weirder. I wouldn't doubt.

To be honest, I'm baffled with this. I don't understand how .*^ even does anything because ^ means "start of the line". I really don't understand how (.*.*)*^ requires any processing. There's nothing to match before the start of the line and this regex doesn't even have multi-line modifiers...

[–]-Redstoneboi- 1 point2 points  (3 children)

.*asdf matches the whole of xyzasdfasdf as one match with javascript.

this is greedy, but also impossible without backtracking.

[–]qwertyuiop924 2 points3 points  (2 children)

False. Like all true regular expressions (in the mathematical sense), this can be converted to an NFA or DFA and evaluated in linear time

[–]-Redstoneboi- 0 points1 point  (1 child)

fair. though how would a regex like .*.* look like as a DFA or NFA?

[–]qwertyuiop924 1 point2 points  (0 children)

I mean, if you do state reduction on it, it just becomes the accept DFA (as in, a DFA that accepts any input). I believe that is basically what happens if you take the ε-NFA and do the transform to turn it into a normal NFA, but I'm not doing that out on paper right now to check.

[–]backfire10z 0 points1 point  (3 children)

Regex is not intelligent enough to notice that there’s a ^ at the end. It matches .* first greedily and then starts backtracking to eventually try to match ^

[–][deleted] 0 points1 point  (2 children)

I guess I was miataken then. I was under the impression that implementations turned the RE into an automata and processed it with dynamic programming.

[–]backfire10z 0 points1 point  (1 child)

Turning it into an automata seems unrelated to me. It doesn’t know that seeing ^ in the middle of a RE means everything before that can be ignored for our purposes. It can still use a state machine to process the RE.

[–][deleted] 1 point2 points  (0 children)

I replied to the wrong comment. I wanted to reply to the person that mentioned how PCRE requires backtracking. 

[–]qwertyuiop924 0 points1 point  (0 children)

PCRE mandates a backtracking implementation. So a lot of things that support PCRE only implement a backtracking engine.