Re: detecting ambiguous grammars

Chris F Clark <cfc@world.std.com>
31 Mar 2001 02:44:15 -0500

          From comp.compilers

Related articles
[10 earlier articles]
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: Chris F Clark <cfc@world.std.com>
Newsgroups: comp.compilers
Date: 31 Mar 2001 02:44:15 -0500
Organization: The World Public Access UNIX, Brookline, MA
References: 01-02-080 01-03-020 01-03-032 01-03-078 01-03-084 01-03-102 01-03-148
Keywords: parse, theory
Posted-Date: 31 Mar 2001 02:44:15 EST

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.


To which Gene Wirchenko replied with the following question
> Excuse my ignorance, but why not? Can you give a simple example?


The reason you cannot is very abstract, and there is no simple
example.


Essentially, there is a way of mapping the Post Correspondence problem
onto the ambiguity of a grammar. In that case the grammar will be
ambiguous if-and-only-if the related Post Correspondence problem has a
solution (and you can read the solution directly out of the way the
ambiguous input is parsed by two or more distinct derivations). Next,
you can map the Turing Halting Problem onto the Post Correspondence
problem. The Turing Machine halts if-and-only-if the Post Machine can
find the correspondence between the two inputs.


Therefore, if you could write an algorithm that could determine if any
arbitrary grammar is ambiguous or not, then you could use that
algorithm to determine whether an arbitrary Turing Machine halts.
Since, we know that problem is undecidable (you can't write an
algorithm that figures out whether a TM halts or not), the ambiguity
of grammars is also undecidable (you can't write a program to
determine if grammars are ambiguous or not).


So, if you want a grammar that is indeterminant as to whether it is
ambiguous or not, you need to have a Turing Machine program that you
cannot (currently) prove whether it halts or not. (Anyone know, Is
McCarthy's 91 program an example of this case?) Then, you translate
the Turing Machine into the equivalent Post Correspondence problem and
translate that into the equivalent Grammar. Then, you have a grammar
which may or may not be ambiguous and no one knows (yet).


The curious opposite fact is that any given grammar is either
ambiguous or not (even if we don't know which applies). There are no
grammars that are both ambiguous and non-ambiguous at the same time.
Thus, for any single given grammar, the ambiguity problem has a
solution. We may not know how to arrive at the solution, but there is
such a solution.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)


Post a followup to this message

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