31 Mar 2001 02:44:15 -0500

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) |

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.