Wed 15 Jun 2016 16:30 - 17:00 at Grand Ballroom San Rafael - Parsing & Compilation Chair(s): Michelle Strout

Current algorithms for context-free parsing inflict a trade-off between ease of understanding, ease of implementation, theoretical complexity, and practical performance. No algorithm achieves all of these properties simultaneously.

Might et al. (2011) introduced parsing with derivatives, which handles arbitrary context-free grammars while being both easy to understand and simple to implement. Despite much initial enthusiasm and a multitude of independent implementations, its worst-case complexity has never been proven to be better than exponential. In fact, high-level arguments claiming it is fundamentally exponential have been advanced and even accepted as part of the folklore. Performance ended up being sluggish in practice, and this sluggishness was taken as informal evidence of exponentiality.

In this paper, we reexamine the performance of parsing with derivatives. We have discovered that it is not exponential but, in fact, cubic. Moreover, simple (though perhaps not obvious) modifications to the implementation by Might et al. (2011) lead to an implementation that is not only easy to understand but also highly performant in practice.

Wed 15 Jun
Times are displayed in time zone: (GMT-07:00) Tijuana, Baja California change

15:30 - 17:00: Research Papers - Parsing & Compilation at Grand Ballroom San Rafael
Chair(s): Michelle StroutThe University of Arizona
pldi-2016-papers15:30 - 16:00
Somashekaracharya G BhaskaracharyaIndian Institute of Science and National Instruments, Uday BondhugulaIndian Institute of Science, Albert CohenINRIA
Media Attached
pldi-2016-papers16:00 - 16:30
Tobias GrosserETH Zurich, Switzerland, Sven Verdoolaege, Albert CohenINRIA
Media Attached
pldi-2016-papers16:30 - 17:00
Michael D. AdamsUniversity of Utah, Celeste HollenbeckUniversity of Utah, Matthew MightUniversity of Utah, USA
Pre-print Media Attached