Please log in to watch this conference skillscast.

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

YOU MAY ALSO LIKE:

• The Secrets of the GHC Garbage Collector (in Online Event on 11th June 2020)
• Lightning Talk: Making and Testing Code Generators in Haskell (SkillsCast recorded in October 2019)
• Functional Lenses Through a Practical Lens (SkillsCast recorded in October 2019)