Oddbean new post about | logout
▲ ▼
Julia Evans | 1 years ago (raw) | root | parent | reply | flag 
 @novalis (when I say "maintaining many parallel possibilites at a time", I'm thinking of this "Implementation: Simulating the NFA" section from https://swtch.com/~rsc/regexp/regexp1.html where he simulates an NFA using an array of states)
▲ ▼
novalis | 1 years ago (raw) | root | parent | reply | flag 
 @Julia Evans I definitely do not think of it as a NFA -- I think of it in terms of backtracking.  That happens to be how Python implements it (last time I checked).  I know that Rust and Golang use NFAs, but even there, it doesn't usually hurt to think about backtracking.
In practice, the NP thing is rarely an issue. I think I hit exponential behavior (not NP) once in the last 25 years, and I really like regexps.  Of course you have to worry about it for untrusted expressions, but that's a pretty rare case.
So, when I see something like "(ab)*abraca" matching ababababraca, I think, "so, we'll match some 'ab's, and then the last one we'll have to backtrack so we can get it to part of 'abraca'. (Actually, I think "let me rewrite that as (ab)+raca", but it's just an example).
▲ ▼
Julia Evans | 1 years ago (raw) | root | parent | reply | flag 
 @novalis that makes sense thanks -- thinking about it in terms of backtracking seems much more realistic