[Haskell-cafe] Frisby grammars that have context

[Carl Witty]

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