In practice, most regular expressions contain some literal strings. You can use Boyer-Moore to anchor the match, then do a full regexp match from there.
..and the classical answer to implementing full Regex is finite state automaton, correct? At least, there is a one to one correspondence.
I'm curious, though, about what tricks are used in actual implementations to speed things up, and what modern Regex features necessitate climbing further up the Chomsky Hierarchy. (I seem to recall reading about features getting slipped into Regex engines that made them no longer finite state, but can't recall what they were, right now.)
Check out Shift-Or: used in agrep, and another example of a very clever algorithm. Rather than translating a non-deterministic finite state automata to a deterministic one, it uses the boolean operations of the hardware to simulate the NFA directly. Result: linear time regexp for patterns that have less than the bit-length of a machine's registers. I.e., 32 bytes on x86, 64 bytes on x86_64, etc.
Comments
In practice, most regular expressions contain some literal strings. You can use Boyer-Moore to anchor the match, then do a full regexp match from there.
..and the classical answer to implementing full Regex is finite state automaton, correct? At least, there is a one to one correspondence.
I'm curious, though, about what tricks are used in actual implementations to speed things up, and what modern Regex features necessitate climbing further up the Chomsky Hierarchy. (I seem to recall reading about features getting slipped into Regex engines that made them no longer finite state, but can't recall what they were, right now.)
http://en.wikipedia.org/wiki/Shift-or
Check out Shift-Or: used in agrep, and another example of a very clever algorithm. Rather than translating a non-deterministic finite state automata to a deterministic one, it uses the boolean operations of the hardware to simulate the NFA directly. Result: linear time regexp for patterns that have less than the bit-length of a machine's registers. I.e., 32 bytes on x86, 64 bytes on x86_64, etc.
Back-references are the most common feature in regexp engines that make them non-regular.