On Tue, 2007-05-29 at 10:18 -0400, Mark T.B. Carroll wrote: > I've been playing with Text.Parsers.Frisby to see how it stacks against > other options and, while it's been great so far, I am finding that I > can't encode a grammar where what's acceptable depends on what's already > been parsed in some nontrivial way. To take a simple example, imagine a > grammar where the only lower-case letters that are acceptable are those > where their upper-case equivalent occurred earlier in the text. ... > Is this supposed to not be possible in Frisby, or (quite likely) am I > missing something that allows me to? I've thought about things like > trying to fmap further calls to apply runPeg to rest, but I've not > figured out a trick that will actually work.
I've never used Frisby, but I have read about Parsing Expression Grammars, and I'm pretty sure that this is supposed to not be possible. Basically, PEG parsers manage to be linar-time by caching the result of attempting to parse a particular nonterminal at a particular input position. If your nonterminal depends on previous input to decide what to accept, then such caching would no longer be valid. Carl Witty _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
