Re: Happy and Macros (was Re: ANNOUNCE: Happy 1.10 released)
Manuel M. T. Chakravarty [EMAIL PROTECTED] writes: I didn't say that this works for any kind of parser combinator, I merely said that it works Doitse's and mine. Both implement SLL(1) parsers for which - as I am sure, you know - there exists a decision procedure for testing ambiguity. More precisely, whenever the library can build the parse table, the grammar must be non-ambigious. As the parse table construction is lazy, this covers only the productions exercised in that particular run, which is why I said that you need a file involving all grammar constructs of the language. Nothing magic here. Wow. Clearly I haven't spent enough time looking at your parser systems. I apologize for my incorrect assumptions and statements. Carl Witty ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Happy and Macros (was Re: ANNOUNCE: Happy 1.10 released)
Manuel M. T. Chakravarty [EMAIL PROTECTED] writes: I didn't say that this works for any kind of parser combinator, I merely said that it works Doitse's and mine. Both implement SLL(1) parsers for which - as I am sure, you know - there exists a decision procedure for testing ambiguity. More precisely, whenever the library can build the parse table, the grammar must be non-ambigious. As the parse table construction is lazy, this covers only the productions exercised in that particular run, which is why I said that you need a file involving all grammar constructs of the language. Nothing magic here. Wow. Clearly I haven't spent enough time looking at your parser systems. I apologize for my incorrect assumptions and statements. Carl Witty ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Happy and Macros (was Re: ANNOUNCE: Happy 1.10 released)
Thomas Johnsson [EMAIL PROTECTED] wrote, Happy and others like it generate an LR parser, which is a well-established technology since the late 60's (Knuth): efficient, deterministic, and checks the grammar for you. Parser combinators are usually nondeterministic ie backtracking (pre-Knuth!:-) though Cleverly Disguised in Haskell Higher Order clothes [..] PS would be cool to try to marry the two approaches Doaitse Swierstra et al have done this to a certain extent: http://www.cs.uu.nl/groups/ST/Software/UU_Parsing/ Parser combinators that are efficient, deterministic, and handle errors much better than the classic form of parser combinators. Manuel ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Two Times [was Re: Happy and Macros (was Re: ANNOUNCE: Happy 1.10 released)]
* Marc van Dongen [EMAIL PROTECTED] [2001-05-11T10:52+0100]: Manuel M. T. Chakravarty ([EMAIL PROTECTED]) wrote: [received message twice] Am I just the only one or does everybody receive messages posted to [EMAIL PROTECTED] and [EMAIL PROTECTED] twice? I find it a bit (I know I am exaggerating) annoying. Is there a way to avoid this? Use procmail to eliminate dups... .procmailrc: :0 Whc: msgid.lock | formail -D 8192 msgid.cache :0 a: duplicates More info: man procmail procmailex procmailrc Cheers, Michael -- () ASCII ribbon campaign | Chair for Computer Science II | GPG: F65C68CD /\ against HTML mail | RWTH Aachen, Germany | PGP: 1D0DD0B9 But... but There's no BLINK tag in LaTeX! -- seen on /. ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Two Times [was Re: Happy and Macros (was Re: ANNOUNCE: Happy 1.10 released)]
Manuel M. T. Chakravarty ([EMAIL PROTECTED]) wrote: [received message twice] Am I just the only one or does everybody receive messages posted to [EMAIL PROTECTED] and [EMAIL PROTECTED] twice? I find it a bit (I know I am exaggerating) annoying. Is there a way to avoid this? Regards, Marc ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Happy and Macros (was Re: ANNOUNCE: Happy 1.10 released)
Manuel M. T. Chakravarty [EMAIL PROTECTED] writes: I don't think, the point is the test for non-ambiguity. At least, Doitse's and my self-optimising parser combinator library will detect that a grammar is ambigious when you parse a sentence involving the ambiguous productions. So, you can check that by parsing a file involving all grammar constructs of the language. Sorry, doesn't work. Where do you get this file involving all grammar constructs of the language? If such an approach worked, you could use it to determine whether an arbitrary context-free grammar was ambiguous; but this problem is undecidable. Carl Witty ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Happy and Macros (was Re: ANNOUNCE: Happy 1.10 released)
Carl R. Witty wrote: Manuel M. T. Chakravarty [EMAIL PROTECTED] writes: I don't think, the point is the test for non-ambiguity. At least, Doitse's and my self-optimising parser combinator library will detect that a grammar is ambigious when you parse a sentence involving the ambiguous productions. So, you can check that by parsing a file involving all grammar constructs of the language. Sorry, doesn't work. Where do you get this file involving all grammar constructs of the language? If such an approach worked, you could use it to determine whether an arbitrary context-free grammar was ambiguous; but this problem is undecidable. This illustrates the difference between generality and usefulness. Often, one is less interested in learning that a grammar is ambiguous than learning that it is not. If you have a parser generator for a class of grammars, it will tell you if (and probably why) a candidate grammar you feed to it is not a member of that class. If it is accepted by, for example, a parser generator for LR(1) grammars, then it is a DCFG and therefore unambiguous. If you start with a natural grammar for the language, i.e. one that corresponds to the abstract syntax, and use a generator for a broad class of grammars (e.g LR(1)) then failure will give a good hint that the only way to get an unambiguous grammar in that class is to restrict the language, and you can use that information to make design decisions. For example, although Haskell has both 'let' and 'where' for introducing local definitions, thereby reflecting the typical committee decision when there are varying stylistic preferences, 'where' is not part of the expression syntax. If you write a grammar which includes the natural productions exp - let defs in exp exp - exp where defs and put this through a suitable generator, you will see why not. Of course, it is possible that an unambiguous grammar will fail to be LR(1) - by being non-deterministic, so the proper conclusion is that G is ambiguous or non-deterministic. But that is close enough for most purposes. Early versions of Hope had both 'let' and 'where' as expressions, and had three different forms of condtional. Most combinations of these constructs would interract to create ambiguity. The hand-coded parsers in use had not picked this up. That shows the advantage of using a generator - you get a constructive proof that the grammar is in the desired class. --brian ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Happy and Macros (was Re: ANNOUNCE: Happy 1.10 released)
S. Alexander Jacobson writes: I am not a parsing expert, but given the recent discussion on macros, I have to ask: why use happy rather than monadic parsing? Monadic parsing allows you to avoid a whole additional language/compilation step and work in Hugs (where you don't have a makefile). What does Happy buy you here? Happy and others like it generate an LR parser, which is a well-established technology since the late 60's (Knuth): efficient, deterministic, and checks the grammar for you. Parser combinators are usually nondeterministic ie backtracking (pre-Knuth!:-) though Cleverly Disguised in Haskell Higher Order clothes LR parsers gives you greated freedom in expressing the grammar, with the LR parser generator leaning over your shoulder. Grammars possible with parsing combinators are more constrained: cannot use left recursion, order of rules matters, etc. On the other hand, one has the whole abstraction machinery of Haskell or whatever at hand for writing the grammar rules. The analogy that comes to mind is statically typed languages vs runtime typed ones. --Thomas PS would be cool to try to marry the two approaches ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Two Times [was Re: Happy and Macros (was Re: ANNOUNCE: Happy 1.10 released)]
Manuel M. T. Chakravarty ([EMAIL PROTECTED]) wrote: [received message twice] Am I just the only one or does everybody receive messages posted to [EMAIL PROTECTED] and [EMAIL PROTECTED] twice? I find it a bit (I know I am exaggerating) annoying. Is there a way to avoid this? Regards, Marc ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Happy and Macros (was Re: ANNOUNCE: Happy 1.10 released)
Manuel M. T. Chakravarty [EMAIL PROTECTED] writes: I don't think, the point is the test for non-ambiguity. At least, Doitse's and my self-optimising parser combinator library will detect that a grammar is ambigious when you parse a sentence involving the ambiguous productions. So, you can check that by parsing a file involving all grammar constructs of the language. Sorry, doesn't work. Where do you get this file involving all grammar constructs of the language? If such an approach worked, you could use it to determine whether an arbitrary context-free grammar was ambiguous; but this problem is undecidable. Carl Witty ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Happy and Macros (was Re: ANNOUNCE: Happy 1.10 released)
Carl R. Witty wrote: Manuel M. T. Chakravarty [EMAIL PROTECTED] writes: I don't think, the point is the test for non-ambiguity. At least, Doitse's and my self-optimising parser combinator library will detect that a grammar is ambigious when you parse a sentence involving the ambiguous productions. So, you can check that by parsing a file involving all grammar constructs of the language. Sorry, doesn't work. Where do you get this file involving all grammar constructs of the language? If such an approach worked, you could use it to determine whether an arbitrary context-free grammar was ambiguous; but this problem is undecidable. This illustrates the difference between generality and usefulness. Often, one is less interested in learning that a grammar is ambiguous than learning that it is not. If you have a parser generator for a class of grammars, it will tell you if (and probably why) a candidate grammar you feed to it is not a member of that class. If it is accepted by, for example, a parser generator for LR(1) grammars, then it is a DCFG and therefore unambiguous. If you start with a natural grammar for the language, i.e. one that corresponds to the abstract syntax, and use a generator for a broad class of grammars (e.g LR(1)) then failure will give a good hint that the only way to get an unambiguous grammar in that class is to restrict the language, and you can use that information to make design decisions. For example, although Haskell has both 'let' and 'where' for introducing local definitions, thereby reflecting the typical committee decision when there are varying stylistic preferences, 'where' is not part of the expression syntax. If you write a grammar which includes the natural productions exp - let defs in exp exp - exp where defs and put this through a suitable generator, you will see why not. Of course, it is possible that an unambiguous grammar will fail to be LR(1) - by being non-deterministic, so the proper conclusion is that G is ambiguous or non-deterministic. But that is close enough for most purposes. Early versions of Hope had both 'let' and 'where' as expressions, and had three different forms of condtional. Most combinations of these constructs would interract to create ambiguity. The hand-coded parsers in use had not picked this up. That shows the advantage of using a generator - you get a constructive proof that the grammar is in the desired class. --brian ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: ANNOUNCE: Happy 1.10 released
Simon Marlow [EMAIL PROTECTED] wrote, ANNOUNCING Happy 1.10 - The LALR(1) Parser Generator for Haskell An RPM package for x86 RedHat Linux[1] is now available at ftp://ftp.cse.unsw.edu.au/pub/users/chak/jibunmaki/i386/happy-1.10-2.i386.rpm The matching source RPM is at ftp://ftp.cse.unsw.edu.au/pub/users/chak/jibunmaki/src/happy-1.10-2.src.rpm Happy LALRing, Manuel [1] The binary has been build on RH7.0 with glibc2.2. ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Happy and Macros (was Re: ANNOUNCE: Happy 1.10 released)
Combining two threads... Like macros and preprocessors, Happy generates code. I assume the justification for this is that hand-coding a parser in Haskell is presumed to be too difficult or that it is too hard to get the right level of abstraction (and therefore a macro-like facility is required). However, I've also used Hutton Meijer style monadic parsers and found them extremely elegant, clean, and easy to use in both Haskell and Python (though in Python they were too slow for my xml application -- function call overhead is _very_ high in Python). I am not a parsing expert, but given the recent discussion on macros, I have to ask: why use happy rather than monadic parsing? Monadic parsing allows you to avoid a whole additional language/compilation step and work in Hugs (where you don't have a makefile). What does Happy buy you here? goingovermyhead And generalizing from the above, since Monads/Arrows are types that describe a computation declaratively and Macros are functions that describe a computation procedurally, is it possible that, for any application of Macros, you can find a suitable Monad/Arrow? Or am I not understanding either well enough? /goingovermyhead -Alex- ___ S. Alexander Jacobson Shop.Com 1-646-638-2300 voiceThe Easiest Way To Shop (sm) ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
RE: Happy and Macros (was Re: ANNOUNCE: Happy 1.10 released)
S. Alexander Jacobson writes: I am not a parsing expert, but given the recent discussion on macros, I have to ask: why use happy rather than monadic parsing? Monadic parsing allows you to avoid a whole additional language/compilation step and work in Hugs (where you don't have a makefile). What does Happy buy you here? It buys you (a) speed, (b) confidence that your grammar is non-ambiguous, and (c) familiar BNF notation. On the down side, as you point out, you lose Haskell's abstraction facilities. I'd be willing to sacrifice (c) in order to write parsers in Haskell, but I don't think there's a combinator library that matches Happy in terms of speed (disclaimer: I haven't exhaustively tested them all, but given the tricks Happy does I'd be surprised). AFAIK none of the combinator libraries gives you (b). Cheers, Simon ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Happy and Macros (was Re: ANNOUNCE: Happy 1.10 released)
Just out of curiosity, has anyone done any work at benchmarking the various parsers? I use Parsec pretty exclusivly since it comes with ghc and is pretty straightforward and lightweight to use. I am wondering what I am giving up in terms of speed by going that route, rather than Happy or the compiler toolkit non-monadic but pure-haskell parser? hmm... John On Thu, May 10, 2001 at 03:42:00PM +0100, Simon Marlow wrote: S. Alexander Jacobson writes: I am not a parsing expert, but given the recent discussion on macros, I have to ask: why use happy rather than monadic parsing? Monadic parsing allows you to avoid a whole additional language/compilation step and work in Hugs (where you don't have a makefile). What does Happy buy you here? It buys you (a) speed, (b) confidence that your grammar is non-ambiguous, and (c) familiar BNF notation. On the down side, as you point out, you lose Haskell's abstraction facilities. I'd be willing to sacrifice (c) in order to write parsers in Haskell, but I don't think there's a combinator library that matches Happy in terms of speed (disclaimer: I haven't exhaustively tested them all, but given the tricks Happy does I'd be surprised). AFAIK none of the combinator libraries gives you (b). -- -- John Meacham http://www.ugcs.caltech.edu/~john/ California Institute of Technology, Alum. [EMAIL PROTECTED] -- ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Happy and Macros (was Re: ANNOUNCE: Happy 1.10 released)
Combining two threads... Like macros and preprocessors, Happy generates code. I assume the justification for this is that hand-coding a parser in Haskell is presumed to be too difficult or that it is too hard to get the right level of abstraction (and therefore a macro-like facility is required). However, I've also used Hutton Meijer style monadic parsers and found them extremely elegant, clean, and easy to use in both Haskell and Python (though in Python they were too slow for my xml application -- function call overhead is _very_ high in Python). I am not a parsing expert, but given the recent discussion on macros, I have to ask: why use happy rather than monadic parsing? Monadic parsing allows you to avoid a whole additional language/compilation step and work in Hugs (where you don't have a makefile). What does Happy buy you here? goingovermyhead And generalizing from the above, since Monads/Arrows are types that describe a computation declaratively and Macros are functions that describe a computation procedurally, is it possible that, for any application of Macros, you can find a suitable Monad/Arrow? Or am I not understanding either well enough? /goingovermyhead -Alex- ___ S. Alexander Jacobson Shop.Com 1-646-638-2300 voiceThe Easiest Way To Shop (sm) ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Happy and Macros (was Re: ANNOUNCE: Happy 1.10 released)
S. Alexander Jacobson [EMAIL PROTECTED] writes: I am not a parsing expert, but given the recent discussion on macros, I have to ask: why use happy rather than monadic parsing? Monadic parsing allows you to avoid a whole additional language/compilation step and work in Hugs (where you don't have a makefile). What does Happy buy you here? I've used Happy instead of parser combinators because I wanted the additional global error-checking. I believe that the standard implementations of parser combinators will allow you to specify an ambiguous grammar, and return one of the multiple possible parses, without warning. Carl Witty ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
RE: Happy and Macros (was Re: ANNOUNCE: Happy 1.10 released)
S. Alexander Jacobson writes: I am not a parsing expert, but given the recent discussion on macros, I have to ask: why use happy rather than monadic parsing? Monadic parsing allows you to avoid a whole additional language/compilation step and work in Hugs (where you don't have a makefile). What does Happy buy you here? It buys you (a) speed, (b) confidence that your grammar is non-ambiguous, and (c) familiar BNF notation. On the down side, as you point out, you lose Haskell's abstraction facilities. I'd be willing to sacrifice (c) in order to write parsers in Haskell, but I don't think there's a combinator library that matches Happy in terms of speed (disclaimer: I haven't exhaustively tested them all, but given the tricks Happy does I'd be surprised). AFAIK none of the combinator libraries gives you (b). Cheers, Simon ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Happy and Macros (was Re: ANNOUNCE: Happy 1.10 released)
Just out of curiosity, has anyone done any work at benchmarking the various parsers? I use Parsec pretty exclusivly since it comes with ghc and is pretty straightforward and lightweight to use. I am wondering what I am giving up in terms of speed by going that route, rather than Happy or the compiler toolkit non-monadic but pure-haskell parser? hmm... John On Thu, May 10, 2001 at 03:42:00PM +0100, Simon Marlow wrote: S. Alexander Jacobson writes: I am not a parsing expert, but given the recent discussion on macros, I have to ask: why use happy rather than monadic parsing? Monadic parsing allows you to avoid a whole additional language/compilation step and work in Hugs (where you don't have a makefile). What does Happy buy you here? It buys you (a) speed, (b) confidence that your grammar is non-ambiguous, and (c) familiar BNF notation. On the down side, as you point out, you lose Haskell's abstraction facilities. I'd be willing to sacrifice (c) in order to write parsers in Haskell, but I don't think there's a combinator library that matches Happy in terms of speed (disclaimer: I haven't exhaustively tested them all, but given the tricks Happy does I'd be surprised). AFAIK none of the combinator libraries gives you (b). -- -- John Meacham http://www.ugcs.caltech.edu/~john/ California Institute of Technology, Alum. [EMAIL PROTECTED] -- ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: ANNOUNCE: Happy 1.10 released
Simon Marlow [EMAIL PROTECTED] wrote, ANNOUNCING Happy 1.10 - The LALR(1) Parser Generator for Haskell - It seems that the build system does not create a link from `happy-version' to `happy'. Is this intentional? Cheers, Manuel ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
ANNOUNCE: Happy 1.10 released
ANNOUNCING Happy 1.10 - The LALR(1) Parser Generator for Haskell - I'm pleased to announce version 1.10 of Happy, the parser generator system for Haskell. Changes in this version, relative to version 1.10 (the previous full release): * bugfixes, and minor performance improvements, * most of the examples work again. Happy is available in source form, which can be compiled with GHC version 4.xx (4.08 or 5.00 recommended), and we also provide binaries for some architectures. The Happy homepage with links to the various distributions lives at: http://www.haskell.org/happy/ Please send any bug reports and comments to [EMAIL PROTECTED] ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
ANNOUNCE: Happy 1.10 released
ANNOUNCING Happy 1.10 - The LALR(1) Parser Generator for Haskell - I'm pleased to announce version 1.10 of Happy, the parser generator system for Haskell. Changes in this version, relative to version 1.10 (the previous full release): * bugfixes, and minor performance improvements, * most of the examples work again. Happy is available in source form, which can be compiled with GHC version 4.xx (4.08 or 5.00 recommended), and we also provide binaries for some architectures. The Happy homepage with links to the various distributions lives at: http://www.haskell.org/happy/ Please send any bug reports and comments to [EMAIL PROTECTED] ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
