index.md (7696B)
1 --- 2 title: "Write You a Parser for Fun and Win" 3 date: 2013-11-26T00:00:00+00:00 4 draft: false 5 canonical_url: https://www.viget.com/articles/write-you-a-parser-for-fun-and-win/ 6 --- 7 8 As a software developer, you're probably familiar with the concept of a 9 parser, at least at a high level. Maybe you took a course on compilers 10 in school, or downloaded a copy of [*Create Your Own Programming 11 Language*](http://createyourproglang.com), but this isn't the sort of 12 thing many of us get paid to work on. I'm writing this post to describe 13 a real-world web development problem to which creating a series of 14 parsers was the best, most elegant solution. This is more in-the-weeds 15 than I usually like to go with these things, but stick with me -- this 16 is cool stuff. 17 18 ## The Problem 19 20 Our client, the [Chronicle of Higher Education](http://chronicle.com/), 21 [hired us](https://viget.com/work/chronicle-vitae) to build 22 [Vitae](http://chroniclevitae.com/), a series of tools for academics to 23 find and apply to jobs, chief among which is the *profile*, an online 24 résumé of sorts. I'm not sure when the last time you looked at a career 25 academic's CV was, but these suckers are *long*, packed with degrees, 26 publications, honors, etc. We created some slick [Backbone-powered 27 interactions](https://viget.com/extend/backbone-js-on-vitae) for 28 creating and editing individual items, but a user with 70 publications 29 still faced a long road to create her profile. 30 31 Since academics are accustomed to following well-defined formats (e.g. 32 bibliographies), [KV](https://viget.com/about/team/kvigneault) had the 33 idea of creating formats for each profile element, and giving users the 34 option to create and edit all their data of a given type at once, as 35 text. So, for example, a user might enter his degrees in the following 36 format: 37 38 Duke University 39 ; Ph.D.; Biomedical Engineering 40 41 University of North Carolina 42 2010; M.S.; Biology 43 2007; B.S.; Biology 44 45 That is to say, the user has a bachelor's and a master's in Biology from 46 UNC, and is working on a Ph.D. in Biomedical Engineering at Duke. 47 48 ## The Solution 49 50 My initial, naïve approach to processing this input involved splitting 51 it up by line and attempting to suss out what each line was supposed to 52 be. It quickly became apparent that this was untenable for even one 53 model, let alone the 15+ that we eventually needed. 54 [Chris](https://viget.com/about/team/cjones) suggested creating custom 55 parsers for each resource, an approach I'd initially written off as 56 being too heavy-handed for our needs. 57 58 What is a parser, you ask? [According to 59 Wikipedia](https://en.wikipedia.org/wiki/Parsing#Computer_languages), 60 it's 61 62 > a software component that takes input data (frequently text) and 63 > builds a data structure -- often some kind of parse tree, abstract 64 > syntax tree or other hierarchical structure -- giving a structural 65 > representation of the input, checking for correct syntax in the 66 > process. 67 68 Sounds about right. I investigated 69 [Treetop](http://treetop.rubyforge.org/), the most well-known Ruby 70 library for creating parsers, but I found it to be targeted more toward 71 building standalone tools rather than use inside a larger application. 72 Searching further, I found 73 [Parslet](http://kschiess.github.io/parslet/), a "small Ruby library for 74 constructing parsers in the PEG (Parsing Expression Grammar) fashion." 75 Parslet turned out to be the perfect tool for the job. Here, for 76 example, is a basic parser for the above degree input: 77 78 ```ruby 79 class DegreeParser < Parslet::Parser 80 root :degree_groups 81 82 rule(:degree_groups) { degree_group.repeat(0, 1) >> 83 additional_degrees.repeat(0) } 84 85 rule(:degree_group) { institution_name >> 86 (newline >> degree).repeat(1).as(:degrees_attributes) } 87 88 rule(:additional_degrees) { blank_line.repeat(2) >> degree_group } 89 90 rule(:institution_name) { line.as(:institution_name) } 91 92 rule(:degree) { year.as(:year).maybe >> 93 semicolon >> 94 name >> 95 semicolon >> 96 field_of_study } 97 98 rule(:name) { segment.as(:name) } 99 100 rule(:field_of_study) { segment.as(:field_of_study) } 101 102 rule(:year) { spaces >> 103 match("[0-9]").repeat(4, 4) >> 104 spaces } 105 106 rule(:line) { spaces >> 107 match('[^ \r\n]').repeat(1) >> 108 match('[^\r\n]').repeat(0) } 109 110 rule(:segment) { spaces >> 111 match('[^ ;\r\n]').repeat(1) >> 112 match('[^;\r\n]').repeat(0) } 113 114 rule(:blank_line) { spaces >> newline >> spaces } 115 rule(:newline) { str("\r").maybe >> str("\n") } 116 rule(:semicolon) { str(";") } 117 rule(:space) { str(" ") } 118 rule(:spaces) { space.repeat(0) } 119 end 120 ``` 121 122 Let's take this line-by-line: 123 124 **2:** the `root` directive tells the parser what rule to start parsing 125 with. 126 127 **4-5:** `degree_groups` is a Parslet rule. It can reference other 128 rules, Parslet instructions, or both. In this case, `degree_groups`, our 129 parsing root, is made up of zero or one `degree_group` followed by any 130 number of `additional_degrees`. 131 132 **7-8:** a `degree_group` is defined as an institution name followed by 133 one more more newline + degree combinations. The `.as` method defines 134 the keys in the resulting output hash. Use names that match up with your 135 ActiveRecord objects for great justice. 136 137 **10:** `additional_degrees` is just a blank line followed by another 138 `degree_group`. 139 140 **12:** `institution_name` makes use of our `line` directive (which 141 we'll discuss in a minute) and simply gives it a name. 142 143 **14-18:** Here's where a degree (e.g. "1997; M.S.; Psychology") is 144 defined. We use the `year` rule, defined on line 23 as four digits in a 145 row, give it the name "year," and make it optional with the `.maybe` 146 method. `.maybe` is similar to the `.repeat(0, 1)` we used earlier, the 147 difference being that the latter will always put its results in an 148 array. After that, we have a semicolon, the name of the degree, another 149 semicolon, and the field of study. 150 151 **20-21:** `name` and `field_of_study` are segments, text content 152 terminated by semicolons. 153 154 **23-25:** a `year` is exactly four digits with optional whitespace on 155 either side. 156 157 **27-29:** a `line` (used here for our institution name) is at least one 158 non-newline, non-whitespace character plus everything up to the next 159 newline. 160 161 **31-33:** a `segment` is like a `line`, except it also terminates at 162 semicolons. 163 164 **35-39:** here we put names to some literal string matches, like 165 semicolons, spaces, and newlines. 166 167 In the actual app, the common rules between parsers (year, segment, 168 newline, etc.) are part of a parent class so that only the 169 resource-specific instructions would be included in this parser. Here's 170 what we get when we pass our degree info to this new parser: 171 172 ```ruby 173 [{:institution_name=>"Duke University"@0, 174 :degrees_attributes=> 175 [{:name=>" Ph.D."@17, :field_of_study=>" Biomedical Engineering"@24}]}, 176 {:institution_name=>"University of North Carolina"@49, 177 :degrees_attributes=> 178 [{:year=>"2010"@78, :name=>" M.S."@83, :field_of_study=>" Biology"@89}, 179 {:year=>"2007"@98, :name=>" B.S."@103, :field_of_study=>" Biology"@109}]}] 180 ``` 181 182 The values are Parslet nodes, and the `@XX` indicates where in the input 183 the rule was matched. With a little bit of string coercion, this output 184 can be fed directly into an ActiveRecord model. If the user's input is 185 invalid, Parslet makes it similarly straightforward to point out the 186 offending line. 187 188 ------------------------------------------------------------------------ 189 190 This component of Vitae was incredibly satisfying to work on, because it 191 solved a real-world issue for our users while scratching a nerdy 192 personal itch. I encourage you to learn more about parsers (and 193 [Parslet](http://kschiess.github.io/parslet/) specifically) and to look 194 for ways to use them in projects both personal and professional.