Re:A Regular Expression Matcher (2007)
by jstimpfle on Thursday February 13, 2020 @05:10PM
(#22321932)
Skimming over it, the implementation looks inefficient:
That can be used to match short strings, but not to grep through a filesystem. A good regex matcher has runtime O(N*M) where N is the length of the regex (typically very short) and M is the length of the scanned text.
[ Parent
| on HN ]
A surprising number of regex tools used in the wild employ a backtracking algorithm like this one. Some popular features such as lookaheada, lookbehinds, and backreferences can't always be matched using a finite automaton.
Re:A Regular Expression Matcher (2007)
by user2994cb on Friday February 14, 2020 @08:10AM
(#22326168)
An FSA matcher will be O(M) - one state transition per input character.