[Haskell-cafe] Re: Fwd: Parsing in Practice

[Sylvain Schmitz]

Tomasz Zielonka <tomasz.zielonka <at> gmail.com> writes:

> The problem is that the set of LALR grammars is not closed under composition
> (as I've read in some paper on GLR parsing).

If I'm right, the set of unambiguous grammars is not closed under concatenation
nor union.  This makes things rather difficult.  If you are looking for closed
sets under most language operations, but deterministic parsing, you can give a
look at packrat parsers, but then you may have some issues when trying to find
out which language you are really defining.

> On 10/18/05, Tom Hawkins <tom <at> confluent.org> wrote:
> > Even though I hate debugging LALR(1) parsing ambiguities,
> > it prevents problems.
> 
> Yes, when you fight the conflicts, you get static guarantees in return.
> I wonder how it is with GLR?

You will not get any static guarantees with GLR.  Until you feed the generated
parser with an input that reveals an ambiguity, you will not know for sure
whether such a case might occur or not.  Except of course if your grammar is in
one of the nice subsets of all CFGs for which you do have static guarantees,
like LALR(1).  But in that case, there is no point in using a GLR parser.
  Thus, when using a GLR parser, try to have foolproof code ready to catch an
unexpected ambiguity.

-- 
Regards,

  Sylvain