Re: detecting ambiguous grammars

Gene Wirchenko wrote:


> christian.bau@isltd.insignia.com (Christian Bau) wrote:
>
> > [...] What you cannot do is write a parser generator that will
> >succeed for all unambigous grammars and that will stop and admit
> >failure for all ambiguous grammars.
>
> Excuse my ignorance, but why not? Can you give a simple example?


I think I can answer this now. :-)


First off, we need to be clear about the difference between detecting
whether a given statement is ambiguous with respect to a given grammer
(which is easy), and detecting whether or not there exists statements
that are ambiguous with respect to a given grammar (which is hard in
the general case).


The answer is that you *can* write a program that will detect whether
a grammar allows ambiguous statements. The problem is that there is no
way to determine how long it is going to take to detect that
ambiguity. So if you run your grammar ambiguity detection program, and
you wait around for ten days without detecting an ambiguity, you may
have a non-ambiguous grammar, or you may have not waited long enough.


Earlier in this thread, David Lester offered an example of a grammar
(or rather, a way of generating a grammar) that demonstrates that the
amount of time and memory used by the grammar ambiguity detector can
get big much faster than the grammar you're testing. (Chris F Clark
also helped me with this point in e-mail.)


The good news is that there are classes of grammars which can be
proved unambiguous in a bounded amount of time. If yacc doesn't report
an ambiguity for a given grammar, then the act of generating a parser
has proved that that grammar is unambiguous. The price yacc pays for
this is the inability to handle some grammars even though they aren't
ambiguous.


-thant

Return to the comp.compilers page.
Search the comp.compilers archives again.