Thanks guys for the links to parsers. I wasn't so much looking for a parser as I was exploring the mappings of algorithms. One of my passions is to explore how different computer programming languages interrelate. In particular, I am fascinated with the concept of transforming a program in one language into another language. A parser language is, almost by definition, the specification of a transform (from a linear structure to a heirarchal one), so I am very interested in different ways to build parsers, as then I'm transforming a transform.... Matthew Walton wrote:
Isn't Happy [1] a bottom-up parser generator in the style of yacc?
[1] http://www.haskell.org/happy/
As for parsing yacc's input files, if you can come up with an EBNF grammar for it that avoids some of the nasty recursion possibilities [2] then I can't see why you couldn't parse it with Parsec or some other parsing library. Or even with a parser written using Happy.
Parsec's not that bad really, but the HuttonMeijerWallace one is easier if you start off with those and move to Parsec if you need a more powerful solution. But I may be biased as I'm a former student of Graham Hutton's.
With all the choices available though there's not much point writing your own unless you've got very unusual requirements, something new to bring to the table, or you like the challenge.
So I would definitely recommend HuttonMeijerWallace or Parsec if you're wanting to parse something. It's possible Happy-generated parsers run faster, but I don't really know and I was quite content with Parsec's speed when I used it in my final-year project. Not that it was parsing anything particularly huge at the time.
Matthew
[1] http://www.haskell.org/happy/ [2] the proper terms for which I can't remember, but I seem to recall that left recusion is one of the nasty ones
Graham Klyne wrote:
I'm not familiar with yacc, but I understand that it's a bottom-up parser generator. I've not come across any bottom-up parser generators written in Haskell.
I have seen (at least) three examples of top-down parser generators coded in Haskell: (1) in Simon Thompson's book, the Craft of Functional Programming. I have done an implementation based on these ideas [3], which I have since discarded in favour of Parsec... (2) the Parsec parser library [1], which is a very full-functioned and easy-to-use library, but which might be not-so-easy for a Haskell newcomer to figure out its internal workings because it is heavily based on Monads. (3) the HuttonMeijerWallace parser combinator library [2], which is also based on a Monad but, being less complex, is easier to follow its internals.
[1] http://www.cs.uu.nl/~daan/parsec.html (also in the Haskell hierarchical libraries, under 'text'.
[2] API Documentation: http://www.cs.york.ac.uk/fp/HaXml/HaXml/Text.ParserCombinators.HuttonMeijerW...
Source in CVS: http://cvs.haskell.org/cgi-bin/cvsweb.cgi/HaXml/src/Text/ParserCombinators/H...
Being part of HaXml: http://www.cs.york.ac.uk/fp/HaXml/
[3] http://www.ninebynine.org/Software/HaskellUtils/Withdrawn/Parse.hs (And related code in same directory. This was just about the first real program I write in Haskell, so don't look to this for an example of how one *should* program using Haskell!)
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe