{"id":8667,"date":"2020-02-17T10:39:51","date_gmt":"2020-02-17T15:39:51","guid":{"rendered":"https:\/\/irreal.org\/blog\/?p=8667"},"modified":"2020-02-17T10:39:51","modified_gmt":"2020-02-17T15:39:51","slug":"regular-expressions-in-30-lines-of-c","status":"publish","type":"post","link":"https:\/\/irreal.org\/blog\/?p=8667","title":{"rendered":"Regular Expressions in 30 Lines of C"},"content":{"rendered":"

I recently saw a pointer to a nice article by Brian Kernighan that describes some beautiful code written by Rob Pike for their book The Practice of Programming<\/a>. As an example of the power of notation, they wanted to show a simple implementation of regular expression matching. They couldn\u2019t use one of the existing implementations because they were too long so Pike sat down for an hour or two and whipped out a 30-line version in C.<\/p>\n

In the article, A Regular Expression Matcher<\/a>, Kernighan explains why he thinks Pike\u2019s creation is \u201cbeautiful code.\u201d It\u2019s compact, clear, elegant and implements a simple example of a real tool. If you know C or can read it, you should definitely take a look at Kernighan\u2019s article.<\/p>\n

If, after reading the article, you\u2019d like to know a bit more about how regular expressions are implemented, you should take a look at Russ Cox\u2019s posts on the subject<\/a>. The first two posts, in particular discuss some of the theory and show how to implement efficient<\/i> algorithms. Efficiency can be important in certain edge cases where the implementations in Perl and many other popular languages can take exponential time. Compare that with Ken Thompson\u2019s original implementation<\/a> for the QED editor from the 60s. Thompson\u2019s version is literally a million times faster than Perl\u2019s for one pathological regular expression and even faster for others. You can read all about that and why Thompson\u2019s version performs so much better in Cox\u2019s first post. The second post has a virtual machine implementation that more or less duplicates Thompson\u2019s QED algorithm that generated native code on the fly for the matcher.<\/p>\n","protected":false},"excerpt":{"rendered":"

I recently saw a pointer to a nice article by Brian Kernighan that describes some beautiful code written by Rob Pike for their book The Practice of Programming. As an example of the power of notation, they wanted to show … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[135,37],"class_list":["post-8667","post","type-post","status-publish","format-standard","hentry","category-general","tag-programming","tag-tech"],"_links":{"self":[{"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/posts\/8667","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=8667"}],"version-history":[{"count":1,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/posts\/8667\/revisions"}],"predecessor-version":[{"id":8668,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/posts\/8667\/revisions\/8668"}],"wp:attachment":[{"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=8667"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=8667"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=8667"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}