Monadic Parsing in F#
This article is also available in PDF
Abstract
This article is a short tutorial on how to write extensible recursive
descent parsers with no mutable state using monads in F#. The parsers
that are build using the techniques described here are able to accept
ambiguous grammars, and have arbitrary lenght lookahead. These LL(*)
(Parr 2007) parsers are not limited to any finite number of lookaheads.
Although this potentially reduces performance in comparison to machine
generated bottom-up parsers, the techniques described in this article
will make simpler and more elegant parsers. Also the parsers eliminate
the need for lexical analysis (tokenization) which is done on the
fly.