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