12 ms·
A regular expression matcher By Rob Pike and Brian Kernighan (2007)
- minikomi 13y agoOn 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 https://cuddle.googlecode.com/hg/talk/lex.html#landing-slide
- pdog 13y agoAltough 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 13y agoNot 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.
- nrbafna 13y agoOn 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/ http://imgur.com/a/KtaEC/
- afandian 13y agoOr just resize your window and increase the font size.
- jamesrcole 13y agoYes, 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.
- nrbafna 13y agoIt 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 http://imgur.com/a/MxFtD
- nodesocket 13y agoMy recommendations, for a more pleasurable reading experience: body { width: 70%; font-size: 20px; margin: auto; font-family: sans-serif; line-height: 30px; }
- huhtenberg 13y agoPedantic 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.
- gliptic 13y agoThis might very well be a myth. See e.g. http://alexpoole.info/blog/which-are-more-legible-serif-or-sans-serif-typefaces/#part2 http://alexpoole.info/blog/which-are-more-legible-serif-or-s....
- huhtenberg 13y agoEverything that has to do with the perception might very well be a myth :) However, in typography and type designer circles it is commonly accepted that Serifs are superior for consuming large quantities of text. Also in layman terms - serifs make the glyphs more distinct and easier to recognize at a glance, in contrast to the sans where there are several glyph pairs that look virtually the same.
- dpark 13y ago"Commonly accepted" isn't worth much when it conflicts with actual science. Lots of things commonly accepted are simply incorrect.
- huhtenberg 13y ago
- nilkn 13y agoI 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.
- sid6376 13y agoFor those unfamiliar with pointer arithmetic I wrote a python port here. https://gist.github.com/siddharthsarda/5538928 https://gist.github.com/siddharthsarda/5538928
- mixedbit 13y agoBe 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 13y agoThere 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 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 13y agoI 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 13y agoI 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 13y agoA 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 13y agoI'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.
- abecedarius 13y agohttps://github.com/darius/ung/blob/master/c/regexpoid.c 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.)
- erre 13y agoFor 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-Practice/dp/0596510047 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 13y agoThis 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/ http://dtrace.org/blogs/bmc/2007/07/11/beautiful-code/
- agentS 13y agoI 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 http://swtch.com/~rsc/regexp/regexp1.html
- erre 13y agoAh, 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 http://www.youtube.com/watch?v=aMnn0Jq0J-E
- b0rsuk 13y agoGreat code is often deceptively simple. It can lead you to believe it was simple to write.
- toolslive 13y agoI saw this in a drdobbs article in the 90s as well.
- toolslive 13y agoapril 1999: http://www.drdobbs.com/architecture-and-design/regular-expressions/228700838?queryText=pike%2Bkernighan%2Bregular http://www.drdobbs.com/architecture-and-design/regular-expre...
- McUsr 13y agoThanks 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 13y agoIt's interesting that this is in a very functional style, no global state is used.
- chollida1 13y agoCan 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 13y agoIt 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.
- abecedarius 13y agoThe usual reason is to allow c to be EOF, but I don't see why anyone would in this case.
- nilkn 13y agoI 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 _ [] = []