News for hackers. Stuff that matters.
Re:A Regular Expression Matcher (2007) by abecedarius on Thursday August 25, 2022 @09:53AM (#32593743)
Good prompt for a beautiful matcher with better complexity. Have a favorite?

https://www.oilshell.org/archive/Thompson-1968.pdf is longer and doesn't quite fix the problem (see third-to-last paragraph) but it is interesting and very tight.

Re:A Regular Expression Matcher (2007) by eutectic on Thursday August 25, 2022 @11:42AM (#32595268)
I don't know about beautiful, but I just came up with this small NFA matcher for the same problem:

    #include <stdlib.h>
    #include <string.h>

    int match(char* regex, char* text) {
        int n = strlen(regex);
        char* active = calloc(n + 1, 1);
        char* next_active = calloc(n + 1, 1);
        active[0] = 1;
        int found = 0;
        int anchor = regex[0] == '^';
        regex += anchor;
        do {
            for (int i = 0; i <= n; i++) {
                if (!active[i])
                    continue;
                if (regex[i] == '\0') {
                    found = 1;
                    goto DONE;
                } else if (regex[i + 1] == '*') {
                    next_active[i + 2] = 1;
                    if (regex[i] == '.' || regex[i] == *text)
                        next_active[i] = 1;
                } else if (regex[i] == '$' && regex[i + 1] == '\0') {
                    found = *text == '\0';
                    goto DONE;
                } else {
                    next_active[i + 1] = regex[i] == *text;
                }
            }
            char* tmp = next_active;
            next_active = active;
            active = tmp;
            active[0] = !anchor;
            memset(next_active, 0, n + 1);
        } while (*text++ != '\0');
    DONE:;
        free(active);
        free(next_active);
        return found;
    }
Re:A Regular Expression Matcher (2007) by abecedarius on Friday August 26, 2022 @10:48AM (#32608246)
Nice! I should've expected this could be that short, but I didn't.

Here's my favorite approach to "rediscovering" efficient regex matching: https://semantic-domain.blogspot.com/2013/11/antimirov-deriv... It's implicit in the Thompson paper I linked above, but imo not obvious from it.