Brandon Michael Moore wrote:
> I'm wondering if there are any libraries out there for creating parsers > that lazily build up their result. I know I could thread the remaining > input through a parser by hand, but it seems like someone should have > already done it. This turns out to be rather difficult to do in the general case (but see below -- XML is a special case). If you have type Parser sym result = [sym] -> Maybe (result, [sym]) a Parser can't decide whether to return 'Just (result,rest)' or 'Nothing' until it has successfully parsed the complete result. So pattern matching on the parser's return value will force the entire production. Variations on the theme -- Either instead of Maybe, list-of-successes, continuation-passing combinators, etc -- all face a similar problem. However, if your top-level grammar is of the form: things :: empty | thing things {- == thing* -} then instead of: case runParser (pMany pThing) input of Just (result,[]) -> ... you can use something like unfoldr (runParser pThing) input to build the result list incrementally. This will be less eager; instead of parsing and returning an entire list of Things, it parses one Thing at a time. Another thing to watch out for is heap drag. The list-of-successes approach tends to retain the entire input, just in case the parser needs to backtrack. Parsec [1] and UU_Parsing [?] solve this by severely restricting the amount of required lookahead. > I'd like to be able to turn a stream of XML into a lazy tree of tags > (probably Maybe tags, or Either errors tags), but I don't think HaXml and > the like do that sort of thing. That's exactly how HXML [2] works. The parser returns a lazy list of tokens (analogous to SAX events), which are folded up into a tree by a separate function. In addition it uses a CPS parser library so (as with Parsec), there is minimal heap drag. [1] Parsec: <URL: http://www.cs.ruu.nl/~daan/parsec.html > [1] HXML: <URL: http://www.flightlab.com/~joe/hxml > (Note: HXML release 0.2 will be ready Real Soon Now, and there have been many incompatible changes since 0.1. The main thing left to be finished is the documentation, if you can live without that let me know and I'll put a snapshot up.) --Joe English [EMAIL PROTECTED] _______________________________________________ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe