[Haskell-cafe] Re: Frisby grammars that have context

[apfelmus]

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.
> [...]
> Is this supposed to not be possible in Frisby, or (quite likely) am I
> missing something that allows me to?

It's intentionally impossible. Frisby uses a dynamic programming
approach that crucially depends on the fact that the grammar in question
is context-free (actually something related, but the effect is the
same). You're trying to parse a context-sensitive language.

Sometimes, you can avoid context-sensitivity if there's a way to parse
the token in question regardless of whether it's valid. For example,
Pascal is a context-sensitive language because you may not use a
variable before it has been declared:

  procedure Foo(x:Integer)
  begin
    y := 1;
  end;

This not a correct Pascal program, nevertheless the parse succeeds just
fine. The missing declaration for y will be detected when processing the
abstract syntax tree further. The key point is that the shape of the
abstract syntax tree doesn't depend on whether y is declared or not.

Regards,
apfelmus