[Haskell-cafe] Question about implementing an off-side rule in Parsec 2

Lennart Augustsson lennart at augustsson.net
Tue Apr 28 04:08:45 EDT 2009

Implementing exactly Haskell's rule for indentation is incredibly hard.
In fact, no known Haskell compiler gets it right.
But if you make a slightly simpler one, it's easy.  The simple one is
the one based only on indentation.

There are different ways you can do this.

For instance, you can preprocess the token stream from the lexer.
This prprocessor needs a little bit of parsing, e.g., if it encounters
a "let" token that is not followed by a "{" token it should insert a
"{" and then a corresponding "}" at the right place (this requires
every token to carry its column number).

You can also integrate it more into the parser.  Make, say, a block
parsing combinator that is called after seeing a "let".  If block does
not see a "{" it will modify the remaining token stream to insert the
"}" at the right place.  Nested blocks will similarely to their

You can also imagine inserting indentation change as a new kind of
token in the token streak and then rewriting the grammar to deal with

Personally, I like option two (the block parsing combinator).  I've
used it several times.

  -- Lennart

On Mon, Apr 27, 2009 at 10:41 PM, Bas van Gijzel <nenekotan at gmail.com> wrote:
> Hello everyone,
> I'm doing a bachelor project focused on comparing parsers. One of the parser
> libraries I'm using is Parsec (2) and I'm going to implement a very small
> subset of haskell with it, with as most important feature the off-side rule
> (indentation based parsing) used in function definitions and possibly in
> where clauses.
> But I'm still a bit stuck on how to implement this cleanly. I tried to
> search for some examples on blogs but I haven't found anything yet. As far
> as I can see the way to go would be using getState and updateState methods
> defined in Parsec.Prim and to use the methods in Parsec.Pos to compare the
> difference in indendation for tokens.
> But I haven't completely wrapped my head around any state monad yet and I
> don't understand Parsec enough yet to see how to use the methods Parsec.Pos
> and state easily. Some examples or pointers to something to read would
> really be helpful.
> Thanks in advance,
> Bas van Gijzel
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

More information about the Haskell-Cafe mailing list