Software GR Presents Scott Vokes: Write a Parser Today!

Tuesday, June 28, 2016

6:00 pm - 8:00 pm

Atomic Object, 941 Wealthy St, Grand Rapids, MI

Abstract

From wire protocols to DSLs, applying structure to raw data is a core part of programming. The best tools for the job, parsers, have a  scary reputation -- developers often settle for others (such as  regular expressions) and suffer through their limitations instead. Parsers don't have to be intimidating, though -- they may be a huge branch of computer science, but a little knowledge goes a long way.

In  this talk, I'll focus on two parsing techniques that are widely applicable and independent of language or platform-specific libraries.

The first, recursive descent parsing, is a technique that belongs in  everyone's toolkit. It can be built up from only fundamental constructs,  yet is able to parse practical languages. It is particularly handy for creating DSLs and other tools where usability is important.

The second, a combination of Earley and intersection parsing, is a more  advanced algorithm. While comparatively obscure, it's worth knowing  because it can deftly handle data that would tie most common parsers in  knots. When a grammar is inherently ambiguous, it can even return all possible interpretations of the input at once, using a familiar and  space-efficient data structure in an unexpected way.

About Scott
Scott works on embedded and distributed systems at Helium. His other  interests include data compression, testing tools, cooking, and electronics.

Scott can often be found bicycling around Grand Rapids, MI.