7 ms·

A Regular Expression Matcher (2007)

132 points by _acme 10y ago

forgotpwtomain 10y ago
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/ https://swtch.com/~rsc/regexp/
NotQuantum 10y ago
I appreciate that he acknowledges me at the end. Thanks Rob!
- f2f 10y 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 10y ago
    Exegete.
adrianratnapala 10y 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.
- asveikau 10y 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.
  - groovy2shoes 10y 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 https://en.wikipedia.org/wiki/Varint
harry8 10y 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 10y ago
  In Rust the {} are mandatory, but you don't need the (), so you can just write this: if a == b { stuff(); }
  - harry8 10y ago
    Thank $whatever for that. Go rust. Sanity prevailing.
- gfody 10y 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 10y 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.
    - eru 10y ago
tiarkrompf 10y 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 https://scala-lms.github.io/tutorials/regex.html
kchoudhu 10y 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.
brownhats 10y ago
Stack overflow
eru 10y ago
Automata make for good regular expression matchers. Another interesting approach is via derivatives: https://www.mpi-sws.org/~turon/re-deriv.pdf https://www.mpi-sws.org/~turon/re-deriv.pdf
andyzweb 10y ago
http://doc.cat-v.org/bell_labs/structural_regexps/se.pdf http://doc.cat-v.org/bell_labs/structural_regexps/se.pdf

132 points by _acme 10y ago

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/ https://swtch.com/~rsc/regexp/

NotQuantum 10y ago

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

f2f 10y 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 10y ago
  Exegete.

adrianratnapala 10y 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.

asveikau 10y 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.
- groovy2shoes 10y 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 https://en.wikipedia.org/wiki/Varint

harry8 10y 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 10y ago
In Rust the {} are mandatory, but you don't need the (), so you can just write this: if a == b { stuff(); }
- harry8 10y ago
  Thank $whatever for that. Go rust. Sanity prevailing.
gfody 10y 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 10y 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.
  - eru 10y ago

tiarkrompf 10y 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 https://scala-lms.github.io/tutorials/regex.html

kchoudhu 10y 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.

brownhats 10y ago

Stack overflow

eru 10y ago

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

andyzweb 10y ago

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