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

[S. Doaitse Swierstra]

As Lennart said, the complete offside rule as found in Haskell is  
almost impossible to get right. This is mainly due to the way in which  
it is formulated: in terms of error correction. This makes it very  
difficult to build a parser for such rules which have error correction  
built into them. We need to do a kind of open brain surgery to get  
this working. Note that the GHC treats the offside rule even a bit  
different in case it is caused by the do notation, in which case the  
indentation does not have to be greater, but has to be just at least  
as great as the previous indentation.

In the uulib package you will find a module which handles the offside  
parsing as we understand it; you may take it as an object of study. We  
use it in the UHC and we managed to compile almost all the basic  
libraries with it (with the exception of the do's mention above, which  
we had to give some extra indentation).  It basically follows the  
suggestion made by Lennart in this thread, by redefining the input  
state which is being maintained.

I understand that you try to build an Occam compiler. Fortunately the  
offside rule for Occam is much simpler, and resembles closely the  
Miranda rule.

I uploaded a new version of our parser combinators (uu-parisnglib) to  
Hackage, which is well documented in an associated tutorial. I think  
it could give you a good starting point. Note however that the library  
is far from stable, and will be extended in the near future. E.g. with  
a pBlock as we have in the uulib library to deal with the offside  
rule ;-}

  Hope you enjoy jumping into the deep,

  Doaitse Swierstra






On 28 apr 2009, at 22:03, Bas van Gijzel wrote:

> Hey,
>
> Thanks for the help thusfar. These are interesting suggestions, and  
> I think the occam-pi compiler would help a bit as example. I'll  
> force myself to learn some more about the state monad, but I haven't  
> found really good examples except in Real World Haskell until now so  
> I hope I'll manage. I'll keep you posted about my further progress.
>
> Cheers,
>
> Bas
>
> On Tue, Apr 28, 2009 at 2:04 PM, Neil Brown <nccb2 at kent.ac.uk> wrote:
> Bas van Gijzel 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.
> Hi,
>
> I work on a compiler for occam-pi, which has indentation-based  
> syntax.  It's regular (two-spaces per indent) rather than different- 
> number-of-spaces, and line continuations can only follow certain  
> tokens, but perhaps our code might help you.
>
> We use alex for tokenising and parsec for parsing.  We tokenise the  
> file, and then use the source positions to create indent/outdent  
> tokens in the token stream, and after that the parser parses things  
> like a PAR block as: do {reserved "PAR"; indent; many1 subItem;  
> outdent}.  Our code can be found at:
>
> http://offog.org/darcs/tock/
>
> Look in the frontends subdirectory, particularly at  
> StructureOccam.hs, but also LexOccam.x and ParseOccam.hs.  It may  
> not be the most elegant way to do things (occam has all sorts of  
> oddities that make parsing a pain), but it does work :-)
>
> Thanks,
>
> Neil.
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090428/7f332fc5/attachment.htm