SPLASH 2014
Mon 20 - Fri 24 October 2014 Portland, Oregon, United States
Thu 23 Oct 2014 16:37 - 17:00 at Salon F - Compilation Tools Chair(s): Robert Grimm

Parsers are ubiquitous in computing: many applications de- pend on fast decoding of data. Parser combinators are an in- tuitive tool for writing parsers: tight integration with the host language enables grammar specifications to be interleaved with processing of parse results. Unfortunately, parser com- binators are slow due to the high overhead on the abstraction mechanisms that enable composition. We present a technique for eliminating such overhead. We use staging, a form of runtime code generation, to dissoci- ate input parsing from parser composition, and eliminate in- termediate data structures and computations associated with parser composition at staging time. A key challenge is to maintain support for input dependent grammars, which have no clear stage distinction. Our approach applies to top-down recursive-descent parsers as well as bottom-up nondeterministic parsers with key applications in dynamic programming on sequences, where we auto-generate code for parallel hardware. We achieve performance comparable to specialized, hand-written parsers.