Re: detecting ambiguous grammars

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)

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