Constructing And Composing Efficient Top-downParsersAtRuntime

Date: 2008-10-09

Time: 11:45

Room: BBL room 471

Speaker: Doaitse Swierstra

Title: Constructing and Composing Efficient Top-down Parsers at Runtime

(Marcos Viera, S. Doaitse Swierstra and Eelco Lempsink)

Abstract

The Haskell definition and implementation of read is far from perfect. In the first place read is not able to handle the associativities defined for infix operators. Furthermore, it puts constraints on the way show is defined, and especially forces it to generate far more parentheses than expected. Lastly, it may give rise to exponential parsing times. All this is due to the compositionality requirement for read functions, which imposes a top-down parsing strategy.

We propose a different approach, based on typed abstract syntax, in which grammars describing the data types are composed dynamically. Using the transformation libraries described in a companion paper these syntax descriptions are combined and transformed into parsers at runtime, from which the required read function are constructed. In this way we obtain linear parsing times, achieve consistency with the defined associativities, and may use a version of show which generates far fewer parentheses, thus improving readability of printed values.

The described transformation algorithms can be incorporated in a Haskell compiler, thus moving most of the work involved to compile time.

BibTeX Entry

@inproceedings{1411296,
 author = {Marcos Viera and S. Doaitse Swierstra and Eelco Lempsink},
 title = {Haskell, do you read me?: constructing and composing efficient top-down parsers at runtime},
 booktitle = {Haskell '08: Proceedings of the first ACM SIGPLAN symposium on Haskell},
 year = {2008},
 isbn = {978-1-60558-064-7},
 pages = {63--74},
 location = {Victoria, BC, Canada},
 doi = {http://doi.acm.org/10.1145/1411286.1411296},
 publisher = {ACM},
 address = {New York, NY, USA},
 }