How Regexes Work

This isn't an article about how to use regexes; you've probably seen plenty of those already. It's about how you would write a regex package from scratch, in a language like C that doesn't already have regexes.

I'll demonstrate a new module, Regex.pm, which implements regexes from nothing, in Perl. This will give you an idea of how regex matching is possible, although the details differ rather substantially from what Perl actually does.

Here's the basic strategy: We'll see a simple kind of `machine' that reads a input, one character at a time, and then, depending on what's in the input and on the various wheels and gears in the machine, either says `yes' or `no'. The machines are simple, and it turns out that if we have a regex, it's not hard to construct a machine that says `yes' for exactly those strings that match the regex, and `no' for other strings.