Re: detecting ambiguous grammars

Thant Tessman <thant@acm.org>
31 Mar 2001 02:37:09 -0500

          From comp.compilers

Related articles
[9 earlier articles]
Re: detecting ambiguous grammars christian.bau@isltd.insignia.com (2001-03-22)
Re: detecting ambiguous grammars thant@acm.org (Thant Tessman) (2001-03-26)
Re: detecting ambiguous grammars joachim_d@gmx.de (Joachim Durchholz) (2001-03-26)
Re: detecting ambiguous grammars cfc@world.std.com (Chris F Clark) (2001-03-27)
Re: detecting ambiguous grammars genew@shuswap.net (2001-03-27)
Re: detecting ambiguous grammars genew@shuswap.net (2001-03-27)
Re: detecting ambiguous grammars thant@acm.org (Thant Tessman) (2001-03-31)
Re: detecting ambiguous grammars cfc@world.std.com (Chris F Clark) (2001-03-31)
Re: detecting ambiguous grammars kenarose@earthlink.net (Ken Rose) (2001-03-31)
Re: detecting ambiguous grammars vbdis@aol.com (2001-03-31)
Re: detecting ambiguous grammars joachim_d@gmx.de (Joachim Durchholz) (2001-04-04)
Re: detecting ambiguous grammars world!bobduff@uunet.uu.net (Robert A Duff) (2001-04-10)
Re: detecting ambiguous grammars ki3084lx@ecs.cmc.osaka-u.ac.jp (Le Harusada) (2005-12-15)
| List of all articles for this month |

From: Thant Tessman <thant@acm.org>
Newsgroups: comp.compilers
Date: 31 Mar 2001 02:37:09 -0500
Organization: XMission http://www.xmission.com/
References: 01-02-080 01-03-020 01-03-032 01-03-078 01-03-084 01-03-102 01-03-148
Keywords: parse
Posted-Date: 31 Mar 2001 02:37:09 EST

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


Post a followup to this message

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