News for hackers. Stuff that matters.
Re:A Regular Expression Matcher (2007) by jstimpfle on Thursday February 13, 2020 @05:10PM (#22321932)
Skimming over it, the implementation looks inefficient:

    int matchstar(int c, char *regexp, char *text)
    {
        do {    /* a * matches zero or more instances */
            if (matchhere(regexp, text))
                return 1;
        } while (*text != '\0' && (*text++ == c || c == '.'));
        return 0;
    }
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.
Re:A Regular Expression Matcher (2007) by ufo on Thursday February 13, 2020 @06:07PM (#22322292)
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.
Re:A Regular Expression Matcher (2007) by jstimpfle on Friday February 14, 2020 @12:16PM (#22328227)
If you're looking at a specific regex (~FSA), then N is constant... If you have a function that runs an arbitrary regex, then N will vary.