3 ms·
Is this implementation close to the theoretical concept of regular expressions? I have read that some implementations of regular expressions are quite a bit mor
by Dewie 13y ago
Is this implementation close to the theoretical concept of regular expressions? I have read that some implementations of regular expressions are quite a bit more powerful than regular expressions from CS, in that they can recognize languages that are not regular.
- burntsushi 13y agoYes. It's a reasonably faithful port of RE2, which elides features like backreferences.
- pjscott 13y agoThis is usually a small price to pay for guaranteed O(n) matching speed. (Kudos to the author for doing the Right Thing here.)
- burntsushi 13y agoThanks :-) The implementation is basically the Pike VM as described by Russ Cox. Recursion depth in particular has an upper bound corresponding to the number of instructions in the regex. In practice, this means it's safe to run a regex on untrusted data. (Creating a regex from untrusted data still needs a bit of work, but is fixable!)