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

Displayed time zone: Tijuana, Baja California change

15:30 - 17:00
Parsing & CompilationResearch Papers at Grand Ballroom San Rafael
Chair(s): Michelle Strout The University of Arizona
15:30
30m
Talk
Automatic Storage Optimization for Arrays [TOPLAS]
Research Papers
Somashekaracharya G Bhaskaracharya Indian Institute of Science and National Instruments, Uday Bondhugula Indian Institute of Science, Albert Cohen INRIA
Media Attached
16:00
30m
Talk
Polyhedral AST generation is more than scanning polyhedra [TOPLAS]
Research Papers
Tobias Grosser ETH Zurich, Switzerland, Sven Verdoolaege , Albert Cohen INRIA
Media Attached
16:30
30m
Talk
On the Complexity and Performance of Parsing with Derivatives
Research Papers
Michael D. Adams University of Utah, Celeste Hollenbeck University of Utah, Matthew Might University of Utah, USA
Pre-print Media Attached