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.

Thu 23 Oct

15:30 - 17:00: OOPSLA - Compilation Tools at Salon F
Chair(s): Robert GrimmGoldman Sachs
oopsla2014141407100000015:30 - 15:52
Terence ParrUniversity of San Francisco, Sam HarwellUniversity of Texas at Austin, Kathleen FisherTufts University
Link to publication File Attached
oopsla2014141407235000015:52 - 16:15
Milos GligoricUniversity of Illinois at Urbana-Champaign, Wolfram SchulteMicrosoft, Chandra PrasadMicrosoft, Danny van VelzenMicrosoft, Iman NarasamdyaMicrosoft, Ben LivshitsMicrosoft Research
Link to publication
oopsla2014141407370000016:15 - 16:37
Vineet Kumar, Laurie HendrenMcGill University
Link to publication
oopsla2014141407505000016:37 - 17:00
Manohar JonnalageddaEPFL, Switzerland, Thierry CoppeyEPFL, Switzerland; Google, Sandro StuckiEPFL, Switzerland, Tiark RompfPurdue & Oracle Labs, Martin OderskyEcole Polytechnique Federale de Lausanne
Link to publication