A Regular Expression Matcher (2007)

> extending this implementation

The exercises at the end of the chapter ask the student to extension the implementation along these lines. Including support for utf8.

> exponential nature

Both the essay and the book highlight this issue. The latter comments that some commercial greps (at the time) also had exponential behavior. https://archive.org/details/practiceofprogra0000kern/page/22...

If we're trying to measure code complexity I think we have to ask "complexity to whom". If it's to humans, we should measure the code as it appears to humans. If it's to machines, then "line" is meaningless and we should look at tokens, the way PG suggested years ago.

    #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;
    }