3 ms·
Just wanted to draw your attention to a proof of concept regex engine that I wrote a few years ago that does handle backreferences and arbitrary look around usi
by karthikj2017 9y ago
Just wanted to draw your attention to a proof of concept regex engine that I wrote a few years ago that does handle backreferences and arbitrary look around using a Thomson NFA and with no backtracking.
The point of this engine was to show that, while it seems to be commonly believed that an automata-based regex engine cannot handle backreferences and arbitrary look around, that is not entirely true. It does use a stack when it encounters backreferences though.
The source code for the regex engine is at https://github.com/karthikj1/JRegexPlus https://github.com/karthikj1/JRegexPlus and a brief explanation of how it works is at http://karthikj1.github.io/JRegexPlus/ http://karthikj1.github.io/JRegexPlus/
I would be interested to hear any thoughts on this.
- glangdale 9y agoI think the idea is interesting. I don't think most reasonable people believe that you can't handle backreferences and arbitrary lookaround in something that's largely based on automata; rather that if you're using automata you probably made the decision to use them to avoid having to allocate arbitrary amounts of memory, to "stream" or for multiple pattern support and/or performance reasons. If those criteria frame why you are using an automata to begin with, then you either (a) can't use a stack either or (b) you at least need to make a performance argument that using NFA+stack is better than a back-tracker. Arbitrary lookaround seems straightforward except in streaming mode, although efficient support for forward asserts for arbitrary regexes without "grows with the input size" side storage is IMO not trivial (it also breaks our ordering model). Backward lookaround seems easy if you are OK with adding logical AND to your NFA.