3 ms·
Obligatory comment: Nowadays nearly nothing uses actually "regular" regexes, which is also the reason why regex engines are typically using backtracking and not
by nikic 13y ago
Obligatory comment: Nowadays nearly nothing uses actually "regular" regexes, which is also the reason why regex engines are typically using backtracking and not Thompson NFAs.
For general-purpose applications (e.g. use in programming languages) people usually want a regex flavor with support for at least backreferences and typically also (recursive) subpattern references. Note: Adding support for backreferences makes matching regexes an NP-complete problem (as opposed to a simple linear-time algorithm without them).
(But of course, having fast NFA implementations for really-regular regexes is still useful. After all a large part of the regexes you typically write will not use backreference etc)
- acdha 13y ago> Obligatory comment: Nowadays nearly nothing uses actually "regular" regexes This is only partially true: while most people use implementations which support back references, it's likely that a significant percentage of regular expressions actually executed do not use that complexity. Given the widespread use of regular expressions for input validation, log-file analysis, URL dispatching in web frameworks, etc. there's a fair chance that a majority of the regular expressions executed would benefit from this approach, particularly since it would be trivial for an engine to transparently fall down to the current implementation when it encounters a complex construct.
- nikic 13y agoNot disagreeing there. Fast NFA implementations are very nice for matching the regular subset and falling back to a more general algorithm for the non-regular cases :)
- dalke 13y agoOne of the places where you don't want backtracking is with public-facing regexp search, where specially constructed patterns from anonymous users can bog down a search. These are also cases where it's likely okay to omit back-references and the more complex options which give rise to exponential time.
- abecedarius 13y agoI guess some people do, but I don't think I've ever used backrefs outside of solving puzzles. If I want more-general parsing I reach for a PEG library like LPEG or my own Peglet.
- rames 13y agoSupport for backreferences can be added without making the whole engine backtracking. See more detailed comments at: https://plus.google.com/114767693573247408592/posts/ZeUHc7ro2h1 https://plus.google.com/114767693573247408592/posts/ZeUHc7ro... Edit: So we can keep the best of both worlds !