Happy and Macros (was Re: ANNOUNCE: Happy 1.10 released)

[Manuel M. T. Chakravarty]

cwitty@newtonlabs.com (Carl R. Witty) wrote,

> "Manuel M. T. Chakravarty" <chak@cse.unsw.edu.au> writes:
> 
> > I don't think, the point is the test for non-ambiguity.  At
> > least, Doitse's and my self-optimising parser combinator
> > library will detect that a grammar is ambigious when you
> > parse a sentence involving the ambiguous productions.  So,
> > you can check that by parsing a file involving all grammar
> > constructs of the language.
> 
> Sorry, doesn't work.  Where do you get this "file involving all
> grammar constructs of the language"?
> 
> If such an approach worked, you could use it to determine whether an
> arbitrary context-free grammar was ambiguous; but this problem is
> undecidable.

I didn't say that this works for any kind of parser
combinator, I merely said that it works Doitse's and mine.
Both implement SLL(1) parsers for which - as I am sure, you
know - there exists a decision procedure for testing
ambiguity.  More precisely, whenever the library can build
the parse table, the grammar must be non-ambigious.  As the
parse table construction is lazy, this covers only the
productions exercised in that particular run, which is why I
said that you need a "file involving all grammar constructs
of the language."  Nothing magic here.

Cheers,
Manuel

PS: AFAIK Doitse recently made his combinators a bit more
    general, and I am not entirely sure how that affects
    the ambiguity check.