4 ms·

Good prompt for a beautiful matcher with better complexity. Have a favorite? https://www.oilshell.org/archive/Thompson-1968.pdf https://www.oilshell.org/archiv

Good prompt for a beautiful matcher with better complexity. Have a favorite? https://www.oilshell.org/archive/Thompson-1968.pdf 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.

eutectic 4y ago
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; }
- abecedarius 4y ago
  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-derivatives-for-regular.html 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.

eutectic 4y ago

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

abecedarius 4y ago
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-derivatives-for-regular.html 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.