[Haskell-cafe] Parsec to parse tree structures?

[Jason Dagit]

On Sun, Mar 14, 2010 at 9:03 AM, david fries <djf at gmx.ch> wrote:

> Hello Café
>
> Some time ago I wrote a parser for a project of one our customers. The
> format was proprietary and binary. The data was structured as a tree
> with tables pointing to sub tables farther in the file. (Well actually
> there was one or two cases where branches joined together, so I guess it
> was a directed graph.) Also it had no defined endianess, some tables
> were bigendian others were little endian and some were in their very own
> in-house-endianess.
> All in all, the typical binary data structure that has been in use and
> continuously extended for the last 15 years. You know the kind.
>
> Oddly enough, our customer never bothered to write a parser of their
> own. I wonder why.
>
> My parser was written in C# and wasn't particularly elegant, but it
> worked reliably. I was wondering how you would parse tree-like
> structures with Parsec (or other functional parsers)? Up to know, all
> examples I've seen were of sequential data. To parse trees, you'd
> essentially need to be able to follow pointers, parse whatever is there
> and then jump back. I guess I'd have to mess around with the internal
> state of the parser to do that, which is something I'd rather avoid.
>

Would binary or cereal be right for this task?
http://hackage.haskell.org/packages/archive/binary/0.4.1/doc/html/Data-Binary.html
http://hackage.haskell.org/packages/archive/cereal/0.2/doc/html/Data-Serialize.html

My understanding is they provide low-level ways to get at bytes in a chunk
of memory.  Using them, I believe you'd read the data into a bytestring and
then load in the bytes and seek/jump as needed.  I don't know if they
support the backwards jumping though.

And, I think ideally you use it by defining a type class instance for each
object in the binary format and then use the provided type classes to just
get/put your format.

If the representation is very much like a C struct, you might consider
Storable.  Although, I've never heard of anyone using it as a parser.

Jason
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100318/7c2e1a5b/attachment.html