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

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

"Manuel M. T. Chakravarty" 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.