www.idziorek.net | blog | contact
March 2019

Applicative vs. Monadic Parsing

Some real world parsers as Parsec, let us choose between applicative and monadic parsing. The applicative style should be sufficient to parse context-free languages and is easier to reason about, but it is not capable of parsing context-sensitive grammars.

Functor, Applicative, Alternative, Monad

Before we discuss Applicative and Monadic Parsing, it is important to understand what Functors, Applicative Functors, Alternatives and Monads have to offer. When in doubt simply look up the type-class definition.

Two well-known data types which are instances of all of the above are Maybe and List. Try it yourself in GHCi.

Simple Parser

Our simple toy Parser simply encapsulates a parsing function that returns Nothing if parsing fails. Otherwise a pair consisting of the parsed and unparsed input inside its respective elements.

Notice that we made our Parser instance of all the type-classes already.

Primitives

We also need at least a minimal set of primitives to parse something. Note that the primitives can give you the effects of Applicative or Alternative even if the Parser itself is not an instance of these. (Thanks to dmwit for pointing this out on #haskell).

The num parser makes use of the some combinator which requires our Parser to be an instance of Alternative as well. Applicative alone is of limited use in practice since without it, we also lack the <|> combinator.

Applicative / Alternative parsing

Now we are able to parse any context free grammar, given our satisfy Parser along with Applicative, Alternative, and recursion.

Let’s parse something!

Monadic parsing of context-sensitive grammars

The canonical non-context-free language can not be caputred by applicative parsing anymore:

$$\{a^n b^n c^n : n \geqslant 1\}$$

The following monadic parser will work here:

Git Repo

Here you can find the complete source code of this little toy parser along with the examples presented in this article:

https://gitweb.softwarefools.com/?p=miguel/haskell.git;a=blob;f=parser/main.hs

Summary

As usual, use the simplest tool that will suffice 😄

Ref / Further Reading