Combinators for Generalised Parsing

6th October 2016 in London at CodeNode

There are 42 other SkillsCasts available from Haskell eXchange 2016

Please log in to watch this conference skillscast.

595873338 640

Many Haskell programmers write parsers using parser combinator libraries like `parsec` or `uu-lib`, or parser generators like `happy`. These systems are popular because they are easy to get started with and suitable for production applications. In particular, parser combinators libraries are popular because the parsers obtained in this way are easy to debug, maintain, generalise and compose. The disadvantages of the underlying parsing technologies - left-recursion, nondeterminism and ambiguity - are well understood and can be circumnavigated. Some argue that parsing is therefore a solved problem. Others turn to generalised parsing. Generalised parsing overcomes these disadvantages: modern parser generators are capable of generating parsers for arbitrary context-free grammars. The generated parsers find all possible derivations of an input string in worst-case cubic time and space. In recent years, combinator libraries like `p3` (OCaml) and `meerkat` (Scala) emerged, promising to combine the advantages of parser combinators with those of generalised parsing. In this talk, you will explore the implementation of the `gll` combinator library, offering generalised top-down parsing to Haskell programmers. The combinators of these libraries are so powerful that they may compute explicit representations of context-free grammars, enabling features common to parser generators like lookahead tests and grammar transformations. This power comes at a price. Following the authors of the `grammar-combinators` library, I argue that combinator libraries for generalised parsing require observable sharing. As a consequence, such combinator libraries cannot offer programmers the same flexibility as `parsec` and `uu-lib`. Although offering generalised parsing, some benefits of combinator parsing are definitely lost.

In this talk, - You learn the basics of combinator based parsing in Haskell - You are introduced to generalised parsing - You get a glimpse of the gll combinator library you can find on Hackage


Thanks to our sponsors

Combinators for Generalised Parsing

Thomas van Binsbergen

L. Thomas van Binsbergen is a PhD student in Computer Science at Royal Holloway, University of London, and an MSc graduate of Utrecht University. His work revolves around the specificying and prototyping programming languages. Notable are the contributions he made to the Utrecht University Attribute Grammar Compiler (UUAGC), implementing algorithms for compile-time scheduling of attribute evaluation based on dependency analysis. In recent years, Thomas has been associated with the PLanCompS project and has developed Haskell tools for defining and executing FunCons: highly reusable and modular components used in the formal specification of programming languages' semantics.