On Mon, Apr 27, 2009 at 2:41 PM, 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.

I've never tried to implement a whitespace sensitive parser like you'd need for Haskell or Python, but my thought was that maybe you use a stack and you push/pop from it when the indentation level changes. That way, I think you could isolate the part of the parser that handles changes in indentation from the rest. Maybe I haven't thought about this enough yet because I'm not sure what I would store on the stack. In some sense, you want the indentation level change to determine which production(s) of the grammar you are looking for. You might also use it to track scope so that you know the scope of the names in the program source.

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.

I'd start by playing with some toy examples in the State monad, then try implementing a State monad. Only look at the real implementation when you get stuck. Once you get State, then go back to Parsec which is more complex. This way you'll be in over your head less. Good luck, Jason

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 modifications. 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 this. 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 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

2009/4/28 Bas van Gijzel

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.

Parsing a simple form of the offside rule is discussed in the paper: Monadic Parser Combinators, Hutton and Meijer, 1996 http://www.cs.nott.ac.uk/~gmh/monparsing.pdf see section 8, page 30. Their parsers are similar in style to Parsec, but you may need to do some translation. I haven't thought about it hard, but I suspect their approach is not efficient for deeply nested examples, due to repeated processing of the token stream (but I could be wrong, and maybe it doesn't matter for what you are trying to do). I followed their approach in a toy language once, and the result was very pleasing to read in code. Cheers, Bernie.