[m-dev.] Request for suggestions: packrat parsing candidate

[Ralph Becket]

I've been thinking, on and off, about writing a little packrat parsing
paper.  Packrat parsing [1] is essentially recursive descent, but with
linear parsing ensured by memoing.  The results for parsing Java using
a packrat parser written in Haskell were good, but the parser consumed
300 bytes of heap for every byte of input!

It occurred to me that a packrat parser could be written trivially in
Mercury in two steps:
(1) write a plain recursive descent parser;
(2) add `pragma memo' declarations.
There's no need for extra machinery.

The obvious thing to do, given I want to compare Mercury's general
purpose memoing against the Haskell-specific packrat parser, would be to
write a parser for Java, but I thought I ought first to see whether
anyone has a suggestion for a language that would be genuinely useful to
have a parser for instead.

-- Ralph

[1] "Packrat parsing: simple, powerful, lazy, linear time", Functional
Pearl, Bryan Ford, ICFP02.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------