On the Complexity and Performance of Parsing with Derivatives
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 JunDisplayed 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
|Automatic Storage Optimization for Arrays [TOPLAS]|
Somashekaracharya G Bhaskaracharya Indian Institute of Science and National Instruments, Uday Bondhugula Indian Institute of Science, Albert Cohen INRIAMedia Attached
|Polyhedral AST generation is more than scanning polyhedra [TOPLAS]|
Tobias Grosser ETH Zurich, Switzerland, Sven Verdoolaege , Albert Cohen INRIAMedia Attached
|On the Complexity and Performance of Parsing with Derivatives|
Michael D. Adams University of Utah, Celeste Hollenbeck University of Utah, Matthew Might University of Utah, USAPre-print Media Attached