Software GR Presents Scott Vokes: Write a Parser Today!

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

http://photos1.meetupstatic.com/photos/event/2/b/4/600_450600692.jpeg

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.