A Regular Expression Matcher (2007)

http://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html

by _acme • 10 years ago

132 34 10 years ago

cs.princeton.edu

I have a re.c file in my best-of collection of code examples locally - but I can't seem to find the original source quickly - nevertheless it was written by Russ Cox[0] and he's spent a lot of time making regular expressions accessible and elegant, his articles are a great resource.

[0] https://swtch.com/~rsc/regexp/

NotQuantum• 10 years ago

I appreciate that he acknowledges me at the end. Thanks Rob!

f2f• 10 years ago

it's brian who acknowledged you. rob only wrote the code.

exegesis is a nice word to have in one's vocabulary. brian is a good exegesist (or is that exegesisticist?)

gpvos• 10 years ago

Exegete.

adrianratnapala3• 10 years ago

I'm impressed.

The code lives up to its goal of being a good example of programming. As Kernighan says, it shows the value of handling special cases early and of recursion. (It's also a good example of how pointer-arithmetic and nul-terminated strings should be used, but the less said about that, the better).

Students are likely to not notice the tail recursion, so converting this to an iterative version is probably a nice exercise.

But notice that explaining regexps is a non-goal of this example. There is an underlying state-machine here (encoded in a combination of the instruction pointer and the `text` variable), but it is not very obvious. For that, Russ Cox' articles are the go-to.

asveikau2• 10 years ago

(It's also a good example of how pointer-arithmetic and nul-terminated strings should be used, but the less said about that, the better).

Why the less said the better?

I'm always disappointed when people say C is bad at string manipulation. The "character at a time, no allocations needed, stop when you hit the end" style demonstrated here and elsewhere have always resonated deeply with me.

adrianratnapala3• 10 years ago

Roghly speaking, I don't want to start a flame war by defending pointer-arith. The haters are right that languages could use other, safer features (like array slicing).

But if it is how your language does things, then use it, and use it well -- as in this example. Also I find counted strings preferable for most tasks, but nul-terminated have the advantage of working so nicely with the ptr++ operation.

There was real insight behind C's minimalistic string handling. And C's minimalism is has always been its best feature. But today's minimal languages should support strings explicitly.

groovy2shoes7• 10 years ago

I'm always disappointed when people say C is bad at string manipulation. The "character at a time, no allocations needed, stop when you hit the end" style demonstrated here and elsewhere have always resonated deeply with me.

The main reason is that C doesn't really offer many primitives for string manipulation beyond pointer manipulation. All you really get is the stuff in `string.h`, which isn't much, and most of those functions are deeply flawed in one way or another:

* strcpy() can easily lead to buffer overflows if the destination array is not large enough to hold the entire string

* strncpy() will not nul-terminate the destination string if the size of the source string exceeds n

* ditto for strcat()/strncat()

* strtok() is not re-entrant, and therefore not thread-safe. The C11 standard is explicit that strtok() is not required to avoid data races with other calls to the function.

* You're not allowed to modify the result of strerror(), yet the function returns a regular ol' char* and, as such, the type system can't prevent anyone from doing so.

And perhaps the biggest problem of them all:

* strlen() potentially diverges (i.e., it can loop indefinitely or overflow the buffer, which causes undefined behavior[0]), making it literally impossible to reliably validate a C string in standard C without knowing the length of that string a priori. It is also the case that the length of a string is not necessarily equal to the size of the buffer it is stored in, which means you now potentially have a third thing you need to know a priori (the buffer size).

The small size of C's string library means you get to roll a lot of your own string functions, including the kinds of primitives you'd expect. Even QBasic has a larger (and arguably better) string library. Alternatively, you can just forgo the functions and write loops through strings everywhere, but then as soon as you want to support some other character encoding (or multiple character encodings), you're in for a boatload of fixes throughout your codebase.

The nature of C strings being represented as arrays of characters rather than an abstract string type means that it brings you the joy of manual memory management everywhere. You need to constantly be allocating space for strings, deallocating buffers, keeping track of ownership, copying strings between buffers, etc. Of course, since the length of the string isn't included in the string itself, if you want to use the safe string-handling functions, you need to keep track of the lengths separately. This usually means returning a `size_t` for the length of the string, while the output of the string functions goes to a pointer ("sorta pass-by-reference") "out" parameter.

Strings that rely on sentinel values are themselves pretty flawed. Continuing the note above, it's safer and more convenient to use strings that are somehow bundled with their length. With sentinels only, reasonable things like nul-padding the strings for alignment purposes can also be a pain in the ass, since C considers the end of the string to be the first nul character it encounters. An abstract string type would allow you to store the length of the string and the size of the buffer in the same package as the pointer to the buffer (and possibly even the buffer itself). This can have advantages other than easier handling of padding as well, allowing you to grow or shrink the string within the same buffer without (re)allocating memory and can potentially save some copying. If you can sacrifice a byte, you can retain interoperability with functions expecting C-style strings while enabling better string handling by including the nul-terminator in addition to bundled the length (Lua does this, for example). A common complaint is that this places an upper bound on the length of a string, whereas a sole sentinel value does not. This does not have to be the case if a varint[1] is used to hold the length.

C strings are also woefully inadequate for dealing with character encodings larger than 8 bits, but that's another can of worms.

In short, C's standard strings are fine, really, but they could be so much better with a touch of abstraction. Fortunately, it's possible to make some improvements from within C itself, but unfortunately that's often a mild pain in the ass, and not all programmers bother to do it.

---

[0]: Of course, once your program enters undefined-behavior territory, it's off the chain and can do anything it wants, regardless of what you intended it to do, even if your program is 100% correct in cases where there is no undefined behavior.

If you're lucky, a buffer overflow will cause the program to crash and die immediately, due to segfault or something. If you're unlucky, it'll go haywire and run amok. If you're really unlucky, it'll continue to operate with no outward signs of problems, silently doing something horrible and nasty without any indication to the contrary.

[1] https://en.wikipedia.org/wiki/Varint

harry83• 10 years ago

I found I didn't hate, loathe and detest unbraced blocks any less when it's Rob Pike code

    if(x) {
        do_y();}

2 characters, no vertical space difference. Unbraced blocks only feature is they introduce bugs - they have no legitimate use. But man do you feel like a tough, macho-man "I'm such a hard man I leave my blocks un-braced."

Is there a list of languages that repeated this C idiocy (an optimization of syntax for the parser rather than the programmers?) I sure hope those languages that would like to replace C, ie D, go, Rust etc. Haven't repeated it this far into the 21st century.

FreeFull• 10 years ago

In Rust the {} are mandatory, but you don't need the (), so you can just write this:

    if a == b {
        stuff();
    }

harry83• 10 years ago

Thank $whatever for that. Go rust. Sanity prevailing.

gfody• 10 years ago

I keep one-line blocks unbraced when possible and my reasoning is definitely not to feel like a tough macho man. It's more like a mild form of OCD where any syntax that's not necessary just bothers me if I don't omit it.

jake-low• 10 years ago

Reductio ad absurdum: I assume your variable names are single-letter, your Python is indented only one space per block level and every C program is a one-liner? You should check out the Code Golf stackexchange; you'd do well.

Kidding aside, I can appreciate your feeling of OCD (I fight that urge too) but remember that most syntax is for humans, not machines. Using braces communicates intent to the reader; omitting them offers an opportunity to stumble.

gmac• 10 years ago

I'm with you on that.

The one line version isn't prone to goto fail, and to me reads very nicely.

    if (x == 1) return;

The two line version, however, I avoid like the plague.

    if (x == 1)
        return;

adrianratnapala3• 10 years ago

I use unbraced blocks as an unwise habit brought over from Pascal, which I learned before C.

I think of these things not as "blocks" but as "statements" -- those can be sandwiched between begin/end or else be one-liners. Pretending that one-liners aren't statements doesn't make any sense at all.

The rules of C are the same -- except it doesn't work as well in practice. Because (1) explicit `{...}` in a one-liner is far less painful than explicit `begin...end`. (2) errors caused by a missing `{`, `}` are harder to spot than errors caused by missing `begin`, `end`.

That said, the best syntax I know of for this is indentation based -- then the whole issue just goes away.

taeric• 10 years ago

I hate to be that person, but your extra two characters version is only slightly less prone to errors than the one that you are replacing. At the very least, if you are going to insist that these be required, the closing has to be on its own line, or you lose much of the benefit.

And, while I do agree it is easy to vilify this style of statement, I question hating on it. I have found reading code like this is somewhat easy to read if you have internalized reading it to be "if this, then do a single thing." Where the "a single thing" is different from the normal reading of "if this, then that."

Still, I support style guides that prohibit this.

harry83• 10 years ago

Much to easy to read over, much less likely to get syntax errors on a merge tool mistake, internalise all you like to make fewer mistakes and still don't do it and there will be fewer mistakes. Even if you're so amazing you could never make that mistake yourself a future maintainer might, a tool might and your benefit for taking that risk is zero.

I hate it because it's just so silly. Do we use a feature that has no benefit and carries risk? Do we really need a statistical analysis for this one?

lmm• 10 years ago

Syntactic noise matters. You don't notice how much it costs until you're used to a lots-of-small-functions style in a language where that's possible.

I prefer consistency in the opposite direction, like I have in Scala: all constructs can be written as expressions. Function body? Expression. Try/catch body? Expression. Loop body? Expression. If you want to put a bunch of statements in rather than an expression, then you put them in braces. (But most of the time there's a better way to express what you wanted).

tiarkrompf• 10 years ago

It's a nice piece of code. I like to use it to explain how to turn interpreters into compilers through staging/specialization: https://scala-lms.github.io/tutorials/regex.html

kchoudhu• 10 years ago

I got the guided tour of this code from bwk back in... 2006?[1]

I wasn't sure I wanted to deal with computers on a day to day basis when I took the course. The lecture blew my mind, and I started looking for programming jobs the next day.

[1] COS333. Memories... man, I'm getting old.

eru2• 10 years ago

Automata make for good regular expression matchers. Another interesting approach is via derivatives: https://www.mpi-sws.org/~turon/re-deriv.pdf

andyzweb• 10 years ago

http://doc.cat-v.org/bell_labs/structural_regexps/se.pdf

A Regular Expression Matcher (2007)

Related Stories