Combinators for Generalised Parsing

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:

• Theorems for Free (SkillsCast recorded in November 2020)
• Comparing Strict and Lazy (SkillsCast recorded in November 2020)