Parser.y rewrite with parser combinators

Simon Marlow marlowsd at
Tue Oct 16 21:13:00 UTC 2018

I personally love to hack things up with parser combinators, but for
anything longer term where I want a degree of confidence that changes
aren't going to introduce new problems I'd still use Happy. Yes it's a
total pain sometimes, and LALR(1) is very restrictive, but I wouldn't want
to lose the guarantees of unambiguity and performance. We have *always* had
to shoehorn the Haskell grammar into LALR(1) - patterns and expressions had
to be parsed using the same grammar fragment from the start due to the list
comprehension syntax. And some post-processing is inevitable - it's
technically not possible to parse Haskell without rearranging infix
expressions later, because you don't know the fixities of imported
operators.  And layout is truly horrible to deal with - Happy's error token
is designed purely to handle the layout rule, and it differs in semantics
from yacc's error token for this reason (that is, if yacc's error token has
a semantics, I could never figure out what it was supposed to do). Dealing
with layout using parser combinators would probably require at least one
layer of backtracking in addition to whatever other backtracking you needed
to handle the other parts of the grammar.


On Tue, 9 Oct 2018 at 15:18, Sven Panne <svenpanne at> wrote:

> Am Di., 9. Okt. 2018 um 15:45 Uhr schrieb Richard Eisenberg <
> rae at>:
>> [...] What I'm trying to say here is that tracking the backtracking level
>> in types doesn't seem like it will fly (tempting though it may be).
> ... and even if it did fly, parser combinators with backtracking have a
> strong tendency to introduce space leaks: To backtrack, you have too keep
> previous input somehow, at least up to some point. So to keep the memory
> requirements sane, you have to explicitly commit to one parse or another at
> some point. Different combinator libraries have different ways to do that,
> but you have to do that by hand somehow, and that's where the beauty and
> maintainability of the combinator approach really suffers.
> Note that I'm not against parser combinators, far from it, but I don't
> think they are necessarily the right tool for the problem at hand. The
> basic problem is: Haskell's syntax, especially with all those extensions,
> is quite tricky, and this will be reflected in any parser for it. IMHO a
> parser generator is the lesser evil here, at least it points you to the
> ugly places of your language (on a syntactic level). If Haskell had a few
> more syntactic hints, reading code would be easier, not only for a
> compiler, but (more importantly) for humans, too. Richard's code snippet is
> a good example where some hint would be very useful for the casual reader,
> in some sense humans have to "backtrack", too, when reading such code.
> _______________________________________________
> ghc-devs mailing list
> ghc-devs at
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the ghc-devs mailing list