Happy and Macros (was Re: ANNOUNCE: Happy 1.10 released)
Manuel M. T. Chakravarty
Sun, 13 May 2001 16:51:38 +1000
firstname.lastname@example.org (Carl R. Witty) wrote,
> "Manuel M. T. Chakravarty" <email@example.com> 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
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.
PS: AFAIK Doitse recently made his combinators a bit more
general, and I am not entirely sure how that affects
the ambiguity check.