A regular expression matcher By Rob Pike and Brian Kernighan (2007)

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

by sid6376 • 13 years ago

96 45 13 years ago

cs.princeton.edu

pdog• 13 years ago

Altough performance isn't really part of this exercise, beautiful code is also likely to be fast -- efficiently doing the work to solve the problem and no more.

lmm• 13 years ago

Not always true, e.g. brute force searching can often look more beautiful than more sophisticated techniques. The article mentions how performance could be improved by separating compilation and execution of the regular expression (as most "real" regex libraries do) - but this would almost certainly make it less beautiful.

nrbafna2• 13 years ago

On a unrelated note.

Adding a few lines of css (setting body width, font-size to 16, line-height to 1.4, Georgia for font and larger font size for headings ) makes for a decent reading experience.

http://imgur.com/a/KtaEC/

nodesocket• 13 years ago

My recommendations, for a more pleasurable reading experience:

    body {
      width: 70%;
      font-size: 20px;
      margin: auto;
      font-family: sans-serif;
      line-height: 30px;
    }

huhtenberg4• 13 years ago

Pedantic nitpick incoming

Sans-serifs are generally harder to read. Note, for example, how virtually all books are set in serifs. The primary reason sans-serifs are widely used in computers is the lack of decent display resolution required to display the actual serifs. So if you are using a larger font size to read something off the screen, there is no reason not to use a serifed typeface.

paulnechifor• 13 years ago

I think `width: 70%;` is a bad idea. If you have a very wide screen, 70% of it is too much and on a mobile device you don't want to waste 30%.

afandian• 13 years ago

Or just resize your window and increase the font size.

jamesrcole• 13 years ago

Yes, though it's slightly more complex than that: if you've got multiple tabs open, you'll probably want to resize the window again to view the other tabs, and (at least in Chrome) if you open a new tab or window it'll also have that increased font-size which you'll have to decrease again.

nrbafna2• 13 years ago

It does work as a one time thing.

But, having an extension like Stylebot installed and using a tiny custom CSS does offer an advantage - the CSS applies across the domain and takes effect every time the page is loaded.

For example, see this gallery - http://imgur.com/a/MxFtD

nilkn2• 13 years ago

I was once asked in an interview to write a pattern matcher in C for the exact same class of regular expressions as in this post. I'm pretty sure the interviewer was looking for exactly the approach used here as well.

minikomi• 13 years ago

On a related note, Rob Pike's "Lexical Scanning in Go" talk is also worth a look https://cuddle.googlecode.com/hg/talk/lex.html#landing-slide

sid6376• 13 years ago

For those unfamiliar with pointer arithmetic I wrote a python port here. https://gist.github.com/siddharthsarda/5538928

mixedbit• 13 years ago

Be aware that this isn't an equivalent of the C code. Replacing pointer arithmetic with string copy increases big O complexity of the algorithm.

An equivalent would need to pass indexes to sub functions to avoid additional copies.

stiff• 13 years ago

There is a lovely description of the classic Thompson algorithm of building an NFA from a regular expression and then simulating the NFA with a DFA using two stacks :) in the "Compilers" book by Aho et al. There is also a great article from Russ Cox on it: http://swtch.com/~rsc/regexp/regexp1.html

I recommend implementing this as an exercise, rarely do you see that much classic CS theory put to a practical use in one place.

jonny_eh• 13 years ago

I wonder if this would be a good test to give a software developer candidate. Develop a regex matcher that matches a subset of the regex rules in your language of choice (without using regex abilities, of course).

dreen• 13 years ago

I don't know, regexes have a lot of rules so you need to supply a reference, requiring them to remember it is overkill, not to mention some of those rules are pretty arcane.

barrkel• 13 years ago

A simple implementation of ?, +, * , [] and non-capturing, precedence-only () hardly needs a reference. Whether greedy vs non-greedy + / * are implemented doesn't really matter.

I will say that the problem is much easier if you have a good grounding in the basics of compilers, while that knowledge is not hugely useful very often. Any positive value as a test will come from correlation with interest in CS IMO.

jemfinch• 13 years ago

I've asked it as an interview question many times; it works really well.

The only bad part is that most candidates can't even write a correct strstr(3), so it becomes incredibly depressing.

abecedarius2• 13 years ago

https://github.com/darius/ung/blob/master/c/regexpoid.c was my solution; it handles a slightly more useful subset (including escaping) and saves some code by calling segment_matches at the top level.

(I'd seen Pike's code years before in _The Practice of Programming_, so it's not independent.)

erre2• 13 years ago

For those who don't know, this is Rob Pike's chapter of Beautiful Code, a thoroughly enjoyable book: http://www.amazon.co.uk/Beautiful-Code-Leading-Programmers-P... . Every now and then I read a different chapter, and it's always interesting. I particularly liked Rob Pike's one, and the one about Python's dictionary implementation.

bcantrill• 13 years ago

This code is beautiful, but it's also busted [1] -- albeit only for extraordinarily pathological input. As to whether this ultimately dents its beauty is up to the beholder, presumably; for me personally, I confess to suffer from a utilitarian sense of beauty when it comes to software -- for me, broken code can't achieve absolute beauty.

[1] http://dtrace.org/blogs/bmc/2007/07/11/beautiful-code/

agentS• 13 years ago

I believe Kernighan acknowledged that: "[snip] The depth of recursion is no more than the length of the pattern, which in normal use is quite short, so there is no danger of running out of space. [/snip]".

If you're going to judge this code based on both pathological haystacks but also pathological needle regexs, then you have to admit that this code, which has linear space usage in the pattern length is far better than PCRE, which has exponential time in the pattern length[1].

Considering its succinctness, I find that pretty impressive.

[1] http://swtch.com/~rsc/regexp/regexp1.html

erre2• 13 years ago

Ah, and Jon Bentley's chapter about quicksort, along whose lines there's a (also very interesting) Google Tech Talk: http://www.youtube.com/watch?v=aMnn0Jq0J-E

b0rsuk2• 13 years ago

Great code is often deceptively simple. It can lead you to believe it was simple to write.

toolslive2• 13 years ago

I saw this in a drdobbs article in the 90s as well.

toolslive2• 13 years ago

april 1999: http://www.drdobbs.com/architecture-and-design/regular-expre...

McUsr• 13 years ago

Thanks for posting this, and thanks to the OP for posting the link as well. :) I must shamefully admit that I haven't read the book, but it is now on top of my reading list!

This was really a most pleasurable and insightful read. True elegance!

porlw• 13 years ago

It's interesting that this is in a very functional style, no global state is used.

chollida1• 13 years ago

Can someone explain to me why the matchstar function takes its first param as an integer? to me it should be a char.

    int matchstar(int c, char *regexp, char *text)
    {
        do {    /* a * matches zero or more instances */
            if (matchhere(regexp, text))
                return 1;
        } while (*text != '\0' && (*text++ == c || c == '.'));
        return 0;
    }

deweerdt• 13 years ago

It doesn't seem to make sense in this context. One hypothesis is that it could have been done out of habit to write safer code: whether char is signed or unsigned is left to the implementation, whereas int is guaranteed to be signed.

abecedarius2• 13 years ago

The usual reason is to allow c to be EOF, but I don't see why anyone would in this case.

nilkn2• 13 years ago

I translated this into Haskell just for fun.

    match :: String -> String -> Bool
    match ('^':rest) text     = matchLocal rest text
    match rex        (c:rest) = matchLocal rex (c:rest) || match rex rest
    match _          _        = False
 
    matchLocal :: String -> String -> Bool
    matchLocal []            _         = True
    matchLocal "$"           []        = True
    matchLocal (c:'*':restR) (t:restT) = c == t && matchLocal restR (starSkip c (t:restT))
    matchLocal (r:restR)     (t:restT) = (r == '.' || r == t) && matchLocal restR restT
    matchLocal _             _         = False
 
    starSkip :: Char -> String -> String
    starSkip c (t:rest) = if c == t then starSkip c rest else t:rest
    starSkip _ []       = []

A regular expression matcher By Rob Pike and Brian Kernighan (2007)

Related Stories