Parser.y rewrite with parser combinators

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
23 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Re: Parser.y rewrite with parser combinators

Sven Panne-2
Am Di., 9. Okt. 2018 um 15:45 Uhr schrieb Richard Eisenberg <[hidden email]>:
[...] 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: Parser.y rewrite with parser combinators

Spiwack, Arnaud
In reply to this post by Vladislav Zavialov
On Tue, Oct 9, 2018 at 1:09 PM Vladislav Zavialov <[hidden email]> wrote:
In fact, we do have a fair share of boilerplate in our current grammar
due to lack of parametrisation. That's another issue that would be
solved by parser combinators (or by a fancier parser generator, but
I'm not aware of such one).
 
There is the Menhir [1] parser generator. It provides decent abstraction mechanism. It also generate LR parsers, hence is more flexible than Happy. And generates incremental parsers.

Of course, one would have to make it output Haskell a Haskell parser first. But considering the effort it seem to have been to add a Coq backend, I'd assume it would be less of an effort than porting the entire GHC grammar to parser combinators. (one hard thing would be to decide how to replace the ML functor mechanism that Menhir uses to generate functions from parsers to parsers)


_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: Parser.y rewrite with parser combinators

Simon Marlow-7
In reply to this post by Sven Panne-2
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.

Cheers
Simon


On Tue, 9 Oct 2018 at 15:18, Sven Panne <[hidden email]> wrote:
Am Di., 9. Okt. 2018 um 15:45 Uhr schrieb Richard Eisenberg <[hidden email]>:
[...] 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
12