{"id":1613,"date":"2018-11-09T21:39:09","date_gmt":"2018-11-10T02:39:09","guid":{"rendered":"http:\/\/codinggorilla.domemtech.com\/?p=1613"},"modified":"2018-11-11T10:14:19","modified_gmt":"2018-11-11T15:14:19","slug":"porting-re2-j-to-c","status":"publish","type":"post","link":"http:\/\/165.227.223.229\/index.php\/2018\/11\/09\/porting-re2-j-to-c\/","title":{"rendered":"Porting Re2\/j to C#"},"content":{"rendered":"

For these last few weeks, I’ve been trying to grapple with the problem of p\/invoke<\/a>–the nasty but must-use feature in C#. While one could write these declarations out by hand, some libraries are too large, and change too often, so people use p\/invoke generators, like SWIG<\/a>. However, the is no generator that is easy to use\u00c2\u00a0or generates 100% correct C# declarations. So, as every software developer does,\u00c2\u00a0so I go to re-invent the wheel.<\/p>\n

<\/p>\n

Part of my solution involves using regular expressions–which requires a recognizer<\/a>. Rather than write my own regular expression engine–as I don’t want to spend all day writing one–I decided to look for one.<\/p>\n

If you try to Google for “regular expression engine source code”, you will find a great many implementations<\/a>. But, hardly any I would consider an easy read, in the evening beside your dog at the fireplace. Some say the\u00c2\u00a0implementation by Pike and Kernighan<\/a>\u00c2\u00a0is a nice and clean implementation, but that code really isn’t a regular expression engine. It’s a\u00c2\u00a0glob pattern<\/a> matcher. And, if you try to extend it to include regular expression operators<\/a> like groups (parenthesized patterns), sets (denoted by square brackets), and Boolean Or operators, you end up with a\u00c2\u00a0big, fat, pile of crap<\/a>.<\/p>\n

Surprisingly, virtually all regular expression engines are implemented as NFA’s with backtracking. As I really didn’t want to go through Thompson’s Construction<\/a>, and re-implement something I did years ago, I decided to try a nice implementation of Thompson’s original NFA algorithm by Cox<\/a>. The original code is in C++<\/a>, then\u00c2\u00a0ported to Java<\/a> a few years ago. Starting with that, I\u00c2\u00a0ported it to C#<\/a>\u00c2\u00a0over the last two days. Does it work? Yes!<\/p>\n

How does it work?<\/h3>\n

RE2 works by constructing an NFA<\/a>, then, as explained by Wikipedia, keeps a set data structure of all the possible states that the recognizer is in<\/a>. (Surprisingly, Wiki does not describe the backtracking method, used by most RE recognizers!)<\/p>\n

Let’s take Cox’s example (pattern = “abab|abbb”, text = “abbb”<\/em>).\u00c2\u00a0Debugging the implementation<\/a>, we see the NFA is implemented by the class\u00c2\u00a0Machine<\/a>. Prog<\/a> encodes the states and transitions of the NFA. The\u00c2\u00a0inst<\/em> field of the class encodes the transitions organized by state, which is identified by a\u00c2\u00a0non-negative integer. The main loop of the recognizer is for-loop<\/a>. Starting in state 1, the recognizer steps to {2} on ‘a’. Then, on ‘b’ the recognizer steps to {7, 3, 5}. Then, on ‘b’, the recognizer steps to {6}. Then, on ‘b’, the recognizer steps to {8}, which is the match<\/em> state.<\/p>\n

\"\"<\/p>\n

The Alternative<\/h3>\n

Note: The simplest implementation I’ve seen is just a recursive descent<\/a>, which you can find here<\/a>. I think I even had it on a quiz way back in compiler construction many years ago.<\/p>\n

–Ken<\/p>\n","protected":false},"excerpt":{"rendered":"

For these last few weeks, I’ve been trying to grapple with the problem of p\/invoke–the nasty but must-use feature in C#. While one could write these declarations out by hand, some libraries are too large, and change too often, so people use p\/invoke generators, like SWIG. However, the is no generator that is easy to … <\/p>\n

Continue reading “Porting Re2\/j to C#”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[],"tags":[],"_links":{"self":[{"href":"http:\/\/165.227.223.229\/index.php\/wp-json\/wp\/v2\/posts\/1613"}],"collection":[{"href":"http:\/\/165.227.223.229\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/165.227.223.229\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/165.227.223.229\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/165.227.223.229\/index.php\/wp-json\/wp\/v2\/comments?post=1613"}],"version-history":[{"count":0,"href":"http:\/\/165.227.223.229\/index.php\/wp-json\/wp\/v2\/posts\/1613\/revisions"}],"wp:attachment":[{"href":"http:\/\/165.227.223.229\/index.php\/wp-json\/wp\/v2\/media?parent=1613"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/165.227.223.229\/index.php\/wp-json\/wp\/v2\/categories?post=1613"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/165.227.223.229\/index.php\/wp-json\/wp\/v2\/tags?post=1613"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}